bn_ctx.c revision 344604 
1/* crypto/bn/bn_ctx.c */
2/* Written by Ulf Moeller for the OpenSSL project. */
3/* ====================================================================
4 * Copyright (c) 1998-2019 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 */
92typedef 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 */
99typedef 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;
105static void BN_POOL_init(BN_POOL *);
106static void BN_POOL_finish(BN_POOL *);
107#ifndef OPENSSL_NO_DEPRECATED
108static void BN_POOL_reset(BN_POOL *);
109#endif
110static BIGNUM *BN_POOL_get(BN_POOL *);
111static void BN_POOL_release(BN_POOL *, unsigned int);
112
113/************/
114/* BN_STACK */
115/************/
116
117/* A wrapper to manage the "stack frames" */
118typedef 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;
124static void BN_STACK_init(BN_STACK *);
125static void BN_STACK_finish(BN_STACK *);
126#ifndef OPENSSL_NO_DEPRECATED
127static void BN_STACK_reset(BN_STACK *);
128#endif
129static int BN_STACK_push(BN_STACK *, unsigned int);
130static unsigned int BN_STACK_pop(BN_STACK *);
131
132/**********/
133/* BN_CTX */
134/**********/
135
136/* The opaque BN_CTX type */
137struct 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
152static const char *ctxdbg_cur = NULL;
153static 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
198void 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    BN_POOL_reset(&ctx->pool);
207    BN_STACK_reset(&ctx->stack);
208    ctx->used = 0;
209    ctx->err_stack = 0;
210    ctx->too_many = 0;
211}
212#endif
213
214BN_CTX *BN_CTX_new(void)
215{
216    BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX));
217    if (!ret) {
218        BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
219        return NULL;
220    }
221    /* Initialise the structure */
222    BN_POOL_init(&ret->pool);
223    BN_STACK_init(&ret->stack);
224    ret->used = 0;
225    ret->err_stack = 0;
226    ret->too_many = 0;
227    return ret;
228}
229
230void BN_CTX_free(BN_CTX *ctx)
231{
232    if (ctx == NULL)
233        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    BN_STACK_finish(&ctx->stack);
250    BN_POOL_finish(&ctx->pool);
251    OPENSSL_free(ctx);
252}
253
254void BN_CTX_start(BN_CTX *ctx)
255{
256    CTXDBG_ENTRY("BN_CTX_start", ctx);
257    /* If we're already overflowing ... */
258    if (ctx->err_stack || ctx->too_many)
259        ctx->err_stack++;
260    /* (Try to) get a new frame pointer */
261    else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
262        BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
263        ctx->err_stack++;
264    }
265    CTXDBG_EXIT(ctx);
266}
267
268void BN_CTX_end(BN_CTX *ctx)
269{
270    CTXDBG_ENTRY("BN_CTX_end", ctx);
271    if (ctx->err_stack)
272        ctx->err_stack--;
273    else {
274        unsigned int fp = BN_STACK_pop(&ctx->stack);
275        /* Does this stack frame have anything to release? */
276        if (fp < ctx->used)
277            BN_POOL_release(&ctx->pool, ctx->used - fp);
278        ctx->used = fp;
279        /* Unjam "too_many" in case "get" had failed */
280        ctx->too_many = 0;
281    }
282    CTXDBG_EXIT(ctx);
283}
284
285BIGNUM *BN_CTX_get(BN_CTX *ctx)
286{
287    BIGNUM *ret;
288    CTXDBG_ENTRY("BN_CTX_get", ctx);
289    if (ctx->err_stack || ctx->too_many)
290        return NULL;
291    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        ctx->too_many = 1;
297        BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
298        return NULL;
299    }
300    /* OK, make sure the returned bignum is "zero" */
301    BN_zero(ret);
302    /* clear BN_FLG_CONSTTIME if leaked from previous frames */
303    ret->flags &= (~BN_FLG_CONSTTIME);
304    ctx->used++;
305    CTXDBG_RET(ctx, ret);
306    return ret;
307}
308
309/************/
310/* BN_STACK */
311/************/
312
313static void BN_STACK_init(BN_STACK *st)
314{
315    st->indexes = NULL;
316    st->depth = st->size = 0;
317}
318
319static void BN_STACK_finish(BN_STACK *st)
320{
321    if (st->size)
322        OPENSSL_free(st->indexes);
323}
324
325#ifndef OPENSSL_NO_DEPRECATED
326static void BN_STACK_reset(BN_STACK *st)
327{
328    st->depth = 0;
329}
330#endif
331
332static int BN_STACK_push(BN_STACK *st, unsigned int idx)
333{
334    if (st->depth == st->size)
335        /* Need to expand */
336    {
337        unsigned int newsize = (st->size ?
338                                (st->size * 3 / 2) : BN_CTX_START_FRAMES);
339        unsigned int *newitems = OPENSSL_malloc(newsize *
340                                                sizeof(unsigned int));
341        if (!newitems)
342            return 0;
343        if (st->depth)
344            memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int));
345        if (st->size)
346            OPENSSL_free(st->indexes);
347        st->indexes = newitems;
348        st->size = newsize;
349    }
350    st->indexes[(st->depth)++] = idx;
351    return 1;
352}
353
354static unsigned int BN_STACK_pop(BN_STACK *st)
355{
356    return st->indexes[--(st->depth)];
357}
358
359/***********/
360/* BN_POOL */
361/***********/
362
363static void BN_POOL_init(BN_POOL *p)
364{
365    p->head = p->current = p->tail = NULL;
366    p->used = p->size = 0;
367}
368
369static void BN_POOL_finish(BN_POOL *p)
370{
371    while (p->head) {
372        unsigned int loop = 0;
373        BIGNUM *bn = p->head->vals;
374        while (loop++ < BN_CTX_POOL_SIZE) {
375            if (bn->d)
376                BN_clear_free(bn);
377            bn++;
378        }
379        p->current = p->head->next;
380        OPENSSL_free(p->head);
381        p->head = p->current;
382    }
383}
384
385#ifndef OPENSSL_NO_DEPRECATED
386static void BN_POOL_reset(BN_POOL *p)
387{
388    BN_POOL_ITEM *item = p->head;
389    while (item) {
390        unsigned int loop = 0;
391        BIGNUM *bn = item->vals;
392        while (loop++ < BN_CTX_POOL_SIZE) {
393            if (bn->d)
394                BN_clear(bn);
395            bn++;
396        }
397        item = item->next;
398    }
399    p->current = p->head;
400    p->used = 0;
401}
402#endif
403
404static BIGNUM *BN_POOL_get(BN_POOL *p)
405{
406    if (p->used == p->size) {
407        BIGNUM *bn;
408        unsigned int loop = 0;
409        BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
410        if (!item)
411            return NULL;
412        /* Initialise the structure */
413        bn = item->vals;
414        while (loop++ < BN_CTX_POOL_SIZE)
415            BN_init(bn++);
416        item->prev = p->tail;
417        item->next = NULL;
418        /* Link it in */
419        if (!p->head)
420            p->head = p->current = p->tail = item;
421        else {
422            p->tail->next = item;
423            p->tail = item;
424            p->current = item;
425        }
426        p->size += BN_CTX_POOL_SIZE;
427        p->used++;
428        /* Return the first bignum from the new pool */
429        return item->vals;
430    }
431    if (!p->used)
432        p->current = p->head;
433    else if ((p->used % BN_CTX_POOL_SIZE) == 0)
434        p->current = p->current->next;
435    return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
436}
437
438static void BN_POOL_release(BN_POOL *p, unsigned int num)
439{
440    unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
441    p->used -= num;
442    while (num--) {
443        bn_check_top(p->current->vals + offset);
444        if (!offset) {
445            offset = BN_CTX_POOL_SIZE - 1;
446            p->current = p->current->prev;
447        } else
448            offset--;
449    }
450}
451