2 * Copyright 2000-2019 The OpenSSL Project Authors. All Rights Reserved.
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
10 #include <openssl/trace.h>
11 #include "internal/cryptlib.h"
17 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
18 * check they can be safely removed.
19 * - Check +1 and other ugliness in BN_from_montgomery()
21 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
22 * appropriate 'block' size that will be honoured by bn_expand_internal() to
23 * prevent piddly little reallocations. OTOH, profiling bignum expansions in
24 * BN_CTX doesn't show this to be a big issue.
27 /* How many bignums are in each "pool item"; */
28 #define BN_CTX_POOL_SIZE 16
29 /* The stack frame info is resizing, set a first-time expansion size; */
30 #define BN_CTX_START_FRAMES 32
36 /* A bundle of bignums that can be linked with other bundles */
37 typedef struct bignum_pool_item {
38 /* The bignum values */
39 BIGNUM vals[BN_CTX_POOL_SIZE];
40 /* Linked-list admin */
41 struct bignum_pool_item *prev, *next;
43 /* A linked-list of bignums grouped in bundles */
44 typedef struct bignum_pool {
45 /* Linked-list admin */
46 BN_POOL_ITEM *head, *current, *tail;
47 /* Stack depth and allocation size */
50 static void BN_POOL_init(BN_POOL *);
51 static void BN_POOL_finish(BN_POOL *);
52 static BIGNUM *BN_POOL_get(BN_POOL *, int);
53 static void BN_POOL_release(BN_POOL *, unsigned int);
59 /* A wrapper to manage the "stack frames" */
60 typedef struct bignum_ctx_stack {
61 /* Array of indexes into the bignum stack */
62 unsigned int *indexes;
63 /* Number of stack frames, and the size of the allocated array */
64 unsigned int depth, size;
66 static void BN_STACK_init(BN_STACK *);
67 static void BN_STACK_finish(BN_STACK *);
68 static int BN_STACK_push(BN_STACK *, unsigned int);
69 static unsigned int BN_STACK_pop(BN_STACK *);
75 /* The opaque BN_CTX type */
77 /* The bignum bundles */
79 /* The "stack frames", if you will */
81 /* The number of bignums currently assigned */
83 /* Depth of stack overflow */
85 /* Block "gets" until an "end" (compatibility behaviour) */
91 /* Debugging functionality */
92 static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx)
94 unsigned int bnidx = 0, fpidx = 0;
95 BN_POOL_ITEM *item = ctx->pool.head;
96 BN_STACK *stack = &ctx->stack;
98 BIO_printf(channel, "%s\n", text);
99 BIO_printf(channel, " (%16p): ", (void*)ctx);
100 while (bnidx < ctx->used) {
101 BIO_printf(channel, "%03x ",
102 item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
103 if (!(bnidx % BN_CTX_POOL_SIZE))
106 BIO_printf(channel, "\n");
108 BIO_printf(channel, " %16s : ", "");
109 while (fpidx < stack->depth) {
110 while (bnidx++ < stack->indexes[fpidx])
111 BIO_printf(channel, " ");
112 BIO_printf(channel, "^^^ ");
116 BIO_printf(channel, "\n");
119 #define CTXDBG(str, ctx) \
120 OSSL_TRACE_BEGIN(BN_CTX) { \
121 ctxdbg(trc_out, str, ctx); \
122 } OSSL_TRACE_END(BN_CTX)
125 BN_CTX *BN_CTX_new(void)
129 if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
130 BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
133 /* Initialise the structure */
134 BN_POOL_init(&ret->pool);
135 BN_STACK_init(&ret->stack);
139 BN_CTX *BN_CTX_secure_new(void)
141 BN_CTX *ret = BN_CTX_new();
144 ret->flags = BN_FLG_SECURE;
148 void BN_CTX_free(BN_CTX *ctx)
152 OSSL_TRACE_BEGIN(BN_CTX) {
153 BN_POOL_ITEM *pool = ctx->pool.head;
155 "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n",
156 ctx->stack.size, ctx->pool.size);
157 BIO_printf(trc_out, " dmaxs: ");
160 while (loop < BN_CTX_POOL_SIZE)
161 BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax);
164 BIO_printf(trc_out, "\n");
165 } OSSL_TRACE_END(BN_CTX);
166 BN_STACK_finish(&ctx->stack);
167 BN_POOL_finish(&ctx->pool);
171 void BN_CTX_start(BN_CTX *ctx)
173 CTXDBG("ENTER BN_CTX_start()", ctx);
174 /* If we're already overflowing ... */
175 if (ctx->err_stack || ctx->too_many)
177 /* (Try to) get a new frame pointer */
178 else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
179 BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
182 CTXDBG("LEAVE BN_CTX_start()", ctx);
185 void BN_CTX_end(BN_CTX *ctx)
189 CTXDBG("ENTER BN_CTX_end()", ctx);
193 unsigned int fp = BN_STACK_pop(&ctx->stack);
194 /* Does this stack frame have anything to release? */
196 BN_POOL_release(&ctx->pool, ctx->used - fp);
198 /* Unjam "too_many" in case "get" had failed */
201 CTXDBG("LEAVE BN_CTX_end()", ctx);
204 BIGNUM *BN_CTX_get(BN_CTX *ctx)
208 CTXDBG("ENTER BN_CTX_get()", ctx);
209 if (ctx->err_stack || ctx->too_many)
211 if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) {
213 * Setting too_many prevents repeated "get" attempts from cluttering
217 BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
220 /* OK, make sure the returned bignum is "zero" */
222 /* clear BN_FLG_CONSTTIME if leaked from previous frames */
223 ret->flags &= (~BN_FLG_CONSTTIME);
225 CTXDBG("LEAVE BN_CTX_get()", ctx);
233 static void BN_STACK_init(BN_STACK *st)
236 st->depth = st->size = 0;
239 static void BN_STACK_finish(BN_STACK *st)
241 OPENSSL_free(st->indexes);
246 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
248 if (st->depth == st->size) {
250 unsigned int newsize =
251 st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES;
252 unsigned int *newitems;
254 if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) {
255 BNerr(BN_F_BN_STACK_PUSH, ERR_R_MALLOC_FAILURE);
259 memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth);
260 OPENSSL_free(st->indexes);
261 st->indexes = newitems;
264 st->indexes[(st->depth)++] = idx;
268 static unsigned int BN_STACK_pop(BN_STACK *st)
270 return st->indexes[--(st->depth)];
277 static void BN_POOL_init(BN_POOL *p)
279 p->head = p->current = p->tail = NULL;
280 p->used = p->size = 0;
283 static void BN_POOL_finish(BN_POOL *p)
289 for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++)
292 p->current = p->head->next;
293 OPENSSL_free(p->head);
294 p->head = p->current;
299 static BIGNUM *BN_POOL_get(BN_POOL *p, int flag)
304 /* Full; allocate a new pool item and link it in. */
305 if (p->used == p->size) {
308 if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) {
309 BNerr(BN_F_BN_POOL_GET, ERR_R_MALLOC_FAILURE);
312 for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) {
314 if ((flag & BN_FLG_SECURE) != 0)
315 BN_set_flags(bn, BN_FLG_SECURE);
317 item->prev = p->tail;
321 p->head = p->current = p->tail = item;
323 p->tail->next = item;
327 p->size += BN_CTX_POOL_SIZE;
329 /* Return the first bignum from the new pool */
334 p->current = p->head;
335 else if ((p->used % BN_CTX_POOL_SIZE) == 0)
336 p->current = p->current->next;
337 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
340 static void BN_POOL_release(BN_POOL *p, unsigned int num)
342 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
346 bn_check_top(p->current->vals + offset);
348 offset = BN_CTX_POOL_SIZE - 1;
349 p->current = p->current->prev;