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