159191Skris/* crypto/bn/bn_ctx.c */ 259191Skris/* Written by Ulf Moeller for the OpenSSL project. */ 359191Skris/* ==================================================================== 4160814Ssimon * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. 559191Skris * 659191Skris * Redistribution and use in source and binary forms, with or without 759191Skris * modification, are permitted provided that the following conditions 859191Skris * are met: 959191Skris * 1059191Skris * 1. Redistributions of source code must retain the above copyright 11296341Sdelphij * notice, this list of conditions and the following disclaimer. 1259191Skris * 1359191Skris * 2. Redistributions in binary form must reproduce the above copyright 1459191Skris * notice, this list of conditions and the following disclaimer in 1559191Skris * the documentation and/or other materials provided with the 1659191Skris * distribution. 1759191Skris * 1859191Skris * 3. All advertising materials mentioning features or use of this 1959191Skris * software must display the following acknowledgment: 2059191Skris * "This product includes software developed by the OpenSSL Project 2159191Skris * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 2259191Skris * 2359191Skris * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 2459191Skris * endorse or promote products derived from this software without 2559191Skris * prior written permission. For written permission, please contact 2659191Skris * openssl-core@openssl.org. 2759191Skris * 2859191Skris * 5. Products derived from this software may not be called "OpenSSL" 2959191Skris * nor may "OpenSSL" appear in their names without prior written 3059191Skris * permission of the OpenSSL Project. 3159191Skris * 3259191Skris * 6. Redistributions of any form whatsoever must retain the following 3359191Skris * acknowledgment: 3459191Skris * "This product includes software developed by the OpenSSL Project 3559191Skris * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 3659191Skris * 3759191Skris * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 3859191Skris * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 3959191Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 4059191Skris * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 4159191Skris * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 4259191Skris * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 4359191Skris * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 4459191Skris * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4559191Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 4659191Skris * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 4759191Skris * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 4859191Skris * OF THE POSSIBILITY OF SUCH DAMAGE. 4959191Skris * ==================================================================== 5059191Skris * 5159191Skris * This product includes cryptographic software written by Eric Young 5259191Skris * (eay@cryptsoft.com). This product includes software written by Tim 5359191Skris * Hudson (tjh@cryptsoft.com). 5459191Skris * 5559191Skris */ 5659191Skris 57160814Ssimon#if !defined(BN_CTX_DEBUG) && !defined(BN_DEBUG) 58296341Sdelphij# ifndef NDEBUG 59296341Sdelphij# define NDEBUG 60296341Sdelphij# endif 6159191Skris#endif 6259191Skris 6359191Skris#include <stdio.h> 6459191Skris#include <assert.h> 65109998Smarkm 6659191Skris#include "cryptlib.h" 67109998Smarkm#include "bn_lcl.h" 6859191Skris 69296341Sdelphij/*- 70296341Sdelphij * TODO list 71160814Ssimon * 72160814Ssimon * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and 73160814Ssimon * check they can be safely removed. 74160814Ssimon * - Check +1 and other ugliness in BN_from_montgomery() 75160814Ssimon * 76160814Ssimon * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an 77160814Ssimon * appropriate 'block' size that will be honoured by bn_expand_internal() to 78160814Ssimon * prevent piddly little reallocations. OTOH, profiling bignum expansions in 79160814Ssimon * BN_CTX doesn't show this to be a big issue. 80160814Ssimon */ 8159191Skris 82160814Ssimon/* How many bignums are in each "pool item"; */ 83296341Sdelphij#define BN_CTX_POOL_SIZE 16 84160814Ssimon/* The stack frame info is resizing, set a first-time expansion size; */ 85296341Sdelphij#define BN_CTX_START_FRAMES 32 86160814Ssimon 87160814Ssimon/***********/ 88160814Ssimon/* BN_POOL */ 89160814Ssimon/***********/ 90160814Ssimon 91160814Ssimon/* A bundle of bignums that can be linked with other bundles */ 92296341Sdelphijtypedef struct bignum_pool_item { 93296341Sdelphij /* The bignum values */ 94296341Sdelphij BIGNUM vals[BN_CTX_POOL_SIZE]; 95296341Sdelphij /* Linked-list admin */ 96296341Sdelphij struct bignum_pool_item *prev, *next; 97296341Sdelphij} BN_POOL_ITEM; 98160814Ssimon/* A linked-list of bignums grouped in bundles */ 99296341Sdelphijtypedef struct bignum_pool { 100296341Sdelphij /* Linked-list admin */ 101296341Sdelphij BN_POOL_ITEM *head, *current, *tail; 102296341Sdelphij /* Stack depth and allocation size */ 103296341Sdelphij unsigned used, size; 104296341Sdelphij} BN_POOL; 105296341Sdelphijstatic void BN_POOL_init(BN_POOL *); 106296341Sdelphijstatic void BN_POOL_finish(BN_POOL *); 107160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 108296341Sdelphijstatic void BN_POOL_reset(BN_POOL *); 109160814Ssimon#endif 110296341Sdelphijstatic BIGNUM *BN_POOL_get(BN_POOL *); 111296341Sdelphijstatic void BN_POOL_release(BN_POOL *, unsigned int); 11259191Skris 113160814Ssimon/************/ 114160814Ssimon/* BN_STACK */ 115160814Ssimon/************/ 116160814Ssimon 117160814Ssimon/* A wrapper to manage the "stack frames" */ 118296341Sdelphijtypedef struct bignum_ctx_stack { 119296341Sdelphij /* Array of indexes into the bignum stack */ 120296341Sdelphij unsigned int *indexes; 121296341Sdelphij /* Number of stack frames, and the size of the allocated array */ 122296341Sdelphij unsigned int depth, size; 123296341Sdelphij} BN_STACK; 124296341Sdelphijstatic void BN_STACK_init(BN_STACK *); 125296341Sdelphijstatic void BN_STACK_finish(BN_STACK *); 126160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 127296341Sdelphijstatic void BN_STACK_reset(BN_STACK *); 128160814Ssimon#endif 129296341Sdelphijstatic int BN_STACK_push(BN_STACK *, unsigned int); 130296341Sdelphijstatic unsigned int BN_STACK_pop(BN_STACK *); 131160814Ssimon 132160814Ssimon/**********/ 133160814Ssimon/* BN_CTX */ 134160814Ssimon/**********/ 135160814Ssimon 136160814Ssimon/* The opaque BN_CTX type */ 137296341Sdelphijstruct bignum_ctx { 138296341Sdelphij /* The bignum bundles */ 139296341Sdelphij BN_POOL pool; 140296341Sdelphij /* The "stack frames", if you will */ 141296341Sdelphij BN_STACK stack; 142296341Sdelphij /* The number of bignums currently assigned */ 143296341Sdelphij unsigned int used; 144296341Sdelphij /* Depth of stack overflow */ 145296341Sdelphij int err_stack; 146296341Sdelphij /* Block "gets" until an "end" (compatibility behaviour) */ 147296341Sdelphij int too_many; 148296341Sdelphij}; 149160814Ssimon 150160814Ssimon/* Enable this to find BN_CTX bugs */ 151160814Ssimon#ifdef BN_CTX_DEBUG 152160814Ssimonstatic const char *ctxdbg_cur = NULL; 153160814Ssimonstatic void ctxdbg(BN_CTX *ctx) 154296341Sdelphij{ 155296341Sdelphij unsigned int bnidx = 0, fpidx = 0; 156296341Sdelphij BN_POOL_ITEM *item = ctx->pool.head; 157296341Sdelphij BN_STACK *stack = &ctx->stack; 158296341Sdelphij fprintf(stderr, "(%16p): ", ctx); 159296341Sdelphij while (bnidx < ctx->used) { 160296341Sdelphij fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 161296341Sdelphij if (!(bnidx % BN_CTX_POOL_SIZE)) 162296341Sdelphij item = item->next; 163296341Sdelphij } 164296341Sdelphij fprintf(stderr, "\n"); 165296341Sdelphij bnidx = 0; 166296341Sdelphij fprintf(stderr, " : "); 167296341Sdelphij while (fpidx < stack->depth) { 168296341Sdelphij while (bnidx++ < stack->indexes[fpidx]) 169296341Sdelphij fprintf(stderr, " "); 170296341Sdelphij fprintf(stderr, "^^^ "); 171296341Sdelphij bnidx++; 172296341Sdelphij fpidx++; 173296341Sdelphij } 174296341Sdelphij fprintf(stderr, "\n"); 175296341Sdelphij} 176296341Sdelphij 177296341Sdelphij# define CTXDBG_ENTRY(str, ctx) do { \ 178296341Sdelphij ctxdbg_cur = (str); \ 179296341Sdelphij fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ 180296341Sdelphij ctxdbg(ctx); \ 181296341Sdelphij } while(0) 182296341Sdelphij# define CTXDBG_EXIT(ctx) do { \ 183296341Sdelphij fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ 184296341Sdelphij ctxdbg(ctx); \ 185296341Sdelphij } while(0) 186296341Sdelphij# define CTXDBG_RET(ctx,ret) 187160814Ssimon#else 188296341Sdelphij# define CTXDBG_ENTRY(str, ctx) 189296341Sdelphij# define CTXDBG_EXIT(ctx) 190296341Sdelphij# define CTXDBG_RET(ctx,ret) 191160814Ssimon#endif 19259191Skris 193296341Sdelphij/* 194296341Sdelphij * This function is an evil legacy and should not be used. This 195296341Sdelphij * implementation is WYSIWYG, though I've done my best. 196296341Sdelphij */ 197160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 19859191Skrisvoid BN_CTX_init(BN_CTX *ctx) 199296341Sdelphij{ 200296341Sdelphij /* 201296341Sdelphij * Assume the caller obtained the context via BN_CTX_new() and so is 202296341Sdelphij * trying to reset it for use. Nothing else makes sense, least of all 203296341Sdelphij * binary compatibility from a time when they could declare a static 204296341Sdelphij * variable. 205296341Sdelphij */ 206296341Sdelphij BN_POOL_reset(&ctx->pool); 207296341Sdelphij BN_STACK_reset(&ctx->stack); 208296341Sdelphij ctx->used = 0; 209296341Sdelphij ctx->err_stack = 0; 210296341Sdelphij ctx->too_many = 0; 211296341Sdelphij} 212109998Smarkm#endif 213160814Ssimon 214160814SsimonBN_CTX *BN_CTX_new(void) 215296341Sdelphij{ 216296341Sdelphij BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); 217296341Sdelphij if (!ret) { 218296341Sdelphij BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE); 219296341Sdelphij return NULL; 220296341Sdelphij } 221296341Sdelphij /* Initialise the structure */ 222296341Sdelphij BN_POOL_init(&ret->pool); 223296341Sdelphij BN_STACK_init(&ret->stack); 224296341Sdelphij ret->used = 0; 225296341Sdelphij ret->err_stack = 0; 226296341Sdelphij ret->too_many = 0; 227296341Sdelphij return ret; 228296341Sdelphij} 22959191Skris 23059191Skrisvoid BN_CTX_free(BN_CTX *ctx) 231296341Sdelphij{ 232296341Sdelphij if (ctx == NULL) 233296341Sdelphij return; 234160814Ssimon#ifdef BN_CTX_DEBUG 235296341Sdelphij { 236296341Sdelphij BN_POOL_ITEM *pool = ctx->pool.head; 237296341Sdelphij fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n", 238296341Sdelphij ctx->stack.size, ctx->pool.size); 239296341Sdelphij fprintf(stderr, "dmaxs: "); 240296341Sdelphij while (pool) { 241296341Sdelphij unsigned loop = 0; 242296341Sdelphij while (loop < BN_CTX_POOL_SIZE) 243296341Sdelphij fprintf(stderr, "%02x ", pool->vals[loop++].dmax); 244296341Sdelphij pool = pool->next; 245296341Sdelphij } 246296341Sdelphij fprintf(stderr, "\n"); 247296341Sdelphij } 248160814Ssimon#endif 249296341Sdelphij BN_STACK_finish(&ctx->stack); 250296341Sdelphij BN_POOL_finish(&ctx->pool); 251296341Sdelphij OPENSSL_free(ctx); 252296341Sdelphij} 25359191Skris 25459191Skrisvoid BN_CTX_start(BN_CTX *ctx) 255296341Sdelphij{ 256296341Sdelphij CTXDBG_ENTRY("BN_CTX_start", ctx); 257296341Sdelphij /* If we're already overflowing ... */ 258296341Sdelphij if (ctx->err_stack || ctx->too_many) 259296341Sdelphij ctx->err_stack++; 260296341Sdelphij /* (Try to) get a new frame pointer */ 261296341Sdelphij else if (!BN_STACK_push(&ctx->stack, ctx->used)) { 262296341Sdelphij BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 263296341Sdelphij ctx->err_stack++; 264296341Sdelphij } 265296341Sdelphij CTXDBG_EXIT(ctx); 266296341Sdelphij} 26759191Skris 268160814Ssimonvoid BN_CTX_end(BN_CTX *ctx) 269296341Sdelphij{ 270296341Sdelphij CTXDBG_ENTRY("BN_CTX_end", ctx); 271296341Sdelphij if (ctx->err_stack) 272296341Sdelphij ctx->err_stack--; 273296341Sdelphij else { 274296341Sdelphij unsigned int fp = BN_STACK_pop(&ctx->stack); 275296341Sdelphij /* Does this stack frame have anything to release? */ 276296341Sdelphij if (fp < ctx->used) 277296341Sdelphij BN_POOL_release(&ctx->pool, ctx->used - fp); 278296341Sdelphij ctx->used = fp; 279296341Sdelphij /* Unjam "too_many" in case "get" had failed */ 280296341Sdelphij ctx->too_many = 0; 281296341Sdelphij } 282296341Sdelphij CTXDBG_EXIT(ctx); 283296341Sdelphij} 284109998Smarkm 28559191SkrisBIGNUM *BN_CTX_get(BN_CTX *ctx) 286296341Sdelphij{ 287296341Sdelphij BIGNUM *ret; 288296341Sdelphij CTXDBG_ENTRY("BN_CTX_get", ctx); 289296341Sdelphij if (ctx->err_stack || ctx->too_many) 290296341Sdelphij return NULL; 291296341Sdelphij if ((ret = BN_POOL_get(&ctx->pool)) == NULL) { 292296341Sdelphij /* 293296341Sdelphij * Setting too_many prevents repeated "get" attempts from cluttering 294296341Sdelphij * the error stack. 295296341Sdelphij */ 296296341Sdelphij ctx->too_many = 1; 297296341Sdelphij BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 298296341Sdelphij return NULL; 299296341Sdelphij } 300296341Sdelphij /* OK, make sure the returned bignum is "zero" */ 301296341Sdelphij BN_zero(ret); 302296341Sdelphij ctx->used++; 303296341Sdelphij CTXDBG_RET(ctx, ret); 304296341Sdelphij return ret; 305296341Sdelphij} 306160814Ssimon 307160814Ssimon/************/ 308160814Ssimon/* BN_STACK */ 309160814Ssimon/************/ 310160814Ssimon 311160814Ssimonstatic void BN_STACK_init(BN_STACK *st) 312296341Sdelphij{ 313296341Sdelphij st->indexes = NULL; 314296341Sdelphij st->depth = st->size = 0; 315296341Sdelphij} 316160814Ssimon 317160814Ssimonstatic void BN_STACK_finish(BN_STACK *st) 318296341Sdelphij{ 319296341Sdelphij if (st->size) 320296341Sdelphij OPENSSL_free(st->indexes); 321296341Sdelphij} 322160814Ssimon 323160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 324160814Ssimonstatic void BN_STACK_reset(BN_STACK *st) 325296341Sdelphij{ 326296341Sdelphij st->depth = 0; 327296341Sdelphij} 328160814Ssimon#endif 329160814Ssimon 330160814Ssimonstatic int BN_STACK_push(BN_STACK *st, unsigned int idx) 331296341Sdelphij{ 332296341Sdelphij if (st->depth == st->size) 333296341Sdelphij /* Need to expand */ 334296341Sdelphij { 335296341Sdelphij unsigned int newsize = (st->size ? 336296341Sdelphij (st->size * 3 / 2) : BN_CTX_START_FRAMES); 337296341Sdelphij unsigned int *newitems = OPENSSL_malloc(newsize * 338296341Sdelphij sizeof(unsigned int)); 339296341Sdelphij if (!newitems) 340296341Sdelphij return 0; 341296341Sdelphij if (st->depth) 342296341Sdelphij memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int)); 343296341Sdelphij if (st->size) 344296341Sdelphij OPENSSL_free(st->indexes); 345296341Sdelphij st->indexes = newitems; 346296341Sdelphij st->size = newsize; 347296341Sdelphij } 348296341Sdelphij st->indexes[(st->depth)++] = idx; 349296341Sdelphij return 1; 350296341Sdelphij} 351160814Ssimon 352160814Ssimonstatic unsigned int BN_STACK_pop(BN_STACK *st) 353296341Sdelphij{ 354296341Sdelphij return st->indexes[--(st->depth)]; 355296341Sdelphij} 356160814Ssimon 357160814Ssimon/***********/ 358160814Ssimon/* BN_POOL */ 359160814Ssimon/***********/ 360160814Ssimon 361160814Ssimonstatic void BN_POOL_init(BN_POOL *p) 362296341Sdelphij{ 363296341Sdelphij p->head = p->current = p->tail = NULL; 364296341Sdelphij p->used = p->size = 0; 365296341Sdelphij} 366160814Ssimon 367160814Ssimonstatic void BN_POOL_finish(BN_POOL *p) 368296341Sdelphij{ 369296341Sdelphij while (p->head) { 370296341Sdelphij unsigned int loop = 0; 371296341Sdelphij BIGNUM *bn = p->head->vals; 372296341Sdelphij while (loop++ < BN_CTX_POOL_SIZE) { 373296341Sdelphij if (bn->d) 374296341Sdelphij BN_clear_free(bn); 375296341Sdelphij bn++; 376296341Sdelphij } 377296341Sdelphij p->current = p->head->next; 378296341Sdelphij OPENSSL_free(p->head); 379296341Sdelphij p->head = p->current; 380296341Sdelphij } 381296341Sdelphij} 38259191Skris 383160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 384160814Ssimonstatic void BN_POOL_reset(BN_POOL *p) 385296341Sdelphij{ 386296341Sdelphij BN_POOL_ITEM *item = p->head; 387296341Sdelphij while (item) { 388296341Sdelphij unsigned int loop = 0; 389296341Sdelphij BIGNUM *bn = item->vals; 390296341Sdelphij while (loop++ < BN_CTX_POOL_SIZE) { 391296341Sdelphij if (bn->d) 392296341Sdelphij BN_clear(bn); 393296341Sdelphij bn++; 394296341Sdelphij } 395296341Sdelphij item = item->next; 396296341Sdelphij } 397296341Sdelphij p->current = p->head; 398296341Sdelphij p->used = 0; 399296341Sdelphij} 400160814Ssimon#endif 40159191Skris 402160814Ssimonstatic BIGNUM *BN_POOL_get(BN_POOL *p) 403296341Sdelphij{ 404296341Sdelphij if (p->used == p->size) { 405296341Sdelphij BIGNUM *bn; 406296341Sdelphij unsigned int loop = 0; 407296341Sdelphij BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); 408296341Sdelphij if (!item) 409296341Sdelphij return NULL; 410296341Sdelphij /* Initialise the structure */ 411296341Sdelphij bn = item->vals; 412296341Sdelphij while (loop++ < BN_CTX_POOL_SIZE) 413296341Sdelphij BN_init(bn++); 414296341Sdelphij item->prev = p->tail; 415296341Sdelphij item->next = NULL; 416296341Sdelphij /* Link it in */ 417296341Sdelphij if (!p->head) 418296341Sdelphij p->head = p->current = p->tail = item; 419296341Sdelphij else { 420296341Sdelphij p->tail->next = item; 421296341Sdelphij p->tail = item; 422296341Sdelphij p->current = item; 423296341Sdelphij } 424296341Sdelphij p->size += BN_CTX_POOL_SIZE; 425296341Sdelphij p->used++; 426296341Sdelphij /* Return the first bignum from the new pool */ 427296341Sdelphij return item->vals; 428296341Sdelphij } 429296341Sdelphij if (!p->used) 430296341Sdelphij p->current = p->head; 431296341Sdelphij else if ((p->used % BN_CTX_POOL_SIZE) == 0) 432296341Sdelphij p->current = p->current->next; 433296341Sdelphij return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 434296341Sdelphij} 435160814Ssimon 436160814Ssimonstatic void BN_POOL_release(BN_POOL *p, unsigned int num) 437296341Sdelphij{ 438296341Sdelphij unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 439296341Sdelphij p->used -= num; 440296341Sdelphij while (num--) { 441296341Sdelphij bn_check_top(p->current->vals + offset); 442296341Sdelphij if (!offset) { 443296341Sdelphij offset = BN_CTX_POOL_SIZE - 1; 444296341Sdelphij p->current = p->current->prev; 445296341Sdelphij } else 446296341Sdelphij offset--; 447296341Sdelphij } 448296341Sdelphij} 449