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