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 1159191Skris * 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) 58160814Ssimon#ifndef NDEBUG 59160814Ssimon#define NDEBUG 6059191Skris#endif 61160814Ssimon#endif 6259191Skris 6359191Skris#include <stdio.h> 6459191Skris#include <assert.h> 65109998Smarkm 6659191Skris#include "cryptlib.h" 67109998Smarkm#include "bn_lcl.h" 6859191Skris 69160814Ssimon/* TODO list 70160814Ssimon * 71160814Ssimon * 1. Check a bunch of "(words+1)" type hacks in various bignum functions and 72160814Ssimon * check they can be safely removed. 73160814Ssimon * - Check +1 and other ugliness in BN_from_montgomery() 74160814Ssimon * 75160814Ssimon * 2. Consider allowing a BN_new_ex() that, at least, lets you specify an 76160814Ssimon * appropriate 'block' size that will be honoured by bn_expand_internal() to 77160814Ssimon * prevent piddly little reallocations. OTOH, profiling bignum expansions in 78160814Ssimon * BN_CTX doesn't show this to be a big issue. 79160814Ssimon */ 8059191Skris 81160814Ssimon/* How many bignums are in each "pool item"; */ 82160814Ssimon#define BN_CTX_POOL_SIZE 16 83160814Ssimon/* The stack frame info is resizing, set a first-time expansion size; */ 84160814Ssimon#define BN_CTX_START_FRAMES 32 85160814Ssimon 86160814Ssimon/***********/ 87160814Ssimon/* BN_POOL */ 88160814Ssimon/***********/ 89160814Ssimon 90160814Ssimon/* A bundle of bignums that can be linked with other bundles */ 91160814Ssimontypedef struct bignum_pool_item 9259191Skris { 93160814Ssimon /* The bignum values */ 94160814Ssimon BIGNUM vals[BN_CTX_POOL_SIZE]; 95160814Ssimon /* Linked-list admin */ 96160814Ssimon struct bignum_pool_item *prev, *next; 97160814Ssimon } BN_POOL_ITEM; 98160814Ssimon/* A linked-list of bignums grouped in bundles */ 99160814Ssimontypedef struct bignum_pool 100160814Ssimon { 101160814Ssimon /* Linked-list admin */ 102160814Ssimon BN_POOL_ITEM *head, *current, *tail; 103160814Ssimon /* Stack depth and allocation size */ 104160814Ssimon unsigned used, size; 105160814Ssimon } BN_POOL; 106160814Ssimonstatic void BN_POOL_init(BN_POOL *); 107160814Ssimonstatic void BN_POOL_finish(BN_POOL *); 108160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 109160814Ssimonstatic void BN_POOL_reset(BN_POOL *); 110160814Ssimon#endif 111160814Ssimonstatic BIGNUM * BN_POOL_get(BN_POOL *); 112160814Ssimonstatic void BN_POOL_release(BN_POOL *, unsigned int); 11359191Skris 114160814Ssimon/************/ 115160814Ssimon/* BN_STACK */ 116160814Ssimon/************/ 117160814Ssimon 118160814Ssimon/* A wrapper to manage the "stack frames" */ 119160814Ssimontypedef struct bignum_ctx_stack 120160814Ssimon { 121160814Ssimon /* Array of indexes into the bignum stack */ 122160814Ssimon unsigned int *indexes; 123160814Ssimon /* Number of stack frames, and the size of the allocated array */ 124160814Ssimon unsigned int depth, size; 125160814Ssimon } BN_STACK; 126160814Ssimonstatic void BN_STACK_init(BN_STACK *); 127160814Ssimonstatic void BN_STACK_finish(BN_STACK *); 128160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 129160814Ssimonstatic void BN_STACK_reset(BN_STACK *); 130160814Ssimon#endif 131160814Ssimonstatic int BN_STACK_push(BN_STACK *, unsigned int); 132160814Ssimonstatic unsigned int BN_STACK_pop(BN_STACK *); 133160814Ssimon 134160814Ssimon/**********/ 135160814Ssimon/* BN_CTX */ 136160814Ssimon/**********/ 137160814Ssimon 138160814Ssimon/* The opaque BN_CTX type */ 139160814Ssimonstruct bignum_ctx 140160814Ssimon { 141160814Ssimon /* The bignum bundles */ 142160814Ssimon BN_POOL pool; 143160814Ssimon /* The "stack frames", if you will */ 144160814Ssimon BN_STACK stack; 145160814Ssimon /* The number of bignums currently assigned */ 146160814Ssimon unsigned int used; 147160814Ssimon /* Depth of stack overflow */ 148160814Ssimon int err_stack; 149160814Ssimon /* Block "gets" until an "end" (compatibility behaviour) */ 150160814Ssimon int too_many; 151160814Ssimon }; 152160814Ssimon 153160814Ssimon/* Enable this to find BN_CTX bugs */ 154160814Ssimon#ifdef BN_CTX_DEBUG 155160814Ssimonstatic const char *ctxdbg_cur = NULL; 156160814Ssimonstatic void ctxdbg(BN_CTX *ctx) 157160814Ssimon { 158160814Ssimon unsigned int bnidx = 0, fpidx = 0; 159160814Ssimon BN_POOL_ITEM *item = ctx->pool.head; 160160814Ssimon BN_STACK *stack = &ctx->stack; 161279264Sdelphij fprintf(stderr,"(%16p): ", ctx); 162160814Ssimon while(bnidx < ctx->used) 16359191Skris { 164238405Sjkim fprintf(stderr,"%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 165160814Ssimon if(!(bnidx % BN_CTX_POOL_SIZE)) 166160814Ssimon item = item->next; 16759191Skris } 168160814Ssimon fprintf(stderr,"\n"); 169160814Ssimon bnidx = 0; 170160814Ssimon fprintf(stderr," : "); 171160814Ssimon while(fpidx < stack->depth) 172160814Ssimon { 173160814Ssimon while(bnidx++ < stack->indexes[fpidx]) 174238405Sjkim fprintf(stderr," "); 175238405Sjkim fprintf(stderr,"^^^ "); 176160814Ssimon bnidx++; 177160814Ssimon fpidx++; 178160814Ssimon } 179160814Ssimon fprintf(stderr,"\n"); 18059191Skris } 181160814Ssimon#define CTXDBG_ENTRY(str, ctx) do { \ 182160814Ssimon ctxdbg_cur = (str); \ 183160814Ssimon fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ 184160814Ssimon ctxdbg(ctx); \ 185160814Ssimon } while(0) 186160814Ssimon#define CTXDBG_EXIT(ctx) do { \ 187160814Ssimon fprintf(stderr,"Ending %s\n", ctxdbg_cur); \ 188160814Ssimon ctxdbg(ctx); \ 189160814Ssimon } while(0) 190160814Ssimon#define CTXDBG_RET(ctx,ret) 191160814Ssimon#else 192160814Ssimon#define CTXDBG_ENTRY(str, ctx) 193160814Ssimon#define CTXDBG_EXIT(ctx) 194160814Ssimon#define CTXDBG_RET(ctx,ret) 195160814Ssimon#endif 19659191Skris 197160814Ssimon/* This function is an evil legacy and should not be used. This implementation 198160814Ssimon * is WYSIWYG, though I've done my best. */ 199160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 20059191Skrisvoid BN_CTX_init(BN_CTX *ctx) 20159191Skris { 202160814Ssimon /* Assume the caller obtained the context via BN_CTX_new() and so is 203160814Ssimon * trying to reset it for use. Nothing else makes sense, least of all 204160814Ssimon * binary compatibility from a time when they could declare a static 205160814Ssimon * variable. */ 206160814Ssimon BN_POOL_reset(&ctx->pool); 207160814Ssimon BN_STACK_reset(&ctx->stack); 208160814Ssimon ctx->used = 0; 209160814Ssimon ctx->err_stack = 0; 21059191Skris ctx->too_many = 0; 211160814Ssimon } 212109998Smarkm#endif 213160814Ssimon 214160814SsimonBN_CTX *BN_CTX_new(void) 215160814Ssimon { 216160814Ssimon BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); 217160814Ssimon if(!ret) 218160814Ssimon { 219160814Ssimon BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE); 220160814Ssimon return NULL; 221160814Ssimon } 222160814Ssimon /* Initialise the structure */ 223160814Ssimon BN_POOL_init(&ret->pool); 224160814Ssimon BN_STACK_init(&ret->stack); 225160814Ssimon ret->used = 0; 226160814Ssimon ret->err_stack = 0; 227160814Ssimon ret->too_many = 0; 228160814Ssimon return ret; 22959191Skris } 23059191Skris 23159191Skrisvoid BN_CTX_free(BN_CTX *ctx) 23259191Skris { 233160814Ssimon if (ctx == NULL) 234160814Ssimon return; 235160814Ssimon#ifdef BN_CTX_DEBUG 236160814Ssimon { 237160814Ssimon BN_POOL_ITEM *pool = ctx->pool.head; 238160814Ssimon fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n", 239160814Ssimon ctx->stack.size, ctx->pool.size); 240160814Ssimon fprintf(stderr,"dmaxs: "); 241160814Ssimon while(pool) { 242160814Ssimon unsigned loop = 0; 243160814Ssimon while(loop < BN_CTX_POOL_SIZE) 244160814Ssimon fprintf(stderr,"%02x ", pool->vals[loop++].dmax); 245160814Ssimon pool = pool->next; 24659191Skris } 247160814Ssimon fprintf(stderr,"\n"); 248160814Ssimon } 249160814Ssimon#endif 250160814Ssimon BN_STACK_finish(&ctx->stack); 251160814Ssimon BN_POOL_finish(&ctx->pool); 252160814Ssimon OPENSSL_free(ctx); 253160814Ssimon } 25459191Skris 25559191Skrisvoid BN_CTX_start(BN_CTX *ctx) 25659191Skris { 257160814Ssimon CTXDBG_ENTRY("BN_CTX_start", ctx); 258160814Ssimon /* If we're already overflowing ... */ 259160814Ssimon if(ctx->err_stack || ctx->too_many) 260160814Ssimon ctx->err_stack++; 261160814Ssimon /* (Try to) get a new frame pointer */ 262160814Ssimon else if(!BN_STACK_push(&ctx->stack, ctx->used)) 263160814Ssimon { 264160814Ssimon BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES); 265160814Ssimon ctx->err_stack++; 266160814Ssimon } 267160814Ssimon CTXDBG_EXIT(ctx); 26859191Skris } 26959191Skris 270160814Ssimonvoid BN_CTX_end(BN_CTX *ctx) 271160814Ssimon { 272160814Ssimon CTXDBG_ENTRY("BN_CTX_end", ctx); 273160814Ssimon if(ctx->err_stack) 274160814Ssimon ctx->err_stack--; 275160814Ssimon else 276160814Ssimon { 277160814Ssimon unsigned int fp = BN_STACK_pop(&ctx->stack); 278160814Ssimon /* Does this stack frame have anything to release? */ 279160814Ssimon if(fp < ctx->used) 280160814Ssimon BN_POOL_release(&ctx->pool, ctx->used - fp); 281160814Ssimon ctx->used = fp; 282160814Ssimon /* Unjam "too_many" in case "get" had failed */ 283160814Ssimon ctx->too_many = 0; 284160814Ssimon } 285160814Ssimon CTXDBG_EXIT(ctx); 286160814Ssimon } 287109998Smarkm 28859191SkrisBIGNUM *BN_CTX_get(BN_CTX *ctx) 28959191Skris { 290160814Ssimon BIGNUM *ret; 291160814Ssimon CTXDBG_ENTRY("BN_CTX_get", ctx); 292160814Ssimon if(ctx->err_stack || ctx->too_many) return NULL; 293160814Ssimon if((ret = BN_POOL_get(&ctx->pool)) == NULL) 29459191Skris { 295160814Ssimon /* Setting too_many prevents repeated "get" attempts from 296160814Ssimon * cluttering the error stack. */ 297160814Ssimon ctx->too_many = 1; 298160814Ssimon BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES); 299160814Ssimon return NULL; 300160814Ssimon } 301160814Ssimon /* OK, make sure the returned bignum is "zero" */ 302160814Ssimon BN_zero(ret); 303160814Ssimon ctx->used++; 304160814Ssimon CTXDBG_RET(ctx, ret); 305160814Ssimon return ret; 306160814Ssimon } 307160814Ssimon 308160814Ssimon/************/ 309160814Ssimon/* BN_STACK */ 310160814Ssimon/************/ 311160814Ssimon 312160814Ssimonstatic void BN_STACK_init(BN_STACK *st) 313160814Ssimon { 314160814Ssimon st->indexes = NULL; 315160814Ssimon st->depth = st->size = 0; 316160814Ssimon } 317160814Ssimon 318160814Ssimonstatic void BN_STACK_finish(BN_STACK *st) 319160814Ssimon { 320160814Ssimon if(st->size) OPENSSL_free(st->indexes); 321160814Ssimon } 322160814Ssimon 323160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 324160814Ssimonstatic void BN_STACK_reset(BN_STACK *st) 325160814Ssimon { 326160814Ssimon st->depth = 0; 327160814Ssimon } 328160814Ssimon#endif 329160814Ssimon 330160814Ssimonstatic int BN_STACK_push(BN_STACK *st, unsigned int idx) 331160814Ssimon { 332160814Ssimon if(st->depth == st->size) 333160814Ssimon /* Need to expand */ 334160814Ssimon { 335160814Ssimon unsigned int newsize = (st->size ? 336160814Ssimon (st->size * 3 / 2) : BN_CTX_START_FRAMES); 337160814Ssimon unsigned int *newitems = OPENSSL_malloc(newsize * 338160814Ssimon sizeof(unsigned int)); 339160814Ssimon if(!newitems) return 0; 340160814Ssimon if(st->depth) 341160814Ssimon memcpy(newitems, st->indexes, st->depth * 342160814Ssimon sizeof(unsigned int)); 343160814Ssimon if(st->size) OPENSSL_free(st->indexes); 344160814Ssimon st->indexes = newitems; 345160814Ssimon st->size = newsize; 346160814Ssimon } 347160814Ssimon st->indexes[(st->depth)++] = idx; 348160814Ssimon return 1; 349160814Ssimon } 350160814Ssimon 351160814Ssimonstatic unsigned int BN_STACK_pop(BN_STACK *st) 352160814Ssimon { 353160814Ssimon return st->indexes[--(st->depth)]; 354160814Ssimon } 355160814Ssimon 356160814Ssimon/***********/ 357160814Ssimon/* BN_POOL */ 358160814Ssimon/***********/ 359160814Ssimon 360160814Ssimonstatic void BN_POOL_init(BN_POOL *p) 361160814Ssimon { 362160814Ssimon p->head = p->current = p->tail = NULL; 363160814Ssimon p->used = p->size = 0; 364160814Ssimon } 365160814Ssimon 366160814Ssimonstatic void BN_POOL_finish(BN_POOL *p) 367160814Ssimon { 368160814Ssimon while(p->head) 369160814Ssimon { 370160814Ssimon unsigned int loop = 0; 371160814Ssimon BIGNUM *bn = p->head->vals; 372160814Ssimon while(loop++ < BN_CTX_POOL_SIZE) 37359191Skris { 374160814Ssimon if(bn->d) BN_clear_free(bn); 375160814Ssimon bn++; 37659191Skris } 377160814Ssimon p->current = p->head->next; 378160814Ssimon OPENSSL_free(p->head); 379160814Ssimon p->head = p->current; 38059191Skris } 38159191Skris } 38259191Skris 383160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 384160814Ssimonstatic void BN_POOL_reset(BN_POOL *p) 38559191Skris { 386160814Ssimon BN_POOL_ITEM *item = p->head; 387160814Ssimon while(item) 388160814Ssimon { 389160814Ssimon unsigned int loop = 0; 390160814Ssimon BIGNUM *bn = item->vals; 391160814Ssimon while(loop++ < BN_CTX_POOL_SIZE) 392160814Ssimon { 393160814Ssimon if(bn->d) BN_clear(bn); 394160814Ssimon bn++; 395160814Ssimon } 396160814Ssimon item = item->next; 397160814Ssimon } 398160814Ssimon p->current = p->head; 399160814Ssimon p->used = 0; 400160814Ssimon } 401160814Ssimon#endif 40259191Skris 403160814Ssimonstatic BIGNUM *BN_POOL_get(BN_POOL *p) 404160814Ssimon { 405160814Ssimon if(p->used == p->size) 406160814Ssimon { 407160814Ssimon BIGNUM *bn; 408160814Ssimon unsigned int loop = 0; 409160814Ssimon BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM)); 410160814Ssimon if(!item) return NULL; 411160814Ssimon /* Initialise the structure */ 412160814Ssimon bn = item->vals; 413160814Ssimon while(loop++ < BN_CTX_POOL_SIZE) 414160814Ssimon BN_init(bn++); 415160814Ssimon item->prev = p->tail; 416160814Ssimon item->next = NULL; 417160814Ssimon /* Link it in */ 418160814Ssimon if(!p->head) 419160814Ssimon p->head = p->current = p->tail = item; 420160814Ssimon else 421160814Ssimon { 422160814Ssimon p->tail->next = item; 423160814Ssimon p->tail = item; 424160814Ssimon p->current = item; 425160814Ssimon } 426160814Ssimon p->size += BN_CTX_POOL_SIZE; 427160814Ssimon p->used++; 428160814Ssimon /* Return the first bignum from the new pool */ 429160814Ssimon return item->vals; 430160814Ssimon } 431160814Ssimon if(!p->used) 432160814Ssimon p->current = p->head; 433160814Ssimon else if((p->used % BN_CTX_POOL_SIZE) == 0) 434160814Ssimon p->current = p->current->next; 435160814Ssimon return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 43659191Skris } 437160814Ssimon 438160814Ssimonstatic void BN_POOL_release(BN_POOL *p, unsigned int num) 439160814Ssimon { 440160814Ssimon unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 441160814Ssimon p->used -= num; 442160814Ssimon while(num--) 443160814Ssimon { 444160814Ssimon bn_check_top(p->current->vals + offset); 445160814Ssimon if(!offset) 446160814Ssimon { 447160814Ssimon offset = BN_CTX_POOL_SIZE - 1; 448160814Ssimon p->current = p->current->prev; 449160814Ssimon } 450160814Ssimon else 451160814Ssimon offset--; 452160814Ssimon } 453160814Ssimon } 454160814Ssimon 455