]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
8020d79b | 2 | * Copyright 2000-2021 The OpenSSL Project Authors. All Rights Reserved. |
9b141126 | 3 | * |
367ace68 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
4f22f405 RS |
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 | |
9b141126 UM |
8 | */ |
9 | ||
6e810f2d | 10 | #include <openssl/trace.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
706457b7 | 12 | #include "bn_local.h" |
9b141126 | 13 | |
5c98b2ca | 14 | /* How many bignums are in each "pool item"; */ |
0f113f3e | 15 | #define BN_CTX_POOL_SIZE 16 |
5c98b2ca | 16 | /* The stack frame info is resizing, set a first-time expansion size; */ |
0f113f3e | 17 | #define BN_CTX_START_FRAMES 32 |
5c98b2ca GT |
18 | |
19 | /***********/ | |
20 | /* BN_POOL */ | |
21 | /***********/ | |
22 | ||
23 | /* A bundle of bignums that can be linked with other bundles */ | |
0f113f3e MC |
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; | |
5c98b2ca | 30 | /* A linked-list of bignums grouped in bundles */ |
0f113f3e MC |
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 *); | |
74924dcb | 39 | static BIGNUM *BN_POOL_get(BN_POOL *, int); |
0f113f3e | 40 | static void BN_POOL_release(BN_POOL *, unsigned int); |
5c98b2ca GT |
41 | |
42 | /************/ | |
43 | /* BN_STACK */ | |
44 | /************/ | |
45 | ||
46 | /* A wrapper to manage the "stack frames" */ | |
0f113f3e MC |
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 *); | |
0f113f3e MC |
55 | static int BN_STACK_push(BN_STACK *, unsigned int); |
56 | static unsigned int BN_STACK_pop(BN_STACK *); | |
5c98b2ca GT |
57 | |
58 | /**********/ | |
59 | /* BN_CTX */ | |
60 | /**********/ | |
61 | ||
62 | /* The opaque BN_CTX type */ | |
0f113f3e MC |
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; | |
74924dcb RS |
74 | /* Flags. */ |
75 | int flags; | |
7bc081dd | 76 | /* The library context */ |
b4250010 | 77 | OSSL_LIB_CTX *libctx; |
0f113f3e | 78 | }; |
9b141126 | 79 | |
f844f9eb | 80 | #ifndef FIPS_MODULE |
6e810f2d RL |
81 | /* Debugging functionality */ |
82 | static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx) | |
0f113f3e MC |
83 | { |
84 | unsigned int bnidx = 0, fpidx = 0; | |
85 | BN_POOL_ITEM *item = ctx->pool.head; | |
86 | BN_STACK *stack = &ctx->stack; | |
6e810f2d RL |
87 | |
88 | BIO_printf(channel, "%s\n", text); | |
89 | BIO_printf(channel, " (%16p): ", (void*)ctx); | |
0f113f3e | 90 | while (bnidx < ctx->used) { |
6e810f2d RL |
91 | BIO_printf(channel, "%03x ", |
92 | item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); | |
0f113f3e MC |
93 | if (!(bnidx % BN_CTX_POOL_SIZE)) |
94 | item = item->next; | |
95 | } | |
6e810f2d | 96 | BIO_printf(channel, "\n"); |
0f113f3e | 97 | bnidx = 0; |
6e810f2d | 98 | BIO_printf(channel, " %16s : ", ""); |
0f113f3e MC |
99 | while (fpidx < stack->depth) { |
100 | while (bnidx++ < stack->indexes[fpidx]) | |
6e810f2d RL |
101 | BIO_printf(channel, " "); |
102 | BIO_printf(channel, "^^^ "); | |
0f113f3e MC |
103 | bnidx++; |
104 | fpidx++; | |
105 | } | |
6e810f2d | 106 | BIO_printf(channel, "\n"); |
0f113f3e MC |
107 | } |
108 | ||
636b087e | 109 | # define CTXDBG(str, ctx) \ |
6e810f2d RL |
110 | OSSL_TRACE_BEGIN(BN_CTX) { \ |
111 | ctxdbg(trc_out, str, ctx); \ | |
112 | } OSSL_TRACE_END(BN_CTX) | |
636b087e | 113 | #else |
2ad5bbe3 | 114 | /* We do not want tracing in FIPS module */ |
636b087e | 115 | # define CTXDBG(str, ctx) do {} while(0) |
f844f9eb | 116 | #endif /* FIPS_MODULE */ |
5c98b2ca | 117 | |
b4250010 | 118 | BN_CTX *BN_CTX_new_ex(OSSL_LIB_CTX *ctx) |
0f113f3e | 119 | { |
74924dcb RS |
120 | BN_CTX *ret; |
121 | ||
e077455e | 122 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) |
0f113f3e | 123 | return NULL; |
0f113f3e MC |
124 | /* Initialise the structure */ |
125 | BN_POOL_init(&ret->pool); | |
126 | BN_STACK_init(&ret->stack); | |
7bc081dd | 127 | ret->libctx = ctx; |
74924dcb RS |
128 | return ret; |
129 | } | |
130 | ||
f844f9eb | 131 | #ifndef FIPS_MODULE |
7bc081dd | 132 | BN_CTX *BN_CTX_new(void) |
74924dcb | 133 | { |
7bc081dd MC |
134 | return BN_CTX_new_ex(NULL); |
135 | } | |
2934be91 | 136 | #endif |
7bc081dd | 137 | |
b4250010 | 138 | BN_CTX *BN_CTX_secure_new_ex(OSSL_LIB_CTX *ctx) |
7bc081dd MC |
139 | { |
140 | BN_CTX *ret = BN_CTX_new_ex(ctx); | |
74924dcb | 141 | |
90945fa3 | 142 | if (ret != NULL) |
74924dcb | 143 | ret->flags = BN_FLG_SECURE; |
0f113f3e MC |
144 | return ret; |
145 | } | |
2ce90b9b | 146 | |
f844f9eb | 147 | #ifndef FIPS_MODULE |
7bc081dd MC |
148 | BN_CTX *BN_CTX_secure_new(void) |
149 | { | |
150 | return BN_CTX_secure_new_ex(NULL); | |
151 | } | |
2934be91 | 152 | #endif |
7bc081dd | 153 | |
9b141126 | 154 | void BN_CTX_free(BN_CTX *ctx) |
0f113f3e | 155 | { |
e6e9170d RS |
156 | if (ctx == NULL) |
157 | return; | |
f844f9eb | 158 | #ifndef FIPS_MODULE |
6e810f2d | 159 | OSSL_TRACE_BEGIN(BN_CTX) { |
0f113f3e | 160 | BN_POOL_ITEM *pool = ctx->pool.head; |
6e810f2d RL |
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: "); | |
0f113f3e MC |
165 | while (pool) { |
166 | unsigned loop = 0; | |
167 | while (loop < BN_CTX_POOL_SIZE) | |
6e810f2d | 168 | BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax); |
0f113f3e MC |
169 | pool = pool->next; |
170 | } | |
6e810f2d RL |
171 | BIO_printf(trc_out, "\n"); |
172 | } OSSL_TRACE_END(BN_CTX); | |
aff96597 | 173 | #endif |
0f113f3e MC |
174 | BN_STACK_finish(&ctx->stack); |
175 | BN_POOL_finish(&ctx->pool); | |
176 | OPENSSL_free(ctx); | |
177 | } | |
9b141126 UM |
178 | |
179 | void BN_CTX_start(BN_CTX *ctx) | |
0f113f3e | 180 | { |
6e810f2d | 181 | CTXDBG("ENTER BN_CTX_start()", ctx); |
0f113f3e MC |
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)) { | |
9311d0c4 | 187 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); |
0f113f3e MC |
188 | ctx->err_stack++; |
189 | } | |
6e810f2d | 190 | CTXDBG("LEAVE BN_CTX_start()", ctx); |
0f113f3e | 191 | } |
9b141126 | 192 | |
5c98b2ca | 193 | void BN_CTX_end(BN_CTX *ctx) |
0f113f3e | 194 | { |
ce1415ed SL |
195 | if (ctx == NULL) |
196 | return; | |
6e810f2d | 197 | CTXDBG("ENTER BN_CTX_end()", ctx); |
0f113f3e MC |
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 | } | |
6e810f2d | 209 | CTXDBG("LEAVE BN_CTX_end()", ctx); |
0f113f3e | 210 | } |
7f7b8d68 | 211 | |
9b141126 | 212 | BIGNUM *BN_CTX_get(BN_CTX *ctx) |
0f113f3e MC |
213 | { |
214 | BIGNUM *ret; | |
74924dcb | 215 | |
6e810f2d | 216 | CTXDBG("ENTER BN_CTX_get()", ctx); |
0f113f3e MC |
217 | if (ctx->err_stack || ctx->too_many) |
218 | return NULL; | |
74924dcb | 219 | if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) { |
0f113f3e MC |
220 | /* |
221 | * Setting too_many prevents repeated "get" attempts from cluttering | |
222 | * the error stack. | |
223 | */ | |
224 | ctx->too_many = 1; | |
9311d0c4 | 225 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); |
0f113f3e MC |
226 | return NULL; |
227 | } | |
228 | /* OK, make sure the returned bignum is "zero" */ | |
229 | BN_zero(ret); | |
c8147d37 NT |
230 | /* clear BN_FLG_CONSTTIME if leaked from previous frames */ |
231 | ret->flags &= (~BN_FLG_CONSTTIME); | |
0f113f3e | 232 | ctx->used++; |
6e810f2d | 233 | CTXDBG("LEAVE BN_CTX_get()", ctx); |
0f113f3e MC |
234 | return ret; |
235 | } | |
9b141126 | 236 | |
94553e85 | 237 | OSSL_LIB_CTX *ossl_bn_get_libctx(BN_CTX *ctx) |
636b087e | 238 | { |
ee1d4f3d MC |
239 | if (ctx == NULL) |
240 | return NULL; | |
636b087e MC |
241 | return ctx->libctx; |
242 | } | |
243 | ||
5c98b2ca GT |
244 | /************/ |
245 | /* BN_STACK */ | |
246 | /************/ | |
247 | ||
248 | static void BN_STACK_init(BN_STACK *st) | |
0f113f3e MC |
249 | { |
250 | st->indexes = NULL; | |
251 | st->depth = st->size = 0; | |
252 | } | |
5c98b2ca GT |
253 | |
254 | static void BN_STACK_finish(BN_STACK *st) | |
0f113f3e | 255 | { |
74924dcb RS |
256 | OPENSSL_free(st->indexes); |
257 | st->indexes = NULL; | |
0f113f3e | 258 | } |
37e48b88 | 259 | |
5c98b2ca GT |
260 | |
261 | static int BN_STACK_push(BN_STACK *st, unsigned int idx) | |
0f113f3e | 262 | { |
74924dcb | 263 | if (st->depth == st->size) { |
0f113f3e | 264 | /* Need to expand */ |
74924dcb RS |
265 | unsigned int newsize = |
266 | st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES; | |
cdb10bae | 267 | unsigned int *newitems; |
df443918 | 268 | |
e077455e | 269 | if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) |
0f113f3e MC |
270 | return 0; |
271 | if (st->depth) | |
74924dcb RS |
272 | memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth); |
273 | OPENSSL_free(st->indexes); | |
0f113f3e MC |
274 | st->indexes = newitems; |
275 | st->size = newsize; | |
276 | } | |
277 | st->indexes[(st->depth)++] = idx; | |
278 | return 1; | |
279 | } | |
5c98b2ca GT |
280 | |
281 | static unsigned int BN_STACK_pop(BN_STACK *st) | |
0f113f3e MC |
282 | { |
283 | return st->indexes[--(st->depth)]; | |
284 | } | |
5c98b2ca GT |
285 | |
286 | /***********/ | |
287 | /* BN_POOL */ | |
288 | /***********/ | |
289 | ||
290 | static void BN_POOL_init(BN_POOL *p) | |
0f113f3e MC |
291 | { |
292 | p->head = p->current = p->tail = NULL; | |
293 | p->used = p->size = 0; | |
294 | } | |
5c98b2ca GT |
295 | |
296 | static void BN_POOL_finish(BN_POOL *p) | |
0f113f3e | 297 | { |
74924dcb RS |
298 | unsigned int loop; |
299 | BIGNUM *bn; | |
300 | ||
0f113f3e | 301 | while (p->head) { |
74924dcb | 302 | for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++) |
0f113f3e MC |
303 | if (bn->d) |
304 | BN_clear_free(bn); | |
0f113f3e MC |
305 | p->current = p->head->next; |
306 | OPENSSL_free(p->head); | |
307 | p->head = p->current; | |
308 | } | |
309 | } | |
5c98b2ca | 310 | |
5c98b2ca | 311 | |
74924dcb | 312 | static BIGNUM *BN_POOL_get(BN_POOL *p, int flag) |
0f113f3e | 313 | { |
74924dcb RS |
314 | BIGNUM *bn; |
315 | unsigned int loop; | |
316 | ||
317 | /* Full; allocate a new pool item and link it in. */ | |
0f113f3e | 318 | if (p->used == p->size) { |
cdb10bae | 319 | BN_POOL_ITEM *item; |
df443918 | 320 | |
e077455e | 321 | if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) |
0f113f3e | 322 | return NULL; |
74924dcb | 323 | for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) { |
d59c7c81 | 324 | bn_init(bn); |
74924dcb RS |
325 | if ((flag & BN_FLG_SECURE) != 0) |
326 | BN_set_flags(bn, BN_FLG_SECURE); | |
327 | } | |
0f113f3e MC |
328 | item->prev = p->tail; |
329 | item->next = NULL; | |
74924dcb RS |
330 | |
331 | if (p->head == NULL) | |
0f113f3e MC |
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 | } | |
74924dcb | 343 | |
0f113f3e MC |
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 | } | |
5c98b2ca GT |
350 | |
351 | static void BN_POOL_release(BN_POOL *p, unsigned int num) | |
0f113f3e MC |
352 | { |
353 | unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; | |
74924dcb | 354 | |
0f113f3e MC |
355 | p->used -= num; |
356 | while (num--) { | |
357 | bn_check_top(p->current->vals + offset); | |
74924dcb | 358 | if (offset == 0) { |
0f113f3e MC |
359 | offset = BN_CTX_POOL_SIZE - 1; |
360 | p->current = p->current->prev; | |
361 | } else | |
362 | offset--; | |
363 | } | |
364 | } |