bn_ctx.c 11.7 KB
Newer Older
1 2 3
/* crypto/bn/bn_ctx.c */
/* Written by Ulf Moeller for the OpenSSL project. */
/* ====================================================================
4
 * Copyright (c) 1998-2004 The OpenSSL Project.  All rights reserved.
5 6 7 8 9 10
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
11
 *    notice, this list of conditions and the following disclaimer.
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. All advertising materials mentioning features or use of this
 *    software must display the following acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
 *
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 *    endorse or promote products derived from this software without
 *    prior written permission. For written permission, please contact
 *    openssl-core@openssl.org.
 *
 * 5. Products derived from this software may not be called "OpenSSL"
 *    nor may "OpenSSL" appear in their names without prior written
 *    permission of the OpenSSL Project.
 *
 * 6. Redistributions of any form whatsoever must retain the following
 *    acknowledgment:
 *    "This product includes software developed by the OpenSSL Project
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
 *
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 * ====================================================================
 *
 * This product includes cryptographic software written by Eric Young
 * (eay@cryptsoft.com).  This product includes software written by Tim
 * Hudson (tjh@cryptsoft.com).
 *
 */

57
#if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG)
58 59 60
# ifndef NDEBUG
#  define NDEBUG
# endif
61
#endif
62

63
#include <assert.h>
B
Bodo Möller 已提交
64

65
#include "internal/cryptlib.h"
B
Bodo Möller 已提交
66
#include "bn_lcl.h"
67

68 69
/*-
 * TODO list
70 71 72 73 74 75 76 77 78 79 80 81
 *
 * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
 * check they can be safely removed.
 *  - Check +1 and other ugliness in BN_from_montgomery()
 *
 * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
 * appropriate 'block' size that will be honoured by bn_expand_internal() to
 * prevent piddly little reallocations. OTOH, profiling bignum expansions in
 * BN_CTX doesn't show this to be a big issue.
 */

/* 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 88 89 90

/***********/
/* BN_POOL */
/***********/

/* A bundle of bignums that can be linked with other bundles */
91 92 93 94 95 96
typedef struct bignum_pool_item {
    /* The bignum values */
    BIGNUM vals[BN_CTX_POOL_SIZE];
    /* Linked-list admin */
    struct bignum_pool_item *prev, *next;
} BN_POOL_ITEM;
97
/* A linked-list of bignums grouped in bundles */
98 99 100 101 102 103 104 105
typedef struct bignum_pool {
    /* Linked-list admin */
    BN_POOL_ITEM *head, *current, *tail;
    /* Stack depth and allocation size */
    unsigned used, size;
} BN_POOL;
static void BN_POOL_init(BN_POOL *);
static void BN_POOL_finish(BN_POOL *);
R
Rich Salz 已提交
106
static BIGNUM *BN_POOL_get(BN_POOL *, int);
107
static void BN_POOL_release(BN_POOL *, unsigned int);
108 109 110 111 112 113

/************/
/* BN_STACK */
/************/

/* A wrapper to manage the "stack frames" */
114 115 116 117 118 119 120 121 122 123
typedef struct bignum_ctx_stack {
    /* Array of indexes into the bignum stack */
    unsigned int *indexes;
    /* Number of stack frames, and the size of the allocated array */
    unsigned int depth, size;
} BN_STACK;
static void BN_STACK_init(BN_STACK *);
static void BN_STACK_finish(BN_STACK *);
static int BN_STACK_push(BN_STACK *, unsigned int);
static unsigned int BN_STACK_pop(BN_STACK *);
124 125 126 127 128 129

/**********/
/* BN_CTX */
/**********/

/* The opaque BN_CTX type */
130 131 132 133 134 135 136 137 138 139 140
struct bignum_ctx {
    /* The bignum bundles */
    BN_POOL pool;
    /* The "stack frames", if you will */
    BN_STACK stack;
    /* The number of bignums currently assigned */
    unsigned int used;
    /* Depth of stack overflow */
    int err_stack;
    /* Block "gets" until an "end" (compatibility behaviour) */
    int too_many;
R
Rich Salz 已提交
141 142
    /* Flags. */
    int flags;
143
};
144

