summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_ctx.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_ctx.c')
-rw-r--r--src/lib/libcrypto/bn/bn_ctx.c315
1 files changed, 166 insertions, 149 deletions
diff --git a/src/lib/libcrypto/bn/bn_ctx.c b/src/lib/libcrypto/bn/bn_ctx.c
index ef67f4781c..7407dade50 100644
--- a/src/lib/libcrypto/bn/bn_ctx.c
+++ b/src/lib/libcrypto/bn/bn_ctx.c
@@ -8,7 +8,7 @@
8 * are met: 8 * are met:
9 * 9 *
10 * 1. Redistributions of source code must retain the above copyright 10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer. 11 * notice, this list of conditions and the following disclaimer.
12 * 12 *
13 * 2. Redistributions in binary form must reproduce the above copyright 13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in 14 * notice, this list of conditions and the following disclaimer in
@@ -88,21 +88,21 @@
88/***********/ 88/***********/
89 89
90/* A bundle of bignums that can be linked with other bundles */ 90/* A bundle of bignums that can be linked with other bundles */
91typedef struct bignum_pool_item 91typedef struct bignum_pool_item {
92 {
93 /* The bignum values */ 92 /* The bignum values */
94 BIGNUM vals[BN_CTX_POOL_SIZE]; 93 BIGNUM vals[BN_CTX_POOL_SIZE];
95 /* Linked-list admin */ 94 /* Linked-list admin */
96 struct bignum_pool_item *prev, *next; 95 struct bignum_pool_item *prev, *next;
97 } BN_POOL_ITEM; 96} BN_POOL_ITEM;
97
98/* A linked-list of bignums grouped in bundles */ 98/* A linked-list of bignums grouped in bundles */
99typedef struct bignum_pool 99typedef struct bignum_pool {
100 {
101 /* Linked-list admin */ 100 /* Linked-list admin */
102 BN_POOL_ITEM *head, *current, *tail; 101 BN_POOL_ITEM *head, *current, *tail;
103 /* Stack depth and allocation size */ 102 /* Stack depth and allocation size */
104 unsigned used, size; 103 unsigned used, size;
105 } BN_POOL; 104} BN_POOL;
105
106static void BN_POOL_init(BN_POOL *); 106static void BN_POOL_init(BN_POOL *);
107static void BN_POOL_finish(BN_POOL *); 107static void BN_POOL_finish(BN_POOL *);
108#ifndef OPENSSL_NO_DEPRECATED 108#ifndef OPENSSL_NO_DEPRECATED
@@ -116,13 +116,13 @@ static void BN_POOL_release(BN_POOL *, unsigned int);
116/************/ 116/************/
117 117
118/* A wrapper to manage the "stack frames" */ 118/* A wrapper to manage the "stack frames" */
119typedef struct bignum_ctx_stack 119typedef struct bignum_ctx_stack {
120 {
121 /* Array of indexes into the bignum stack */ 120 /* Array of indexes into the bignum stack */
122 unsigned int *indexes; 121 unsigned int *indexes;
123 /* Number of stack frames, and the size of the allocated array */ 122 /* Number of stack frames, and the size of the allocated array */
124 unsigned int depth, size; 123 unsigned int depth, size;
125 } BN_STACK; 124} BN_STACK;
125
126static void BN_STACK_init(BN_STACK *); 126static void BN_STACK_init(BN_STACK *);
127static void BN_STACK_finish(BN_STACK *); 127static void BN_STACK_finish(BN_STACK *);
128#ifndef OPENSSL_NO_DEPRECATED 128#ifndef OPENSSL_NO_DEPRECATED
@@ -136,8 +136,7 @@ static unsigned int BN_STACK_pop(BN_STACK *);
136/**********/ 136/**********/
137 137
138/* The opaque BN_CTX type */ 138/* The opaque BN_CTX type */
139struct bignum_ctx 139struct bignum_ctx {
140 {
141 /* The bignum bundles */ 140 /* The bignum bundles */
142 BN_POOL pool; 141 BN_POOL pool;
143 /* The "stack frames", if you will */ 142 /* The "stack frames", if you will */
@@ -148,36 +147,38 @@ struct bignum_ctx
148 int err_stack; 147 int err_stack;
149 /* Block "gets" until an "end" (compatibility behaviour) */ 148 /* Block "gets" until an "end" (compatibility behaviour) */
150 int too_many; 149 int too_many;
151 }; 150};
152 151
153/* Enable this to find BN_CTX bugs */ 152/* Enable this to find BN_CTX bugs */
154#ifdef BN_CTX_DEBUG 153#ifdef BN_CTX_DEBUG
155static const char *ctxdbg_cur = NULL; 154static const char *ctxdbg_cur = NULL;
156static void ctxdbg(BN_CTX *ctx) 155
157 { 156static void
157ctxdbg(BN_CTX *ctx)
158{
158 unsigned int bnidx = 0, fpidx = 0; 159 unsigned int bnidx = 0, fpidx = 0;
159 BN_POOL_ITEM *item = ctx->pool.head; 160 BN_POOL_ITEM *item = ctx->pool.head;
160 BN_STACK *stack = &ctx->stack; 161 BN_STACK *stack = &ctx->stack;
161 fprintf(stderr,"(%08x): ", (unsigned int)ctx); 162
162 while(bnidx < ctx->used) 163 fprintf(stderr, "(%08x): ", (unsigned int)ctx);
163 { 164 while (bnidx < ctx->used) {
164 fprintf(stderr,"%03x ", item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax); 165 fprintf(stderr, "%03x ",
165 if(!(bnidx % BN_CTX_POOL_SIZE)) 166 item->vals[bnidx++ % BN_CTX_POOL_SIZE].dmax);
167 if (!(bnidx % BN_CTX_POOL_SIZE))
166 item = item->next; 168 item = item->next;
167 } 169 }
168 fprintf(stderr,"\n"); 170 fprintf(stderr, "\n");
169 bnidx = 0; 171 bnidx = 0;
170 fprintf(stderr," : "); 172 fprintf(stderr, " : ");
171 while(fpidx < stack->depth) 173 while (fpidx < stack->depth) {
172 { 174 while (bnidx++ < stack->indexes[fpidx])
173 while(bnidx++ < stack->indexes[fpidx]) 175 fprintf(stderr, " ");
174 fprintf(stderr," "); 176 fprintf(stderr, "^^^ ");
175 fprintf(stderr,"^^^ ");
176 bnidx++; 177 bnidx++;
177 fpidx++; 178 fpidx++;
178 }
179 fprintf(stderr,"\n");
180 } 179 }
180 fprintf(stderr, "\n");
181}
181#define CTXDBG_ENTRY(str, ctx) do { \ 182#define CTXDBG_ENTRY(str, ctx) do { \
182 ctxdbg_cur = (str); \ 183 ctxdbg_cur = (str); \
183 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \ 184 fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
@@ -197,8 +198,9 @@ static void ctxdbg(BN_CTX *ctx)
197/* This function is an evil legacy and should not be used. This implementation 198/* This function is an evil legacy and should not be used. This implementation
198 * is WYSIWYG, though I've done my best. */ 199 * is WYSIWYG, though I've done my best. */
199#ifndef OPENSSL_NO_DEPRECATED 200#ifndef OPENSSL_NO_DEPRECATED
200void BN_CTX_init(BN_CTX *ctx) 201void
201 { 202BN_CTX_init(BN_CTX *ctx)
203{
202 /* Assume the caller obtained the context via BN_CTX_new() and so is 204 /* Assume the caller obtained the context via BN_CTX_new() and so is
203 * trying to reset it for use. Nothing else makes sense, least of all 205 * trying to reset it for use. Nothing else makes sense, least of all
204 * binary compatibility from a time when they could declare a static 206 * binary compatibility from a time when they could declare a static
@@ -208,17 +210,18 @@ void BN_CTX_init(BN_CTX *ctx)
208 ctx->used = 0; 210 ctx->used = 0;
209 ctx->err_stack = 0; 211 ctx->err_stack = 0;
210 ctx->too_many = 0; 212 ctx->too_many = 0;
211 } 213}
212#endif 214#endif
213 215
214BN_CTX *BN_CTX_new(void) 216BN_CTX *
215 { 217BN_CTX_new(void)
218{
216 BN_CTX *ret = malloc(sizeof(BN_CTX)); 219 BN_CTX *ret = malloc(sizeof(BN_CTX));
217 if(!ret) 220 if (!ret) {
218 { 221 BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
219 BNerr(BN_F_BN_CTX_NEW,ERR_R_MALLOC_FAILURE);
220 return NULL; 222 return NULL;
221 } 223 }
224
222 /* Initialise the structure */ 225 /* Initialise the structure */
223 BN_POOL_init(&ret->pool); 226 BN_POOL_init(&ret->pool);
224 BN_STACK_init(&ret->stack); 227 BN_STACK_init(&ret->stack);
@@ -226,229 +229,243 @@ BN_CTX *BN_CTX_new(void)
226 ret->err_stack = 0; 229 ret->err_stack = 0;
227 ret->too_many = 0; 230 ret->too_many = 0;
228 return ret; 231 return ret;
229 } 232}
230 233
231void BN_CTX_free(BN_CTX *ctx) 234void
232 { 235BN_CTX_free(BN_CTX *ctx)
236{
233 if (ctx == NULL) 237 if (ctx == NULL)
234 return; 238 return;
235#ifdef BN_CTX_DEBUG 239#ifdef BN_CTX_DEBUG
236 { 240 {
237 BN_POOL_ITEM *pool = ctx->pool.head; 241 BN_POOL_ITEM *pool = ctx->pool.head;
238 fprintf(stderr,"BN_CTX_free, stack-size=%d, pool-bignums=%d\n", 242 fprintf(stderr, "BN_CTX_free, stack-size=%d, pool-bignums=%d\n",
239 ctx->stack.size, ctx->pool.size); 243 ctx->stack.size, ctx->pool.size);
240 fprintf(stderr,"dmaxs: "); 244 fprintf(stderr, "dmaxs: ");
241 while(pool) { 245 while (pool) {
242 unsigned loop = 0; 246 unsigned loop = 0;
243 while(loop < BN_CTX_POOL_SIZE) 247 while (loop < BN_CTX_POOL_SIZE)
244 fprintf(stderr,"%02x ", pool->vals[loop++].dmax); 248 fprintf(stderr, "%02x ",
245 pool = pool->next; 249 pool->vals[loop++].dmax);
246 } 250 pool = pool->next;
247 fprintf(stderr,"\n"); 251 }
252 fprintf(stderr, "\n");
248 } 253 }
249#endif 254#endif
250 BN_STACK_finish(&ctx->stack); 255 BN_STACK_finish(&ctx->stack);
251 BN_POOL_finish(&ctx->pool); 256 BN_POOL_finish(&ctx->pool);
252 free(ctx); 257 free(ctx);
253 } 258}
254 259
255void BN_CTX_start(BN_CTX *ctx) 260void
256 { 261BN_CTX_start(BN_CTX *ctx)
262{
257 CTXDBG_ENTRY("BN_CTX_start", ctx); 263 CTXDBG_ENTRY("BN_CTX_start", ctx);
264
258 /* If we're already overflowing ... */ 265 /* If we're already overflowing ... */
259 if(ctx->err_stack || ctx->too_many) 266 if (ctx->err_stack || ctx->too_many)
260 ctx->err_stack++; 267 ctx->err_stack++;
261 /* (Try to) get a new frame pointer */ 268 /* (Try to) get a new frame pointer */
262 else if(!BN_STACK_push(&ctx->stack, ctx->used)) 269 else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
263 { 270 BNerr(BN_F_BN_CTX_START, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
264 BNerr(BN_F_BN_CTX_START,BN_R_TOO_MANY_TEMPORARY_VARIABLES);
265 ctx->err_stack++; 271 ctx->err_stack++;
266 }
267 CTXDBG_EXIT(ctx);
268 } 272 }
273 CTXDBG_EXIT(ctx);
274}
269 275
270void BN_CTX_end(BN_CTX *ctx) 276void
271 { 277BN_CTX_end(BN_CTX *ctx)
278{
272 CTXDBG_ENTRY("BN_CTX_end", ctx); 279 CTXDBG_ENTRY("BN_CTX_end", ctx);
273 if(ctx->err_stack) 280
281 if (ctx->err_stack)
274 ctx->err_stack--; 282 ctx->err_stack--;
275 else 283 else {
276 {
277 unsigned int fp = BN_STACK_pop(&ctx->stack); 284 unsigned int fp = BN_STACK_pop(&ctx->stack);
278 /* Does this stack frame have anything to release? */ 285 /* Does this stack frame have anything to release? */
279 if(fp < ctx->used) 286 if (fp < ctx->used)
280 BN_POOL_release(&ctx->pool, ctx->used - fp); 287 BN_POOL_release(&ctx->pool, ctx->used - fp);
281 ctx->used = fp; 288 ctx->used = fp;
282 /* Unjam "too_many" in case "get" had failed */ 289 /* Unjam "too_many" in case "get" had failed */
283 ctx->too_many = 0; 290 ctx->too_many = 0;
284 }
285 CTXDBG_EXIT(ctx);
286 } 291 }
292 CTXDBG_EXIT(ctx);
293}
287 294
288BIGNUM *BN_CTX_get(BN_CTX *ctx) 295BIGNUM *
289 { 296BN_CTX_get(BN_CTX *ctx)
297{
290 BIGNUM *ret; 298 BIGNUM *ret;
299
291 CTXDBG_ENTRY("BN_CTX_get", ctx); 300 CTXDBG_ENTRY("BN_CTX_get", ctx);
292 if(ctx->err_stack || ctx->too_many) return NULL; 301
293 if((ret = BN_POOL_get(&ctx->pool)) == NULL) 302 if (ctx->err_stack || ctx->too_many)
294 { 303 return NULL;
304 if ((ret = BN_POOL_get(&ctx->pool)) == NULL) {
295 /* Setting too_many prevents repeated "get" attempts from 305 /* Setting too_many prevents repeated "get" attempts from
296 * cluttering the error stack. */ 306 * cluttering the error stack. */
297 ctx->too_many = 1; 307 ctx->too_many = 1;
298 BNerr(BN_F_BN_CTX_GET,BN_R_TOO_MANY_TEMPORARY_VARIABLES); 308 BNerr(BN_F_BN_CTX_GET, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
299 return NULL; 309 return NULL;
300 } 310 }
301 /* OK, make sure the returned bignum is "zero" */ 311 /* OK, make sure the returned bignum is "zero" */
302 BN_zero(ret); 312 BN_zero(ret);
303 ctx->used++; 313 ctx->used++;
304 CTXDBG_RET(ctx, ret); 314 CTXDBG_RET(ctx, ret);
305 return ret; 315 return ret;
306 } 316}
307 317
308/************/ 318/************/
309/* BN_STACK */ 319/* BN_STACK */
310/************/ 320/************/
311 321
312static void BN_STACK_init(BN_STACK *st) 322static void
313 { 323BN_STACK_init(BN_STACK *st)
324{
314 st->indexes = NULL; 325 st->indexes = NULL;
315 st->depth = st->size = 0; 326 st->depth = st->size = 0;
316 } 327}
317 328
318static void BN_STACK_finish(BN_STACK *st) 329static void
319 { 330BN_STACK_finish(BN_STACK *st)
320 if(st->size) free(st->indexes); 331{
321 } 332 if (st->size)
333 free(st->indexes);
334}
322 335
323#ifndef OPENSSL_NO_DEPRECATED 336#ifndef OPENSSL_NO_DEPRECATED
324static void BN_STACK_reset(BN_STACK *st) 337static void
325 { 338BN_STACK_reset(BN_STACK *st)
339{
326 st->depth = 0; 340 st->depth = 0;
327 } 341}
328#endif 342#endif
329 343
330static int BN_STACK_push(BN_STACK *st, unsigned int idx) 344static int
331 { 345BN_STACK_push(BN_STACK *st, unsigned int idx)
332 if(st->depth == st->size) 346{
347 if (st->depth == st->size)
333 /* Need to expand */ 348 /* Need to expand */
334 { 349 {
335 unsigned int newsize = (st->size ? 350 unsigned int newsize = (st->size ?
336 (st->size * 3 / 2) : BN_CTX_START_FRAMES); 351 (st->size * 3 / 2) : BN_CTX_START_FRAMES);
337 unsigned int *newitems = malloc(newsize * 352 unsigned int *newitems = malloc(newsize *
338 sizeof(unsigned int)); 353 sizeof(unsigned int));
339 if(!newitems) return 0; 354 if (!newitems)
340 if(st->depth) 355 return 0;
356 if (st->depth)
341 memcpy(newitems, st->indexes, st->depth * 357 memcpy(newitems, st->indexes, st->depth *
342 sizeof(unsigned int)); 358 sizeof(unsigned int));
343 if(st->size) free(st->indexes); 359 if (st->size)
360 free(st->indexes);
344 st->indexes = newitems; 361 st->indexes = newitems;
345 st->size = newsize; 362 st->size = newsize;
346 } 363 }
347 st->indexes[(st->depth)++] = idx; 364 st->indexes[(st->depth)++] = idx;
348 return 1; 365 return 1;
349 } 366}
350 367
351static unsigned int BN_STACK_pop(BN_STACK *st) 368static unsigned int
352 { 369BN_STACK_pop(BN_STACK *st)
370{
353 return st->indexes[--(st->depth)]; 371 return st->indexes[--(st->depth)];
354 } 372}
355 373
356/***********/ 374/***********/
357/* BN_POOL */ 375/* BN_POOL */
358/***********/ 376/***********/
359 377
360static void BN_POOL_init(BN_POOL *p) 378static void
361 { 379BN_POOL_init(BN_POOL *p)
380{
362 p->head = p->current = p->tail = NULL; 381 p->head = p->current = p->tail = NULL;
363 p->used = p->size = 0; 382 p->used = p->size = 0;
364 } 383}
365 384
366static void BN_POOL_finish(BN_POOL *p) 385static void
367 { 386BN_POOL_finish(BN_POOL *p)
368 while(p->head) 387{
369 { 388 while (p->head) {
370 unsigned int loop = 0; 389 unsigned int loop = 0;
371 BIGNUM *bn = p->head->vals; 390 BIGNUM *bn = p->head->vals;
372 while(loop++ < BN_CTX_POOL_SIZE) 391 while (loop++ < BN_CTX_POOL_SIZE) {
373 { 392 if (bn->d)
374 if(bn->d) BN_clear_free(bn); 393 BN_clear_free(bn);
375 bn++; 394 bn++;
376 } 395 }
377 p->current = p->head->next; 396 p->current = p->head->next;
378 free(p->head); 397 free(p->head);
379 p->head = p->current; 398 p->head = p->current;
380 }
381 } 399 }
400}
382 401
383#ifndef OPENSSL_NO_DEPRECATED 402#ifndef OPENSSL_NO_DEPRECATED
384static void BN_POOL_reset(BN_POOL *p) 403static void
385 { 404BN_POOL_reset(BN_POOL *p)
405{
386 BN_POOL_ITEM *item = p->head; 406 BN_POOL_ITEM *item = p->head;
387 while(item) 407 while (item) {
388 {
389 unsigned int loop = 0; 408 unsigned int loop = 0;
390 BIGNUM *bn = item->vals; 409 BIGNUM *bn = item->vals;
391 while(loop++ < BN_CTX_POOL_SIZE) 410 while (loop++ < BN_CTX_POOL_SIZE) {
392 { 411 if (bn->d)
393 if(bn->d) BN_clear(bn); 412 BN_clear(bn);
394 bn++; 413 bn++;
395 }
396 item = item->next;
397 } 414 }
415 item = item->next;
416 }
398 p->current = p->head; 417 p->current = p->head;
399 p->used = 0; 418 p->used = 0;
400 } 419}
401#endif 420#endif
402 421
403static BIGNUM *BN_POOL_get(BN_POOL *p) 422static BIGNUM *
404 { 423BN_POOL_get(BN_POOL *p)
405 if(p->used == p->size) 424{
406 { 425 if (p->used == p->size) {
407 BIGNUM *bn; 426 BIGNUM *bn;
408 unsigned int loop = 0; 427 unsigned int loop = 0;
409 BN_POOL_ITEM *item = malloc(sizeof(BN_POOL_ITEM)); 428 BN_POOL_ITEM *item = malloc(sizeof(BN_POOL_ITEM));
410 if(!item) return NULL; 429 if (!item)
430 return NULL;
411 /* Initialise the structure */ 431 /* Initialise the structure */
412 bn = item->vals; 432 bn = item->vals;
413 while(loop++ < BN_CTX_POOL_SIZE) 433 while (loop++ < BN_CTX_POOL_SIZE)
414 BN_init(bn++); 434 BN_init(bn++);
415 item->prev = p->tail; 435 item->prev = p->tail;
416 item->next = NULL; 436 item->next = NULL;
417 /* Link it in */ 437 /* Link it in */
418 if(!p->head) 438 if (!p->head)
419 p->head = p->current = p->tail = item; 439 p->head = p->current = p->tail = item;
420 else 440 else {
421 {
422 p->tail->next = item; 441 p->tail->next = item;
423 p->tail = item; 442 p->tail = item;
424 p->current = item; 443 p->current = item;
425 } 444 }
426 p->size += BN_CTX_POOL_SIZE; 445 p->size += BN_CTX_POOL_SIZE;
427 p->used++; 446 p->used++;
428 /* Return the first bignum from the new pool */ 447 /* Return the first bignum from the new pool */
429 return item->vals; 448 return item->vals;
430 } 449 }
431 if(!p->used) 450 if (!p->used)
432 p->current = p->head; 451 p->current = p->head;
433 else if((p->used % BN_CTX_POOL_SIZE) == 0) 452 else if ((p->used % BN_CTX_POOL_SIZE) == 0)
434 p->current = p->current->next; 453 p->current = p->current->next;
435 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE); 454 return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
436 } 455}
437 456
438static void BN_POOL_release(BN_POOL *p, unsigned int num) 457static void
439 { 458BN_POOL_release(BN_POOL *p, unsigned int num)
459{
440 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE; 460 unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
461
441 p->used -= num; 462 p->used -= num;
442 while(num--) 463 while (num--) {
443 {
444 bn_check_top(p->current->vals + offset); 464 bn_check_top(p->current->vals + offset);
445 if(!offset) 465 if (!offset) {
446 {
447 offset = BN_CTX_POOL_SIZE - 1; 466 offset = BN_CTX_POOL_SIZE - 1;
448 p->current = p->current->prev; 467 p->current = p->current->prev;
449 } 468 } else
450 else
451 offset--; 469 offset--;
452 }
453 } 470 }
454 471}