4857661d2db32748ef9f6c84aa74b047e342c092
[openssl.git] / crypto / bn / bn_ctx.c
1 /*
2  * Copyright 2000-2019 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_lcl.h"
13
14 /*-
15  * TODO list
16  *
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()
20  *
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.
25  */
26
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
31
32 /***********/
33 /* BN_POOL */
34 /***********/
35
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;
42 } BN_POOL_ITEM;
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 */
48     unsigned used, size;
49 } BN_POOL;
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);
54
55 /************/
56 /* BN_STACK */
57 /************/
58
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;
65 } BN_STACK;
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 *);
70
71 /**********/
72 /* BN_CTX */
73 /**********/
74
75 /* The opaque BN_CTX type */
76 struct bignum_ctx {
77     /* The bignum bundles */
78     BN_POOL pool;
79     /* The "stack frames", if you will */
80     BN_STACK stack;
81     /* The number of bignums currently assigned */
82     unsigned int used;
83     /* Depth of stack overflow */
84     int err_stack;
85     /* Block "gets" until an "end" (compatibility behaviour) */
86     int too_many;
87     /* Flags. */
88     int flags;
89     /* The library context */
90     OPENSSL_CTX *libctx;
91 };
92
93 /* Debugging functionality */
94 static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx)
95 {
96     unsigned int bnidx = 0, fpidx = 0;
97     BN_POOL_ITEM *item = ctx->pool.head;
98     BN_STACK *stack = &ctx->stack;
99
100     BIO_printf(channel, "%s\n", text);
101     BIO_printf(channel, "  (%16p): ", (void*)ctx);
102     while (bnidx < ctx->used) {
103         BIO_printf(channel, "%03x ",
104                    item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
105         if (!(bnidx % BN_CTX_POOL_SIZE))
106             item = item->next;
107     }
108     BIO_printf(channel, "\n");
109     bnidx = 0;
110     BIO_printf(channel, "   %16s : ", "");
111     while (fpidx < stack->depth) {
112         while (bnidx++ < stack->indexes[fpidx])
113             BIO_printf(channel, "    ");
114         BIO_printf(channel, "^^^ ");
115         bnidx++;
116         fpidx++;
117     }
118     BIO_printf(channel, "\n");
119 }
120
121 #define CTXDBG(str, ctx)            \
122     OSSL_TRACE_BEGIN(BN_CTX) {      \
123         ctxdbg(trc_out, str, ctx);  \
124     } OSSL_TRACE_END(BN_CTX)
125
126 BN_CTX *BN_CTX_new_ex(OPENSSL_CTX *ctx)
127 {
128     BN_CTX *ret;
129
130     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
131         BNerr(BN_F_BN_CTX_NEW_EX, ERR_R_MALLOC_FAILURE);
132         return NULL;
133     }
134     /* Initialise the structure */
135     BN_POOL_init(&ret->pool);
136     BN_STACK_init(&ret->stack);
137     ret->libctx = ctx;
138     return ret;
139 }
140
141 BN_CTX *BN_CTX_new(void)
142 {
143     return BN_CTX_new_ex(NULL);
144 }
145
146 BN_CTX *BN_CTX_secure_new_ex(OPENSSL_CTX *ctx)
147 {
148     BN_CTX *ret = BN_CTX_new_ex(ctx);
149
150     if (ret != NULL)
151         ret->flags = BN_FLG_SECURE;
152     return ret;
153 }
154
155 BN_CTX *BN_CTX_secure_new(void)
156 {
157     return BN_CTX_secure_new_ex(NULL);
158 }
159
160 void BN_CTX_free(BN_CTX *ctx)
161 {
162     if (ctx == NULL)
163         return;
164     OSSL_TRACE_BEGIN(BN_CTX) {
165         BN_POOL_ITEM *pool = ctx->pool.head;
166         BIO_printf(trc_out,
167                    "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n",
168                    ctx->stack.size, ctx->pool.size);
169         BIO_printf(trc_out, "  dmaxs: ");
170         while (pool) {
171             unsigned loop = 0;
172             while (loop < BN_CTX_POOL_SIZE)
173                 BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax);
174             pool = pool->next;
175         }
176         BIO_printf(trc_out, "\n");
177     } OSSL_TRACE_END(BN_CTX);
178     BN_STACK_finish(&ctx->stack);
179     BN_POOL_finish(&ctx->pool);
180     OPENSSL_free(ctx);
181 }
182
183 void BN_CTX_start(BN_CTX *ctx)
184 {
185     CTXDBG("ENTER BN_CTX_start()", ctx);
186     /* If we're already overflowing ... */
187     if (ctx->err_stack || ctx->too_many)
188         ctx->err_stack++;
189     /* (Try to) get a new frame pointer */
190     else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
191         BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
192         ctx->err_stack++;
193     }
194     CTXDBG("LEAVE BN_CTX_start()", ctx);
195 }
196
197 void BN_CTX_end(BN_CTX *ctx)
198 {
199     if (ctx == NULL)
200         return;
201     CTXDBG("ENTER BN_CTX_end()", ctx);
202     if (ctx->err_stack)
203         ctx->err_stack--;
204     else {
205         unsigned int fp = BN_STACK_pop(&ctx->stack);
206         /* Does this stack frame have anything to release? */
207         if (fp < ctx->used)
208             BN_POOL_release(&ctx->pool, ctx->used - fp);
209         ctx->used = fp;
210         /* Unjam "too_many" in case "get" had failed */
211         ctx->too_many = 0;
212     }
213     CTXDBG("LEAVE BN_CTX_end()", ctx);
214 }
215
216 BIGNUM *BN_CTX_get(BN_CTX *ctx)
217 {
218     BIGNUM *ret;
219
220     CTXDBG("ENTER BN_CTX_get()", ctx);
221     if (ctx->err_stack || ctx->too_many)
222         return NULL;
223     if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) {
224         /*
225          * Setting too_many prevents repeated "get" attempts from cluttering
226          * the error stack.
227          */
228         ctx->too_many = 1;
229         BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
230         return NULL;
231     }
232     /* OK, make sure the returned bignum is "zero" */
233     BN_zero(ret);
234     /* clear BN_FLG_CONSTTIME if leaked from previous frames */
235     ret->flags &= (~BN_FLG_CONSTTIME);
236     ctx->used++;
237     CTXDBG("LEAVE BN_CTX_get()", ctx);
238     return ret;
239 }
240
241 /************/
242 /* BN_STACK */
243 /************/
244
245 static void BN_STACK_init(BN_STACK *st)
246 {
247     st->indexes = NULL;
248     st->depth = st->size = 0;
249 }
250
251 static void BN_STACK_finish(BN_STACK *st)
252 {
253     OPENSSL_free(st->indexes);
254     st->indexes = NULL;
255 }
256
257
258 static int BN_STACK_push(BN_STACK *st, unsigned int idx)
259 {
260     if (st->depth == st->size) {
261         /* Need to expand */
262         unsigned int newsize =
263             st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES;
264         unsigned int *newitems;
265
266         if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) {
267             BNerr(BN_F_BN_STACK_PUSH, ERR_R_MALLOC_FAILURE);
268             return 0;
269         }
270         if (st->depth)
271             memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth);
272         OPENSSL_free(st->indexes);
273         st->indexes = newitems;
274         st->size = newsize;
275     }
276     st->indexes[(st->depth)++] = idx;
277     return 1;
278 }
279
280 static unsigned int BN_STACK_pop(BN_STACK *st)
281 {
282     return st->indexes[--(st->depth)];
283 }
284
285 /***********/
286 /* BN_POOL */
287 /***********/
288
289 static void BN_POOL_init(BN_POOL *p)
290 {
291     p->head = p->current = p->tail = NULL;
292     p->used = p->size = 0;
293 }
294
295 static void BN_POOL_finish(BN_POOL *p)
296 {
297     unsigned int loop;
298     BIGNUM *bn;
299
300     while (p->head) {
301         for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++)
302             if (bn->d)
303                 BN_clear_free(bn);
304         p->current = p->head->next;
305         OPENSSL_free(p->head);
306         p->head = p->current;
307     }
308 }
309
310
311 static BIGNUM *BN_POOL_get(BN_POOL *p, int flag)
312 {
313     BIGNUM *bn;
314     unsigned int loop;
315
316     /* Full; allocate a new pool item and link it in. */
317     if (p->used == p->size) {
318         BN_POOL_ITEM *item;
319
320         if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) {
321             BNerr(BN_F_BN_POOL_GET, ERR_R_MALLOC_FAILURE);
322             return NULL;
323         }
324         for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) {
325             bn_init(bn);
326             if ((flag & BN_FLG_SECURE) != 0)
327                 BN_set_flags(bn, BN_FLG_SECURE);
328         }
329         item->prev = p->tail;
330         item->next = NULL;
331
332         if (p->head == NULL)
333             p->head = p->current = p->tail = item;
334         else {
335             p->tail->next = item;
336             p->tail = item;
337             p->current = item;
338         }
339         p->size += BN_CTX_POOL_SIZE;
340         p->used++;
341         /* Return the first bignum from the new pool */
342         return item->vals;
343     }
344
345     if (!p->used)
346         p->current = p->head;
347     else if ((p->used % BN_CTX_POOL_SIZE) == 0)
348         p->current = p->current->next;
349     return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
350 }
351
352 static void BN_POOL_release(BN_POOL *p, unsigned int num)
353 {
354     unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
355
356     p->used -= num;
357     while (num--) {
358         bn_check_top(p->current->vals + offset);
359         if (offset == 0) {
360             offset = BN_CTX_POOL_SIZE - 1;
361             p->current = p->current->prev;
362         } else
363             offset--;
364     }
365 }