Rewrite BN_CTX.
While allocating near INT_MAX BIGNUMs or stack frames would never happen, we
should properly handle overflow here. Rewrite it to just be a STACK_OF(BIGNUM)
plus a stack of indices. Also simplify the error-handling. If we make the
errors truly sticky (rather than just sticky per frame), we don't need to keep
track of err_stack and friends.
Thanks to mlbrown for reporting the integer overflows in the original
implementation.
Bug: chromium:942269
Change-Id: Ie9c9baea3eeb82d65d88b1cb1388861f5cd84fe5
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/35328
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
diff --git a/crypto/fipsmodule/bn/ctx.c b/crypto/fipsmodule/bn/ctx.c
index af50de9..1926e80 100644
--- a/crypto/fipsmodule/bn/ctx.c
+++ b/crypto/fipsmodule/bn/ctx.c
@@ -54,6 +54,7 @@
#include <openssl/bn.h>
+#include <assert.h>
#include <string.h>
#include <openssl/err.h>
@@ -62,63 +63,46 @@
#include "../../internal.h"
-// How many bignums are in each "pool item";
-#define BN_CTX_POOL_SIZE 16
// The stack frame info is resizing, set a first-time expansion size;
#define BN_CTX_START_FRAMES 32
-// A bundle of bignums that can be linked with other bundles
-typedef struct bignum_pool_item {
- // The bignum values
- BIGNUM vals[BN_CTX_POOL_SIZE];
- // Linked-list admin
- struct bignum_pool_item *prev, *next;
-} BN_POOL_ITEM;
-
-
-typedef struct bignum_pool {
- // Linked-list admin
- BN_POOL_ITEM *head, *current, *tail;
- // Stack depth and allocation size
- unsigned used, size;
-} BN_POOL;
-
-static void BN_POOL_init(BN_POOL *);
-static void BN_POOL_finish(BN_POOL *);
-static BIGNUM *BN_POOL_get(BN_POOL *);
-static void BN_POOL_release(BN_POOL *, unsigned int);
-
// BN_STACK
-// A wrapper to manage the "stack frames"
-typedef struct bignum_ctx_stack {
- // Array of indexes into the bignum stack
- unsigned int *indexes;
+// A |BN_STACK| is a stack of |size_t| values.
+typedef struct {
+ // Array of indexes into |ctx->bignums|.
+ size_t *indexes;
// Number of stack frames, and the size of the allocated array
- unsigned int depth, size;
+ size_t depth, size;
} BN_STACK;
-static void BN_STACK_init(BN_STACK *);
-static void BN_STACK_finish(BN_STACK *);
-static int BN_STACK_push(BN_STACK *, unsigned int);
-static unsigned int BN_STACK_pop(BN_STACK *);
+static void BN_STACK_init(BN_STACK *);
+static void BN_STACK_cleanup(BN_STACK *);
+static int BN_STACK_push(BN_STACK *, size_t idx);
+static size_t BN_STACK_pop(BN_STACK *);
// BN_CTX
+DEFINE_STACK_OF(BIGNUM)
+
// The opaque BN_CTX type
struct bignum_ctx {
- // The bignum bundles
- BN_POOL pool;
- // The "stack frames", if you will
+ // bignums is the stack of |BIGNUM|s managed by this |BN_CTX|.
+ STACK_OF(BIGNUM) *bignums;
+ // stack is the stack of |BN_CTX_start| frames. It is the value of |used| at
+ // the time |BN_CTX_start| was called.
BN_STACK stack;
- // The number of bignums currently assigned
- unsigned int used;
- // Depth of stack overflow
- int err_stack;
- // Block "gets" until an "end" (compatibility behaviour)
- int too_many;
+ // used is the number of |BIGNUM|s from |bignums| that have been used.
+ size_t used;
+ // error is one if any operation on this |BN_CTX| failed. All subsequent
+ // operations will fail.
+ char error;
+ // defer_error is one if an operation on this |BN_CTX| has failed, but no
+ // error has been pushed to the queue yet. This is used to defer errors from
+ // |BN_CTX_start| to |BN_CTX_get|.
+ char defer_error;
};
BN_CTX *BN_CTX_new(void) {
@@ -129,11 +113,11 @@
}
// Initialise the structure
- BN_POOL_init(&ret->pool);
+ ret->bignums = NULL;
BN_STACK_init(&ret->stack);
ret->used = 0;
- ret->err_stack = 0;
- ret->too_many = 0;
+ ret->error = 0;
+ ret->defer_error = 0;
return ret;
}
@@ -142,57 +126,69 @@
return;
}
- BN_STACK_finish(&ctx->stack);
- BN_POOL_finish(&ctx->pool);
+ sk_BIGNUM_pop_free(ctx->bignums, BN_free);
+ BN_STACK_cleanup(&ctx->stack);
OPENSSL_free(ctx);
}
void BN_CTX_start(BN_CTX *ctx) {
- // If we're already overflowing ...
- if (ctx->err_stack || ctx->too_many) {
- ctx->err_stack++;
- } else if (!BN_STACK_push(&ctx->stack, ctx->used)) {
- // (Try to) get a new frame pointer
- OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
- ctx->err_stack++;
+ if (ctx->error) {
+ // Once an operation has failed, |ctx->stack| no longer matches the number
+ // of |BN_CTX_end| calls to come. Do nothing.
+ return;
+ }
+
+ if (!BN_STACK_push(&ctx->stack, ctx->used)) {
+ ctx->error = 1;
+ // |BN_CTX_start| cannot fail, so defer the error to |BN_CTX_get|.
+ ctx->defer_error = 1;
}
}
BIGNUM *BN_CTX_get(BN_CTX *ctx) {
- BIGNUM *ret;
- if (ctx->err_stack || ctx->too_many) {
+ // Once any operation has failed, they all do.
+ if (ctx->error) {
+ if (ctx->defer_error) {
+ OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
+ ctx->defer_error = 0;
+ }
return NULL;
}
- ret = BN_POOL_get(&ctx->pool);
- if (ret == NULL) {
- // Setting too_many prevents repeated "get" attempts from
- // cluttering the error stack.
- ctx->too_many = 1;
- OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
- return NULL;
+ if (ctx->bignums == NULL) {
+ ctx->bignums = sk_BIGNUM_new_null();
+ if (ctx->bignums == NULL) {
+ OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
+ ctx->error = 1;
+ return NULL;
+ }
}
- // OK, make sure the returned bignum is "zero"
+ if (ctx->used == sk_BIGNUM_num(ctx->bignums)) {
+ BIGNUM *bn = BN_new();
+ if (bn == NULL || !sk_BIGNUM_push(ctx->bignums, bn)) {
+ OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES);
+ BN_free(bn);
+ ctx->error = 1;
+ return NULL;
+ }
+ }
+
+ BIGNUM *ret = sk_BIGNUM_value(ctx->bignums, ctx->used);
BN_zero(ret);
+ // This is bounded by |sk_BIGNUM_num|, so it cannot overflow.
ctx->used++;
return ret;
}
void BN_CTX_end(BN_CTX *ctx) {
- if (ctx->err_stack) {
- ctx->err_stack--;
- } else {
- unsigned int fp = BN_STACK_pop(&ctx->stack);
- // Does this stack frame have anything to release?
- if (fp < ctx->used) {
- BN_POOL_release(&ctx->pool, ctx->used - fp);
- }
-
- ctx->used = fp;
- // Unjam "too_many" in case "get" had failed
- ctx->too_many = 0;
+ if (ctx->error) {
+ // Once an operation has failed, |ctx->stack| no longer matches the number
+ // of |BN_CTX_end| calls to come. Do nothing.
+ return;
}
+
+ ctx->used = BN_STACK_pop(&ctx->stack);
}
@@ -203,101 +199,34 @@
st->depth = st->size = 0;
}
-static void BN_STACK_finish(BN_STACK *st) {
+static void BN_STACK_cleanup(BN_STACK *st) {
OPENSSL_free(st->indexes);
}
-static int BN_STACK_push(BN_STACK *st, unsigned int idx) {
+static int BN_STACK_push(BN_STACK *st, size_t idx) {
if (st->depth == st->size) {
- // Need to expand
- unsigned int newsize =
- (st->size ? (st->size * 3 / 2) : BN_CTX_START_FRAMES);
- unsigned int *newitems = OPENSSL_malloc(newsize * sizeof(unsigned int));
- if (!newitems) {
+ // This function intentionally does not push to the error queue on error.
+ // Error-reporting is deferred to |BN_CTX_get|.
+ size_t new_size = st->size != 0 ? st->size * 3 / 2 : BN_CTX_START_FRAMES;
+ if (new_size <= st->size || new_size > ((size_t)-1) / sizeof(size_t)) {
return 0;
}
- if (st->depth) {
- OPENSSL_memcpy(newitems, st->indexes, st->depth * sizeof(unsigned int));
+ size_t *new_indexes =
+ OPENSSL_realloc(st->indexes, new_size * sizeof(size_t));
+ if (new_indexes == NULL) {
+ return 0;
}
- OPENSSL_free(st->indexes);
- st->indexes = newitems;
- st->size = newsize;
+ st->indexes = new_indexes;
+ st->size = new_size;
}
- st->indexes[(st->depth)++] = idx;
+ st->indexes[st->depth] = idx;
+ st->depth++;
return 1;
}
-static unsigned int BN_STACK_pop(BN_STACK *st) {
- return st->indexes[--(st->depth)];
-}
-
-
-static void BN_POOL_init(BN_POOL *p) {
- p->head = p->current = p->tail = NULL;
- p->used = p->size = 0;
-}
-
-static void BN_POOL_finish(BN_POOL *p) {
- while (p->head) {
- for (size_t i = 0; i < BN_CTX_POOL_SIZE; i++) {
- BN_clear_free(&p->head->vals[i]);
- }
-
- p->current = p->head->next;
- OPENSSL_free(p->head);
- p->head = p->current;
- }
-}
-
-static BIGNUM *BN_POOL_get(BN_POOL *p) {
- if (p->used == p->size) {
- BN_POOL_ITEM *item = OPENSSL_malloc(sizeof(BN_POOL_ITEM));
- if (!item) {
- return NULL;
- }
-
- // Initialise the structure
- for (size_t i = 0; i < BN_CTX_POOL_SIZE; i++) {
- BN_init(&item->vals[i]);
- }
-
- item->prev = p->tail;
- item->next = NULL;
- // Link it in
- if (!p->head) {
- p->head = p->current = p->tail = item;
- } else {
- p->tail->next = item;
- p->tail = item;
- p->current = item;
- }
-
- p->size += BN_CTX_POOL_SIZE;
- p->used++;
- // Return the first bignum from the new pool
- return item->vals;
- }
-
- if (!p->used) {
- p->current = p->head;
- } else if ((p->used % BN_CTX_POOL_SIZE) == 0) {
- p->current = p->current->next;
- }
-
- return p->current->vals + ((p->used++) % BN_CTX_POOL_SIZE);
-}
-
-static void BN_POOL_release(BN_POOL *p, unsigned int num) {
- unsigned int offset = (p->used - 1) % BN_CTX_POOL_SIZE;
- p->used -= num;
-
- while (num--) {
- if (!offset) {
- offset = BN_CTX_POOL_SIZE - 1;
- p->current = p->current->prev;
- } else {
- offset--;
- }
- }
+static size_t BN_STACK_pop(BN_STACK *st) {
+ assert(st->depth > 0);
+ st->depth--;
+ return st->indexes[st->depth];
}
