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 11280304Sjkim * 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) 58280304Sjkim# ifndef NDEBUG 59280304Sjkim# define NDEBUG 60280304Sjkim# endif 6159191Skris#endif 6259191Skris 6359191Skris#include <stdio.h> 6459191Skris#include <assert.h> 65109998Smarkm 6659191Skris#include "cryptlib.h" 67109998Smarkm#include "bn_lcl.h" 6859191Skris 69280304Sjkim/*- 70280304Sjkim * 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"; */ 83280304Sjkim#define BN_CTX_POOL_SIZE 16 84160814Ssimon/* The stack frame info is resizing, set a first-time expansion size; */ 85280304Sjkim#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 */ 92280304Sjkimtypedef struct bignum_pool_item { 93280304Sjkim /* The bignum values */ 94280304Sjkim BIGNUM vals[BN_CTX_POOL_SIZE]; 95280304Sjkim /* Linked-list admin */ 96280304Sjkim struct bignum_pool_item *prev, *next; 97280304Sjkim} BN_POOL_ITEM; 98160814Ssimon/* A linked-list of bignums grouped in bundles */ 99280304Sjkimtypedef struct bignum_pool { 100280304Sjkim /* Linked-list admin */ 101280304Sjkim BN_POOL_ITEM *head, *current, *tail; 102280304Sjkim /* Stack depth and allocation size */ 103280304Sjkim unsigned used, size; 104280304Sjkim} BN_POOL; 105280304Sjkimstatic void BN_POOL_init(BN_POOL *); 106280304Sjkimstatic void BN_POOL_finish(BN_POOL *); 107160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 108280304Sjkimstatic void BN_POOL_reset(BN_POOL *); 109160814Ssimon#endif 110280304Sjkimstatic BIGNUM *BN_POOL_get(BN_POOL *); 111280304Sjkimstatic void BN_POOL_release(BN_POOL *, unsigned int); 11259191Skris 113160814Ssimon/************/ 114160814Ssimon/* BN_STACK */ 115160814Ssimon/************/ 116160814Ssimon 117160814Ssimon/* A wrapper to manage the "stack frames" */ 118280304Sjkimtypedef struct bignum_ctx_stack { 119280304Sjkim /* Array of indexes into the bignum stack */ 120280304Sjkim unsigned int *indexes; 121280304Sjkim /* Number of stack frames, and the size of the allocated array */ 122280304Sjkim unsigned int depth, size; 123280304Sjkim} BN_STACK; 124280304Sjkimstatic void BN_STACK_init(BN_STACK *); 125280304Sjkimstatic void BN_STACK_finish(BN_STACK *); 126160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 127280304Sjkimstatic void BN_STACK_reset(BN_STACK *); 128160814Ssimon#endif 129280304Sjkimstatic int BN_STACK_push(BN_STACK *, unsigned int); 130280304Sjkimstatic unsigned int BN_STACK_pop(BN_STACK *); 131160814Ssimon 132160814Ssimon/**********/ 133160814Ssimon/* BN_CTX */ 134160814Ssimon/**********/ 135160814Ssimon 136160814Ssimon/* The opaque BN_CTX type */ 137280304Sjkimstruct bignum_ctx { 138280304Sjkim /* The bignum bundles */ 139280304Sjkim BN_POOL pool; 140280304Sjkim /* The "stack frames", if you will */ 141280304Sjkim BN_STACK stack; 142280304Sjkim /* The number of bignums currently assigned */ 143280304Sjkim unsigned int used; 144280304Sjkim /* Depth of stack overflow */ 145280304Sjkim int err_stack; 146280304Sjkim /* Block "gets" until an "end" (compatibility behaviour) */ 147280304Sjkim int too_many; 148280304Sjkim}; 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) 154280304Sjkim{ 155280304Sjkim unsigned int bnidx = 0, fpidx = 0; 156280304Sjkim BN_POOL_ITEM *item = ctx->pool.head; 157280304Sjkim BN_STACK *stack = &ctx->stack; 158280304Sjkim fprintf(stderr, "(%16p): ", ctx); 159280304Sjkim while (bnidx < ctx->used) { 160280304Sjkim fprintf(stderr, "%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 161280304Sjkim if (!(bnidx % BN_CTX_POOL_SIZE)) 162280304Sjkim item = item->next; 163280304Sjkim } 164280304Sjkim fprintf(stderr, "\n"); 165280304Sjkim bnidx = 0; 166280304Sjkim fprintf(stderr, " : "); 167280304Sjkim while (fpidx < stack->depth) { 168280304Sjkim while (bnidx++ < stack->indexes[fpidx]) 169280304Sjkim fprintf(stderr, " "); 170280304Sjkim fprintf(stderr, "^^^ "); 171280304Sjkim bnidx++; 172280304Sjkim fpidx++; 173280304Sjkim } 174280304Sjkim fprintf(stderr, "\n"); 175280304Sjkim} 176280304Sjkim 177280304Sjkim# define CTXDBG_ENTRY(str, ctx) do { \ 178280304Sjkim ctxdbg_cur = (str); \ 179280304Sjkim fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ 180280304Sjkim ctxdbg(ctx); \ 181280304Sjkim } while(0) 182280304Sjkim# define CTXDBG_EXIT(ctx) do { \ 183280304Sjkim fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ 184280304Sjkim ctxdbg(ctx); \ 185280304Sjkim } while(0) 186280304Sjkim# define CTXDBG_RET(ctx,ret) 187160814Ssimon#else 188280304Sjkim# define CTXDBG_ENTRY(str, ctx) 189280304Sjkim# define CTXDBG_EXIT(ctx) 190280304Sjkim# define CTXDBG_RET(ctx,ret) 191160814Ssimon#endif 19259191Skris 193280304Sjkim/* 194280304Sjkim * This function is an evil legacy and should not be used. This 195280304Sjkim * implementation is WYSIWYG, though I've done my best. 196280304Sjkim */ 197160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 19859191Skrisvoid BN_CTX_init(BN_CTX *ctx) 199280304Sjkim{ 200280304Sjkim /* 201280304Sjkim * Assume the caller obtained the context via BN_CTX_new() and so is 202280304Sjkim * trying to reset it for use. Nothing else makes sense, least of all 203280304Sjkim * binary compatibility from a time when they could declare a static 204280304Sjkim * variable. 205280304Sjkim */ 206280304Sjkim BN_POOL_reset(&ctx->pool); 207280304Sjkim BN_STACK_reset(&ctx->stack); 208280304Sjkim ctx->used = 0; 209280304Sjkim ctx->err_stack = 0; 210280304Sjkim ctx->too_many = 0; 211280304Sjkim} 212109998Smarkm#endif 213160814Ssimon 214160814SsimonBN_CTX *BN_CTX_new(void) 215280304Sjkim{ 216280304Sjkim BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); 217280304Sjkim if (!ret) { 218280304Sjkim BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE); 219280304Sjkim return NULL; 220280304Sjkim } 221280304Sjkim /* Initialise the structure */ 222280304Sjkim BN_POOL_init(&ret->pool); 223280304Sjkim BN_STACK_init(&ret->stack); 224280304Sjkim ret->used = 0; 225280304Sjkim ret->err_stack = 0; 226280304Sjkim ret->too_many = 0; 227280304Sjkim return ret; 228280304Sjkim} 22959191Skris 23059191Skrisvoid BN_CTX_free(BN_CTX *ctx) 231280304Sjkim{ 232280304Sjkim if (ctx == NULL) 233280304Sjkim return; 234160814Ssimon#ifdef BN_CTX_DEBUG 235280304Sjkim { 236280304Sjkim BN_POOL_ITEM *pool = ctx->pool.head; 237280304Sjkim fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n", 238280304Sjkim ctx->stack.size, ctx->pool.size); 239280304Sjkim fprintf(stderr, "dmaxs: "); 240280304Sjkim while (pool) { 241280304Sjkim unsigned loop = 0; 242280304Sjkim while (loop < BN_CTX_POOL_SIZE) 243280304Sjkim fprintf(stderr, "%02x ", pool->vals[loop++].dmax); 244280304Sjkim pool = pool->next; 245280304Sjkim } 246280304Sjkim fprintf(stderr, "\n"); 247280304Sjkim } 248160814Ssimon#endif 249280304Sjkim BN_STACK_finish(&ctx->stack); 250280304Sjkim BN_POOL_finish(&ctx->pool); 251280304Sjkim OPENSSL_free(ctx); 252280304Sjkim} 25359191Skris 25459191Skrisvoid BN_CTX_start(BN_CTX *ctx) 255280304Sjkim{ 256280304Sjkim CTXDBG_ENTRY("BN_CTX_start", ctx); 257280304Sjkim /* If we're already overflowing ... */ 258280304Sjkim if (ctx->err_stack || ctx->too_many) 259280304Sjkim ctx->err_stack++; 260280304Sjkim /* (Try to) get a new frame pointer */ 261280304Sjkim else if (!BN_STACK_push(&ctx->stack, ctx->used)) { 262280304Sjkim BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 263280304Sjkim ctx->err_stack++; 264280304Sjkim } 265280304Sjkim CTXDBG_EXIT(ctx); 266280304Sjkim} 26759191Skris 268160814Ssimonvoid BN_CTX_end(BN_CTX *ctx) 269280304Sjkim{ 270280304Sjkim CTXDBG_ENTRY("BN_CTX_end", ctx); 271280304Sjkim if (ctx->err_stack) 272280304Sjkim ctx->err_stack--; 273280304Sjkim else { 274280304Sjkim unsigned int fp = BN_STACK_pop(&ctx->stack); 275280304Sjkim /* Does this stack frame have anything to release? */ 276280304Sjkim if (fp < ctx->used) 277280304Sjkim BN_POOL_release(&ctx->pool, ctx->used - fp); 278280304Sjkim ctx->used = fp; 279280304Sjkim /* Unjam "too_many" in case "get" had failed */ 280280304Sjkim ctx->too_many = 0; 281280304Sjkim } 282280304Sjkim CTXDBG_EXIT(ctx); 283280304Sjkim} 284109998Smarkm 28559191SkrisBIGNUM *BN_CTX_get(BN_CTX *ctx) 286280304Sjkim{ 287280304Sjkim BIGNUM *ret; 288280304Sjkim CTXDBG_ENTRY("BN_CTX_get", ctx); 289280304Sjkim if (ctx->err_stack || ctx->too_many) 290280304Sjkim return NULL; 291280304Sjkim if ((ret = BN_POOL_get(&ctx->pool)) == NULL) { 292280304Sjkim /* 293280304Sjkim * Setting too_many prevents repeated "get" attempts from cluttering 294280304Sjkim * the error stack. 295280304Sjkim */ 296280304Sjkim ctx->too_many = 1; 297280304Sjkim BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES); 298280304Sjkim return NULL; 299280304Sjkim } 300280304Sjkim /* OK, make sure the returned bignum is "zero" */ 301280304Sjkim BN_zero(ret); 302280304Sjkim ctx->used++; 303280304Sjkim CTXDBG_RET(ctx, ret); 304280304Sjkim return ret; 305280304Sjkim} 306160814Ssimon 307160814Ssimon/************/ 308160814Ssimon/* BN_STACK */ 309160814Ssimon/************/ 310160814Ssimon 311160814Ssimonstatic void BN_STACK_init(BN_STACK *st) 312280304Sjkim{ 313280304Sjkim st->indexes = NULL; 314280304Sjkim st->depth = st->size = 0; 315280304Sjkim} 316160814Ssimon 317160814Ssimonstatic void BN_STACK_finish(BN_STACK *st) 318280304Sjkim{ 319280304Sjkim if (st->size) 320280304Sjkim OPENSSL_free(st->indexes); 321280304Sjkim} 322160814Ssimon 323160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 324160814Ssimonstatic void BN_STACK_reset(BN_STACK *st) 325280304Sjkim{ 326280304Sjkim st->depth = 0; 327280304Sjkim} 328160814Ssimon#endif 329160814Ssimon 330160814Ssimonstatic int BN_STACK_push(BN_STACK *st, unsigned int idx) 331280304Sjkim{ 332280304Sjkim if (st->depth == st->size) 333280304Sjkim /* Need to expand */ 334280304Sjkim { 335280304Sjkim unsigned int newsize = (st->size ? 336280304Sjkim (st->size * 3 / 2) : BN_CTX_START_FRAMES); 337280304Sjkim unsigned int *newitems = OPENSSL_malloc(newsize * 338280304Sjkim sizeof(unsigned int)); 339280304Sjkim if (!newitems) 340280304Sjkim return 0; 341280304Sjkim if (st->depth) 342280304Sjkim memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int)); 343280304Sjkim if (st->size) 344280304Sjkim OPENSSL_free(st->indexes); 345280304Sjkim st->indexes = newitems; 346280304Sjkim st->size = newsize; 347280304Sjkim } 348280304Sjkim st->indexes[(st->depth)++] = idx; 349280304Sjkim return 1; 350280304Sjkim} 351160814Ssimon 352160814Ssimonstatic unsigned int BN_STACK_pop(BN_STACK *st) 353280304Sjkim{ 354280304Sjkim return st->indexes[--(st->depth)]; 355280304Sjkim} 356160814Ssimon 357160814Ssimon/***********/ 358160814Ssimon/* BN_POOL */ 359160814Ssimon/***********/ 360160814Ssimon 361160814Ssimonstatic void BN_POOL_init(BN_POOL *p) 362280304Sjkim{ 363280304Sjkim p->head = p->current = p->tail = NULL; 364280304Sjkim p->used = p->size = 0; 365280304Sjkim} 366160814Ssimon 367160814Ssimonstatic void BN_POOL_finish(BN_POOL *p) 368280304Sjkim{ 369280304Sjkim while (p->head) { 370280304Sjkim unsigned int loop = 0; 371280304Sjkim BIGNUM *bn = p->head->vals; 372280304Sjkim while (loop++ < BN_CTX_POOL_SIZE) { 373280304Sjkim if (bn->d) 374280304Sjkim BN_clear_free(bn); 375280304Sjkim bn++; 376280304Sjkim } 377280304Sjkim p->current = p->head->next; 378280304Sjkim OPENSSL_free(p->head); 379280304Sjkim p->head = p->current; 380280304Sjkim } 381280304Sjkim} 38259191Skris 383160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 384160814Ssimonstatic void BN_POOL_reset(BN_POOL *p) 385280304Sjkim{ 386280304Sjkim BN_POOL_ITEM *item = p->head; 387280304Sjkim while (item) { 388280304Sjkim unsigned int loop = 0; 389280304Sjkim BIGNUM *bn = item->vals; 390280304Sjkim while (loop++ < BN_CTX_POOL_SIZE) { 391280304Sjkim if (bn->d) 392280304Sjkim BN_clear(bn); 393280304Sjkim bn++; 394280304Sjkim } 395280304Sjkim item = item->next; 396280304Sjkim } 397280304Sjkim p->current = p->head; 398280304Sjkim p->used = 0; 399280304Sjkim} 400160814Ssimon#endif 40159191Skris 402160814Ssimonstatic BIGNUM *BN_POOL_get(BN_POOL *p) 403280304Sjkim{ 404280304Sjkim if (p->used == p->size) { 405280304Sjkim BIGNUM *bn; 406280304Sjkim unsigned int loop = 0; 407280304Sjkim BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); 408280304Sjkim if (!item) 409280304Sjkim return NULL; 410280304Sjkim /* Initialise the structure */ 411280304Sjkim bn = item->vals; 412280304Sjkim while (loop++ < BN_CTX_POOL_SIZE) 413280304Sjkim BN_init(bn++); 414280304Sjkim item->prev = p->tail; 415280304Sjkim item->next = NULL; 416280304Sjkim /* Link it in */ 417280304Sjkim if (!p->head) 418280304Sjkim p->head = p->current = p->tail = item; 419280304Sjkim else { 420280304Sjkim p->tail->next = item; 421280304Sjkim p->tail = item; 422280304Sjkim p->current = item; 423280304Sjkim } 424280304Sjkim p->size += BN_CTX_POOL_SIZE; 425280304Sjkim p->used++; 426280304Sjkim /* Return the first bignum from the new pool */ 427280304Sjkim return item->vals; 428280304Sjkim } 429280304Sjkim if (!p->used) 430280304Sjkim p->current = p->head; 431280304Sjkim else if ((p->used % BN_CTX_POOL_SIZE) == 0) 432280304Sjkim p->current = p->current->next; 433280304Sjkim return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 434280304Sjkim} 435160814Ssimon 436160814Ssimonstatic void BN_POOL_release(BN_POOL *p, unsigned int num) 437280304Sjkim{ 438280304Sjkim unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 439280304Sjkim p->used -= num; 440280304Sjkim while (num--) { 441280304Sjkim bn_check_top(p->current->vals + offset); 442280304Sjkim if (!offset) { 443280304Sjkim offset = BN_CTX_POOL_SIZE - 1; 444280304Sjkim p->current = p->current->prev; 445280304Sjkim } else 446280304Sjkim offset--; 447280304Sjkim } 448280304Sjkim} 449