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 #ifdef OPENSSL_FIPS
  72 #include <openssl/fips.h>
  73 #endif
  74
  75 /* TODO list
  76  *
  77  * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
  78  * check they can be safely removed.
  79  *  - Check +1 and other ugliness in BN_from_montgomery()
  80  *
  81  * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
  82  * appropriate 'block' size that will be honoured by bn_expand_internal() to
  83  * prevent piddly little reallocations. OTOH, profiling bignum expansions in
  84  * BN_CTX doesn't show this to be a big issue.
  85  */
  86
  87 /* How many bignums are in each "pool item"; */
  88 #define BN_CTX_POOL_SIZE        16
  89 /* The stack frame info is resizing, set a first-time expansion size; */
  90 #define BN_CTX_START_FRAMES     32
  91
  92 /***********/
  93 /* BN_POOL */
  94 /***********/
  95
  96 /* A bundle of bignums that can be linked with other bundles */
  97 typedef struct bignum_pool_item
  98         {
  99         /* The bignum values */
 100         BIGNUM vals[BN_CTX_POOL_SIZE];
 101         /* Linked-list admin */
 102         struct bignum_pool_item *prev, *next;
 103         } BN_POOL_ITEM;
 104 /* A linked-list of bignums grouped in bundles */
 105 typedef struct bignum_pool
 106         {
 107         /* Linked-list admin */
 108         BN_POOL_ITEM *head, *current, *tail;
 109         /* Stack depth and allocation size */
 110         unsigned used, size;
 111         } BN_POOL;
 112 static void             BN_POOL_init(BN_POOL *);
 113 static void             BN_POOL_finish(BN_POOL *);
 114 #ifndef OPENSSL_NO_DEPRECATED
 115 static void             BN_POOL_reset(BN_POOL *);
 116 #endif
 117 static BIGNUM *         BN_POOL_get(BN_POOL *);
 118 static void             BN_POOL_release(BN_POOL *, unsigned int);
 119
 120 /************/
 121 /* BN_STACK */
 122 /************/
 123
 124 /* A wrapper to manage the "stack frames" */
 125 typedef struct bignum_ctx_stack
 126         {
 127         /* Array of indexes into the bignum stack */
 128         unsigned int *indexes;
 129         /* Number of stack frames, and the size of the allocated array */
 130         unsigned int depth, size;
 131         } BN_STACK;
 132 static void             BN_STACK_init(BN_STACK *);
 133 static void             BN_STACK_finish(BN_STACK *);
 134 #ifndef OPENSSL_NO_DEPRECATED
 135 static void             BN_STACK_reset(BN_STACK *);
 136 #endif
 137 static int              BN_STACK_push(BN_STACK *, unsigned int);
 138 static unsigned int     BN_STACK_pop(BN_STACK *);
 139
 140 /**********/
 141 /* BN_CTX */
 142 /**********/
 143
 144 /* The opaque BN_CTX type */
 145 struct bignum_ctx
 146         {
 147         /* The bignum bundles */
 148         BN_POOL pool;
 149         /* The "stack frames", if you will */
 150         BN_STACK stack;
 151         /* The number of bignums currently assigned */
 152         unsigned int used;
 153         /* Depth of stack overflow */
 154         int err_stack;
 155         /* Block "gets" until an "end" (compatibility behaviour) */
 156         int too_many;
 157         };
 158
 159 /* Enable this to find BN_CTX bugs */
 160 #ifdef BN_CTX_DEBUG
 161 static const char *ctxdbg_cur = NULL;
 162 static void ctxdbg(BN_CTX *ctx)
 163         {
 164         unsigned int bnidx = 0, fpidx = 0;
 165         BN_POOL_ITEM *item = ctx->pool.head;
 166         BN_STACK *stack = &ctx->stack;
 167         fprintf(stderr,"(%08x): ", (unsigned int)ctx);
 168         while(bnidx < ctx->used)
 169                 {
 170                 fprintf(stderr,"%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
 171                 if(!(bnidx % BN_CTX_POOL_SIZE))
 172                         item = item->next;
 173                 }
 174         fprintf(stderr,"\n");
 175         bnidx = 0;
 176         fprintf(stderr,"          : ");
 177         while(fpidx < stack->depth)
 178                 {
 179                 while(bnidx++ < stack->indexes[fpidx])
 180                         fprintf(stderr,"    ");
 181                 fprintf(stderr,"^^^ ");
 182                 bnidx++;
 183                 fpidx++;
 184                 }
 185         fprintf(stderr,"\n");
 186         }
 187 #define CTXDBG_ENTRY(str, ctx)  do { \
 188                                 ctxdbg_cur = (str); \
 189                                 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
 190                                 ctxdbg(ctx); \
 191                                 } while(0)
 192 #define CTXDBG_EXIT(ctx)        do { \
 193                                 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
 194                                 ctxdbg(ctx); \
 195                                 } while(0)
 196 #define CTXDBG_RET(ctx,ret)
 197 #else
 198 #define CTXDBG_ENTRY(str, ctx)
 199 #define CTXDBG_EXIT(ctx)
 200 #define CTXDBG_RET(ctx,ret)
 201 #endif
 202
 203 /* This function is an evil legacy and should not be used. This implementation
 204  * is WYSIWYG, though I've done my best. */
 205 #ifndef OPENSSL_NO_DEPRECATED
 206 void BN_CTX_init(BN_CTX *ctx)
 207         {
 208         /* Assume the caller obtained the context via BN_CTX_new() and so is
 209          * trying to reset it for use. Nothing else makes sense, least of all
 210          * binary compatibility from a time when they could declare a static
 211          * variable. */
 212         BN_POOL_reset(&ctx->pool);
 213         BN_STACK_reset(&ctx->stack);
 214         ctx->used = 0;
 215         ctx->err_stack = 0;
 216         ctx->too_many = 0;
 217         }
 218 #endif
 219
 220 BN_CTX *BN_CTX_new(void)
 221         {
 222         BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
 223         if(!ret)
 224                 {
 225                 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
 226                 return NULL;
 227                 }
 228         /* Initialise the structure */
 229         BN_POOL_init(&ret->pool);
 230         BN_STACK_init(&ret->stack);
 231         ret->used = 0;
 232         ret->err_stack = 0;
 233         ret->too_many = 0;
 234         return ret;
 235         }
 236
 237 void BN_CTX_free(BN_CTX *ctx)
 238         {
 239         if (ctx == NULL)
 240                 return;
 241 #ifdef BN_CTX_DEBUG
 242         {
 243         BN_POOL_ITEM *pool = ctx->pool.head;
 244         fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
 245                 ctx->stack.size, ctx->pool.size);
 246         fprintf(stderr,"dmaxs: ");
 247         while(pool) {
 248                 unsigned loop = 0;
 249                 while(loop < BN_CTX_POOL_SIZE)
 250                         fprintf(stderr,"%02x ", pool->vals[loop++].dmax);
 251                 pool = pool->next;
 252         }
 253         fprintf(stderr,"\n");
 254         }
 255 #endif
 256         BN_STACK_finish(&ctx->stack);
 257         BN_POOL_finish(&ctx->pool);
 258         OPENSSL_free(ctx);
 259         }
 260
 261 void BN_CTX_start(BN_CTX *ctx)
 262         {
 263         CTXDBG_ENTRY("BN_CTX_start", ctx);
 264         /* If we're already overflowing ... */
 265         if(ctx->err_stack || ctx->too_many)
 266                 ctx->err_stack++;
 267         /* (Try to) get a new frame pointer */
 268         else if(!BN_STACK_push(&ctx->stack, ctx->used))
 269                 {
 270                 BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
 271                 ctx->err_stack++;
 272                 }
 273         CTXDBG_EXIT(ctx);
 274         }
 275
 276 void BN_CTX_end(BN_CTX *ctx)
 277         {
 278         CTXDBG_ENTRY("BN_CTX_end", ctx);
 279         if(ctx->err_stack)
 280                 ctx->err_stack--;
 281         else
 282                 {
 283                 unsigned int fp = BN_STACK_pop(&ctx->stack);
 284                 /* Does this stack frame have anything to release? */
 285                 if(fp < ctx->used)
 286                         BN_POOL_release(&ctx->pool, ctx->used - fp);
 287                 ctx->used = fp;
 288                 /* Unjam "too_many" in case "get" had failed */
 289                 ctx->too_many = 0;
 290                 }
 291         CTXDBG_EXIT(ctx);
 292         }
 293
 294 BIGNUM *BN_CTX_get(BN_CTX *ctx)
 295         {
 296         BIGNUM *ret;
 297         CTXDBG_ENTRY("BN_CTX_get", ctx);
 298         if(ctx->err_stack || ctx->too_many) return NULL;
 299         if((ret = BN_POOL_get(&ctx->pool)) == NULL)
 300                 {
 301                 /* Setting too_many prevents repeated "get" attempts from
 302                  * cluttering the error stack. */
 303                 ctx->too_many = 1;
 304                 BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
 305                 return NULL;
 306                 }
 307         /* OK, make sure the returned bignum is "zero" */
 308         BN_zero(ret);
 309         ctx->used++;
 310         CTXDBG_RET(ctx, ret);
 311         return ret;
 312         }
 313
 314 /************/
 315 /* BN_STACK */
 316 /************/
 317
 318 static void BN_STACK_init(BN_STACK *st)
 319         {
 320         st->indexes = NULL;
 321         st->depth = st->size = 0;
 322         }
 323
 324 static void BN_STACK_finish(BN_STACK *st)
 325         {
 326         if(st->size) OPENSSL_free(st->indexes);
 327         }
 328
 329 #ifndef OPENSSL_NO_DEPRECATED
 330 static void BN_STACK_reset(BN_STACK *st)
 331         {
 332         st->depth = 0;
 333         }
 334 #endif
 335
 336 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
 337         {
 338         if(st->depth == st->size)
 339                 /* Need to expand */
 340                 {
 341                 unsigned int newsize = (st->size ?
 342                                 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
 343                 unsigned int *newitems = OPENSSL_malloc(newsize *
 344                                                 sizeof(unsigned int));
 345                 if(!newitems) return 0;
 346                 if(st->depth)
 347                         memcpy(newitems, st->indexes, st->depth *
 348                                                 sizeof(unsigned int));
 349                 if(st->size) OPENSSL_free(st->indexes);
 350                 st->indexes = newitems;
 351                 st->size = newsize;
 352                 }
 353         st->indexes[(st->depth)++] = idx;
 354         return 1;
 355         }
 356
 357 static unsigned int BN_STACK_pop(BN_STACK *st)
 358         {
 359         return st->indexes[--(st->depth)];
 360         }
 361
 362 /***********/
 363 /* BN_POOL */
 364 /***********/
 365
 366 static void BN_POOL_init(BN_POOL *p)
 367         {
 368         p->head = p->current = p->tail = NULL;
 369         p->used = p->size = 0;
 370         }
 371
 372 static void BN_POOL_finish(BN_POOL *p)
 373         {
 374         while(p->head)
 375                 {
 376                 unsigned int loop = 0;
 377                 BIGNUM *bn = p->head->vals;
 378                 while(loop++ < BN_CTX_POOL_SIZE)
 379                         {
 380                         if(bn->d) BN_clear_free(bn);
 381                         bn++;
 382                         }
 383                 p->current = p->head->next;
 384                 OPENSSL_free(p->head);
 385                 p->head = p->current;
 386                 }
 387         }
 388
 389 #ifndef OPENSSL_NO_DEPRECATED
 390 static void BN_POOL_reset(BN_POOL *p)
 391         {
 392         BN_POOL_ITEM *item = p->head;
 393         while(item)
 394                 {
 395                 unsigned int loop = 0;
 396                 BIGNUM *bn = item->vals;
 397                 while(loop++ < BN_CTX_POOL_SIZE)
 398                         {
 399                         if(bn->d) BN_clear(bn);
 400                         bn++;
 401                         }
 402                 item = item->next;
 403                 }
 404         p->current = p->head;
 405         p->used = 0;
 406         }
 407 #endif
 408
 409 static BIGNUM *BN_POOL_get(BN_POOL *p)
 410         {
 411         if(p->used == p->size)
 412                 {
 413                 BIGNUM *bn;
 414                 unsigned int loop = 0;
 415                 BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
 416                 if(!item) return NULL;
 417                 /* Initialise the structure */
 418                 bn = item->vals;
 419                 while(loop++ < BN_CTX_POOL_SIZE)
 420                         BN_init(bn++);
 421                 item->prev = p->tail;
 422                 item->next = NULL;
 423                 /* Link it in */
 424                 if(!p->head)
 425                         p->head = p->current = p->tail = item;
 426                 else
 427                         {
 428                         p->tail->next = item;
 429                         p->tail = item;
 430                         p->current = item;
 431                         }
 432                 p->size += BN_CTX_POOL_SIZE;
 433                 p->used++;
 434                 /* Return the first bignum from the new pool */
 435                 return item->vals;
 436                 }
 437         if(!p->used)
 438                 p->current = p->head;
 439         else if((p->used % BN_CTX_POOL_SIZE) == 0)
 440                 p->current = p->current->next;
 441         return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
 442         }
 443
 444 static void BN_POOL_release(BN_POOL *p, unsigned int num)
 445         {
 446         unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
 447         p->used -= num;
 448         while(num--)
 449                 {
 450                 bn_check_top(p->current->vals + offset);
 451                 if(!offset)
 452                         {
 453                         offset = BN_CTX_POOL_SIZE - 1;
 454                         p->current = p->current->prev;
 455                         }
 456                 else
 457                         offset--;
 458                 }
 459         }
 460