1 /* 2 * Copyright 2000-2018 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_lcl.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 CTXDBG_ENTRY("BN_CTX_end", ctx); 198 if (ctx->err_stack) 199 ctx->err_stack--; 200 else { 201 unsigned int fp = BN_STACK_pop(&ctx->stack); 202 /* Does this stack frame have anything to release? */ 203 if (fp < ctx->used) 204 BN_POOL_release(&ctx->pool, ctx->used - fp); 205 ctx->used = fp; 206 /* Unjam "too_many" in case "get" had failed */ 207 ctx->too_many = 0; 208 } 209 CTXDBG_EXIT(ctx); 210 } 211 212 BIGNUM *BN_CTX_get(BN_CTX *ctx) 213 { 214 BIGNUM *ret; 215 216 CTXDBG_ENTRY("BN_CTX_get", ctx); 217 if (ctx->err_stack || ctx->too_many) 218 return NULL; 219 if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) { 220 /* 221 * Setting too_many prevents repeated "get" attempts from cluttering 222 * the error stack. 223 */ 224 ctx->too_many = 1; 225 BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 226 return NULL; 227 } 228 /* OK, make sure the returned bignum is "zero" */ 229 BN_zero(ret); 230 ctx->used++; 231 CTXDBG_RET(ctx, ret); 232 return ret; 233 } 234 235 /************/ 236 /* BN_STACK */ 237 /************/ 238 239 static void BN_STACK_init(BN_STACK *st) 240 { 241 st->indexes = NULL; 242 st->depth = st->size = 0; 243 } 244 245 static void BN_STACK_finish(BN_STACK *st) 246 { 247 OPENSSL_free(st->indexes); 248 st->indexes = NULL; 249 } 250 251 252 static int BN_STACK_push(BN_STACK *st, unsigned int idx) 253 { 254 if (st->depth == st->size) { 255 /* Need to expand */ 256 unsigned int newsize = 257 st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES; 258 unsigned int *newitems; 259 260 if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) { 261 BNerr(BN_F_BN_STACK_PUSH, ERR_R_MALLOC_FAILURE); 262 return 0; 263 } 264 if (st->depth) 265 memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth); 266 OPENSSL_free(st->indexes); 267 st->indexes = newitems; 268 st->size = newsize; 269 } 270 st->indexes[(st->depth)++] = idx; 271 return 1; 272 } 273 274 static unsigned int BN_STACK_pop(BN_STACK *st) 275 { 276 return st->indexes[--(st->depth)]; 277 } 278 279 /***********/ 280 /* BN_POOL */ 281 /***********/ 282 283 static void BN_POOL_init(BN_POOL *p) 284 { 285 p->head = p->current = p->tail = NULL; 286 p->used = p->size = 0; 287 } 288 289 static void BN_POOL_finish(BN_POOL *p) 290 { 291 unsigned int loop; 292 BIGNUM *bn; 293 294 while (p->head) { 295 for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++) 296 if (bn->d) 297 BN_clear_free(bn); 298 p->current = p->head->next; 299 OPENSSL_free(p->head); 300 p->head = p->current; 301 } 302 } 303 304 305 static BIGNUM *BN_POOL_get(BN_POOL *p, int flag) 306 { 307 BIGNUM *bn; 308 unsigned int loop; 309 310 /* Full; allocate a new pool item and link it in. */ 311 if (p->used == p->size) { 312 BN_POOL_ITEM *item; 313 314 if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) { 315 BNerr(BN_F_BN_POOL_GET, ERR_R_MALLOC_FAILURE); 316 return NULL; 317 } 318 for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) { 319 bn_init(bn); 320 if ((flag & BN_FLG_SECURE) != 0) 321 BN_set_flags(bn, BN_FLG_SECURE); 322 } 323 item->prev = p->tail; 324 item->next = NULL; 325 326 if (p->head == NULL) 327 p->head = p->current = p->tail = item; 328 else { 329 p->tail->next = item; 330 p->tail = item; 331 p->current = item; 332 } 333 p->size += BN_CTX_POOL_SIZE; 334 p->used++; 335 /* Return the first bignum from the new pool */ 336 return item->vals; 337 } 338 339 if (!p->used) 340 p->current = p->head; 341 else if ((p->used % BN_CTX_POOL_SIZE) == 0) 342 p->current = p->current->next; 343 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 344 } 345 346 static void BN_POOL_release(BN_POOL *p, unsigned int num) 347 { 348 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 349 350 p->used -= num; 351 while (num--) { 352 bn_check_top(p->current->vals + offset); 353 if (offset == 0) { 354 offset = BN_CTX_POOL_SIZE - 1; 355 p->current = p->current->prev; 356 } else 357 offset--; 358 } 359 } 360