X-Git-Url: https://git.openssl.org/gitweb/?p=openssl.git;a=blobdiff_plain;f=crypto%2Fbn%2Fbn_ctx.c;h=62e29b5dcc2dff736c51cc21f8b9790d8955058e;hp=46132fd1806a04506803f23c4a2e03a4c4b2a336;hb=ce1415ed2ce15305356cd028bcf7b9bc688d6d5c;hpb=cae55bfc68bed0a2d562891f11a75bf2145eb81e diff --git a/crypto/bn/bn_ctx.c b/crypto/bn/bn_ctx.c index 46132fd180..62e29b5dcc 100644 --- a/crypto/bn/bn_ctx.c +++ b/crypto/bn/bn_ctx.c @@ -1,144 +1,353 @@ -/* crypto/bn/bn_ctx.c */ -/* Written by Ulf Moeller for the OpenSSL project. */ -/* ==================================================================== - * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. +/* + * Copyright 2000-2019 The OpenSSL Project Authors. All Rights Reserved. * - * 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 - * notice, this list of conditions and the following disclaimer. - * - * 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. - * ==================================================================== + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include +#include "internal/cryptlib.h" +#include "bn_lcl.h" + +/*- + * TODO list * - * This product includes cryptographic software written by Eric Young - * (eay@cryptsoft.com). This product includes software written by Tim - * Hudson (tjh@cryptsoft.com). + * 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. */ -#ifndef BN_CTX_DEBUG -# undef NDEBUG /* avoid conflicting definitions */ -# define NDEBUG -#endif +/* How many bignums are in each "pool item"; */ +#define BN_CTX_POOL_SIZE 16 +/* The stack frame info is resizing, set a first-time expansion size; */ +#define BN_CTX_START_FRAMES 32 + +/***********/ +/* BN_POOL */ +/***********/ -#include -#include -#include "cryptlib.h" -#include +/* A bundle of bignums that can be linked with other bundles */ +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; +/* A linked-list of bignums grouped in bundles */ +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 *); +static BIGNUM *BN_POOL_get(BN_POOL *, int); +static void BN_POOL_release(BN_POOL *, unsigned int); + +/************/ +/* BN_STACK */ +/************/ + +/* A wrapper to manage the "stack frames" */ +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 *); + +/**********/ +/* BN_CTX */ +/**********/ + +/* The opaque BN_CTX type */ +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; + /* Flags. */ + int flags; +}; + +/* Debugging functionality */ +static void ctxdbg(BIO *channel, const char *text, BN_CTX *ctx) +{ + unsigned int bnidx = 0, fpidx = 0; + BN_POOL_ITEM *item = ctx->pool.head; + BN_STACK *stack = &ctx->stack; + + BIO_printf(channel, "%s\n", text); + BIO_printf(channel, " (%16p): ", (void*)ctx); + while (bnidx < ctx->used) { + BIO_printf(channel, "%03x ", + item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); + if (!(bnidx % BN_CTX_POOL_SIZE)) + item = item->next; + } + BIO_printf(channel, "\n"); + bnidx = 0; + BIO_printf(channel, " %16s : ", ""); + while (fpidx < stack->depth) { + while (bnidx++ < stack->indexes[fpidx]) + BIO_printf(channel, " "); + BIO_printf(channel, "^^^ "); + bnidx++; + fpidx++; + } + BIO_printf(channel, "\n"); +} + +#define CTXDBG(str, ctx) \ + OSSL_TRACE_BEGIN(BN_CTX) { \ + ctxdbg(trc_out, str, ctx); \ + } OSSL_TRACE_END(BN_CTX) BN_CTX *BN_CTX_new(void) - { - BN_CTX *ret; - - ret=(BN_CTX *)Malloc(sizeof(BN_CTX)); - if (ret == NULL) - { - BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); - return(NULL); - } - - BN_CTX_init(ret); - ret->flags=BN_FLG_MALLOCED; - return(ret); - } - -void BN_CTX_init(BN_CTX *ctx) - { - int i; - ctx->tos = 0; - ctx->flags = 0; - ctx->depth = 0; - ctx->too_many = 0; - for (i = 0; i < BN_CTX_NUM; i++) - BN_init(&(ctx->bn[i])); - } +{ + BN_CTX *ret; -void BN_CTX_free(BN_CTX *ctx) - { - int i; + if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { + 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); + return ret; +} - if (ctx == NULL) return; - assert(ctx->depth == 0); +BN_CTX *BN_CTX_secure_new(void) +{ + BN_CTX *ret = BN_CTX_new(); - for (i=0; i < BN_CTX_NUM; i++) - BN_clear_free(&(ctx->bn[i])); - if (ctx->flags & BN_FLG_MALLOCED) - Free(ctx); - } + if (ret != NULL) + ret->flags = BN_FLG_SECURE; + return ret; +} + +void BN_CTX_free(BN_CTX *ctx) +{ + if (ctx == NULL) + return; + OSSL_TRACE_BEGIN(BN_CTX) { + BN_POOL_ITEM *pool = ctx->pool.head; + BIO_printf(trc_out, + "BN_CTX_free(): stack-size=%d, pool-bignums=%d\n", + ctx->stack.size, ctx->pool.size); + BIO_printf(trc_out, " dmaxs: "); + while (pool) { + unsigned loop = 0; + while (loop < BN_CTX_POOL_SIZE) + BIO_printf(trc_out, "%02x ", pool->vals[loop++].dmax); + pool = pool->next; + } + BIO_printf(trc_out, "\n"); + } OSSL_TRACE_END(BN_CTX); + BN_STACK_finish(&ctx->stack); + BN_POOL_finish(&ctx->pool); + OPENSSL_free(ctx); +} void BN_CTX_start(BN_CTX *ctx) - { - if (ctx->depth < BN_CTX_NUM_POS) - ctx->pos[ctx->depth] = ctx->tos; - ctx->depth++; - } +{ + CTXDBG("ENTER 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("LEAVE BN_CTX_start()", ctx); +} + +void BN_CTX_end(BN_CTX *ctx) +{ + if (ctx == NULL) + return; + CTXDBG("ENTER 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("LEAVE BN_CTX_end()", ctx); +} BIGNUM *BN_CTX_get(BN_CTX *ctx) - { - if (ctx->depth > BN_CTX_NUM_POS || ctx->tos >= BN_CTX_NUM) - { - if (!ctx->too_many) - { - BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES); - /* disable error code until BN_CTX_end is called: */ - ctx->too_many = 1; - } - return NULL; - } - return (&(ctx->bn[ctx->tos++])); - } +{ + BIGNUM *ret; -void BN_CTX_end(BN_CTX *ctx) - { - if (ctx == NULL) return; - assert(ctx->depth > 0); - if (ctx->depth == 0) - /* should never happen, but we can tolerate it if not in - * debug mode (could be a 'goto err' in the calling function - * before BN_CTX_start was reached) */ - BN_CTX_start(ctx); - - ctx->too_many = 0; - ctx->depth--; - if (ctx->depth < BN_CTX_NUM_POS) - ctx->tos = ctx->pos[ctx->depth]; - } + CTXDBG("ENTER BN_CTX_get()", ctx); + if (ctx->err_stack || ctx->too_many) + return NULL; + if ((ret = BN_POOL_get(&ctx->pool, ctx->flags)) == NULL) { + /* + * 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); + /* clear BN_FLG_CONSTTIME if leaked from previous frames */ + ret->flags &= (~BN_FLG_CONSTTIME); + ctx->used++; + CTXDBG("LEAVE BN_CTX_get()", ctx); + return ret; +} + +/************/ +/* BN_STACK */ +/************/ + +static void BN_STACK_init(BN_STACK *st) +{ + st->indexes = NULL; + st->depth = st->size = 0; +} + +static void BN_STACK_finish(BN_STACK *st) +{ + OPENSSL_free(st->indexes); + st->indexes = NULL; +} + + +static int BN_STACK_push(BN_STACK *st, unsigned int idx) +{ + if (st->depth == st->size) { + /* Need to expand */ + unsigned int newsize = + st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES; + unsigned int *newitems; + + if ((newitems = OPENSSL_malloc(sizeof(*newitems) * newsize)) == NULL) { + BNerr(BN_F_BN_STACK_PUSH, ERR_R_MALLOC_FAILURE); + return 0; + } + if (st->depth) + memcpy(newitems, st->indexes, sizeof(*newitems) * st->depth); + OPENSSL_free(st->indexes); + st->indexes = newitems; + st->size = newsize; + } + st->indexes[(st->depth)++] = idx; + return 1; +} + +static unsigned int BN_STACK_pop(BN_STACK *st) +{ + return st->indexes[--(st->depth)]; +} + +/***********/ +/* BN_POOL */ +/***********/ + +static void BN_POOL_init(BN_POOL *p) +{ + p->head = p->current = p->tail = NULL; + p->used = p->size = 0; +} + +static void BN_POOL_finish(BN_POOL *p) +{ + unsigned int loop; + BIGNUM *bn; + + while (p->head) { + for (loop = 0, bn = p->head->vals; loop++ < BN_CTX_POOL_SIZE; bn++) + if (bn->d) + BN_clear_free(bn); + p->current = p->head->next; + OPENSSL_free(p->head); + p->head = p->current; + } +} + + +static BIGNUM *BN_POOL_get(BN_POOL *p, int flag) +{ + BIGNUM *bn; + unsigned int loop; + + /* Full; allocate a new pool item and link it in. */ + if (p->used == p->size) { + BN_POOL_ITEM *item; + + if ((item = OPENSSL_malloc(sizeof(*item))) == NULL) { + BNerr(BN_F_BN_POOL_GET, ERR_R_MALLOC_FAILURE); + return NULL; + } + 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); + } + item->prev = p->tail; + item->next = NULL; + + if (p->head == NULL) + 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; + } + + 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); +} + +static void BN_POOL_release(BN_POOL *p, unsigned int num) +{ + unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; + + p->used -= num; + while (num--) { + bn_check_top(p->current->vals + offset); + if (offset == 0) { + offset = BN_CTX_POOL_SIZE - 1; + p->current = p->current->prev; + } else + offset--; + } +}