1 /* 2 * Copyright 2000-2019 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 #include "internal/cryptlib.h" 11 #include "bn_local.h" 12 13 /*- 14 * TODO list 15 * 16 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and 17 * check they can be safely removed. 18 * - Check +1 and other ugliness in BN_from_montgomery() 19 * 20 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an 21 * appropriate 'block' size that will be honoured by bn_expand_internal() to 22 * prevent piddly little reallocations. OTOH, profiling bignum expansions in 23 * BN_CTX doesn't show this to be a big issue. 24 */ 25 26 /* How many bignums are in each "pool item"; */ 27 #define BN_CTX_POOL_SIZE 16 28 /* The stack frame info is resizing, set a first-time expansion size; */ 29 #define BN_CTX_START_FRAMES 32 30 31 /***********/ 32 /* BN_POOL */ 33 /***********/ 34 35 /* A bundle of bignums that can be linked with other bundles */ 36 typedef struct bignum_pool_item { 37 /* The bignum values */ 38 BIGNUM vals[BN_CTX_POOL_SIZE]; 39 /* Linked-list admin */ 40 struct bignum_pool_item *prev, *next; 41 } BN_POOL_ITEM; 42 /* A linked-list of bignums grouped in bundles */ 43 typedef struct bignum_pool { 44 /* Linked-list admin */ 45 BN_POOL_ITEM *head, *current, *tail; 46 /* Stack depth and allocation size */ 47 unsigned used, size; 48 } BN_POOL; 49 static void BN_POOL_init(BN_POOL *); 50 static void BN_POOL_finish(BN_POOL *); 51 static BIGNUM *BN_POOL_get(BN_POOL *, int); 52 static void BN_POOL_release(BN_POOL *, unsigned int); 53 54 /************/ 55 /* BN_STACK */ 56 /************/ 57 58 /* A wrapper to manage the "stack frames" */ 59 typedef struct bignum_ctx_stack { 60 /* Array of indexes into the bignum stack */ 61 unsigned int *indexes; 62 /* Number of stack frames, and the size of the allocated array */ 63 unsigned int depth, size; 64 } BN_STACK; 65 static void BN_STACK_init(BN_STACK *); 66 static void BN_STACK_finish(BN_STACK *); 67 static int BN_STACK_push(BN_STACK *, unsigned int); 68 static unsigned int BN_STACK_pop(BN_STACK *); 69 70 /**********/ 71 /* BN_CTX */ 72 /**********/ 73 74 /* The opaque BN_CTX type */ 75 struct bignum_ctx { 76 /* The bignum bundles */ 77 BN_POOL pool; 78 /* The "stack frames", if you will */ 79 BN_STACK stack; 80 /* The number of bignums currently assigned */ 81 unsigned int used; 82 /* Depth of stack overflow */ 83 int err_stack; 84 /* Block "gets" until an "end" (compatibility behaviour) */ 85 int too_many; 86 /* Flags. */ 87 int flags; 88 }; 89 90 /* Enable this to find BN_CTX bugs */ 91 #ifdef BN_CTX_DEBUG 92 static const char *ctxdbg_cur = NULL; 93 static void ctxdbg(BN_CTX *ctx) 94 { 95 unsigned int bnidx = 0, fpidx = 0; 96 BN_POOL_ITEM *item = ctx->pool.head; 97 BN_STACK *stack = &ctx->stack; 98 fprintf(stderr, "(%16p): ", ctx); 99 while (bnidx < ctx->used) { 100 fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 101 if (!(bnidx % BN_CTX_POOL_SIZE)) 102 item = item->next; 103 } 104 fprintf(stderr, "\n"); 105 bnidx = 0; 106 fprintf(stderr, " : "); 107 while (fpidx < stack->depth) { 108 while (bnidx++ < stack->indexes[fpidx]) 109 fprintf(stderr, " "); 110 fprintf(stderr, "^^^ "); 111 bnidx++; 112 fpidx++; 113 } 114 fprintf(stderr, "\n"); 115 } 116 117 # define CTXDBG_ENTRY(str, ctx) do { \ 118 ctxdbg_cur = (str); \ 119 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ 120 ctxdbg(ctx); \ 121 } while(0) 122 # define CTXDBG_EXIT(ctx) do { \ 123 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ 124 ctxdbg(ctx); \ 125 } while(0) 126 # define CTXDBG_RET(ctx,ret) 127 #else 128 # define CTXDBG_ENTRY(str, ctx) 129 # define CTXDBG_EXIT(ctx) 130 # define CTXDBG_RET(ctx,ret) 131 #endif 132 133 134 BN_CTX *BN_CTX_new(void) 135 { 136 BN_CTX *ret; 137 138 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { 139 BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE); 140 return NULL; 141 } 142 /* Initialise the structure */ 143 BN_POOL_init(&ret->pool); 144 BN_STACK_init(&ret->stack); 145 return ret; 146 } 147 148 BN_CTX *BN_CTX_secure_new(void) 149 { 150 BN_CTX *ret = BN_CTX_new(); 151 152 if (ret != NULL) 153 ret->flags = BN_FLG_SECURE; 154 return ret; 155 } 156 157 void BN_CTX_free(BN_CTX *ctx) 158 { 159 if (ctx == NULL) 160 return; 161 #ifdef BN_CTX_DEBUG 162 { 163 BN_POOL_ITEM *pool = ctx->pool.head; 164 fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n", 165 ctx->stack.size, ctx->pool.size); 166 fprintf(stderr, "dmaxs: "); 167 while (pool) { 168 unsigned loop = 0; 169 while (loop < BN_CTX_POOL_SIZE) 170 fprintf(stderr, "%02x ", pool->vals[loop++].dmax); 171 pool = pool->next; 172 } 173 fprintf(stderr, "\n"); 174 } 175 #endif 176 BN_STACK_finish(&ctx->stack); 177 BN_POOL_finish(&ctx->pool); 178 OPENSSL_free(ctx); 179 } 180 181 void BN_CTX_start(BN_CTX *ctx) 182 { 183 CTXDBG_ENTRY("BN_CTX_start", ctx); 184 /* If we're already overflowing ... */ 185 if (ctx->err_stack || ctx->too_many) 186 ctx->err_stack++; 187 /* (Try to) get a new frame pointer */ 188 else if (!BN_STACK_push(&ctx->stack, ctx->used)) { 189 BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 190 ctx->err_stack++; 191 } 192 CTXDBG_EXIT(ctx); 193 } 194 195 void BN_CTX_end(BN_CTX *ctx) 196 { 197 if (ctx == NULL) 198 return; 199 CTXDBG_ENTRY("BN_CTX_end", ctx); 200 if (ctx->err_stack) 201 ctx->err_stack--; 202 else { 203 unsigned int fp = BN_STACK_pop(&ctx->stack); 204 /* Does this stack frame have anything to release? */ 205 if (fp < ctx->used) 206 BN_POOL_release(&ctx->pool, ctx->used - fp); 207 ctx->used = fp; 208 /* Unjam "too_many" in case "get" had failed */ 209 ctx->too_many = 0; 210 } 211 CTXDBG_EXIT(ctx); 212 } 213 214 BIGNUM *BN_CTX_get(BN_CTX *ctx) 215 { 216 BIGNUM *ret; 217 218 CTXDBG_ENTRY("BN_CTX_get", ctx); 219 if (ctx->err_stack || ctx->too_many) 220 return NULL; 221 if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) { 222 /* 223 * Setting too_many prevents repeated "get" attempts from cluttering 224 * the error stack. 225 */ 226 ctx->too_many = 1; 227 BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 228 return NULL; 229 } 230 /* OK, make sure the returned bignum is "zero" */ 231 BN_zero(ret); 232 /* clear BN_FLG_CONSTTIME if leaked from previous frames */ 233 ret->flags &= (~BN_FLG_CONSTTIME); 234 ctx->used++; 235 CTXDBG_RET(ctx, ret); 236 return ret; 237 } 238 239 /************/ 240 /* BN_STACK */ 241 /************/ 242 243 static void BN_STACK_init(BN_STACK *st) 244 { 245 st->indexes = NULL; 246 st->depth = st->size = 0; 247 } 248 249 static void BN_STACK_finish(BN_STACK *st) 250 { 251 OPENSSL_free(st->indexes); 252 st->indexes = NULL; 253 } 254 255 256 static int BN_STACK_push(BN_STACK *st, unsigned int idx) 257 { 258 if (st->depth == st->size) { 259 /* Need to expand */ 260 unsigned int newsize = 261 st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES; 262 unsigned int *newitems; 263 264 if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) { 265 BNerr(BN_F_BN_STACK_PUSH, ERR_R_MALLOC_FAILURE); 266 return 0; 267 } 268 if (st->depth) 269 memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth); 270 OPENSSL_free(st->indexes); 271 st->indexes = newitems; 272 st->size = newsize; 273 } 274 st->indexes[(st->depth)++] = idx; 275 return 1; 276 } 277 278 static unsigned int BN_STACK_pop(BN_STACK *st) 279 { 280 return st->indexes[--(st->depth)]; 281 } 282 283 /***********/ 284 /* BN_POOL */ 285 /***********/ 286 287 static void BN_POOL_init(BN_POOL *p) 288 { 289 p->head = p->current = p->tail = NULL; 290 p->used = p->size = 0; 291 } 292 293 static void BN_POOL_finish(BN_POOL *p) 294 { 295 unsigned int loop; 296 BIGNUM *bn; 297 298 while (p->head) { 299 for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++) 300 if (bn->d) 301 BN_clear_free(bn); 302 p->current = p->head->next; 303 OPENSSL_free(p->head); 304 p->head = p->current; 305 } 306 } 307 308 309 static BIGNUM *BN_POOL_get(BN_POOL *p, int flag) 310 { 311 BIGNUM *bn; 312 unsigned int loop; 313 314 /* Full; allocate a new pool item and link it in. */ 315 if (p->used == p->size) { 316 BN_POOL_ITEM *item; 317 318 if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) { 319 BNerr(BN_F_BN_POOL_GET, ERR_R_MALLOC_FAILURE); 320 return NULL; 321 } 322 for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) { 323 bn_init(bn); 324 if ((flag & BN_FLG_SECURE) != 0) 325 BN_set_flags(bn, BN_FLG_SECURE); 326 } 327 item->prev = p->tail; 328 item->next = NULL; 329 330 if (p->head == NULL) 331 p->head = p->current = p->tail = item; 332 else { 333 p->tail->next = item; 334 p->tail = item; 335 p->current = item; 336 } 337 p->size += BN_CTX_POOL_SIZE; 338 p->used++; 339 /* Return the first bignum from the new pool */ 340 return item->vals; 341 } 342 343 if (!p->used) 344 p->current = p->head; 345 else if ((p->used % BN_CTX_POOL_SIZE) == 0) 346 p->current = p->current->next; 347 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 348 } 349 350 static void BN_POOL_release(BN_POOL *p, unsigned int num) 351 { 352 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 353 354 p->used -= num; 355 while (num--) { 356 bn_check_top(p->current->vals + offset); 357 if (offset == 0) { 358 offset = BN_CTX_POOL_SIZE - 1; 359 p->current = p->current->prev; 360 } else 361 offset--; 362 } 363 } 364