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 11296465Sdelphij * 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) 58296465Sdelphij# ifndef NDEBUG 59296465Sdelphij# define NDEBUG 60296465Sdelphij# endif 6159191Skris#endif 6259191Skris 6359191Skris#include <stdio.h> 6459191Skris#include <assert.h> 65109998Smarkm 6659191Skris#include "cryptlib.h" 67109998Smarkm#include "bn_lcl.h" 6859191Skris 69296465Sdelphij/*- 70296465Sdelphij * 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"; */ 83296465Sdelphij#define BN_CTX_POOL_SIZE 16 84160814Ssimon/* The stack frame info is resizing, set a first-time expansion size; */ 85296465Sdelphij#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 */ 92296465Sdelphijtypedef struct bignum_pool_item { 93296465Sdelphij /* The bignum values */ 94296465Sdelphij BIGNUM vals[BN_CTX_POOL_SIZE]; 95296465Sdelphij /* Linked-list admin */ 96296465Sdelphij struct bignum_pool_item *prev, *next; 97296465Sdelphij} BN_POOL_ITEM; 98160814Ssimon/* A linked-list of bignums grouped in bundles */ 99296465Sdelphijtypedef struct bignum_pool { 100296465Sdelphij /* Linked-list admin */ 101296465Sdelphij BN_POOL_ITEM *head, *current, *tail; 102296465Sdelphij /* Stack depth and allocation size */ 103296465Sdelphij unsigned used, size; 104296465Sdelphij} BN_POOL; 105296465Sdelphijstatic void BN_POOL_init(BN_POOL *); 106296465Sdelphijstatic void BN_POOL_finish(BN_POOL *); 107160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 108296465Sdelphijstatic void BN_POOL_reset(BN_POOL *); 109160814Ssimon#endif 110296465Sdelphijstatic BIGNUM *BN_POOL_get(BN_POOL *); 111296465Sdelphijstatic void BN_POOL_release(BN_POOL *, unsigned int); 11259191Skris 113160814Ssimon/************/ 114160814Ssimon/* BN_STACK */ 115160814Ssimon/************/ 116160814Ssimon 117160814Ssimon/* A wrapper to manage the "stack frames" */ 118296465Sdelphijtypedef struct bignum_ctx_stack { 119296465Sdelphij /* Array of indexes into the bignum stack */ 120296465Sdelphij unsigned int *indexes; 121296465Sdelphij /* Number of stack frames, and the size of the allocated array */ 122296465Sdelphij unsigned int depth, size; 123296465Sdelphij} BN_STACK; 124296465Sdelphijstatic void BN_STACK_init(BN_STACK *); 125296465Sdelphijstatic void BN_STACK_finish(BN_STACK *); 126160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 127296465Sdelphijstatic void BN_STACK_reset(BN_STACK *); 128160814Ssimon#endif 129296465Sdelphijstatic int BN_STACK_push(BN_STACK *, unsigned int); 130296465Sdelphijstatic unsigned int BN_STACK_pop(BN_STACK *); 131160814Ssimon 132160814Ssimon/**********/ 133160814Ssimon/* BN_CTX */ 134160814Ssimon/**********/ 135160814Ssimon 136160814Ssimon/* The opaque BN_CTX type */ 137296465Sdelphijstruct bignum_ctx { 138296465Sdelphij /* The bignum bundles */ 139296465Sdelphij BN_POOL pool; 140296465Sdelphij /* The "stack frames", if you will */ 141296465Sdelphij BN_STACK stack; 142296465Sdelphij /* The number of bignums currently assigned */ 143296465Sdelphij unsigned int used; 144296465Sdelphij /* Depth of stack overflow */ 145296465Sdelphij int err_stack; 146296465Sdelphij /* Block "gets" until an "end" (compatibility behaviour) */ 147296465Sdelphij int too_many; 148296465Sdelphij}; 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) 154296465Sdelphij{ 155296465Sdelphij unsigned int bnidx = 0, fpidx = 0; 156296465Sdelphij BN_POOL_ITEM *item = ctx->pool.head; 157296465Sdelphij BN_STACK *stack = &ctx->stack; 158296465Sdelphij fprintf(stderr, "(%08x): ", (unsigned int)ctx); 159296465Sdelphij while (bnidx < ctx->used) { 160296465Sdelphij fprintf(stderr, "%02x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 161296465Sdelphij if (!(bnidx % BN_CTX_POOL_SIZE)) 162296465Sdelphij item = item->next; 163296465Sdelphij } 164296465Sdelphij fprintf(stderr, "\n"); 165296465Sdelphij bnidx = 0; 166296465Sdelphij fprintf(stderr, " : "); 167296465Sdelphij while (fpidx < stack->depth) { 168296465Sdelphij while (bnidx++ < stack->indexes[fpidx]) 169296465Sdelphij fprintf(stderr, " "); 170296465Sdelphij fprintf(stderr, "^^ "); 171296465Sdelphij bnidx++; 172296465Sdelphij fpidx++; 173296465Sdelphij } 174296465Sdelphij fprintf(stderr, "\n"); 175296465Sdelphij} 176296465Sdelphij 177296465Sdelphij# define CTXDBG_ENTRY(str, ctx) do { \ 178296465Sdelphij ctxdbg_cur = (str); \ 179296465Sdelphij fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ 180296465Sdelphij ctxdbg(ctx); \ 181296465Sdelphij } while(0) 182296465Sdelphij# define CTXDBG_EXIT(ctx) do { \ 183296465Sdelphij fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ 184296465Sdelphij ctxdbg(ctx); \ 185296465Sdelphij } while(0) 186296465Sdelphij# define CTXDBG_RET(ctx,ret) 187160814Ssimon#else 188296465Sdelphij# define CTXDBG_ENTRY(str, ctx) 189296465Sdelphij# define CTXDBG_EXIT(ctx) 190296465Sdelphij# define CTXDBG_RET(ctx,ret) 191160814Ssimon#endif 19259191Skris 193296465Sdelphij/* 194296465Sdelphij * This function is an evil legacy and should not be used. This 195296465Sdelphij * implementation is WYSIWYG, though I've done my best. 196296465Sdelphij */ 197160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 19859191Skrisvoid BN_CTX_init(BN_CTX *ctx) 199296465Sdelphij{ 200296465Sdelphij /* 201296465Sdelphij * Assume the caller obtained the context via BN_CTX_new() and so is 202296465Sdelphij * trying to reset it for use. Nothing else makes sense, least of all 203296465Sdelphij * binary compatibility from a time when they could declare a static 204296465Sdelphij * variable. 205296465Sdelphij */ 206296465Sdelphij BN_POOL_reset(&ctx->pool); 207296465Sdelphij BN_STACK_reset(&ctx->stack); 208296465Sdelphij ctx->used = 0; 209296465Sdelphij ctx->err_stack = 0; 210296465Sdelphij ctx->too_many = 0; 211296465Sdelphij} 212109998Smarkm#endif 213160814Ssimon 214160814SsimonBN_CTX *BN_CTX_new(void) 215296465Sdelphij{ 216296465Sdelphij BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); 217296465Sdelphij if (!ret) { 218296465Sdelphij BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE); 219296465Sdelphij return NULL; 220296465Sdelphij } 221296465Sdelphij /* Initialise the structure */ 222296465Sdelphij BN_POOL_init(&ret->pool); 223296465Sdelphij BN_STACK_init(&ret->stack); 224296465Sdelphij ret->used = 0; 225296465Sdelphij ret->err_stack = 0; 226296465Sdelphij ret->too_many = 0; 227296465Sdelphij return ret; 228296465Sdelphij} 22959191Skris 23059191Skrisvoid BN_CTX_free(BN_CTX *ctx) 231296465Sdelphij{ 232296465Sdelphij if (ctx == NULL) 233296465Sdelphij return; 234160814Ssimon#ifdef BN_CTX_DEBUG 235296465Sdelphij { 236296465Sdelphij BN_POOL_ITEM *pool = ctx->pool.head; 237296465Sdelphij fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n", 238296465Sdelphij ctx->stack.size, ctx->pool.size); 239296465Sdelphij fprintf(stderr, "dmaxs: "); 240296465Sdelphij while (pool) { 241296465Sdelphij unsigned loop = 0; 242296465Sdelphij while (loop < BN_CTX_POOL_SIZE) 243296465Sdelphij fprintf(stderr, "%02x ", pool->vals[loop++].dmax); 244296465Sdelphij pool = pool->next; 245296465Sdelphij } 246296465Sdelphij fprintf(stderr, "\n"); 247296465Sdelphij } 248160814Ssimon#endif 249296465Sdelphij BN_STACK_finish(&ctx->stack); 250296465Sdelphij BN_POOL_finish(&ctx->pool); 251296465Sdelphij OPENSSL_free(ctx); 252296465Sdelphij} 25359191Skris 25459191Skrisvoid BN_CTX_start(BN_CTX *ctx) 255296465Sdelphij{ 256296465Sdelphij CTXDBG_ENTRY("BN_CTX_start", ctx); 257296465Sdelphij /* If we're already overflowing ... */ 258296465Sdelphij if (ctx->err_stack || ctx->too_many) 259296465Sdelphij ctx->err_stack++; 260296465Sdelphij /* (Try to) get a new frame pointer */ 261296465Sdelphij else if (!BN_STACK_push(&ctx->stack, ctx->used)) { 262296465Sdelphij BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 263296465Sdelphij ctx->err_stack++; 264296465Sdelphij } 265296465Sdelphij CTXDBG_EXIT(ctx); 266296465Sdelphij} 26759191Skris 268160814Ssimonvoid BN_CTX_end(BN_CTX *ctx) 269296465Sdelphij{ 270296465Sdelphij CTXDBG_ENTRY("BN_CTX_end", ctx); 271296465Sdelphij if (ctx->err_stack) 272296465Sdelphij ctx->err_stack--; 273296465Sdelphij else { 274296465Sdelphij unsigned int fp = BN_STACK_pop(&ctx->stack); 275296465Sdelphij /* Does this stack frame have anything to release? */ 276296465Sdelphij if (fp < ctx->used) 277296465Sdelphij BN_POOL_release(&ctx->pool, ctx->used - fp); 278296465Sdelphij ctx->used = fp; 279296465Sdelphij /* Unjam "too_many" in case "get" had failed */ 280296465Sdelphij ctx->too_many = 0; 281296465Sdelphij } 282296465Sdelphij CTXDBG_EXIT(ctx); 283296465Sdelphij} 284109998Smarkm 28559191SkrisBIGNUM *BN_CTX_get(BN_CTX *ctx) 286296465Sdelphij{ 287296465Sdelphij BIGNUM *ret; 288296465Sdelphij CTXDBG_ENTRY("BN_CTX_get", ctx); 289296465Sdelphij if (ctx->err_stack || ctx->too_many) 290296465Sdelphij return NULL; 291296465Sdelphij if ((ret = BN_POOL_get(&ctx->pool)) == NULL) { 292296465Sdelphij /* 293296465Sdelphij * Setting too_many prevents repeated "get" attempts from cluttering 294296465Sdelphij * the error stack. 295296465Sdelphij */ 296296465Sdelphij ctx->too_many = 1; 297296465Sdelphij BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 298296465Sdelphij return NULL; 299296465Sdelphij } 300296465Sdelphij /* OK, make sure the returned bignum is "zero" */ 301296465Sdelphij BN_zero(ret); 302296465Sdelphij ctx->used++; 303296465Sdelphij CTXDBG_RET(ctx, ret); 304296465Sdelphij return ret; 305296465Sdelphij} 306160814Ssimon 307160814Ssimon/************/ 308160814Ssimon/* BN_STACK */ 309160814Ssimon/************/ 310160814Ssimon 311160814Ssimonstatic void BN_STACK_init(BN_STACK *st) 312296465Sdelphij{ 313296465Sdelphij st->indexes = NULL; 314296465Sdelphij st->depth = st->size = 0; 315296465Sdelphij} 316160814Ssimon 317160814Ssimonstatic void BN_STACK_finish(BN_STACK *st) 318296465Sdelphij{ 319296465Sdelphij if (st->size) 320296465Sdelphij OPENSSL_free(st->indexes); 321296465Sdelphij} 322160814Ssimon 323160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 324160814Ssimonstatic void BN_STACK_reset(BN_STACK *st) 325296465Sdelphij{ 326296465Sdelphij st->depth = 0; 327296465Sdelphij} 328160814Ssimon#endif 329160814Ssimon 330160814Ssimonstatic int BN_STACK_push(BN_STACK *st, unsigned int idx) 331296465Sdelphij{ 332296465Sdelphij if (st->depth == st->size) 333296465Sdelphij /* Need to expand */ 334296465Sdelphij { 335296465Sdelphij unsigned int newsize = (st->size ? 336296465Sdelphij (st->size * 3 / 2) : BN_CTX_START_FRAMES); 337296465Sdelphij unsigned int *newitems = OPENSSL_malloc(newsize * 338296465Sdelphij sizeof(unsigned int)); 339296465Sdelphij if (!newitems) 340296465Sdelphij return 0; 341296465Sdelphij if (st->depth) 342296465Sdelphij memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int)); 343296465Sdelphij if (st->size) 344296465Sdelphij OPENSSL_free(st->indexes); 345296465Sdelphij st->indexes = newitems; 346296465Sdelphij st->size = newsize; 347296465Sdelphij } 348296465Sdelphij st->indexes[(st->depth)++] = idx; 349296465Sdelphij return 1; 350296465Sdelphij} 351160814Ssimon 352160814Ssimonstatic unsigned int BN_STACK_pop(BN_STACK *st) 353296465Sdelphij{ 354296465Sdelphij return st->indexes[--(st->depth)]; 355296465Sdelphij} 356160814Ssimon 357160814Ssimon/***********/ 358160814Ssimon/* BN_POOL */ 359160814Ssimon/***********/ 360160814Ssimon 361160814Ssimonstatic void BN_POOL_init(BN_POOL *p) 362296465Sdelphij{ 363296465Sdelphij p->head = p->current = p->tail = NULL; 364296465Sdelphij p->used = p->size = 0; 365296465Sdelphij} 366160814Ssimon 367160814Ssimonstatic void BN_POOL_finish(BN_POOL *p) 368296465Sdelphij{ 369296465Sdelphij while (p->head) { 370296465Sdelphij unsigned int loop = 0; 371296465Sdelphij BIGNUM *bn = p->head->vals; 372296465Sdelphij while (loop++ < BN_CTX_POOL_SIZE) { 373296465Sdelphij if (bn->d) 374296465Sdelphij BN_clear_free(bn); 375296465Sdelphij bn++; 376296465Sdelphij } 377296465Sdelphij p->current = p->head->next; 378296465Sdelphij OPENSSL_free(p->head); 379296465Sdelphij p->head = p->current; 380296465Sdelphij } 381296465Sdelphij} 38259191Skris 383160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 384160814Ssimonstatic void BN_POOL_reset(BN_POOL *p) 385296465Sdelphij{ 386296465Sdelphij BN_POOL_ITEM *item = p->head; 387296465Sdelphij while (item) { 388296465Sdelphij unsigned int loop = 0; 389296465Sdelphij BIGNUM *bn = item->vals; 390296465Sdelphij while (loop++ < BN_CTX_POOL_SIZE) { 391296465Sdelphij if (bn->d) 392296465Sdelphij BN_clear(bn); 393296465Sdelphij bn++; 394296465Sdelphij } 395296465Sdelphij item = item->next; 396296465Sdelphij } 397296465Sdelphij p->current = p->head; 398296465Sdelphij p->used = 0; 399296465Sdelphij} 400160814Ssimon#endif 40159191Skris 402160814Ssimonstatic BIGNUM *BN_POOL_get(BN_POOL *p) 403296465Sdelphij{ 404296465Sdelphij if (p->used == p->size) { 405296465Sdelphij BIGNUM *bn; 406296465Sdelphij unsigned int loop = 0; 407296465Sdelphij BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); 408296465Sdelphij if (!item) 409296465Sdelphij return NULL; 410296465Sdelphij /* Initialise the structure */ 411296465Sdelphij bn = item->vals; 412296465Sdelphij while (loop++ < BN_CTX_POOL_SIZE) 413296465Sdelphij BN_init(bn++); 414296465Sdelphij item->prev = p->tail; 415296465Sdelphij item->next = NULL; 416296465Sdelphij /* Link it in */ 417296465Sdelphij if (!p->head) 418296465Sdelphij p->head = p->current = p->tail = item; 419296465Sdelphij else { 420296465Sdelphij p->tail->next = item; 421296465Sdelphij p->tail = item; 422296465Sdelphij p->current = item; 423296465Sdelphij } 424296465Sdelphij p->size += BN_CTX_POOL_SIZE; 425296465Sdelphij p->used++; 426296465Sdelphij /* Return the first bignum from the new pool */ 427296465Sdelphij return item->vals; 428296465Sdelphij } 429296465Sdelphij if (!p->used) 430296465Sdelphij p->current = p->head; 431296465Sdelphij else if ((p->used % BN_CTX_POOL_SIZE) == 0) 432296465Sdelphij p->current = p->current->next; 433296465Sdelphij return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 434296465Sdelphij} 435160814Ssimon 436160814Ssimonstatic void BN_POOL_release(BN_POOL *p, unsigned int num) 437296465Sdelphij{ 438296465Sdelphij unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 439296465Sdelphij p->used -= num; 440296465Sdelphij while (num--) { 441296465Sdelphij bn_check_top(p->current->vals + offset); 442296465Sdelphij if (!offset) { 443296465Sdelphij offset = BN_CTX_POOL_SIZE - 1; 444296465Sdelphij p->current = p->current->prev; 445296465Sdelphij } else 446296465Sdelphij offset--; 447296465Sdelphij } 448296465Sdelphij} 449