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 */ 24typedef 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 */ 31typedef 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; 37static void BN_POOL_init(BN_POOL *); 38static void BN_POOL_finish(BN_POOL *); 39static BIGNUM *BN_POOL_get(BN_POOL *, int); 40static void BN_POOL_release(BN_POOL *, unsigned int); 41 42/************/ 43/* BN_STACK */ 44/************/ 45 46/* A wrapper to manage the "stack frames" */ 47typedef 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; 53static void BN_STACK_init(BN_STACK *); 54static void BN_STACK_finish(BN_STACK *); 55static int BN_STACK_push(BN_STACK *, unsigned int); 56static unsigned int BN_STACK_pop(BN_STACK *); 57 58/**********/ 59/* BN_CTX */ 60/**********/ 61 62/* The opaque BN_CTX type */ 63struct 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 */ 82static 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 118BN_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 134BN_CTX *BN_CTX_new(void) 135{ 136 return BN_CTX_new_ex(NULL); 137} 138#endif 139 140BN_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 150BN_CTX *BN_CTX_secure_new(void) 151{ 152 return BN_CTX_secure_new_ex(NULL); 153} 154#endif 155 156void 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 181void 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 195void 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 214BIGNUM *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 239OSSL_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 250static void BN_STACK_init(BN_STACK *st) 251{ 252 st->indexes = NULL; 253 st->depth = st->size = 0; 254} 255 256static void BN_STACK_finish(BN_STACK *st) 257{ 258 OPENSSL_free(st->indexes); 259 st->indexes = NULL; 260} 261 262 263static 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 285static unsigned int BN_STACK_pop(BN_STACK *st) 286{ 287 return st->indexes[--(st->depth)]; 288} 289 290/***********/ 291/* BN_POOL */ 292/***********/ 293 294static void BN_POOL_init(BN_POOL *p) 295{ 296 p->head = p->current = p->tail = NULL; 297 p->used = p->size = 0; 298} 299 300static 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 316static 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 357static 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