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