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