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