1 /* 2 * Copyright 2000-2021 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (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 <openssl/trace.h> 11 #include "internal/cryptlib.h" 12 #include "bn_local.h" 13 14 /* How many bignums are in each "pool item"; */ 15 #define BN_CTX_POOL_SIZE 16 16 /* The stack frame info is resizing, set a first-time expansion size; */ 17 #define BN_CTX_START_FRAMES 32 18 19 /***********/ 20 /* BN_POOL */ 21 /***********/ 22 23 /* A bundle of bignums that can be linked with other bundles */ 24 typedef struct bignum_pool_item { 25 /* The bignum values */ 26 BIGNUM vals[BN_CTX_POOL_SIZE]; 27 /* Linked-list admin */ 28 struct bignum_pool_item *prev, *next; 29 } BN_POOL_ITEM; 30 /* A linked-list of bignums grouped in bundles */ 31 typedef struct bignum_pool { 32 /* Linked-list admin */ 33 BN_POOL_ITEM *head, *current, *tail; 34 /* Stack depth and allocation size */ 35 unsigned used, size; 36 } BN_POOL; 37 static void BN_POOL_init(BN_POOL *); 38 static void BN_POOL_finish(BN_POOL *); 39 static BIGNUM *BN_POOL_get(BN_POOL *, int); 40 static void BN_POOL_release(BN_POOL *, unsigned int); 41 42 /************/ 43 /* BN_STACK */ 44 /************/ 45 46 /* A wrapper to manage the "stack frames" */ 47 typedef struct bignum_ctx_stack { 48 /* Array of indexes into the bignum stack */ 49 unsigned int *indexes; 50 /* Number of stack frames, and the size of the allocated array */ 51 unsigned int depth, size; 52 } BN_STACK; 53 static void BN_STACK_init(BN_STACK *); 54 static void BN_STACK_finish(BN_STACK *); 55 static int BN_STACK_push(BN_STACK *, unsigned int); 56 static unsigned int BN_STACK_pop(BN_STACK *); 57 58 /**********/ 59 /* BN_CTX */ 60 /**********/ 61 62 /* The opaque BN_CTX type */ 63 struct bignum_ctx { 64 /* The bignum bundles */ 65 BN_POOL pool; 66 /* The "stack frames", if you will */ 67 BN_STACK stack; 68 /* The number of bignums currently assigned */ 69 unsigned int used; 70 /* Depth of stack overflow */ 71 int err_stack; 72 /* Block "gets" until an "end" (compatibility behaviour) */ 73 int too_many; 74 /* Flags. */ 75 int flags; 76 /* The library context */ 77 OSSL_LIB_CTX *libctx; 78 }; 79 80 #ifndef FIPS_MODULE 81 /* Debugging functionality */ 82 static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx) 83 { 84 unsigned int bnidx = 0, fpidx = 0; 85 BN_POOL_ITEM *item = ctx->pool.head; 86 BN_STACK *stack = &ctx->stack; 87 88 BIO_printf(channel, "%s\n", text); 89 BIO_printf(channel, " (%16p): ", (void*)ctx); 90 while (bnidx < ctx->used) { 91 BIO_printf(channel, "%03x ", 92 item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 93 if (!(bnidx % BN_CTX_POOL_SIZE)) 94 item = item->next; 95 } 96 BIO_printf(channel, "\n"); 97 bnidx = 0; 98 BIO_printf(channel, " %16s : ", ""); 99 while (fpidx < stack->depth) { 100 while (bnidx++ < stack->indexes[fpidx]) 101 BIO_printf(channel, " "); 102 BIO_printf(channel, "^^^ "); 103 bnidx++; 104 fpidx++; 105 } 106 BIO_printf(channel, "\n"); 107 } 108 109 # define CTXDBG(str, ctx) \ 110 OSSL_TRACE_BEGIN(BN_CTX) { \ 111 ctxdbg(trc_out, str, ctx); \ 112 } OSSL_TRACE_END(BN_CTX) 113 #else 114 /* We do not want tracing in FIPS module */ 115 # define CTXDBG(str, ctx) do {} while(0) 116 #endif /* FIPS_MODULE */ 117 118 BN_CTX *BN_CTX_new_ex(OSSL_LIB_CTX *ctx) 119 { 120 BN_CTX *ret; 121 122 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { 123 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 124 return NULL; 125 } 126 /* Initialise the structure */ 127 BN_POOL_init(&ret->pool); 128 BN_STACK_init(&ret->stack); 129 ret->libctx = ctx; 130 return ret; 131 } 132 133 #ifndef FIPS_MODULE 134 BN_CTX *BN_CTX_new(void) 135 { 136 return BN_CTX_new_ex(NULL); 137 } 138 #endif 139 140 BN_CTX *BN_CTX_secure_new_ex(OSSL_LIB_CTX *ctx) 141 { 142 BN_CTX *ret = BN_CTX_new_ex(ctx); 143 144 if (ret != NULL) 145 ret->flags = BN_FLG_SECURE; 146 return ret; 147 } 148 149 #ifndef FIPS_MODULE 150 BN_CTX *BN_CTX_secure_new(void) 151 { 152 return BN_CTX_secure_new_ex(NULL); 153 } 154 #endif 155 156 void BN_CTX_free(BN_CTX *ctx) 157 { 158 if (ctx == NULL) 159 return; 160 #ifndef FIPS_MODULE 161 OSSL_TRACE_BEGIN(BN_CTX) { 162 BN_POOL_ITEM *pool = ctx->pool.head; 163 BIO_printf(trc_out, 164 "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n", 165 ctx->stack.size, ctx->pool.size); 166 BIO_printf(trc_out, " dmaxs: "); 167 while (pool) { 168 unsigned loop = 0; 169 while (loop < BN_CTX_POOL_SIZE) 170 BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax); 171 pool = pool->next; 172 } 173 BIO_printf(trc_out, "\n"); 174 } OSSL_TRACE_END(BN_CTX); 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("ENTER 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 ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 190 ctx->err_stack++; 191 } 192 CTXDBG("LEAVE BN_CTX_start()", ctx); 193 } 194 195 void BN_CTX_end(BN_CTX *ctx) 196 { 197 if (ctx == NULL) 198 return; 199 CTXDBG("ENTER 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("LEAVE BN_CTX_end()", ctx); 212 } 213 214 BIGNUM *BN_CTX_get(BN_CTX *ctx) 215 { 216 BIGNUM *ret; 217 218 CTXDBG("ENTER 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 ERR_raise(ERR_LIB_BN, 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("LEAVE BN_CTX_get()", ctx); 236 return ret; 237 } 238 239 OSSL_LIB_CTX *ossl_bn_get_libctx(BN_CTX *ctx) 240 { 241 if (ctx == NULL) 242 return NULL; 243 return ctx->libctx; 244 } 245 246 /************/ 247 /* BN_STACK */ 248 /************/ 249 250 static void BN_STACK_init(BN_STACK *st) 251 { 252 st->indexes = NULL; 253 st->depth = st->size = 0; 254 } 255 256 static void BN_STACK_finish(BN_STACK *st) 257 { 258 OPENSSL_free(st->indexes); 259 st->indexes = NULL; 260 } 261 262 263 static int BN_STACK_push(BN_STACK *st, unsigned int idx) 264 { 265 if (st->depth == st->size) { 266 /* Need to expand */ 267 unsigned int newsize = 268 st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES; 269 unsigned int *newitems; 270 271 if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) { 272 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 273 return 0; 274 } 275 if (st->depth) 276 memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth); 277 OPENSSL_free(st->indexes); 278 st->indexes = newitems; 279 st->size = newsize; 280 } 281 st->indexes[(st->depth)++] = idx; 282 return 1; 283 } 284 285 static unsigned int BN_STACK_pop(BN_STACK *st) 286 { 287 return st->indexes[--(st->depth)]; 288 } 289 290 /***********/ 291 /* BN_POOL */ 292 /***********/ 293 294 static void BN_POOL_init(BN_POOL *p) 295 { 296 p->head = p->current = p->tail = NULL; 297 p->used = p->size = 0; 298 } 299 300 static void BN_POOL_finish(BN_POOL *p) 301 { 302 unsigned int loop; 303 BIGNUM *bn; 304 305 while (p->head) { 306 for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++) 307 if (bn->d) 308 BN_clear_free(bn); 309 p->current = p->head->next; 310 OPENSSL_free(p->head); 311 p->head = p->current; 312 } 313 } 314 315 316 static BIGNUM *BN_POOL_get(BN_POOL *p, int flag) 317 { 318 BIGNUM *bn; 319 unsigned int loop; 320 321 /* Full; allocate a new pool item and link it in. */ 322 if (p->used == p->size) { 323 BN_POOL_ITEM *item; 324 325 if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) { 326 ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE); 327 return NULL; 328 } 329 for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) { 330 bn_init(bn); 331 if ((flag & BN_FLG_SECURE) != 0) 332 BN_set_flags(bn, BN_FLG_SECURE); 333 } 334 item->prev = p->tail; 335 item->next = NULL; 336 337 if (p->head == NULL) 338 p->head = p->current = p->tail = item; 339 else { 340 p->tail->next = item; 341 p->tail = item; 342 p->current = item; 343 } 344 p->size += BN_CTX_POOL_SIZE; 345 p->used++; 346 /* Return the first bignum from the new pool */ 347 return item->vals; 348 } 349 350 if (!p->used) 351 p->current = p->head; 352 else if ((p->used % BN_CTX_POOL_SIZE) == 0) 353 p->current = p->current->next; 354 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 355 } 356 357 static void BN_POOL_release(BN_POOL *p, unsigned int num) 358 { 359 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 360 361 p->used -= num; 362 while (num--) { 363 bn_check_top(p->current->vals + offset); 364 if (offset == 0) { 365 offset = BN_CTX_POOL_SIZE - 1; 366 p->current = p->current->prev; 367 } else 368 offset--; 369 } 370 } 371