1/* crypto/bn/bn_ctx.c */
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 <assert.h>
65
66#include "../bn/bn_lcl.h"
67
68/*-
69 * TODO list
70 *
71 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
72 * check they can be safely removed.
73 * - Check +1 and other ugliness in BN_from_montgomery()
74 *
75 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
76 * appropriate 'block' size that will be honoured by bn_expand_internal() to
77 * prevent piddly little reallocations. OTOH, profiling bignum expansions in
78 * BN_CTX doesn't show this to be a big issue.
79 */
80
81/* How many bignums are in each "pool item"; */
82#define BN_CTX_POOL_SIZE 16
83/* The stack frame info is resizing, set a first-time expansion size; */
84#define BN_CTX_START_FRAMES 32
85
86/***********/
87/* BN_POOL */
88/***********/
89
90/* A bundle of bignums that can be linked with other bundles */
91typedef struct bignum_pool_item {
92 /* The bignum values */
93 BIGNUM vals[BN_CTX_POOL_SIZE];
94 /* Linked-list admin */
95 struct bignum_pool_item *prev, *next;
96} BN_POOL_ITEM;
97/* A linked-list of bignums grouped in bundles */
98typedef struct bignum_pool {
99 /* Linked-list admin */
100 BN_POOL_ITEM *head, *current, *tail;
101 /* Stack depth and allocation size */
102 unsigned used, size;
103} BN_POOL;
104static void BN_POOL_init(BN_POOL *);
105static void BN_POOL_finish(BN_POOL *);
106#ifndef OPENSSL_NO_DEPRECATED
107static void BN_POOL_reset(BN_POOL *);
108#endif
109static BIGNUM *BN_POOL_get(BN_POOL *);
110static void BN_POOL_release(BN_POOL *, unsigned int);
111
112/************/
113/* BN_STACK */
114/************/
115
116/* A wrapper to manage the "stack frames" */
117typedef struct bignum_ctx_stack {
118 /* Array of indexes into the bignum stack */
119 unsigned int *indexes;
120 /* Number of stack frames, and the size of the allocated array */
121 unsigned int depth, size;
122} BN_STACK;
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 {
137 /* The bignum bundles */
138 BN_POOL pool;
139 /* The "stack frames", if you will */
140 BN_STACK stack;
141 /* The number of bignums currently assigned */
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
149/* Enable this to find BN_CTX bugs */
150#ifdef BN_CTX_DEBUG
151static const char *ctxdbg_cur = NULL;
152static void ctxdbg(BN_CTX *ctx)
153{
154 unsigned int bnidx = 0, fpidx = 0;
155 BN_POOL_ITEM *item = ctx->pool.head;
156 BN_STACK *stack = &ctx->stack;
157 fprintf(stderr, "(%16p): ", ctx);
158 while (bnidx < ctx->used) {
159 fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
160 if (!(bnidx % BN_CTX_POOL_SIZE))
161 item = item->next;
162 }
163 fprintf(stderr, "\n");
164 bnidx = 0;
165 fprintf(stderr, " : ");
166 while (fpidx < stack->depth) {
167 while (bnidx++ < stack->indexes[fpidx])
168 fprintf(stderr, " ");
169 fprintf(stderr, "^^^ ");
170 bnidx++;
171 fpidx++;
172 }
173 fprintf(stderr, "\n");
174}
175
176# define CTXDBG_ENTRY(str, ctx) do { \
177 ctxdbg_cur = (str); \
178 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
179 ctxdbg(ctx); \
180 } while(0)
181# define CTXDBG_EXIT(ctx) do { \
182 fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
183 ctxdbg(ctx); \
184 } while(0)
185# define CTXDBG_RET(ctx,ret)
186#else
187# define CTXDBG_ENTRY(str, ctx)
188# define CTXDBG_EXIT(ctx)
189# define CTXDBG_RET(ctx,ret)
190#endif
191
192/*
193 * This function is an evil legacy and should not be used. This
194 * implementation is WYSIWYG, though I've done my best.
195 */
196#ifndef OPENSSL_NO_DEPRECATED
197void BN_CTX_init(BN_CTX *ctx)
198{
199 /*
200 * Assume the caller obtained the context via BN_CTX_new() and so is
201 * trying to reset it for use. Nothing else makes sense, least of all
202 * binary compatibility from a time when they could declare a static
203 * variable.
204 */
205 BN_POOL_reset(&ctx->pool);
206 BN_STACK_reset(&ctx->stack);
207 ctx->used = 0;
208 ctx->err_stack = 0;
209 ctx->too_many = 0;
210}
211#endif
212
213BN_CTX *BN_CTX_new(void)
214{
215 BN_CTX *ret = (BN_CTX *)OPENSSL_malloc(sizeof(BN_CTX));
216 if (!ret) {
217 BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
218 return NULL;
219 }
220 /* Initialise the structure */
221 BN_POOL_init(&ret->pool);
222 BN_STACK_init(&ret->stack);
223 ret->used = 0;
224 ret->err_stack = 0;
225 ret->too_many = 0;
226 return ret;
227}
228
229void BN_CTX_free(BN_CTX *ctx)
230{
231 if (ctx == NULL)
232 return;
233#ifdef BN_CTX_DEBUG
234 {
235 BN_POOL_ITEM *pool = ctx->pool.head;
236 fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
237 ctx->stack.size, ctx->pool.size);
238 fprintf(stderr, "dmaxs: ");
239 while (pool) {
240 unsigned loop = 0;
241 while (loop < BN_CTX_POOL_SIZE)
242 fprintf(stderr, "%02x ", pool->vals[loop++].dmax);
243 pool = pool->next;
244 }
245 fprintf(stderr, "\n");
246 }
247#endif
248 BN_STACK_finish(&ctx->stack);
249 BN_POOL_finish(&ctx->pool);
250 OPENSSL_free(ctx);
251}
252
253void BN_CTX_start(BN_CTX *ctx)
254{
255 CTXDBG_ENTRY("BN_CTX_start", ctx);
256 /* If we're already overflowing ... */
257 if (ctx->err_stack || ctx->too_many)
258 ctx->err_stack++;
259 /* (Try to) get a new frame pointer */
260 else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
261 BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
262 ctx->err_stack++;
263 }
264 CTXDBG_EXIT(ctx);
265}
266
267void BN_CTX_end(BN_CTX *ctx)
268{
269 CTXDBG_ENTRY("BN_CTX_end", ctx);
270 if (ctx->err_stack)
271 ctx->err_stack--;
272 else {
273 unsigned int fp = BN_STACK_pop(&ctx->stack);
274 /* Does this stack frame have anything to release? */
275 if (fp < ctx->used)
276 BN_POOL_release(&ctx->pool, ctx->used - fp);
277 ctx->used = fp;
278 /* Unjam "too_many" in case "get" had failed */
279 ctx->too_many = 0;
280 }
281 CTXDBG_EXIT(ctx);
282}
283
284BIGNUM *BN_CTX_get(BN_CTX *ctx)
285{
286 BIGNUM *ret;
287 CTXDBG_ENTRY("BN_CTX_get", ctx);
288 if (ctx->err_stack || ctx->too_many)
289 return NULL;
290 if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
291 /*
292 * Setting too_many prevents repeated "get" attempts from cluttering
293 * the error stack.
294 */
295 ctx->too_many = 1;
296 BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
297 return NULL;
298 }
299 /* OK, make sure the returned bignum is "zero" */
300 BN_zero(ret);
301 ctx->used++;
302 CTXDBG_RET(ctx, ret);
303 return ret;
304}
305
306/************/
307/* BN_STACK */
308/************/
309
310static void BN_STACK_init(BN_STACK *st)
311{
312 st->indexes = NULL;
313 st->depth = st->size = 0;
314}
315
316static void BN_STACK_finish(BN_STACK *st)
317{
318 if (st->size)
319 OPENSSL_free(st->indexes);
320}
321
322#ifndef OPENSSL_NO_DEPRECATED
323static void BN_STACK_reset(BN_STACK *st)
324{
325 st->depth = 0;
326}
327#endif
328
329static int BN_STACK_push(BN_STACK *st, unsigned int idx)
330{
331 if (st->depth == st->size)
332 /* Need to expand */
333 {
334 unsigned int newsize = (st->size ?
335 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
336 unsigned int *newitems = (unsigned int *)OPENSSL_malloc(newsize *
337 sizeof(unsigned int));
338 if (!newitems)
339 return 0;
340 if (st->depth)
341 memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int));
342 if (st->size)
343 OPENSSL_free(st->indexes);
344 st->indexes = newitems;
345 st->size = newsize;
346 }
347 st->indexes[(st->depth)++] = idx;
348 return 1;
349}
350
351static unsigned int BN_STACK_pop(BN_STACK *st)
352{
353 return st->indexes[--(st->depth)];
354}
355
356/***********/
357/* BN_POOL */
358/***********/
359
360static void BN_POOL_init(BN_POOL *p)
361{
362 p->head = p->current = p->tail = NULL;
363 p->used = p->size = 0;
364}
365
366static void BN_POOL_finish(BN_POOL *p)
367{
368 while (p->head) {
369 unsigned int loop = 0;
370 BIGNUM *bn = p->head->vals;
371 while (loop++ < BN_CTX_POOL_SIZE) {
372 if (bn->d)
373 BN_clear_free(bn);
374 bn++;
375 }
376 p->current = p->head->next;
377 OPENSSL_free(p->head);
378 p->head = p->current;
379 }
380}
381
382#ifndef OPENSSL_NO_DEPRECATED
383static void BN_POOL_reset(BN_POOL *p)
384{
385 BN_POOL_ITEM *item = p->head;
386 while (item) {
387 unsigned int loop = 0;
388 BIGNUM *bn = item->vals;
389 while (loop++ < BN_CTX_POOL_SIZE) {
390 if (bn->d)
391 BN_clear(bn);
392 bn++;
393 }
394 item = item->next;
395 }
396 p->current = p->head;
397 p->used = 0;
398}
399#endif
400
401static BIGNUM *BN_POOL_get(BN_POOL *p)
402{
403 if (p->used == p->size) {
404 BIGNUM *bn;
405 unsigned int loop = 0;
406 BN_POOL_ITEM *item = (BN_POOL_ITEM *)OPENSSL_malloc(sizeof(BN_POOL_ITEM));
407 if (!item)
408 return NULL;
409 /* Initialise the structure */
410 bn = item->vals;
411 while (loop++ < BN_CTX_POOL_SIZE)
412 BN_init(bn++);
413 item->prev = p->tail;
414 item->next = NULL;
415 /* Link it in */
416 if (!p->head)
417 p->head = p->current = p->tail = item;
418 else {
419 p->tail->next = item;
420 p->tail = item;
421 p->current = item;
422 }
423 p->size += BN_CTX_POOL_SIZE;
424 p->used++;
425 /* Return the first bignum from the new pool */
426 return item->vals;
427 }
428 if (!p->used)
429 p->current = p->head;
430 else if ((p->used % BN_CTX_POOL_SIZE) == 0)
431 p->current = p->current->next;
432 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
433}
434
435static void BN_POOL_release(BN_POOL *p, unsigned int num)
436{
437 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
438 p->used -= num;
439 while (num--) {
440 bn_check_top(p->current->vals + offset);
441 if (!offset) {
442 offset = BN_CTX_POOL_SIZE - 1;
443 p->current = p->current->prev;
444 } else
445 offset--;
446 }
447}
448