145 146 147 148
/* Enable this to find BN_CTX bugs */
#ifdef BN_CTX_DEBUG
static const char *ctxdbg_cur = NULL;
static void ctxdbg(BN_CTX *ctx)
149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
{
    unsigned int bnidx = 0, fpidx = 0;
    BN_POOL_ITEM *item = ctx->pool.head;
    BN_STACK *stack = &ctx->stack;
    fprintf(stderr, "(%16p): ", ctx);
    while (bnidx < ctx->used) {
        fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
        if (!(bnidx % BN_CTX_POOL_SIZE))
            item = item->next;
    }
    fprintf(stderr, "\n");
    bnidx = 0;
    fprintf(stderr, "          : ");
    while (fpidx < stack->depth) {
        while (bnidx++ < stack->indexes[fpidx])
            fprintf(stderr, "    ");
        fprintf(stderr, "^^^ ");
        bnidx++;
        fpidx++;
    }
    fprintf(stderr, "\n");
}

# define CTXDBG_ENTRY(str, ctx)  do { \
                                ctxdbg_cur = (str); \
                                fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
                                ctxdbg(ctx); \
                                } while(0)
# define CTXDBG_EXIT(ctx)        do { \
                                fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
                                ctxdbg(ctx); \
                                } while(0)
# define CTXDBG_RET(ctx,ret)
182
#else
183 184 185
# define CTXDBG_ENTRY(str, ctx)
# define CTXDBG_EXIT(ctx)
# define CTXDBG_RET(ctx,ret)
186
#endif
187

188

189
BN_CTX *BN_CTX_new(void)
190
{
R
Rich Salz 已提交
191 192
    BN_CTX *ret;

R
Rich Salz 已提交
193
    if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
194 195 196 197 198 199
        BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
        return NULL;
    }
    /* Initialise the structure */
    BN_POOL_init(&ret->pool);
    BN_STACK_init(&ret->stack);
R
Rich Salz 已提交
200 201 202 203 204 205 206
    return ret;
}

BN_CTX *BN_CTX_secure_new(void)
{
    BN_CTX *ret = BN_CTX_new();

207
    if (ret != NULL)
R
Rich Salz 已提交
208
        ret->flags = BN_FLG_SECURE;
209 210
    return ret;
}
211

212
void BN_CTX_free(BN_CTX *ctx)
213 214 215
{
    if (ctx == NULL)
        return;
216
#ifdef BN_CTX_DEBUG
217 218 219 220 221 222 223 224 225 226 227 228 229
    {
        BN_POOL_ITEM *pool = ctx->pool.head;
        fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
                ctx->stack.size, ctx->pool.size);
        fprintf(stderr, "dmaxs: ");
        while (pool) {
            unsigned loop = 0;
            while (loop < BN_CTX_POOL_SIZE)
                fprintf(stderr, "%02x ", pool->vals[loop++].dmax);
            pool = pool->next;
        }
        fprintf(stderr, "\n");
    }
230
#endif
231 232 233 234
    BN_STACK_finish(&ctx->stack);
    BN_POOL_finish(&ctx->pool);
    OPENSSL_free(ctx);
}
235 236

void BN_CTX_start(BN_CTX *ctx)
237 238 239 240 241 242 243 244 245 246 247 248
{
    CTXDBG_ENTRY("BN_CTX_start", ctx);
    /* If we're already overflowing ... */
    if (ctx->err_stack || ctx->too_many)
        ctx->err_stack++;
    /* (Try to) get a new frame pointer */
    else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
        BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
        ctx->err_stack++;
    }
    CTXDBG_EXIT(ctx);
}
249

250
void BN_CTX_end(BN_CTX *ctx)
251 252 253 254 255 256 257 258 259 260 261 262 263 264 265
{
    CTXDBG_ENTRY("BN_CTX_end", ctx);
    if (ctx->err_stack)
        ctx->err_stack--;
    else {
        unsigned int fp = BN_STACK_pop(&ctx->stack);
        /* Does this stack frame have anything to release? */
        if (fp < ctx->used)
            BN_POOL_release(&ctx->pool, ctx->used - fp);
        ctx->used = fp;
        /* Unjam "too_many" in case "get" had failed */
        ctx->too_many = 0;
    }
    CTXDBG_EXIT(ctx);
}
B
Bodo Möller 已提交
266

