xref: /openssl/crypto/bn/bn_ctx.c (revision e077455e)
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 */
ctxdbg(BIO * channel,const char * text,BN_CTX * ctx)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 
BN_CTX_new_ex(OSSL_LIB_CTX * ctx)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         return NULL;
124     /* Initialise the structure */
125     BN_POOL_init(&ret->pool);
126     BN_STACK_init(&ret->stack);
127     ret->libctx = ctx;
128     return ret;
129 }
130 
131 #ifndef FIPS_MODULE
BN_CTX_new(void)132 BN_CTX *BN_CTX_new(void)
133 {
134     return BN_CTX_new_ex(NULL);
135 }
136 #endif
137 
BN_CTX_secure_new_ex(OSSL_LIB_CTX * ctx)138 BN_CTX *BN_CTX_secure_new_ex(OSSL_LIB_CTX *ctx)
139 {
140     BN_CTX *ret = BN_CTX_new_ex(ctx);
141 
142     if (ret != NULL)
143         ret->flags = BN_FLG_SECURE;
144     return ret;
145 }
146 
147 #ifndef FIPS_MODULE
BN_CTX_secure_new(void)148 BN_CTX *BN_CTX_secure_new(void)
149 {
150     return BN_CTX_secure_new_ex(NULL);
151 }
152 #endif
153 
BN_CTX_free(BN_CTX * ctx)154 void BN_CTX_free(BN_CTX *ctx)
155 {
156     if (ctx == NULL)
157         return;
158 #ifndef FIPS_MODULE
159     OSSL_TRACE_BEGIN(BN_CTX) {
160         BN_POOL_ITEM *pool = ctx->pool.head;
161         BIO_printf(trc_out,
162                    "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n",
163                    ctx->stack.size, ctx->pool.size);
164         BIO_printf(trc_out, "  dmaxs: ");
165         while (pool) {
166             unsigned loop = 0;
167             while (loop < BN_CTX_POOL_SIZE)
168                 BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax);
169             pool = pool->next;
170         }
171         BIO_printf(trc_out, "\n");
172     } OSSL_TRACE_END(BN_CTX);
173 #endif
174     BN_STACK_finish(&ctx->stack);
175     BN_POOL_finish(&ctx->pool);
176     OPENSSL_free(ctx);
177 }
178 
BN_CTX_start(BN_CTX * ctx)179 void BN_CTX_start(BN_CTX *ctx)
180 {
181     CTXDBG("ENTER BN_CTX_start()", ctx);
182     /* If we're already overflowing ... */
183     if (ctx->err_stack || ctx->too_many)
184         ctx->err_stack++;
185     /* (Try to) get a new frame pointer */
186     else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
187         ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
188         ctx->err_stack++;
189     }
190     CTXDBG("LEAVE BN_CTX_start()", ctx);
191 }
192 
BN_CTX_end(BN_CTX * ctx)193 void BN_CTX_end(BN_CTX *ctx)
194 {
195     if (ctx == NULL)
196         return;
197     CTXDBG("ENTER 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("LEAVE BN_CTX_end()", ctx);
210 }
211 
BN_CTX_get(BN_CTX * ctx)212 BIGNUM *BN_CTX_get(BN_CTX *ctx)
213 {
214     BIGNUM *ret;
215 
216     CTXDBG("ENTER 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         ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
226         return NULL;
227     }
228     /* OK, make sure the returned bignum is "zero" */
229     BN_zero(ret);
230     /* clear BN_FLG_CONSTTIME if leaked from previous frames */
231     ret->flags &= (~BN_FLG_CONSTTIME);
232     ctx->used++;
233     CTXDBG("LEAVE BN_CTX_get()", ctx);
234     return ret;
235 }
236 
ossl_bn_get_libctx(BN_CTX * ctx)237 OSSL_LIB_CTX *ossl_bn_get_libctx(BN_CTX *ctx)
238 {
239     if (ctx == NULL)
240         return NULL;
241     return ctx->libctx;
242 }
243 
244 /************/
245 /* BN_STACK */
246 /************/
247 
BN_STACK_init(BN_STACK * st)248 static void BN_STACK_init(BN_STACK *st)
249 {
250     st->indexes = NULL;
251     st->depth = st->size = 0;
252 }
253 
BN_STACK_finish(BN_STACK * st)254 static void BN_STACK_finish(BN_STACK *st)
255 {
256     OPENSSL_free(st->indexes);
257     st->indexes = NULL;
258 }
259 
260 
BN_STACK_push(BN_STACK * st,unsigned int idx)261 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
262 {
263     if (st->depth == st->size) {
264         /* Need to expand */
265         unsigned int newsize =
266             st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES;
267         unsigned int *newitems;
268 
269         if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL)
270             return 0;
271         if (st->depth)
272             memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth);
273         OPENSSL_free(st->indexes);
274         st->indexes = newitems;
275         st->size = newsize;
276     }
277     st->indexes[(st->depth)++] = idx;
278     return 1;
279 }
280 
BN_STACK_pop(BN_STACK * st)281 static unsigned int BN_STACK_pop(BN_STACK *st)
282 {
283     return st->indexes[--(st->depth)];
284 }
285 
286 /***********/
287 /* BN_POOL */
288 /***********/
289 
BN_POOL_init(BN_POOL * p)290 static void BN_POOL_init(BN_POOL *p)
291 {
292     p->head = p->current = p->tail = NULL;
293     p->used = p->size = 0;
294 }
295 
BN_POOL_finish(BN_POOL * p)296 static void BN_POOL_finish(BN_POOL *p)
297 {
298     unsigned int loop;
299     BIGNUM *bn;
300 
301     while (p->head) {
302         for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++)
303             if (bn->d)
304                 BN_clear_free(bn);
305         p->current = p->head->next;
306         OPENSSL_free(p->head);
307         p->head = p->current;
308     }
309 }
310 
311 
BN_POOL_get(BN_POOL * p,int flag)312 static BIGNUM *BN_POOL_get(BN_POOL *p, int flag)
313 {
314     BIGNUM *bn;
315     unsigned int loop;
316 
317     /* Full; allocate a new pool item and link it in. */
318     if (p->used == p->size) {
319         BN_POOL_ITEM *item;
320 
321         if ((item = OPENSSL_malloc(sizeof(*item))) == NULL)
322             return NULL;
323         for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) {
324             bn_init(bn);
325             if ((flag & BN_FLG_SECURE) != 0)
326                 BN_set_flags(bn, BN_FLG_SECURE);
327         }
328         item->prev = p->tail;
329         item->next = NULL;
330 
331         if (p->head == NULL)
332             p->head = p->current = p->tail = item;
333         else {
334             p->tail->next = item;
335             p->tail = item;
336             p->current = item;
337         }
338         p->size += BN_CTX_POOL_SIZE;
339         p->used++;
340         /* Return the first bignum from the new pool */
341         return item->vals;
342     }
343 
344     if (!p->used)
345         p->current = p->head;
346     else if ((p->used % BN_CTX_POOL_SIZE) == 0)
347         p->current = p->current->next;
348     return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
349 }
350 
BN_POOL_release(BN_POOL * p,unsigned int num)351 static void BN_POOL_release(BN_POOL *p, unsigned int num)
352 {
353     unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
354 
355     p->used -= num;
356     while (num--) {
357         bn_check_top(p->current->vals + offset);
358         if (offset == 0) {
359             offset = BN_CTX_POOL_SIZE - 1;
360             p->current = p->current->prev;
361         } else
362             offset--;
363     }
364 }
365