/src/openssl/crypto/bn/bn_ctx.c
Line | Count | Source (jump to first uncovered line) |
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 | 313M | #define BN_CTX_POOL_SIZE 16 |
16 | | /* The stack frame info is resizing, set a first-time expansion size; */ |
17 | 15.4k | #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 */ |
82 | | static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx) |
83 | 0 | { |
84 | 0 | unsigned int bnidx = 0, fpidx = 0; |
85 | 0 | BN_POOL_ITEM *item = ctx->pool.head; |
86 | 0 | BN_STACK *stack = &ctx->stack; |
87 | 0 |
|
88 | 0 | BIO_printf(channel, "%s\n", text); |
89 | 0 | BIO_printf(channel, " (%16p): ", (void*)ctx); |
90 | 0 | while (bnidx < ctx->used) { |
91 | 0 | BIO_printf(channel, "%03x ", |
92 | 0 | item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); |
93 | 0 | if (!(bnidx % BN_CTX_POOL_SIZE)) |
94 | 0 | item = item->next; |
95 | 0 | } |
96 | 0 | BIO_printf(channel, "\n"); |
97 | 0 | bnidx = 0; |
98 | 0 | BIO_printf(channel, " %16s : ", ""); |
99 | 0 | while (fpidx < stack->depth) { |
100 | 0 | while (bnidx++ < stack->indexes[fpidx]) |
101 | 0 | BIO_printf(channel, " "); |
102 | 0 | BIO_printf(channel, "^^^ "); |
103 | 0 | bnidx++; |
104 | 0 | fpidx++; |
105 | 0 | } |
106 | 0 | BIO_printf(channel, "\n"); |
107 | 0 | } |
108 | | |
109 | | # define CTXDBG(str, ctx) \ |
110 | 619M | OSSL_TRACE_BEGIN(BN_CTX) { \ |
111 | 0 | ctxdbg(trc_out, str, ctx); \ |
112 | 619M | } 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 | | |
118 | | BN_CTX *BN_CTX_new_ex(OSSL_LIB_CTX *ctx) |
119 | 20.7k | { |
120 | 20.7k | BN_CTX *ret; |
121 | | |
122 | 20.7k | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) |
123 | 0 | return NULL; |
124 | | /* Initialise the structure */ |
125 | 20.7k | BN_POOL_init(&ret->pool); |
126 | 20.7k | BN_STACK_init(&ret->stack); |
127 | 20.7k | ret->libctx = ctx; |
128 | 20.7k | return ret; |
129 | 20.7k | } |
130 | | |
131 | | #ifndef FIPS_MODULE |
132 | | BN_CTX *BN_CTX_new(void) |
133 | 8.81k | { |
134 | 8.81k | return BN_CTX_new_ex(NULL); |
135 | 8.81k | } |
136 | | #endif |
137 | | |
138 | | BN_CTX *BN_CTX_secure_new_ex(OSSL_LIB_CTX *ctx) |
139 | 1.30k | { |
140 | 1.30k | BN_CTX *ret = BN_CTX_new_ex(ctx); |
141 | | |
142 | 1.30k | if (ret != NULL) |
143 | 1.30k | ret->flags = BN_FLG_SECURE; |
144 | 1.30k | return ret; |
145 | 1.30k | } |
146 | | |
147 | | #ifndef FIPS_MODULE |
148 | | BN_CTX *BN_CTX_secure_new(void) |
149 | 1.07k | { |
150 | 1.07k | return BN_CTX_secure_new_ex(NULL); |
151 | 1.07k | } |
152 | | #endif |
153 | | |
154 | | void BN_CTX_free(BN_CTX *ctx) |
155 | 2.29M | { |
156 | 2.29M | if (ctx == NULL) |
157 | 2.27M | return; |
158 | 20.7k | #ifndef FIPS_MODULE |
159 | 20.7k | OSSL_TRACE_BEGIN(BN_CTX) { |
160 | 0 | BN_POOL_ITEM *pool = ctx->pool.head; |
161 | 0 | BIO_printf(trc_out, |
162 | 0 | "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n", |
163 | 0 | ctx->stack.size, ctx->pool.size); |
164 | 0 | BIO_printf(trc_out, " dmaxs: "); |
165 | 0 | while (pool) { |
166 | 0 | unsigned loop = 0; |
167 | 0 | while (loop < BN_CTX_POOL_SIZE) |
168 | 0 | BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax); |
169 | 0 | pool = pool->next; |
170 | 0 | } |
171 | 0 | BIO_printf(trc_out, "\n"); |
172 | 20.7k | } OSSL_TRACE_END(BN_CTX); |
173 | 20.7k | #endif |
174 | 20.7k | BN_STACK_finish(&ctx->stack); |
175 | 20.7k | BN_POOL_finish(&ctx->pool); |
176 | 20.7k | OPENSSL_free(ctx); |
177 | 20.7k | } |
178 | | |
179 | | void BN_CTX_start(BN_CTX *ctx) |
180 | 101M | { |
181 | 101M | CTXDBG("ENTER BN_CTX_start()", ctx); |
182 | | /* If we're already overflowing ... */ |
183 | 101M | if (ctx->err_stack || ctx->too_many) |
184 | 0 | ctx->err_stack++; |
185 | | /* (Try to) get a new frame pointer */ |
186 | 101M | else if (!BN_STACK_push(&ctx->stack, ctx->used)) { |
187 | 0 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); |
188 | 0 | ctx->err_stack++; |
189 | 0 | } |
190 | 101M | CTXDBG("LEAVE BN_CTX_start()", ctx); |
191 | 101M | } |
192 | | |
193 | | void BN_CTX_end(BN_CTX *ctx) |
194 | 101M | { |
195 | 101M | if (ctx == NULL) |
196 | 17 | return; |
197 | 101M | CTXDBG("ENTER BN_CTX_end()", ctx); |
198 | 101M | if (ctx->err_stack) |
199 | 0 | ctx->err_stack--; |
200 | 101M | else { |
201 | 101M | unsigned int fp = BN_STACK_pop(&ctx->stack); |
202 | | /* Does this stack frame have anything to release? */ |
203 | 101M | if (fp < ctx->used) |
204 | 98.4M | BN_POOL_release(&ctx->pool, ctx->used - fp); |
205 | 101M | ctx->used = fp; |
206 | | /* Unjam "too_many" in case "get" had failed */ |
207 | 101M | ctx->too_many = 0; |
208 | 101M | } |
209 | 101M | CTXDBG("LEAVE BN_CTX_end()", ctx); |
210 | 101M | } |
211 | | |
212 | | BIGNUM *BN_CTX_get(BN_CTX *ctx) |
213 | 107M | { |
214 | 107M | BIGNUM *ret; |
215 | | |
216 | 107M | CTXDBG("ENTER BN_CTX_get()", ctx); |
217 | 107M | if (ctx->err_stack || ctx->too_many) |
218 | 0 | return NULL; |
219 | 107M | 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 | 0 | ctx->too_many = 1; |
225 | 0 | ERR_raise(ERR_LIB_BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); |
226 | 0 | return NULL; |
227 | 0 | } |
228 | | /* OK, make sure the returned bignum is "zero" */ |
229 | 107M | BN_zero(ret); |
230 | | /* clear BN_FLG_CONSTTIME if leaked from previous frames */ |
231 | 107M | ret->flags &= (~BN_FLG_CONSTTIME); |
232 | 107M | ctx->used++; |
233 | 107M | CTXDBG("LEAVE BN_CTX_get()", ctx); |
234 | 107M | return ret; |
235 | 107M | } |
236 | | |
237 | | OSSL_LIB_CTX *ossl_bn_get_libctx(BN_CTX *ctx) |
238 | 105k | { |
239 | 105k | if (ctx == NULL) |
240 | 128 | return NULL; |
241 | 104k | return ctx->libctx; |
242 | 105k | } |
243 | | |
244 | | /************/ |
245 | | /* BN_STACK */ |
246 | | /************/ |
247 | | |
248 | | static void BN_STACK_init(BN_STACK *st) |
249 | 20.7k | { |
250 | 20.7k | st->indexes = NULL; |
251 | 20.7k | st->depth = st->size = 0; |
252 | 20.7k | } |
253 | | |
254 | | static void BN_STACK_finish(BN_STACK *st) |
255 | 20.7k | { |
256 | 20.7k | OPENSSL_free(st->indexes); |
257 | 20.7k | st->indexes = NULL; |
258 | 20.7k | } |
259 | | |
260 | | |
261 | | static int BN_STACK_push(BN_STACK *st, unsigned int idx) |
262 | 101M | { |
263 | 101M | if (st->depth == st->size) { |
264 | | /* Need to expand */ |
265 | 15.4k | unsigned int newsize = |
266 | 15.4k | st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES; |
267 | 15.4k | unsigned int *newitems; |
268 | | |
269 | 15.4k | if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) |
270 | 0 | return 0; |
271 | 15.4k | if (st->depth) |
272 | 0 | memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth); |
273 | 15.4k | OPENSSL_free(st->indexes); |
274 | 15.4k | st->indexes = newitems; |
275 | 15.4k | st->size = newsize; |
276 | 15.4k | } |
277 | 101M | st->indexes[(st->depth)++] = idx; |
278 | 101M | return 1; |
279 | 101M | } |
280 | | |
281 | | static unsigned int BN_STACK_pop(BN_STACK *st) |
282 | 101M | { |
283 | 101M | return st->indexes[--(st->depth)]; |
284 | 101M | } |
285 | | |
286 | | /***********/ |
287 | | /* BN_POOL */ |
288 | | /***********/ |
289 | | |
290 | | static void BN_POOL_init(BN_POOL *p) |
291 | 20.7k | { |
292 | 20.7k | p->head = p->current = p->tail = NULL; |
293 | 20.7k | p->used = p->size = 0; |
294 | 20.7k | } |
295 | | |
296 | | static void BN_POOL_finish(BN_POOL *p) |
297 | 20.7k | { |
298 | 20.7k | unsigned int loop; |
299 | 20.7k | BIGNUM *bn; |
300 | | |
301 | 39.0k | while (p->head) { |
302 | 311k | for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++) |
303 | 293k | if (bn->d) |
304 | 149k | BN_clear_free(bn); |
305 | 18.3k | p->current = p->head->next; |
306 | 18.3k | OPENSSL_free(p->head); |
307 | 18.3k | p->head = p->current; |
308 | 18.3k | } |
309 | 20.7k | } |
310 | | |
311 | | |
312 | | static BIGNUM *BN_POOL_get(BN_POOL *p, int flag) |
313 | 107M | { |
314 | 107M | BIGNUM *bn; |
315 | 107M | unsigned int loop; |
316 | | |
317 | | /* Full; allocate a new pool item and link it in. */ |
318 | 107M | if (p->used == p->size) { |
319 | 18.3k | BN_POOL_ITEM *item; |
320 | | |
321 | 18.3k | if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) |
322 | 0 | return NULL; |
323 | 311k | for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) { |
324 | 293k | bn_init(bn); |
325 | 293k | if ((flag & BN_FLG_SECURE) != 0) |
326 | 31.4k | BN_set_flags(bn, BN_FLG_SECURE); |
327 | 293k | } |
328 | 18.3k | item->prev = p->tail; |
329 | 18.3k | item->next = NULL; |
330 | | |
331 | 18.3k | if (p->head == NULL) |
332 | 15.3k | p->head = p->current = p->tail = item; |
333 | 3.00k | else { |
334 | 3.00k | p->tail->next = item; |
335 | 3.00k | p->tail = item; |
336 | 3.00k | p->current = item; |
337 | 3.00k | } |
338 | 18.3k | p->size += BN_CTX_POOL_SIZE; |
339 | 18.3k | p->used++; |
340 | | /* Return the first bignum from the new pool */ |
341 | 18.3k | return item->vals; |
342 | 18.3k | } |
343 | | |
344 | 107M | if (!p->used) |
345 | 973k | p->current = p->head; |
346 | 106M | else if ((p->used % BN_CTX_POOL_SIZE) == 0) |
347 | 371k | p->current = p->current->next; |
348 | 107M | return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); |
349 | 107M | } |
350 | | |
351 | | static void BN_POOL_release(BN_POOL *p, unsigned int num) |
352 | 98.4M | { |
353 | 98.4M | unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; |
354 | | |
355 | 98.4M | p->used -= num; |
356 | 205M | while (num--) { |
357 | 107M | bn_check_top(p->current->vals + offset); |
358 | 107M | if (offset == 0) { |
359 | 1.36M | offset = BN_CTX_POOL_SIZE - 1; |
360 | 1.36M | p->current = p->current->prev; |
361 | 1.36M | } else |
362 | 105M | offset--; |
363 | 107M | } |
364 | 98.4M | } |