Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 1 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
| 2 | * All rights reserved. |
| 3 | * |
| 4 | * This package is an SSL implementation written |
| 5 | * by Eric Young (eay@cryptsoft.com). |
| 6 | * The implementation was written so as to conform with Netscapes SSL. |
| 7 | * |
| 8 | * This library is free for commercial and non-commercial use as long as |
| 9 | * the following conditions are aheared to. The following conditions |
| 10 | * apply to all code found in this distribution, be it the RC4, RSA, |
| 11 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation |
| 12 | * included with this distribution is covered by the same copyright terms |
| 13 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). |
| 14 | * |
| 15 | * Copyright remains Eric Young's, and as such any Copyright notices in |
| 16 | * the code are not to be removed. |
| 17 | * If this package is used in a product, Eric Young should be given attribution |
| 18 | * as the author of the parts of the library used. |
| 19 | * This can be in the form of a textual message at program startup or |
| 20 | * in documentation (online or textual) provided with the package. |
| 21 | * |
| 22 | * Redistribution and use in source and binary forms, with or without |
| 23 | * modification, are permitted provided that the following conditions |
| 24 | * are met: |
| 25 | * 1. Redistributions of source code must retain the copyright |
| 26 | * notice, this list of conditions and the following disclaimer. |
| 27 | * 2. Redistributions in binary form must reproduce the above copyright |
| 28 | * notice, this list of conditions and the following disclaimer in the |
| 29 | * documentation and/or other materials provided with the distribution. |
| 30 | * 3. All advertising materials mentioning features or use of this software |
| 31 | * must display the following acknowledgement: |
| 32 | * "This product includes cryptographic software written by |
| 33 | * Eric Young (eay@cryptsoft.com)" |
| 34 | * The word 'cryptographic' can be left out if the rouines from the library |
| 35 | * being used are not cryptographic related :-). |
| 36 | * 4. If you include any Windows specific code (or a derivative thereof) from |
| 37 | * the apps directory (application code) you must include an acknowledgement: |
| 38 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" |
| 39 | * |
| 40 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
| 41 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 42 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 43 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| 44 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 45 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 46 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 47 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 48 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 49 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 50 | * SUCH DAMAGE. |
| 51 | * |
| 52 | * The licence and distribution terms for any publically available version or |
| 53 | * derivative of this code cannot be changed. i.e. this code cannot simply be |
| 54 | * copied and put under another distribution licence |
| 55 | * [including the GNU Public Licence.] |
| 56 | * |
| 57 | * The DSS routines are based on patches supplied by |
| 58 | * Steven Schoch <schoch@sheba.arc.nasa.gov>. */ |
| 59 | |
| 60 | #include <openssl/dsa.h> |
| 61 | |
| 62 | #include <string.h> |
| 63 | |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 64 | #include <openssl/bn.h> |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 65 | #include <openssl/dh.h> |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 66 | #include <openssl/digest.h> |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 67 | #include <openssl/engine.h> |
| 68 | #include <openssl/err.h> |
| 69 | #include <openssl/ex_data.h> |
| 70 | #include <openssl/mem.h> |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 71 | #include <openssl/rand.h> |
| 72 | #include <openssl/sha.h> |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 73 | #include <openssl/thread.h> |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 74 | |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame] | 75 | #include "../fipsmodule/bn/internal.h" |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 76 | #include "../internal.h" |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 77 | |
| 78 | |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 79 | #define OPENSSL_DSA_MAX_MODULUS_BITS 10000 |
| 80 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 81 | // Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of |
| 82 | // Rabin-Miller |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 83 | #define DSS_prime_checks 50 |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 84 | |
Robert Sloan | 99319a1 | 2017-11-27 10:32:46 -0800 | [diff] [blame] | 85 | static int dsa_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv, |
| 86 | BIGNUM **out_r); |
| 87 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 88 | static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT; |
| 89 | |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 90 | DSA *DSA_new(void) { |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 91 | DSA *dsa = OPENSSL_malloc(sizeof(DSA)); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 92 | if (dsa == NULL) { |
Kenny Root | b849459 | 2015-09-25 02:29:14 +0000 | [diff] [blame] | 93 | OPENSSL_PUT_ERROR(DSA, ERR_R_MALLOC_FAILURE); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 94 | return NULL; |
| 95 | } |
| 96 | |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 97 | OPENSSL_memset(dsa, 0, sizeof(DSA)); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 98 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 99 | dsa->references = 1; |
| 100 | |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 101 | CRYPTO_MUTEX_init(&dsa->method_mont_lock); |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 102 | CRYPTO_new_ex_data(&dsa->ex_data); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 103 | |
| 104 | return dsa; |
| 105 | } |
| 106 | |
| 107 | void DSA_free(DSA *dsa) { |
| 108 | if (dsa == NULL) { |
| 109 | return; |
| 110 | } |
| 111 | |
Adam Langley | f4e4272 | 2015-06-04 17:45:09 -0700 | [diff] [blame] | 112 | if (!CRYPTO_refcount_dec_and_test_zero(&dsa->references)) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 113 | return; |
| 114 | } |
| 115 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 116 | CRYPTO_free_ex_data(&g_ex_data_class, dsa, &dsa->ex_data); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 117 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 118 | BN_clear_free(dsa->p); |
| 119 | BN_clear_free(dsa->q); |
| 120 | BN_clear_free(dsa->g); |
| 121 | BN_clear_free(dsa->pub_key); |
| 122 | BN_clear_free(dsa->priv_key); |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 123 | BN_MONT_CTX_free(dsa->method_mont_p); |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 124 | BN_MONT_CTX_free(dsa->method_mont_q); |
| 125 | CRYPTO_MUTEX_cleanup(&dsa->method_mont_lock); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 126 | OPENSSL_free(dsa); |
| 127 | } |
| 128 | |
| 129 | int DSA_up_ref(DSA *dsa) { |
Adam Langley | f4e4272 | 2015-06-04 17:45:09 -0700 | [diff] [blame] | 130 | CRYPTO_refcount_inc(&dsa->references); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 131 | return 1; |
| 132 | } |
| 133 | |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 134 | void DSA_get0_key(const DSA *dsa, const BIGNUM **out_pub_key, |
| 135 | const BIGNUM **out_priv_key) { |
| 136 | if (out_pub_key != NULL) { |
| 137 | *out_pub_key = dsa->pub_key; |
| 138 | } |
| 139 | if (out_priv_key != NULL) { |
| 140 | *out_priv_key = dsa->priv_key; |
| 141 | } |
| 142 | } |
| 143 | |
| 144 | void DSA_get0_pqg(const DSA *dsa, const BIGNUM **out_p, const BIGNUM **out_q, |
| 145 | const BIGNUM **out_g) { |
| 146 | if (out_p != NULL) { |
| 147 | *out_p = dsa->p; |
| 148 | } |
| 149 | if (out_q != NULL) { |
| 150 | *out_q = dsa->q; |
| 151 | } |
| 152 | if (out_g != NULL) { |
| 153 | *out_g = dsa->g; |
| 154 | } |
| 155 | } |
| 156 | |
Robert Sloan | 4562e9d | 2017-10-02 10:26:51 -0700 | [diff] [blame] | 157 | int DSA_set0_key(DSA *dsa, BIGNUM *pub_key, BIGNUM *priv_key) { |
| 158 | if (dsa->pub_key == NULL && pub_key == NULL) { |
| 159 | return 0; |
| 160 | } |
| 161 | |
| 162 | if (pub_key != NULL) { |
| 163 | BN_free(dsa->pub_key); |
| 164 | dsa->pub_key = pub_key; |
| 165 | } |
| 166 | if (priv_key != NULL) { |
| 167 | BN_free(dsa->priv_key); |
| 168 | dsa->priv_key = priv_key; |
| 169 | } |
| 170 | |
| 171 | return 1; |
| 172 | } |
| 173 | |
| 174 | int DSA_set0_pqg(DSA *dsa, BIGNUM *p, BIGNUM *q, BIGNUM *g) { |
| 175 | if ((dsa->p == NULL && p == NULL) || |
| 176 | (dsa->q == NULL && q == NULL) || |
| 177 | (dsa->g == NULL && g == NULL)) { |
| 178 | return 0; |
| 179 | } |
| 180 | |
| 181 | if (p != NULL) { |
| 182 | BN_free(dsa->p); |
| 183 | dsa->p = p; |
| 184 | } |
| 185 | if (q != NULL) { |
| 186 | BN_free(dsa->q); |
| 187 | dsa->q = q; |
| 188 | } |
| 189 | if (g != NULL) { |
| 190 | BN_free(dsa->g); |
| 191 | dsa->g = g; |
| 192 | } |
| 193 | |
| 194 | return 1; |
| 195 | } |
| 196 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 197 | int DSA_generate_parameters_ex(DSA *dsa, unsigned bits, const uint8_t *seed_in, |
| 198 | size_t seed_len, int *out_counter, |
| 199 | unsigned long *out_h, BN_GENCB *cb) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 200 | int ok = 0; |
| 201 | unsigned char seed[SHA256_DIGEST_LENGTH]; |
| 202 | unsigned char md[SHA256_DIGEST_LENGTH]; |
| 203 | unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; |
| 204 | BIGNUM *r0, *W, *X, *c, *test; |
| 205 | BIGNUM *g = NULL, *q = NULL, *p = NULL; |
| 206 | BN_MONT_CTX *mont = NULL; |
| 207 | int k, n = 0, m = 0; |
| 208 | unsigned i; |
| 209 | int counter = 0; |
| 210 | int r = 0; |
| 211 | BN_CTX *ctx = NULL; |
| 212 | unsigned int h = 2; |
| 213 | unsigned qsize; |
| 214 | const EVP_MD *evpmd; |
| 215 | |
| 216 | evpmd = (bits >= 2048) ? EVP_sha256() : EVP_sha1(); |
| 217 | qsize = EVP_MD_size(evpmd); |
| 218 | |
| 219 | if (bits < 512) { |
| 220 | bits = 512; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 221 | } |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 222 | |
| 223 | bits = (bits + 63) / 64 * 64; |
| 224 | |
| 225 | if (seed_in != NULL) { |
| 226 | if (seed_len < (size_t)qsize) { |
| 227 | return 0; |
| 228 | } |
| 229 | if (seed_len > (size_t)qsize) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 230 | // Only consume as much seed as is expected. |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 231 | seed_len = qsize; |
| 232 | } |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 233 | OPENSSL_memcpy(seed, seed_in, seed_len); |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 234 | } |
| 235 | |
| 236 | ctx = BN_CTX_new(); |
| 237 | if (ctx == NULL) { |
| 238 | goto err; |
| 239 | } |
| 240 | BN_CTX_start(ctx); |
| 241 | |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 242 | r0 = BN_CTX_get(ctx); |
| 243 | g = BN_CTX_get(ctx); |
| 244 | W = BN_CTX_get(ctx); |
| 245 | q = BN_CTX_get(ctx); |
| 246 | X = BN_CTX_get(ctx); |
| 247 | c = BN_CTX_get(ctx); |
| 248 | p = BN_CTX_get(ctx); |
| 249 | test = BN_CTX_get(ctx); |
| 250 | |
| 251 | if (test == NULL || !BN_lshift(test, BN_value_one(), bits - 1)) { |
| 252 | goto err; |
| 253 | } |
| 254 | |
| 255 | for (;;) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 256 | // Find q. |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 257 | for (;;) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 258 | // step 1 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 259 | if (!BN_GENCB_call(cb, 0, m++)) { |
| 260 | goto err; |
| 261 | } |
| 262 | |
| 263 | int use_random_seed = (seed_in == NULL); |
| 264 | if (use_random_seed) { |
| 265 | if (!RAND_bytes(seed, qsize)) { |
| 266 | goto err; |
| 267 | } |
| 268 | } else { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 269 | // If we come back through, use random seed next time. |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 270 | seed_in = NULL; |
| 271 | } |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 272 | OPENSSL_memcpy(buf, seed, qsize); |
| 273 | OPENSSL_memcpy(buf2, seed, qsize); |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 274 | // precompute "SEED + 1" for step 7: |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 275 | for (i = qsize - 1; i < qsize; i--) { |
| 276 | buf[i]++; |
| 277 | if (buf[i] != 0) { |
| 278 | break; |
| 279 | } |
| 280 | } |
| 281 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 282 | // step 2 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 283 | if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL) || |
| 284 | !EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) { |
| 285 | goto err; |
| 286 | } |
| 287 | for (i = 0; i < qsize; i++) { |
| 288 | md[i] ^= buf2[i]; |
| 289 | } |
| 290 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 291 | // step 3 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 292 | md[0] |= 0x80; |
| 293 | md[qsize - 1] |= 0x01; |
| 294 | if (!BN_bin2bn(md, qsize, q)) { |
| 295 | goto err; |
| 296 | } |
| 297 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 298 | // step 4 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 299 | r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, use_random_seed, cb); |
| 300 | if (r > 0) { |
| 301 | break; |
| 302 | } |
| 303 | if (r != 0) { |
| 304 | goto err; |
| 305 | } |
| 306 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 307 | // do a callback call |
| 308 | // step 5 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 309 | } |
| 310 | |
| 311 | if (!BN_GENCB_call(cb, 2, 0) || !BN_GENCB_call(cb, 3, 0)) { |
| 312 | goto err; |
| 313 | } |
| 314 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 315 | // step 6 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 316 | counter = 0; |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 317 | // "offset = 2" |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 318 | |
| 319 | n = (bits - 1) / 160; |
| 320 | |
| 321 | for (;;) { |
| 322 | if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) { |
| 323 | goto err; |
| 324 | } |
| 325 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 326 | // step 7 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 327 | BN_zero(W); |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 328 | // now 'buf' contains "SEED + offset - 1" |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 329 | for (k = 0; k <= n; k++) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 330 | // obtain "SEED + offset + k" by incrementing: |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 331 | for (i = qsize - 1; i < qsize; i--) { |
| 332 | buf[i]++; |
| 333 | if (buf[i] != 0) { |
| 334 | break; |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) { |
| 339 | goto err; |
| 340 | } |
| 341 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 342 | // step 8 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 343 | if (!BN_bin2bn(md, qsize, r0) || |
| 344 | !BN_lshift(r0, r0, (qsize << 3) * k) || |
| 345 | !BN_add(W, W, r0)) { |
| 346 | goto err; |
| 347 | } |
| 348 | } |
| 349 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 350 | // more of step 8 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 351 | if (!BN_mask_bits(W, bits - 1) || |
| 352 | !BN_copy(X, W) || |
| 353 | !BN_add(X, X, test)) { |
| 354 | goto err; |
| 355 | } |
| 356 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 357 | // step 9 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 358 | if (!BN_lshift1(r0, q) || |
| 359 | !BN_mod(c, X, r0, ctx) || |
| 360 | !BN_sub(r0, c, BN_value_one()) || |
| 361 | !BN_sub(p, X, r0)) { |
| 362 | goto err; |
| 363 | } |
| 364 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 365 | // step 10 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 366 | if (BN_cmp(p, test) >= 0) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 367 | // step 11 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 368 | r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); |
| 369 | if (r > 0) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 370 | goto end; // found it |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 371 | } |
| 372 | if (r != 0) { |
| 373 | goto err; |
| 374 | } |
| 375 | } |
| 376 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 377 | // step 13 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 378 | counter++; |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 379 | // "offset = offset + n + 1" |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 380 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 381 | // step 14 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 382 | if (counter >= 4096) { |
| 383 | break; |
| 384 | } |
| 385 | } |
| 386 | } |
| 387 | end: |
| 388 | if (!BN_GENCB_call(cb, 2, 1)) { |
| 389 | goto err; |
| 390 | } |
| 391 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 392 | // We now need to generate g |
| 393 | // Set r0=(p-1)/q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 394 | if (!BN_sub(test, p, BN_value_one()) || |
| 395 | !BN_div(r0, NULL, test, q, ctx)) { |
| 396 | goto err; |
| 397 | } |
| 398 | |
Robert Sloan | 8542c08 | 2018-02-05 09:07:34 -0800 | [diff] [blame] | 399 | mont = BN_MONT_CTX_new_for_modulus(p, ctx); |
| 400 | if (mont == NULL || |
| 401 | !BN_set_word(test, h)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 402 | goto err; |
| 403 | } |
| 404 | |
| 405 | for (;;) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 406 | // g=test^r0%p |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 407 | if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) { |
| 408 | goto err; |
| 409 | } |
| 410 | if (!BN_is_one(g)) { |
| 411 | break; |
| 412 | } |
| 413 | if (!BN_add(test, test, BN_value_one())) { |
| 414 | goto err; |
| 415 | } |
| 416 | h++; |
| 417 | } |
| 418 | |
| 419 | if (!BN_GENCB_call(cb, 3, 1)) { |
| 420 | goto err; |
| 421 | } |
| 422 | |
| 423 | ok = 1; |
| 424 | |
| 425 | err: |
| 426 | if (ok) { |
| 427 | BN_free(dsa->p); |
| 428 | BN_free(dsa->q); |
| 429 | BN_free(dsa->g); |
| 430 | dsa->p = BN_dup(p); |
| 431 | dsa->q = BN_dup(q); |
| 432 | dsa->g = BN_dup(g); |
| 433 | if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) { |
| 434 | ok = 0; |
| 435 | goto err; |
| 436 | } |
| 437 | if (out_counter != NULL) { |
| 438 | *out_counter = counter; |
| 439 | } |
| 440 | if (out_h != NULL) { |
| 441 | *out_h = h; |
| 442 | } |
| 443 | } |
| 444 | |
| 445 | if (ctx) { |
| 446 | BN_CTX_end(ctx); |
| 447 | BN_CTX_free(ctx); |
| 448 | } |
| 449 | |
| 450 | BN_MONT_CTX_free(mont); |
| 451 | |
| 452 | return ok; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 453 | } |
| 454 | |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 455 | DSA *DSAparams_dup(const DSA *dsa) { |
| 456 | DSA *ret = DSA_new(); |
| 457 | if (ret == NULL) { |
| 458 | return NULL; |
| 459 | } |
| 460 | ret->p = BN_dup(dsa->p); |
| 461 | ret->q = BN_dup(dsa->q); |
| 462 | ret->g = BN_dup(dsa->g); |
| 463 | if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { |
| 464 | DSA_free(ret); |
| 465 | return NULL; |
| 466 | } |
| 467 | return ret; |
| 468 | } |
| 469 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 470 | int DSA_generate_key(DSA *dsa) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 471 | int ok = 0; |
| 472 | BN_CTX *ctx = NULL; |
| 473 | BIGNUM *pub_key = NULL, *priv_key = NULL; |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 474 | |
| 475 | ctx = BN_CTX_new(); |
| 476 | if (ctx == NULL) { |
| 477 | goto err; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 478 | } |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 479 | |
| 480 | priv_key = dsa->priv_key; |
| 481 | if (priv_key == NULL) { |
| 482 | priv_key = BN_new(); |
| 483 | if (priv_key == NULL) { |
| 484 | goto err; |
| 485 | } |
| 486 | } |
| 487 | |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 488 | if (!BN_rand_range_ex(priv_key, 1, dsa->q)) { |
| 489 | goto err; |
| 490 | } |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 491 | |
| 492 | pub_key = dsa->pub_key; |
| 493 | if (pub_key == NULL) { |
| 494 | pub_key = BN_new(); |
| 495 | if (pub_key == NULL) { |
| 496 | goto err; |
| 497 | } |
| 498 | } |
| 499 | |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 500 | if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, &dsa->method_mont_lock, |
| 501 | dsa->p, ctx) || |
Steven Valdez | b0b45c6 | 2017-01-17 16:23:54 -0500 | [diff] [blame] | 502 | !BN_mod_exp_mont_consttime(pub_key, dsa->g, priv_key, dsa->p, ctx, |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 503 | dsa->method_mont_p)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 504 | goto err; |
| 505 | } |
| 506 | |
| 507 | dsa->priv_key = priv_key; |
| 508 | dsa->pub_key = pub_key; |
| 509 | ok = 1; |
| 510 | |
| 511 | err: |
| 512 | if (dsa->pub_key == NULL) { |
| 513 | BN_free(pub_key); |
| 514 | } |
| 515 | if (dsa->priv_key == NULL) { |
| 516 | BN_free(priv_key); |
| 517 | } |
| 518 | BN_CTX_free(ctx); |
| 519 | |
| 520 | return ok; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 521 | } |
| 522 | |
| 523 | DSA_SIG *DSA_SIG_new(void) { |
| 524 | DSA_SIG *sig; |
| 525 | sig = OPENSSL_malloc(sizeof(DSA_SIG)); |
| 526 | if (!sig) { |
| 527 | return NULL; |
| 528 | } |
| 529 | sig->r = NULL; |
| 530 | sig->s = NULL; |
| 531 | return sig; |
| 532 | } |
| 533 | |
| 534 | void DSA_SIG_free(DSA_SIG *sig) { |
| 535 | if (!sig) { |
| 536 | return; |
| 537 | } |
| 538 | |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 539 | BN_free(sig->r); |
| 540 | BN_free(sig->s); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 541 | OPENSSL_free(sig); |
| 542 | } |
| 543 | |
Robert Sloan | 99319a1 | 2017-11-27 10:32:46 -0800 | [diff] [blame] | 544 | DSA_SIG *DSA_do_sign(const uint8_t *digest, size_t digest_len, const DSA *dsa) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 545 | BIGNUM *kinv = NULL, *r = NULL, *s = NULL; |
| 546 | BIGNUM m; |
| 547 | BIGNUM xr; |
| 548 | BN_CTX *ctx = NULL; |
| 549 | int reason = ERR_R_BN_LIB; |
| 550 | DSA_SIG *ret = NULL; |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 551 | |
| 552 | BN_init(&m); |
| 553 | BN_init(&xr); |
| 554 | |
| 555 | if (!dsa->p || !dsa->q || !dsa->g) { |
| 556 | reason = DSA_R_MISSING_PARAMETERS; |
| 557 | goto err; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 558 | } |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 559 | |
| 560 | s = BN_new(); |
| 561 | if (s == NULL) { |
| 562 | goto err; |
| 563 | } |
| 564 | ctx = BN_CTX_new(); |
| 565 | if (ctx == NULL) { |
| 566 | goto err; |
| 567 | } |
| 568 | |
| 569 | redo: |
Robert Sloan | 99319a1 | 2017-11-27 10:32:46 -0800 | [diff] [blame] | 570 | if (!dsa_sign_setup(dsa, ctx, &kinv, &r)) { |
| 571 | goto err; |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 572 | } |
| 573 | |
| 574 | if (digest_len > BN_num_bytes(dsa->q)) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 575 | // if the digest length is greater than the size of q use the |
| 576 | // BN_num_bits(dsa->q) leftmost bits of the digest, see |
| 577 | // fips 186-3, 4.2 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 578 | digest_len = BN_num_bytes(dsa->q); |
| 579 | } |
| 580 | |
| 581 | if (BN_bin2bn(digest, digest_len, &m) == NULL) { |
| 582 | goto err; |
| 583 | } |
| 584 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 585 | // Compute s = inv(k) (m + xr) mod q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 586 | if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 587 | goto err; // s = xr |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 588 | } |
| 589 | if (!BN_add(s, &xr, &m)) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 590 | goto err; // s = m + xr |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 591 | } |
| 592 | if (BN_cmp(s, dsa->q) > 0) { |
| 593 | if (!BN_sub(s, s, dsa->q)) { |
| 594 | goto err; |
| 595 | } |
| 596 | } |
| 597 | if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) { |
| 598 | goto err; |
| 599 | } |
| 600 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 601 | // Redo if r or s is zero as required by FIPS 186-3: this is |
| 602 | // very unlikely. |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 603 | if (BN_is_zero(r) || BN_is_zero(s)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 604 | goto redo; |
| 605 | } |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 606 | ret = DSA_SIG_new(); |
| 607 | if (ret == NULL) { |
| 608 | goto err; |
| 609 | } |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 610 | ret->r = r; |
| 611 | ret->s = s; |
| 612 | |
| 613 | err: |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 614 | if (ret == NULL) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 615 | OPENSSL_PUT_ERROR(DSA, reason); |
| 616 | BN_free(r); |
| 617 | BN_free(s); |
| 618 | } |
| 619 | BN_CTX_free(ctx); |
| 620 | BN_clear_free(&m); |
| 621 | BN_clear_free(&xr); |
| 622 | BN_clear_free(kinv); |
| 623 | |
| 624 | return ret; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 625 | } |
| 626 | |
| 627 | int DSA_do_verify(const uint8_t *digest, size_t digest_len, DSA_SIG *sig, |
| 628 | const DSA *dsa) { |
| 629 | int valid; |
| 630 | if (!DSA_do_check_signature(&valid, digest, digest_len, sig, dsa)) { |
| 631 | return -1; |
| 632 | } |
| 633 | return valid; |
| 634 | } |
| 635 | |
| 636 | int DSA_do_check_signature(int *out_valid, const uint8_t *digest, |
| 637 | size_t digest_len, DSA_SIG *sig, const DSA *dsa) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 638 | BN_CTX *ctx; |
| 639 | BIGNUM u1, u2, t1; |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 640 | int ret = 0; |
| 641 | unsigned i; |
| 642 | |
| 643 | *out_valid = 0; |
| 644 | |
| 645 | if (!dsa->p || !dsa->q || !dsa->g) { |
| 646 | OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS); |
| 647 | return 0; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 648 | } |
| 649 | |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 650 | i = BN_num_bits(dsa->q); |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 651 | // fips 186-3 allows only different sizes for q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 652 | if (i != 160 && i != 224 && i != 256) { |
| 653 | OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE); |
| 654 | return 0; |
| 655 | } |
| 656 | |
| 657 | if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { |
| 658 | OPENSSL_PUT_ERROR(DSA, DSA_R_MODULUS_TOO_LARGE); |
| 659 | return 0; |
| 660 | } |
| 661 | |
| 662 | BN_init(&u1); |
| 663 | BN_init(&u2); |
| 664 | BN_init(&t1); |
| 665 | |
| 666 | ctx = BN_CTX_new(); |
| 667 | if (ctx == NULL) { |
| 668 | goto err; |
| 669 | } |
| 670 | |
| 671 | if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || |
| 672 | BN_ucmp(sig->r, dsa->q) >= 0) { |
| 673 | ret = 1; |
| 674 | goto err; |
| 675 | } |
| 676 | if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || |
| 677 | BN_ucmp(sig->s, dsa->q) >= 0) { |
| 678 | ret = 1; |
| 679 | goto err; |
| 680 | } |
| 681 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 682 | // Calculate W = inv(S) mod Q |
| 683 | // save W in u2 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 684 | if (BN_mod_inverse(&u2, sig->s, dsa->q, ctx) == NULL) { |
| 685 | goto err; |
| 686 | } |
| 687 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 688 | // save M in u1 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 689 | if (digest_len > (i >> 3)) { |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 690 | // if the digest length is greater than the size of q use the |
| 691 | // BN_num_bits(dsa->q) leftmost bits of the digest, see |
| 692 | // fips 186-3, 4.2 |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 693 | digest_len = (i >> 3); |
| 694 | } |
| 695 | |
| 696 | if (BN_bin2bn(digest, digest_len, &u1) == NULL) { |
| 697 | goto err; |
| 698 | } |
| 699 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 700 | // u1 = M * w mod q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 701 | if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) { |
| 702 | goto err; |
| 703 | } |
| 704 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 705 | // u2 = r * w mod q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 706 | if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) { |
| 707 | goto err; |
| 708 | } |
| 709 | |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 710 | if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 711 | (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p, |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 712 | ctx)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 713 | goto err; |
| 714 | } |
| 715 | |
| 716 | if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 717 | dsa->method_mont_p)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 718 | goto err; |
| 719 | } |
| 720 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 721 | // BN_copy(&u1,&t1); |
| 722 | // let u1 = u1 mod q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 723 | if (!BN_mod(&u1, &t1, dsa->q, ctx)) { |
| 724 | goto err; |
| 725 | } |
| 726 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 727 | // V is now in u1. If the signature is correct, it will be |
| 728 | // equal to R. |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 729 | *out_valid = BN_ucmp(&u1, sig->r) == 0; |
| 730 | ret = 1; |
| 731 | |
| 732 | err: |
| 733 | if (ret != 1) { |
| 734 | OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB); |
| 735 | } |
| 736 | BN_CTX_free(ctx); |
| 737 | BN_free(&u1); |
| 738 | BN_free(&u2); |
| 739 | BN_free(&t1); |
| 740 | |
| 741 | return ret; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 742 | } |
| 743 | |
| 744 | int DSA_sign(int type, const uint8_t *digest, size_t digest_len, |
Robert Sloan | 99319a1 | 2017-11-27 10:32:46 -0800 | [diff] [blame] | 745 | uint8_t *out_sig, unsigned int *out_siglen, const DSA *dsa) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 746 | DSA_SIG *s; |
| 747 | |
| 748 | s = DSA_do_sign(digest, digest_len, dsa); |
| 749 | if (s == NULL) { |
| 750 | *out_siglen = 0; |
| 751 | return 0; |
| 752 | } |
| 753 | |
| 754 | *out_siglen = i2d_DSA_SIG(s, &out_sig); |
| 755 | DSA_SIG_free(s); |
| 756 | return 1; |
| 757 | } |
| 758 | |
| 759 | int DSA_verify(int type, const uint8_t *digest, size_t digest_len, |
| 760 | const uint8_t *sig, size_t sig_len, const DSA *dsa) { |
| 761 | int valid; |
| 762 | if (!DSA_check_signature(&valid, digest, digest_len, sig, sig_len, dsa)) { |
| 763 | return -1; |
| 764 | } |
| 765 | return valid; |
| 766 | } |
| 767 | |
| 768 | int DSA_check_signature(int *out_valid, const uint8_t *digest, |
| 769 | size_t digest_len, const uint8_t *sig, size_t sig_len, |
| 770 | const DSA *dsa) { |
| 771 | DSA_SIG *s = NULL; |
| 772 | int ret = 0; |
| 773 | uint8_t *der = NULL; |
| 774 | |
| 775 | s = DSA_SIG_new(); |
| 776 | if (s == NULL) { |
| 777 | goto err; |
| 778 | } |
| 779 | |
| 780 | const uint8_t *sigp = sig; |
| 781 | if (d2i_DSA_SIG(&s, &sigp, sig_len) == NULL || sigp != sig + sig_len) { |
| 782 | goto err; |
| 783 | } |
| 784 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 785 | // Ensure that the signature uses DER and doesn't have trailing garbage. |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 786 | int der_len = i2d_DSA_SIG(s, &der); |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 787 | if (der_len < 0 || (size_t)der_len != sig_len || |
| 788 | OPENSSL_memcmp(sig, der, sig_len)) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 789 | goto err; |
| 790 | } |
| 791 | |
| 792 | ret = DSA_do_check_signature(out_valid, digest, digest_len, s, dsa); |
| 793 | |
| 794 | err: |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 795 | OPENSSL_free(der); |
| 796 | DSA_SIG_free(s); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 797 | return ret; |
| 798 | } |
| 799 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 800 | // der_len_len returns the number of bytes needed to represent a length of |len| |
| 801 | // in DER. |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 802 | static size_t der_len_len(size_t len) { |
| 803 | if (len < 0x80) { |
| 804 | return 1; |
| 805 | } |
| 806 | size_t ret = 1; |
| 807 | while (len > 0) { |
| 808 | ret++; |
| 809 | len >>= 8; |
| 810 | } |
| 811 | return ret; |
| 812 | } |
| 813 | |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 814 | int DSA_size(const DSA *dsa) { |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 815 | size_t order_len = BN_num_bytes(dsa->q); |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 816 | // Compute the maximum length of an |order_len| byte integer. Defensively |
| 817 | // assume that the leading 0x00 is included. |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 818 | size_t integer_len = 1 /* tag */ + der_len_len(order_len + 1) + 1 + order_len; |
| 819 | if (integer_len < order_len) { |
| 820 | return 0; |
| 821 | } |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 822 | // A DSA signature is two INTEGERs. |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 823 | size_t value_len = 2 * integer_len; |
| 824 | if (value_len < integer_len) { |
| 825 | return 0; |
| 826 | } |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 827 | // Add the header. |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 828 | size_t ret = 1 /* tag */ + der_len_len(value_len) + value_len; |
| 829 | if (ret < value_len) { |
| 830 | return 0; |
| 831 | } |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 832 | return ret; |
| 833 | } |
| 834 | |
Robert Sloan | 99319a1 | 2017-11-27 10:32:46 -0800 | [diff] [blame] | 835 | static int dsa_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv, |
| 836 | BIGNUM **out_r) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 837 | BN_CTX *ctx; |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 838 | BIGNUM k, kq, *kinv = NULL, *r = NULL; |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 839 | int ret = 0; |
| 840 | |
| 841 | if (!dsa->p || !dsa->q || !dsa->g) { |
| 842 | OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS); |
| 843 | return 0; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 844 | } |
| 845 | |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 846 | BN_init(&k); |
| 847 | BN_init(&kq); |
| 848 | |
| 849 | ctx = ctx_in; |
| 850 | if (ctx == NULL) { |
| 851 | ctx = BN_CTX_new(); |
| 852 | if (ctx == NULL) { |
| 853 | goto err; |
| 854 | } |
| 855 | } |
| 856 | |
| 857 | r = BN_new(); |
| 858 | if (r == NULL) { |
| 859 | goto err; |
| 860 | } |
| 861 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 862 | // Get random k |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 863 | if (!BN_rand_range_ex(&k, 1, dsa->q)) { |
| 864 | goto err; |
| 865 | } |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 866 | |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 867 | if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 868 | (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->p, |
| 869 | ctx) || |
| 870 | !BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_q, |
| 871 | (CRYPTO_MUTEX *)&dsa->method_mont_lock, dsa->q, |
David Benjamin | 4969cc9 | 2016-04-22 15:02:23 -0400 | [diff] [blame] | 872 | ctx)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 873 | goto err; |
| 874 | } |
| 875 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 876 | // Compute r = (g^k mod p) mod q |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 877 | if (!BN_copy(&kq, &k)) { |
| 878 | goto err; |
| 879 | } |
| 880 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 881 | // We do not want timing information to leak the length of k, |
| 882 | // so we compute g^k using an equivalent exponent of fixed length. |
| 883 | // |
| 884 | // (This is a kludge that we need because the BN_mod_exp_mont() |
| 885 | // does not let us specify the desired timing behaviour.) |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 886 | |
| 887 | if (!BN_add(&kq, &kq, dsa->q)) { |
| 888 | goto err; |
| 889 | } |
| 890 | if (BN_num_bits(&kq) <= BN_num_bits(dsa->q) && !BN_add(&kq, &kq, dsa->q)) { |
| 891 | goto err; |
| 892 | } |
| 893 | |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 894 | if (!BN_mod_exp_mont_consttime(r, dsa->g, &kq, dsa->p, ctx, |
| 895 | dsa->method_mont_p)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 896 | goto err; |
| 897 | } |
| 898 | if (!BN_mod(r, r, dsa->q, ctx)) { |
| 899 | goto err; |
| 900 | } |
| 901 | |
Robert Sloan | 8f860b1 | 2017-08-28 07:37:06 -0700 | [diff] [blame] | 902 | // Compute part of 's = inv(k) (m + xr) mod q' using Fermat's Little |
| 903 | // Theorem. |
David Benjamin | c895d6b | 2016-08-11 13:26:41 -0400 | [diff] [blame] | 904 | kinv = BN_new(); |
| 905 | if (kinv == NULL || |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 906 | !bn_mod_inverse_prime(kinv, &k, dsa->q, ctx, dsa->method_mont_q)) { |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 907 | goto err; |
| 908 | } |
| 909 | |
| 910 | BN_clear_free(*out_kinv); |
| 911 | *out_kinv = kinv; |
| 912 | kinv = NULL; |
| 913 | BN_clear_free(*out_r); |
| 914 | *out_r = r; |
| 915 | ret = 1; |
| 916 | |
| 917 | err: |
| 918 | if (!ret) { |
| 919 | OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB); |
| 920 | if (r != NULL) { |
| 921 | BN_clear_free(r); |
| 922 | } |
| 923 | } |
| 924 | |
| 925 | if (ctx_in == NULL) { |
| 926 | BN_CTX_free(ctx); |
| 927 | } |
| 928 | BN_clear_free(&k); |
| 929 | BN_clear_free(&kq); |
Robert Sloan | 69939df | 2017-01-09 10:53:07 -0800 | [diff] [blame] | 930 | BN_clear_free(kinv); |
Adam Langley | fad6327 | 2015-11-12 12:15:39 -0800 | [diff] [blame] | 931 | return ret; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 932 | } |
| 933 | |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 934 | int DSA_get_ex_new_index(long argl, void *argp, CRYPTO_EX_unused *unused, |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame] | 935 | CRYPTO_EX_dup *dup_unused, CRYPTO_EX_free *free_func) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 936 | int index; |
Robert Sloan | 8ff0355 | 2017-06-14 12:40:58 -0700 | [diff] [blame] | 937 | if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp, |
Adam Langley | 4139edb | 2016-01-13 15:00:54 -0800 | [diff] [blame] | 938 | free_func)) { |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 939 | return -1; |
| 940 | } |
| 941 | return index; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 942 | } |
| 943 | |
Robert Sloan | fe7cd21 | 2017-08-07 09:03:39 -0700 | [diff] [blame] | 944 | int DSA_set_ex_data(DSA *dsa, int idx, void *arg) { |
| 945 | return CRYPTO_set_ex_data(&dsa->ex_data, idx, arg); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 946 | } |
| 947 | |
Robert Sloan | fe7cd21 | 2017-08-07 09:03:39 -0700 | [diff] [blame] | 948 | void *DSA_get_ex_data(const DSA *dsa, int idx) { |
| 949 | return CRYPTO_get_ex_data(&dsa->ex_data, idx); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 950 | } |
| 951 | |
Robert Sloan | fe7cd21 | 2017-08-07 09:03:39 -0700 | [diff] [blame] | 952 | DH *DSA_dup_DH(const DSA *dsa) { |
| 953 | if (dsa == NULL) { |
| 954 | return NULL; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 955 | } |
Robert Sloan | fe7cd21 | 2017-08-07 09:03:39 -0700 | [diff] [blame] | 956 | |
| 957 | DH *ret = DH_new(); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 958 | if (ret == NULL) { |
| 959 | goto err; |
| 960 | } |
Robert Sloan | fe7cd21 | 2017-08-07 09:03:39 -0700 | [diff] [blame] | 961 | if (dsa->q != NULL) { |
| 962 | ret->priv_length = BN_num_bits(dsa->q); |
| 963 | if ((ret->q = BN_dup(dsa->q)) == NULL) { |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 964 | goto err; |
| 965 | } |
| 966 | } |
Robert Sloan | fe7cd21 | 2017-08-07 09:03:39 -0700 | [diff] [blame] | 967 | if ((dsa->p != NULL && (ret->p = BN_dup(dsa->p)) == NULL) || |
| 968 | (dsa->g != NULL && (ret->g = BN_dup(dsa->g)) == NULL) || |
| 969 | (dsa->pub_key != NULL && (ret->pub_key = BN_dup(dsa->pub_key)) == NULL) || |
| 970 | (dsa->priv_key != NULL && |
| 971 | (ret->priv_key = BN_dup(dsa->priv_key)) == NULL)) { |
| 972 | goto err; |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 973 | } |
| 974 | |
| 975 | return ret; |
| 976 | |
| 977 | err: |
Adam Langley | e9ada86 | 2015-05-11 17:20:37 -0700 | [diff] [blame] | 978 | DH_free(ret); |
Adam Langley | d9e397b | 2015-01-22 14:27:53 -0800 | [diff] [blame] | 979 | return NULL; |
| 980 | } |