267
BIGNUM *BN_CTX_get(BN_CTX *ctx)
268 269
{
    BIGNUM *ret;
R
Rich Salz 已提交
270

271 272 273
    CTXDBG_ENTRY("BN_CTX_get", ctx);
    if (ctx->err_stack || ctx->too_many)
        return NULL;
R
Rich Salz 已提交
274
    if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) {
275 276 277 278 279 280 281 282 283 284 285 286 287 288
        /*
         * Setting too_many prevents repeated "get" attempts from cluttering
         * the error stack.
         */
        ctx->too_many = 1;
        BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
        return NULL;
    }
    /* OK, make sure the returned bignum is "zero" */
    BN_zero(ret);
    ctx->used++;
    CTXDBG_RET(ctx, ret);
    return ret;
}
289

290 291 292 293 294
/************/
/* BN_STACK */
/************/

static void BN_STACK_init(BN_STACK *st)
295 296 297 298
{
    st->indexes = NULL;
    st->depth = st->size = 0;
}
299 300

static void BN_STACK_finish(BN_STACK *st)
301
{
R
Rich Salz 已提交
302 303
    OPENSSL_free(st->indexes);
    st->indexes = NULL;
304
}
305

306 307

static int BN_STACK_push(BN_STACK *st, unsigned int idx)
308
{
R
Rich Salz 已提交
309
    if (st->depth == st->size) {
310
        /* Need to expand */
R
Rich Salz 已提交
311 312 313 314
        unsigned int newsize =
            st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES;
        unsigned int *newitems = OPENSSL_malloc(sizeof(*newitems) * newsize);
        if (newitems == NULL)
315 316
            return 0;
        if (st->depth)
R
Rich Salz 已提交
317 318
            memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth);
        OPENSSL_free(st->indexes);
319 320 321 322 323 324
        st->indexes = newitems;
        st->size = newsize;
    }
    st->indexes[(st->depth)++] = idx;
    return 1;
}
325 326

static unsigned int BN_STACK_pop(BN_STACK *st)
327 328 329
{
    return st->indexes[--(st->depth)];
}
330 331 332 333 334 335

/***********/
/* BN_POOL */
/***********/

static void BN_POOL_init(BN_POOL *p)
336 337 338 339
{
    p->head = p->current = p->tail = NULL;
    p->used = p->size = 0;
}
340 341

static void BN_POOL_finish(BN_POOL *p)
342
{
R
Rich Salz 已提交
343 344 345
    unsigned int loop;
    BIGNUM *bn;

346
    while (p->head) {
R
Rich Salz 已提交
347
        for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++)
348 349 350 351 352 353 354
            if (bn->d)
                BN_clear_free(bn);
        p->current = p->head->next;
        OPENSSL_free(p->head);
        p->head = p->current;
    }
}
355 356


R
Rich Salz 已提交
357
static BIGNUM *BN_POOL_get(BN_POOL *p, int flag)
358
{
R
Rich Salz 已提交
359 360 361 362
    BIGNUM *bn;
    unsigned int loop;

    /* Full; allocate a new pool item and link it in. */
363
    if (p->used == p->size) {
R
Rich Salz 已提交
364
        BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(*item));
R
Rich Salz 已提交
365
        if (item == NULL)
366
            return NULL;
R
Rich Salz 已提交
367 368 369 370 371
        for (loop = 0, bn = item->vals; loop++ < BN_CTX_POOL_SIZE; bn++) {
            BN_init(bn);
            if ((flag & BN_FLG_SECURE) != 0)
                BN_set_flags(bn, BN_FLG_SECURE);
        }
372 373
        item->prev = p->tail;
        item->next = NULL;
R
Rich Salz 已提交
374 375

        if (p->head == NULL)
376 377 378 379 380 381 382 383 384 385 386
            p->head = p->current = p->tail = item;
        else {
            p->tail->next = item;
            p->tail = item;
            p->current = item;
        }
        p->size += BN_CTX_POOL_SIZE;
        p->used++;
        /* Return the first bignum from the new pool */
        return item->vals;
    }
R
Rich Salz 已提交
387

388 389 390 391 392 393
    if (!p->used)
        p->current = p->head;
    else if ((p->used % BN_CTX_POOL_SIZE) == 0)
        p->current = p->current->next;
    return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
}
394 395

static void BN_POOL_release(BN_POOL *p, unsigned int num)
396 397
{
    unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
R
Rich Salz 已提交
398

399 400 401
    p->used -= num;
    while (num--) {
        bn_check_top(p->current->vals + offset);
R
Rich Salz 已提交
402
        if (offset == 0) {
403 404 405 406 407 408
            offset = BN_CTX_POOL_SIZE - 1;
            p->current = p->current->prev;
        } else
            offset--;
    }
}