Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 1 | /* Written by Ulf Moeller for the OpenSSL project. */ |
| 2 | /* ==================================================================== |
| 3 | * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. |
| 4 | * |
| 5 | * Redistribution and use in source and binary forms, with or without |
| 6 | * modification, are permitted provided that the following conditions |
| 7 | * are met: |
| 8 | * |
| 9 | * 1. Redistributions of source code must retain the above copyright |
| 10 | * notice, this list of conditions and the following disclaimer. |
| 11 | * |
| 12 | * 2. Redistributions in binary form must reproduce the above copyright |
| 13 | * notice, this list of conditions and the following disclaimer in |
| 14 | * the documentation and/or other materials provided with the |
| 15 | * distribution. |
| 16 | * |
| 17 | * 3. All advertising materials mentioning features or use of this |
| 18 | * software must display the following acknowledgment: |
| 19 | * "This product includes software developed by the OpenSSL Project |
| 20 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
| 21 | * |
| 22 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
| 23 | * endorse or promote products derived from this software without |
| 24 | * prior written permission. For written permission, please contact |
| 25 | * openssl-core@openssl.org. |
| 26 | * |
| 27 | * 5. Products derived from this software may not be called "OpenSSL" |
| 28 | * nor may "OpenSSL" appear in their names without prior written |
| 29 | * permission of the OpenSSL Project. |
| 30 | * |
| 31 | * 6. Redistributions of any form whatsoever must retain the following |
| 32 | * acknowledgment: |
| 33 | * "This product includes software developed by the OpenSSL Project |
| 34 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
| 35 | * |
| 36 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
| 37 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 38 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
| 39 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
| 40 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 41 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| 42 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| 43 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 44 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| 45 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| 46 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 47 | * OF THE POSSIBILITY OF SUCH DAMAGE. |
| 48 | * ==================================================================== |
| 49 | * |
| 50 | * This product includes cryptographic software written by Eric Young |
| 51 | * (eay@cryptsoft.com). This product includes software written by Tim |
| 52 | * Hudson (tjh@cryptsoft.com). */ |
| 53 | |
| 54 | |
| 55 | #include <openssl/bn.h> |
| 56 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 57 | #include <assert.h> |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 58 | #include <string.h> |
| 59 | |
| 60 | #include <openssl/err.h> |
| 61 | #include <openssl/mem.h> |
| 62 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame] | 63 | #include "../../internal.h" |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 64 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 65 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 66 | // The stack frame info is resizing, set a first-time expansion size; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 67 | #define BN_CTX_START_FRAMES 32 |
| 68 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 69 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 70 | // BN_STACK |
| 71 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 72 | // A |BN_STACK| is a stack of |size_t| values. |
| 73 | typedef struct { |
| 74 | // Array of indexes into |ctx->bignums|. |
| 75 | size_t *indexes; |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 76 | // Number of stack frames, and the size of the allocated array |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 77 | size_t depth, size; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 78 | } BN_STACK; |
| 79 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 80 | static void BN_STACK_init(BN_STACK *); |
| 81 | static void BN_STACK_cleanup(BN_STACK *); |
| 82 | static int BN_STACK_push(BN_STACK *, size_t idx); |
| 83 | static size_t BN_STACK_pop(BN_STACK *); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 84 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 85 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 86 | // BN_CTX |
| 87 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 88 | DEFINE_STACK_OF(BIGNUM) |
| 89 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 90 | // The opaque BN_CTX type |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 91 | struct bignum_ctx { |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 92 | // bignums is the stack of |BIGNUM|s managed by this |BN_CTX|. |
| 93 | STACK_OF(BIGNUM) *bignums; |
| 94 | // stack is the stack of |BN_CTX_start| frames. It is the value of |used| at |
| 95 | // the time |BN_CTX_start| was called. |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 96 | BN_STACK stack; |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 97 | // used is the number of |BIGNUM|s from |bignums| that have been used. |
| 98 | size_t used; |
| 99 | // error is one if any operation on this |BN_CTX| failed. All subsequent |
| 100 | // operations will fail. |
| 101 | char error; |
| 102 | // defer_error is one if an operation on this |BN_CTX| has failed, but no |
| 103 | // error has been pushed to the queue yet. This is used to defer errors from |
| 104 | // |BN_CTX_start| to |BN_CTX_get|. |
| 105 | char defer_error; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 106 | }; |
| 107 | |
| 108 | BN_CTX *BN_CTX_new(void) { |
| 109 | BN_CTX *ret = OPENSSL_malloc(sizeof(BN_CTX)); |
| 110 | if (!ret) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 111 | OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 112 | return NULL; |
| 113 | } |
| 114 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 115 | // Initialise the structure |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 116 | ret->bignums = NULL; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 117 | BN_STACK_init(&ret->stack); |
| 118 | ret->used = 0; |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 119 | ret->error = 0; |
| 120 | ret->defer_error = 0; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 121 | return ret; |
| 122 | } |
| 123 | |
| 124 | void BN_CTX_free(BN_CTX *ctx) { |
| 125 | if (ctx == NULL) { |
| 126 | return; |
| 127 | } |
| 128 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 129 | sk_BIGNUM_pop_free(ctx->bignums, BN_free); |
| 130 | BN_STACK_cleanup(&ctx->stack); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 131 | OPENSSL_free(ctx); |
| 132 | } |
| 133 | |
| 134 | void BN_CTX_start(BN_CTX *ctx) { |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 135 | if (ctx->error) { |
| 136 | // Once an operation has failed, |ctx->stack| no longer matches the number |
| 137 | // of |BN_CTX_end| calls to come. Do nothing. |
| 138 | return; |
| 139 | } |
| 140 | |
| 141 | if (!BN_STACK_push(&ctx->stack, ctx->used)) { |
| 142 | ctx->error = 1; |
| 143 | // |BN_CTX_start| cannot fail, so defer the error to |BN_CTX_get|. |
| 144 | ctx->defer_error = 1; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 145 | } |
| 146 | } |
| 147 | |
| 148 | BIGNUM *BN_CTX_get(BN_CTX *ctx) { |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 149 | // Once any operation has failed, they all do. |
| 150 | if (ctx->error) { |
| 151 | if (ctx->defer_error) { |
| 152 | OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); |
| 153 | ctx->defer_error = 0; |
| 154 | } |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 155 | return NULL; |
| 156 | } |
| 157 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 158 | if (ctx->bignums == NULL) { |
| 159 | ctx->bignums = sk_BIGNUM_new_null(); |
| 160 | if (ctx->bignums == NULL) { |
| 161 | OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); |
| 162 | ctx->error = 1; |
| 163 | return NULL; |
| 164 | } |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 165 | } |
| 166 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 167 | if (ctx->used == sk_BIGNUM_num(ctx->bignums)) { |
| 168 | BIGNUM *bn = BN_new(); |
| 169 | if (bn == NULL || !sk_BIGNUM_push(ctx->bignums, bn)) { |
| 170 | OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_TEMPORARY_VARIABLES); |
| 171 | BN_free(bn); |
| 172 | ctx->error = 1; |
| 173 | return NULL; |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | BIGNUM *ret = sk_BIGNUM_value(ctx->bignums, ctx->used); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 178 | BN_zero(ret); |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 179 | // This is bounded by |sk_BIGNUM_num|, so it cannot overflow. |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 180 | ctx->used++; |
| 181 | return ret; |
| 182 | } |
| 183 | |
| 184 | void BN_CTX_end(BN_CTX *ctx) { |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 185 | if (ctx->error) { |
| 186 | // Once an operation has failed, |ctx->stack| no longer matches the number |
| 187 | // of |BN_CTX_end| calls to come. Do nothing. |
| 188 | return; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 189 | } |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 190 | |
| 191 | ctx->used = BN_STACK_pop(&ctx->stack); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 192 | } |
| 193 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 194 | |
| 195 | // BN_STACK |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 196 | |
| 197 | static void BN_STACK_init(BN_STACK *st) { |
| 198 | st->indexes = NULL; |
| 199 | st->depth = st->size = 0; |
| 200 | } |
| 201 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 202 | static void BN_STACK_cleanup(BN_STACK *st) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 203 | OPENSSL_free(st->indexes); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 204 | } |
| 205 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 206 | static int BN_STACK_push(BN_STACK *st, size_t idx) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 207 | if (st->depth == st->size) { |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 208 | // This function intentionally does not push to the error queue on error. |
| 209 | // Error-reporting is deferred to |BN_CTX_get|. |
| 210 | size_t new_size = st->size != 0 ? st->size * 3 / 2 : BN_CTX_START_FRAMES; |
| 211 | if (new_size <= st->size || new_size > ((size_t)-1) / sizeof(size_t)) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 212 | return 0; |
| 213 | } |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 214 | size_t *new_indexes = |
| 215 | OPENSSL_realloc(st->indexes, new_size * sizeof(size_t)); |
| 216 | if (new_indexes == NULL) { |
| 217 | return 0; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 218 | } |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 219 | st->indexes = new_indexes; |
| 220 | st->size = new_size; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 221 | } |
| 222 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 223 | st->indexes[st->depth] = idx; |
| 224 | st->depth++; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 225 | return 1; |
| 226 | } |
| 227 | |
Robert Sloan | 59e9950 | 2019-03-25 12:33:16 -0700 | [diff] [blame] | 228 | static size_t BN_STACK_pop(BN_STACK *st) { |
| 229 | assert(st->depth > 0); |
| 230 | st->depth--; |
| 231 | return st->indexes[st->depth]; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 232 | } |