crypto/bn/bn_ctx.c

   1 /* crypto/bn/bn_ctx.c */
   2 /* Written by Ulf Moeller for the OpenSSL project. */
   3 /* ====================================================================
   4  * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * 3. All advertising materials mentioning features or use of this
  19  *    software must display the following acknowledgment:
  20  *    "This product includes software developed by the OpenSSL Project
  21  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  22  *
  23  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  24  *    endorse or promote products derived from this software without
  25  *    prior written permission. For written permission, please contact
  26  *    openssl-core@openssl.org.
  27  *
  28  * 5. Products derived from this software may not be called "OpenSSL"
  29  *    nor may "OpenSSL" appear in their names without prior written
  30  *    permission of the OpenSSL Project.
  31  *
  32  * 6. Redistributions of any form whatsoever must retain the following
  33  *    acknowledgment:
  34  *    "This product includes software developed by the OpenSSL Project
  35  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  36  *
  37  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  38  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  40  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  43  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  44  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  45  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  46  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  47  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  48  * OF THE POSSIBILITY OF SUCH DAMAGE.
  49  * ====================================================================
  50  *
  51  * This product includes cryptographic software written by Eric Young
  52  * (eay@cryptsoft.com).  This product includes software written by Tim
  53  * Hudson (tjh@cryptsoft.com).
  54  *
  55  */
  56
  57 #if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG)
  58 #ifndef NDEBUG
  59 #define NDEBUG
  60 #endif
  61 #endif
  62
  63 #define OPENSSL_FIPSAPI
  64
  65 #include <stdio.h>
  66 #include <assert.h>
  67
  68 #include "cryptlib.h"
  69 #include "bn_lcl.h"
  70
  71 /* TODO list
  72  *
  73  * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
  74  * check they can be safely removed.
  75  *  - Check +1 and other ugliness in BN_from_montgomery()
  76  *
  77  * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
  78  * appropriate 'block' size that will be honoured by bn_expand_internal() to
  79  * prevent piddly little reallocations. OTOH, profiling bignum expansions in
  80  * BN_CTX doesn't show this to be a big issue.
  81  */
  82
  83 /* How many bignums are in each "pool item"; */
  84 #define BN_CTX_POOL_SIZE        16
  85 /* The stack frame info is resizing, set a first-time expansion size; */
  86 #define BN_CTX_START_FRAMES     32
  87
  88 /***********/
  89 /* BN_POOL */
  90 /***********/
  91
  92 /* A bundle of bignums that can be linked with other bundles */
  93 typedef struct bignum_pool_item
  94         {
  95         /* The bignum values */
  96         BIGNUM vals[BN_CTX_POOL_SIZE];
  97         /* Linked-list admin */
  98         struct bignum_pool_item *prev, *next;
  99         } BN_POOL_ITEM;
 100 /* A linked-list of bignums grouped in bundles */
 101 typedef struct bignum_pool
 102         {
 103         /* Linked-list admin */
 104         BN_POOL_ITEM *head, *current, *tail;
 105         /* Stack depth and allocation size */
 106         unsigned used, size;
 107         } BN_POOL;
 108 static void             BN_POOL_init(BN_POOL *);
 109 static void             BN_POOL_finish(BN_POOL *);
 110 #ifndef OPENSSL_NO_DEPRECATED
 111 static void             BN_POOL_reset(BN_POOL *);
 112 #endif
 113 static BIGNUM *         BN_POOL_get(BN_POOL *);
 114 static void             BN_POOL_release(BN_POOL *, unsigned int);
 115
 116 /************/
 117 /* BN_STACK */
 118 /************/
 119
 120 /* A wrapper to manage the "stack frames" */
 121 typedef struct bignum_ctx_stack
 122         {
 123         /* Array of indexes into the bignum stack */
 124         unsigned int *indexes;
 125         /* Number of stack frames, and the size of the allocated array */
 126         unsigned int depth, size;
 127         } BN_STACK;
 128 static void             BN_STACK_init(BN_STACK *);
 129 static void             BN_STACK_finish(BN_STACK *);
 130 #ifndef OPENSSL_NO_DEPRECATED
 131 static void             BN_STACK_reset(BN_STACK *);
 132 #endif
 133 static int              BN_STACK_push(BN_STACK *, unsigned int);
 134 static unsigned int     BN_STACK_pop(BN_STACK *);
 135
 136 /**********/
 137 /* BN_CTX */
 138 /**********/
 139
 140 /* The opaque BN_CTX type */
 141 struct bignum_ctx
 142         {
 143         /* The bignum bundles */
 144         BN_POOL pool;
 145         /* The "stack frames", if you will */
 146         BN_STACK stack;
 147         /* The number of bignums currently assigned */
 148         unsigned int used;
 149         /* Depth of stack overflow */
 150         int err_stack;
 151         /* Block "gets" until an "end" (compatibility behaviour) */
 152         int too_many;
 153         };
 154
 155 /* Enable this to find BN_CTX bugs */
 156 #ifdef BN_CTX_DEBUG
 157 static const char *ctxdbg_cur = NULL;
 158 static void ctxdbg(BN_CTX *ctx)
 159         {
 160         unsigned int bnidx = 0, fpidx = 0;
 161         BN_POOL_ITEM *item = ctx->pool.head;
 162         BN_STACK *stack = &ctx->stack;
 163         fprintf(stderr,"(%08x): ", (unsigned int)ctx);
 164         while(bnidx < ctx->used)
 165                 {
 166                 fprintf(stderr,"%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
 167                 if(!(bnidx % BN_CTX_POOL_SIZE))
 168                         item = item->next;
 169                 }
 170         fprintf(stderr,"\n");
 171         bnidx = 0;
 172         fprintf(stderr,"          : ");
 173         while(fpidx < stack->depth)
 174                 {
 175                 while(bnidx++ < stack->indexes[fpidx])
 176                         fprintf(stderr,"    ");
 177                 fprintf(stderr,"^^^ ");
 178                 bnidx++;
 179                 fpidx++;
 180                 }
 181         fprintf(stderr,"\n");
 182         }
 183 #define CTXDBG_ENTRY(str, ctx)  do { \
 184                                 ctxdbg_cur = (str); \
 185                                 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
 186                                 ctxdbg(ctx); \
 187                                 } while(0)
 188 #define CTXDBG_EXIT(ctx)        do { \
 189                                 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
 190                                 ctxdbg(ctx); \
 191                                 } while(0)
 192 #define CTXDBG_RET(ctx,ret)
 193 #else
 194 #define CTXDBG_ENTRY(str, ctx)
 195 #define CTXDBG_EXIT(ctx)
 196 #define CTXDBG_RET(ctx,ret)
 197 #endif
 198
 199 /* This function is an evil legacy and should not be used. This implementation
 200  * is WYSIWYG, though I've done my best. */
 201 #ifndef OPENSSL_NO_DEPRECATED
 202 void BN_CTX_init(BN_CTX *ctx)
 203         {
 204         /* Assume the caller obtained the context via BN_CTX_new() and so is
 205          * trying to reset it for use. Nothing else makes sense, least of all
 206          * binary compatibility from a time when they could declare a static
 207          * variable. */
 208         BN_POOL_reset(&ctx->pool);
 209         BN_STACK_reset(&ctx->stack);
 210         ctx->used = 0;
 211         ctx->err_stack = 0;
 212         ctx->too_many = 0;
 213         }
 214 #endif
 215
 216 BN_CTX *BN_CTX_new(void)
 217         {
 218         BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
 219         if(!ret)
 220                 {
 221                 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
 222                 return NULL;
 223                 }
 224         /* Initialise the structure */
 225         BN_POOL_init(&ret->pool);
 226         BN_STACK_init(&ret->stack);
 227         ret->used = 0;
 228         ret->err_stack = 0;
 229         ret->too_many = 0;
 230         return ret;
 231         }
 232
 233 void BN_CTX_free(BN_CTX *ctx)
 234         {
 235         if (ctx == NULL)
 236                 return;
 237 #ifdef BN_CTX_DEBUG
 238         {
 239         BN_POOL_ITEM *pool = ctx->pool.head;
 240         fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
 241                 ctx->stack.size, ctx->pool.size);
 242         fprintf(stderr,"dmaxs: ");
 243         while(pool) {
 244                 unsigned loop = 0;
 245                 while(loop < BN_CTX_POOL_SIZE)
 246                         fprintf(stderr,"%02x ", pool->vals[loop++].dmax);
 247                 pool = pool->next;
 248         }
 249         fprintf(stderr,"\n");
 250         }
 251 #endif
 252         BN_STACK_finish(&ctx->stack);
 253         BN_POOL_finish(&ctx->pool);
 254         OPENSSL_free(ctx);
 255         }
 256
 257 void BN_CTX_start(BN_CTX *ctx)
 258         {
 259         CTXDBG_ENTRY("BN_CTX_start", ctx);
 260         /* If we're already overflowing ... */
 261         if(ctx->err_stack || ctx->too_many)
 262                 ctx->err_stack++;
 263         /* (Try to) get a new frame pointer */
 264         else if(!BN_STACK_push(&ctx->stack, ctx->used))
 265                 {
 266                 BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
 267                 ctx->err_stack++;
 268                 }
 269         CTXDBG_EXIT(ctx);
 270         }
 271
 272 void BN_CTX_end(BN_CTX *ctx)
 273         {
 274         CTXDBG_ENTRY("BN_CTX_end", ctx);
 275         if(ctx->err_stack)
 276                 ctx->err_stack--;
 277         else
 278                 {
 279                 unsigned int fp = BN_STACK_pop(&ctx->stack);
 280                 /* Does this stack frame have anything to release? */
 281                 if(fp < ctx->used)
 282                         BN_POOL_release(&ctx->pool, ctx->used - fp);
 283                 ctx->used = fp;
 284                 /* Unjam "too_many" in case "get" had failed */
 285                 ctx->too_many = 0;
 286                 }
 287         CTXDBG_EXIT(ctx);
 288         }
 289
 290 BIGNUM *BN_CTX_get(BN_CTX *ctx)
 291         {
 292         BIGNUM *ret;
 293         CTXDBG_ENTRY("BN_CTX_get", ctx);
 294         if(ctx->err_stack || ctx->too_many) return NULL;
 295         if((ret = BN_POOL_get(&ctx->pool)) == NULL)
 296                 {
 297                 /* Setting too_many prevents repeated "get" attempts from
 298                  * cluttering the error stack. */
 299                 ctx->too_many = 1;
 300                 BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
 301                 return NULL;
 302                 }
 303         /* OK, make sure the returned bignum is "zero" */
 304         BN_zero(ret);
 305         ctx->used++;
 306         CTXDBG_RET(ctx, ret);
 307         return ret;
 308         }
 309
 310 /************/
 311 /* BN_STACK */
 312 /************/
 313
 314 static void BN_STACK_init(BN_STACK *st)
 315         {
 316         st->indexes = NULL;
 317         st->depth = st->size = 0;
 318         }
 319
 320 static void BN_STACK_finish(BN_STACK *st)
 321         {
 322         if(st->size) OPENSSL_free(st->indexes);
 323         }
 324
 325 #ifndef OPENSSL_NO_DEPRECATED
 326 static void BN_STACK_reset(BN_STACK *st)
 327         {
 328         st->depth = 0;
 329         }
 330 #endif
 331
 332 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
 333         {
 334         if(st->depth == st->size)
 335                 /* Need to expand */
 336                 {
 337                 unsigned int newsize = (st->size ?
 338                                 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
 339                 unsigned int *newitems = OPENSSL_malloc(newsize *
 340                                                 sizeof(unsigned int));
 341                 if(!newitems) return 0;
 342                 if(st->depth)
 343                         memcpy(newitems, st->indexes, st->depth *
 344                                                 sizeof(unsigned int));
 345                 if(st->size) OPENSSL_free(st->indexes);
 346                 st->indexes = newitems;
 347                 st->size = newsize;
 348                 }
 349         st->indexes[(st->depth)++] = idx;
 350         return 1;
 351         }
 352
 353 static unsigned int BN_STACK_pop(BN_STACK *st)
 354         {
 355         return st->indexes[--(st->depth)];
 356         }
 357
 358 /***********/
 359 /* BN_POOL */
 360 /***********/
 361
 362 static void BN_POOL_init(BN_POOL *p)
 363         {
 364         p->head = p->current = p->tail = NULL;
 365         p->used = p->size = 0;
 366         }
 367
 368 static void BN_POOL_finish(BN_POOL *p)
 369         {
 370         while(p->head)
 371                 {
 372                 unsigned int loop = 0;
 373                 BIGNUM *bn = p->head->vals;
 374                 while(loop++ < BN_CTX_POOL_SIZE)
 375                         {
 376                         if(bn->d) BN_clear_free(bn);
 377                         bn++;
 378                         }
 379                 p->current = p->head->next;
 380                 OPENSSL_free(p->head);
 381                 p->head = p->current;
 382                 }
 383         }
 384
 385 #ifndef OPENSSL_NO_DEPRECATED
 386 static void BN_POOL_reset(BN_POOL *p)
 387         {
 388         BN_POOL_ITEM *item = p->head;
 389         while(item)
 390                 {
 391                 unsigned int loop = 0;
 392                 BIGNUM *bn = item->vals;
 393                 while(loop++ < BN_CTX_POOL_SIZE)
 394                         {
 395                         if(bn->d) BN_clear(bn);
 396                         bn++;
 397                         }
 398                 item = item->next;
 399                 }
 400         p->current = p->head;
 401         p->used = 0;
 402         }
 403 #endif
 404
 405 static BIGNUM *BN_POOL_get(BN_POOL *p)
 406         {
 407         if(p->used == p->size)
 408                 {
 409                 BIGNUM *bn;
 410                 unsigned int loop = 0;
 411                 BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
 412                 if(!item) return NULL;
 413                 /* Initialise the structure */
 414                 bn = item->vals;
 415                 while(loop++ < BN_CTX_POOL_SIZE)
 416                         BN_init(bn++);
 417                 item->prev = p->tail;
 418                 item->next = NULL;
 419                 /* Link it in */
 420                 if(!p->head)
 421                         p->head = p->current = p->tail = item;
 422                 else
 423                         {
 424                         p->tail->next = item;
 425                         p->tail = item;
 426                         p->current = item;
 427                         }
 428                 p->size += BN_CTX_POOL_SIZE;
 429                 p->used++;
 430                 /* Return the first bignum from the new pool */
 431                 return item->vals;
 432                 }
 433         if(!p->used)
 434                 p->current = p->head;
 435         else if((p->used % BN_CTX_POOL_SIZE) == 0)
 436                 p->current = p->current->next;
 437         return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
 438         }
 439
 440 static void BN_POOL_release(BN_POOL *p, unsigned int num)
 441         {
 442         unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
 443         p->used -= num;
 444         while(num--)
 445                 {
 446                 bn_check_top(p->current->vals + offset);
 447                 if(!offset)
 448                         {
 449                         offset = BN_CTX_POOL_SIZE - 1;
 450                         p->current = p->current->prev;
 451                         }
 452                 else
 453                         offset--;
 454                 }
 455         }
 456