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