1 /* $OpenBSD: bn_ctx.c,v 1.16 2019/08/20 10:59:09 schwarze Exp $ */
2 /* Written by Ulf Moeller for the OpenSSL project. */
3 /* ====================================================================
4 * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * 3. All advertising materials mentioning features or use of this
19 * software must display the following acknowledgment:
20 * "This product includes software developed by the OpenSSL Project
21 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
22 *
23 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
24 * endorse or promote products derived from this software without
25 * prior written permission. For written permission, please contact
26 * openssl-core@openssl.org.
27 *
28 * 5. Products derived from this software may not be called "OpenSSL"
29 * nor may "OpenSSL" appear in their names without prior written
30 * permission of the OpenSSL Project.
31 *
32 * 6. Redistributions of any form whatsoever must retain the following
33 * acknowledgment:
34 * "This product includes software developed by the OpenSSL Project
35 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
36 *
37 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
38 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
40 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
41 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
43 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
44 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
45 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
46 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
47 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
48 * OF THE POSSIBILITY OF SUCH DAMAGE.
49 * ====================================================================
50 *
51 * This product includes cryptographic software written by Eric Young
52 * (eay@cryptsoft.com). This product includes software written by Tim
53 * Hudson (tjh@cryptsoft.com).
54 *
55 */
56
57 #if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG)
58 #ifndef NDEBUG
59 #define NDEBUG
60 #endif
61 #endif
62
63 #include <stdio.h>
64 #include <string.h>
65
66 #include <openssl/opensslconf.h>
67
68 #include <openssl/err.h>
69
70 #include "bn_lcl.h"
71
72 /* TODO list
73 *
74 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
75 * check they can be safely removed.
76 * - Check +1 and other ugliness in BN_from_montgomery()
77 *
78 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
79 * appropriate 'block' size that will be honoured by bn_expand_internal() to
80 * prevent piddly little reallocations. OTOH, profiling bignum expansions in
81 * BN_CTX doesn't show this to be a big issue.
82 */
83
84 /* How many bignums are in each "pool item"; */
85 #define BN_CTX_POOL_SIZE 16
86 /* The stack frame info is resizing, set a first-time expansion size; */
87 #define BN_CTX_START_FRAMES 32
88
89 /***********/
90 /* BN_POOL */
91 /***********/
92
93 /* A bundle of bignums that can be linked with other bundles */
94 typedef struct bignum_pool_item {
95 /* The bignum values */
96 BIGNUM vals[BN_CTX_POOL_SIZE];
97 /* Linked-list admin */
98 struct bignum_pool_item *prev, *next;
99 } BN_POOL_ITEM;
100
101 /* A linked-list of bignums grouped in bundles */
102 typedef struct bignum_pool {
103 /* Linked-list admin */
104 BN_POOL_ITEM *head, *current, *tail;
105 /* Stack depth and allocation size */
106 unsigned used, size;
107 } BN_POOL;
108
109 static void BN_POOL_init(BN_POOL *);
110 static void BN_POOL_finish(BN_POOL *);
111 #ifndef OPENSSL_NO_DEPRECATED
112 static void BN_POOL_reset(BN_POOL *);
113 #endif
114 static BIGNUM * BN_POOL_get(BN_POOL *);
115 static void BN_POOL_release(BN_POOL *, unsigned int);
116
117 /************/
118 /* BN_STACK */
119 /************/
120
121 /* A wrapper to manage the "stack frames" */
122 typedef struct bignum_ctx_stack {
123 /* Array of indexes into the bignum stack */
124 unsigned int *indexes;
125 /* Number of stack frames, and the size of the allocated array */
126 unsigned int depth, size;
127 } BN_STACK;
128
129 static void BN_STACK_init(BN_STACK *);
130 static void BN_STACK_finish(BN_STACK *);
131 #ifndef OPENSSL_NO_DEPRECATED
132 static void BN_STACK_reset(BN_STACK *);
133 #endif
134 static int BN_STACK_push(BN_STACK *, unsigned int);
135 static unsigned int BN_STACK_pop(BN_STACK *);
136
137 /**********/
138 /* BN_CTX */
139 /**********/
140
141 /* The opaque BN_CTX type */
142 struct bignum_ctx {
143 /* The bignum bundles */
144 BN_POOL pool;
145 /* The "stack frames", if you will */
146 BN_STACK stack;
147 /* The number of bignums currently assigned */
148 unsigned int used;
149 /* Depth of stack overflow */
150 int err_stack;
151 /* Block "gets" until an "end" (compatibility behaviour) */
152 int too_many;
153 };
154
155 /* Enable this to find BN_CTX bugs */
156 #ifdef BN_CTX_DEBUG
157 static const char *ctxdbg_cur = NULL;
158
159 static void
ctxdbg(BN_CTX * ctx)160 ctxdbg(BN_CTX *ctx)
161 {
162 unsigned int bnidx = 0, fpidx = 0;
163 BN_POOL_ITEM *item = ctx->pool.head;
164 BN_STACK *stack = &ctx->stack;
165
166 fprintf(stderr, "(%08x): ", (unsigned int)ctx);
167 while (bnidx < ctx->used) {
168 fprintf(stderr, "%03x ",
169 item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
170 if (!(bnidx % BN_CTX_POOL_SIZE))
171 item = item->next;
172 }
173 fprintf(stderr, "\n");
174 bnidx = 0;
175 fprintf(stderr, " : ");
176 while (fpidx < stack->depth) {
177 while (bnidx++ < stack->indexes[fpidx])
178 fprintf(stderr, " ");
179 fprintf(stderr, "^^^ ");
180 bnidx++;
181 fpidx++;
182 }
183 fprintf(stderr, "\n");
184 }
185 #define CTXDBG_ENTRY(str, ctx) \
186 do { \
187 ctxdbg_cur = (str); \
188 fprintf(stderr, "Starting %s\n", ctxdbg_cur); \
189 ctxdbg(ctx); \
190 } while(0)
191
192 #define CTXDBG_EXIT(ctx) \
193 do { \
194 fprintf(stderr, "Ending %s\n", ctxdbg_cur); \
195 ctxdbg(ctx); \
196 } while(0)
197
198 #define CTXDBG_RET(ctx,ret)
199 #else
200 #define CTXDBG_ENTRY(str, ctx)
201 #define CTXDBG_EXIT(ctx)
202 #define CTXDBG_RET(ctx,ret)
203 #endif
204
205 /* This function is an evil legacy and should not be used. This implementation
206 * is WYSIWYG, though I've done my best. */
207 #ifndef OPENSSL_NO_DEPRECATED
208 void
BN_CTX_init(BN_CTX * ctx)209 BN_CTX_init(BN_CTX *ctx)
210 {
211 /* Assume the caller obtained the context via BN_CTX_new() and so is
212 * trying to reset it for use. Nothing else makes sense, least of all
213 * binary compatibility from a time when they could declare a static
214 * variable. */
215 BN_POOL_reset(&ctx->pool);
216 BN_STACK_reset(&ctx->stack);
217 ctx->used = 0;
218 ctx->err_stack = 0;
219 ctx->too_many = 0;
220 }
221 #endif
222
223 BN_CTX *
BN_CTX_new(void)224 BN_CTX_new(void)
225 {
226 BN_CTX *ret = malloc(sizeof(BN_CTX));
227 if (!ret) {
228 BNerror(ERR_R_MALLOC_FAILURE);
229 return NULL;
230 }
231
232 /* Initialise the structure */
233 BN_POOL_init(&ret->pool);
234 BN_STACK_init(&ret->stack);
235 ret->used = 0;
236 ret->err_stack = 0;
237 ret->too_many = 0;
238 return ret;
239 }
240
241 void
BN_CTX_free(BN_CTX * ctx)242 BN_CTX_free(BN_CTX *ctx)
243 {
244 if (ctx == NULL)
245 return;
246 #ifdef BN_CTX_DEBUG
247 {
248 BN_POOL_ITEM *pool = ctx->pool.head;
249 fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
250 ctx->stack.size, ctx->pool.size);
251 fprintf(stderr, "dmaxs: ");
252 while (pool) {
253 unsigned loop = 0;
254 while (loop < BN_CTX_POOL_SIZE)
255 fprintf(stderr, "%02x ",
256 pool->vals[loop++].dmax);
257 pool = pool->next;
258 }
259 fprintf(stderr, "\n");
260 }
261 #endif
262 BN_STACK_finish(&ctx->stack);
263 BN_POOL_finish(&ctx->pool);
264 free(ctx);
265 }
266
267 void
BN_CTX_start(BN_CTX * ctx)268 BN_CTX_start(BN_CTX *ctx)
269 {
270 CTXDBG_ENTRY("BN_CTX_start", ctx);
271
272 /* If we're already overflowing ... */
273 if (ctx->err_stack || ctx->too_many)
274 ctx->err_stack++;
275 /* (Try to) get a new frame pointer */
276 else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
277 BNerror(BN_R_TOO_MANY_TEMPORARY_VARIABLES);
278 ctx->err_stack++;
279 }
280 CTXDBG_EXIT(ctx);
281 }
282
283 void
BN_CTX_end(BN_CTX * ctx)284 BN_CTX_end(BN_CTX *ctx)
285 {
286 if (ctx == NULL)
287 return;
288
289 CTXDBG_ENTRY("BN_CTX_end", ctx);
290
291 if (ctx->err_stack)
292 ctx->err_stack--;
293 else {
294 unsigned int fp = BN_STACK_pop(&ctx->stack);
295 /* Does this stack frame have anything to release? */
296 if (fp < ctx->used)
297 BN_POOL_release(&ctx->pool, ctx->used - fp);
298 ctx->used = fp;
299 /* Unjam "too_many" in case "get" had failed */
300 ctx->too_many = 0;
301 }
302 CTXDBG_EXIT(ctx);
303 }
304
305 BIGNUM *
BN_CTX_get(BN_CTX * ctx)306 BN_CTX_get(BN_CTX *ctx)
307 {
308 BIGNUM *ret;
309
310 CTXDBG_ENTRY("BN_CTX_get", ctx);
311
312 if (ctx->err_stack || ctx->too_many)
313 return NULL;
314 if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
315 /* Setting too_many prevents repeated "get" attempts from
316 * cluttering the error stack. */
317 ctx->too_many = 1;
318 BNerror(BN_R_TOO_MANY_TEMPORARY_VARIABLES);
319 return NULL;
320 }
321 /* OK, make sure the returned bignum is "zero" */
322 BN_zero(ret);
323 ctx->used++;
324 CTXDBG_RET(ctx, ret);
325 return ret;
326 }
327
328 /************/
329 /* BN_STACK */
330 /************/
331
332 static void
BN_STACK_init(BN_STACK * st)333 BN_STACK_init(BN_STACK *st)
334 {
335 st->indexes = NULL;
336 st->depth = st->size = 0;
337 }
338
339 static void
BN_STACK_finish(BN_STACK * st)340 BN_STACK_finish(BN_STACK *st)
341 {
342 if (st->size)
343 free(st->indexes);
344 }
345
346 #ifndef OPENSSL_NO_DEPRECATED
347 static void
BN_STACK_reset(BN_STACK * st)348 BN_STACK_reset(BN_STACK *st)
349 {
350 st->depth = 0;
351 }
352 #endif
353
354 static int
BN_STACK_push(BN_STACK * st,unsigned int idx)355 BN_STACK_push(BN_STACK *st, unsigned int idx)
356 {
357 if (st->depth == st->size)
358 /* Need to expand */
359 {
360 unsigned int newsize = (st->size ?
361 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
362 unsigned int *newitems = reallocarray(NULL,
363 newsize, sizeof(unsigned int));
364 if (!newitems)
365 return 0;
366 if (st->depth)
367 memcpy(newitems, st->indexes, st->depth *
368 sizeof(unsigned int));
369 if (st->size)
370 free(st->indexes);
371 st->indexes = newitems;
372 st->size = newsize;
373 }
374 st->indexes[(st->depth)++] = idx;
375 return 1;
376 }
377
378 static unsigned int
BN_STACK_pop(BN_STACK * st)379 BN_STACK_pop(BN_STACK *st)
380 {
381 return st->indexes[--(st->depth)];
382 }
383
384 /***********/
385 /* BN_POOL */
386 /***********/
387
388 static void
BN_POOL_init(BN_POOL * p)389 BN_POOL_init(BN_POOL *p)
390 {
391 p->head = p->current = p->tail = NULL;
392 p->used = p->size = 0;
393 }
394
395 static void
BN_POOL_finish(BN_POOL * p)396 BN_POOL_finish(BN_POOL *p)
397 {
398 while (p->head) {
399 unsigned int loop = 0;
400 BIGNUM *bn = p->head->vals;
401 while (loop++ < BN_CTX_POOL_SIZE) {
402 if (bn->d)
403 BN_clear_free(bn);
404 bn++;
405 }
406 p->current = p->head->next;
407 free(p->head);
408 p->head = p->current;
409 }
410 }
411
412 #ifndef OPENSSL_NO_DEPRECATED
413 static void
BN_POOL_reset(BN_POOL * p)414 BN_POOL_reset(BN_POOL *p)
415 {
416 BN_POOL_ITEM *item = p->head;
417 while (item) {
418 unsigned int loop = 0;
419 BIGNUM *bn = item->vals;
420 while (loop++ < BN_CTX_POOL_SIZE) {
421 if (bn->d)
422 BN_clear(bn);
423 bn++;
424 }
425 item = item->next;
426 }
427 p->current = p->head;
428 p->used = 0;
429 }
430 #endif
431
432 static BIGNUM *
BN_POOL_get(BN_POOL * p)433 BN_POOL_get(BN_POOL *p)
434 {
435 if (p->used == p->size) {
436 BIGNUM *bn;
437 unsigned int loop = 0;
438 BN_POOL_ITEM *item = malloc(sizeof(BN_POOL_ITEM));
439 if (!item)
440 return NULL;
441 /* Initialise the structure */
442 bn = item->vals;
443 while (loop++ < BN_CTX_POOL_SIZE)
444 BN_init(bn++);
445 item->prev = p->tail;
446 item->next = NULL;
447 /* Link it in */
448 if (!p->head)
449 p->head = p->current = p->tail = item;
450 else {
451 p->tail->next = item;
452 p->tail = item;
453 p->current = item;
454 }
455 p->size += BN_CTX_POOL_SIZE;
456 p->used++;
457 /* Return the first bignum from the new pool */
458 return item->vals;
459 }
460 if (!p->used)
461 p->current = p->head;
462 else if ((p->used % BN_CTX_POOL_SIZE) == 0)
463 p->current = p->current->next;
464 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
465 }
466
467 static void
BN_POOL_release(BN_POOL * p,unsigned int num)468 BN_POOL_release(BN_POOL *p, unsigned int num)
469 {
470 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
471
472 p->used -= num;
473 while (num--) {
474 bn_check_top(p->current->vals + offset);
475 if (!offset) {
476 offset = BN_CTX_POOL_SIZE - 1;
477 p->current = p->current->prev;
478 } else
479 offset--;
480 }
481 }
482