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