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