]>
Commit | Line | Data |
---|---|---|
d2e9e320 | 1 | /* |
1212818e | 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
c0711f7f | 3 | * |
3cdbea65 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
d2e9e320 RS |
5 | * this file except in compliance with the License. You can obtain a copy |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
c0711f7f DSH |
8 | */ |
9 | ||
c0711f7f | 10 | #include <stdio.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
25f2138b | 12 | #include "crypto/bn.h" |
c0711f7f | 13 | #include <openssl/bn.h> |
357d5de5 | 14 | #include <openssl/sha.h> |
1258396d | 15 | #include "dsa_locl.h" |
c0711f7f DSH |
16 | #include <openssl/asn1.h> |
17 | ||
18 | static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa); | |
0f113f3e MC |
19 | static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, |
20 | BIGNUM **rp); | |
21 | static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, | |
22 | BIGNUM **rp, const unsigned char *dgst, int dlen); | |
23 | static int dsa_do_verify(const unsigned char *dgst, int dgst_len, | |
24 | DSA_SIG *sig, DSA *dsa); | |
c0711f7f DSH |
25 | static int dsa_init(DSA *dsa); |
26 | static int dsa_finish(DSA *dsa); | |
415c3356 P |
27 | static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q, |
28 | BN_CTX *ctx); | |
c0711f7f DSH |
29 | |
30 | static DSA_METHOD openssl_dsa_meth = { | |
0f113f3e MC |
31 | "OpenSSL DSA method", |
32 | dsa_do_sign, | |
33 | dsa_sign_setup_no_digest, | |
34 | dsa_do_verify, | |
35 | NULL, /* dsa_mod_exp, */ | |
36 | NULL, /* dsa_bn_mod_exp, */ | |
37 | dsa_init, | |
38 | dsa_finish, | |
39 | DSA_FLAG_FIPS_METHOD, | |
40 | NULL, | |
41 | NULL, | |
42 | NULL | |
c0711f7f DSH |
43 | }; |
44 | ||
076fc555 RS |
45 | static const DSA_METHOD *default_DSA_method = &openssl_dsa_meth; |
46 | ||
47 | void DSA_set_default_method(const DSA_METHOD *meth) | |
48 | { | |
49 | default_DSA_method = meth; | |
50 | } | |
51 | ||
52 | const DSA_METHOD *DSA_get_default_method(void) | |
53 | { | |
54 | return default_DSA_method; | |
55 | } | |
56 | ||
a4aba800 | 57 | const DSA_METHOD *DSA_OpenSSL(void) |
c0711f7f | 58 | { |
0f113f3e | 59 | return &openssl_dsa_meth; |
c0711f7f DSH |
60 | } |
61 | ||
62 | static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) | |
0f113f3e | 63 | { |
706a13f1 | 64 | BIGNUM *kinv = NULL; |
7f9822a4 | 65 | BIGNUM *m, *blind, *blindm, *tmp; |
0f113f3e MC |
66 | BN_CTX *ctx = NULL; |
67 | int reason = ERR_R_BN_LIB; | |
68 | DSA_SIG *ret = NULL; | |
706a13f1 | 69 | int rv = 0; |
0f113f3e | 70 | |
7f9822a4 | 71 | if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) { |
0f113f3e MC |
72 | reason = DSA_R_MISSING_PARAMETERS; |
73 | goto err; | |
74 | } | |
7408f675 DO |
75 | if (dsa->priv_key == NULL) { |
76 | reason = DSA_R_MISSING_PRIVATE_KEY; | |
77 | goto err; | |
78 | } | |
0f113f3e | 79 | |
706a13f1 DSH |
80 | ret = DSA_SIG_new(); |
81 | if (ret == NULL) | |
0f113f3e | 82 | goto err; |
8cc44d97 DSH |
83 | ret->r = BN_new(); |
84 | ret->s = BN_new(); | |
85 | if (ret->r == NULL || ret->s == NULL) | |
86 | goto err; | |
706a13f1 | 87 | |
0f113f3e MC |
88 | ctx = BN_CTX_new(); |
89 | if (ctx == NULL) | |
90 | goto err; | |
7f9822a4 MC |
91 | m = BN_CTX_get(ctx); |
92 | blind = BN_CTX_get(ctx); | |
93 | blindm = BN_CTX_get(ctx); | |
94 | tmp = BN_CTX_get(ctx); | |
95 | if (tmp == NULL) | |
96 | goto err; | |
97 | ||
0f113f3e | 98 | redo: |
9267c11b | 99 | if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen)) |
e1d9f1ab | 100 | goto err; |
0f113f3e MC |
101 | |
102 | if (dlen > BN_num_bytes(dsa->q)) | |
103 | /* | |
104 | * if the digest length is greater than the size of q use the | |
105 | * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, | |
106 | * 4.2 | |
107 | */ | |
108 | dlen = BN_num_bytes(dsa->q); | |
109 | if (BN_bin2bn(dgst, dlen, m) == NULL) | |
110 | goto err; | |
111 | ||
7f9822a4 MC |
112 | /* |
113 | * The normal signature calculation is: | |
114 | * | |
115 | * s := k^-1 * (m + r * priv_key) mod q | |
116 | * | |
117 | * We will blind this to protect against side channel attacks | |
118 | * | |
119 | * s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod q | |
120 | */ | |
121 | ||
122 | /* Generate a blinding value */ | |
123 | do { | |
124 | if (!BN_priv_rand(blind, BN_num_bits(dsa->q) - 1, | |
125 | BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY)) | |
0f113f3e | 126 | goto err; |
7f9822a4 MC |
127 | } while (BN_is_zero(blind)); |
128 | BN_set_flags(blind, BN_FLG_CONSTTIME); | |
129 | BN_set_flags(blindm, BN_FLG_CONSTTIME); | |
130 | BN_set_flags(tmp, BN_FLG_CONSTTIME); | |
131 | ||
132 | /* tmp := blind * priv_key * r mod q */ | |
133 | if (!BN_mod_mul(tmp, blind, dsa->priv_key, dsa->q, ctx)) | |
134 | goto err; | |
135 | if (!BN_mod_mul(tmp, tmp, ret->r, dsa->q, ctx)) | |
136 | goto err; | |
137 | ||
138 | /* blindm := blind * m mod q */ | |
139 | if (!BN_mod_mul(blindm, blind, m, dsa->q, ctx)) | |
140 | goto err; | |
141 | ||
142 | /* s : = (blind * priv_key * r) + (blind * m) mod q */ | |
143 | if (!BN_mod_add_quick(ret->s, tmp, blindm, dsa->q)) | |
144 | goto err; | |
145 | ||
146 | /* s := s * k^-1 mod q */ | |
9267c11b | 147 | if (!BN_mod_mul(ret->s, ret->s, kinv, dsa->q, ctx)) |
0f113f3e MC |
148 | goto err; |
149 | ||
7f9822a4 MC |
150 | /* s:= s * blind^-1 mod q */ |
151 | if (BN_mod_inverse(blind, blind, dsa->q, ctx) == NULL) | |
152 | goto err; | |
153 | if (!BN_mod_mul(ret->s, ret->s, blind, dsa->q, ctx)) | |
154 | goto err; | |
155 | ||
0f113f3e MC |
156 | /* |
157 | * Redo if r or s is zero as required by FIPS 186-3: this is very | |
158 | * unlikely. | |
159 | */ | |
9267c11b | 160 | if (BN_is_zero(ret->r) || BN_is_zero(ret->s)) |
0f113f3e | 161 | goto redo; |
706a13f1 DSH |
162 | |
163 | rv = 1; | |
0f113f3e MC |
164 | |
165 | err: | |
706a13f1 | 166 | if (rv == 0) { |
0f113f3e | 167 | DSAerr(DSA_F_DSA_DO_SIGN, reason); |
706a13f1 DSH |
168 | DSA_SIG_free(ret); |
169 | ret = NULL; | |
0f113f3e | 170 | } |
23a1d5e9 | 171 | BN_CTX_free(ctx); |
23a1d5e9 | 172 | BN_clear_free(kinv); |
706a13f1 | 173 | return ret; |
0f113f3e | 174 | } |
c0711f7f | 175 | |
8d6a75dc | 176 | static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, |
0f113f3e MC |
177 | BIGNUM **kinvp, BIGNUM **rp) |
178 | { | |
179 | return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0); | |
190c615d AL |
180 | } |
181 | ||
8d6a75dc | 182 | static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, |
0f113f3e MC |
183 | BIGNUM **kinvp, BIGNUM **rp, |
184 | const unsigned char *dgst, int dlen) | |
185 | { | |
186 | BN_CTX *ctx = NULL; | |
033dc8fa | 187 | BIGNUM *k, *kinv = NULL, *r = *rp; |
a9cfb8c2 | 188 | BIGNUM *l; |
0f113f3e | 189 | int ret = 0; |
a9cfb8c2 | 190 | int q_bits, q_words; |
0f113f3e MC |
191 | |
192 | if (!dsa->p || !dsa->q || !dsa->g) { | |
193 | DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS); | |
194 | return 0; | |
195 | } | |
196 | ||
9acbe07d MC |
197 | /* Reject obviously invalid parameters */ |
198 | if (BN_is_zero(dsa->p) || BN_is_zero(dsa->q) || BN_is_zero(dsa->g)) { | |
199 | DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_INVALID_PARAMETERS); | |
200 | return 0; | |
201 | } | |
7408f675 DO |
202 | if (dsa->priv_key == NULL) { |
203 | DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PRIVATE_KEY); | |
204 | return 0; | |
205 | } | |
9acbe07d | 206 | |
0f113f3e | 207 | k = BN_new(); |
c0caa945 | 208 | l = BN_new(); |
a9cfb8c2 | 209 | if (k == NULL || l == NULL) |
0f113f3e MC |
210 | goto err; |
211 | ||
212 | if (ctx_in == NULL) { | |
213 | if ((ctx = BN_CTX_new()) == NULL) | |
214 | goto err; | |
215 | } else | |
216 | ctx = ctx_in; | |
217 | ||
c0caa945 P |
218 | /* Preallocate space */ |
219 | q_bits = BN_num_bits(dsa->q); | |
a9cfb8c2 P |
220 | q_words = bn_get_top(dsa->q); |
221 | if (!bn_wexpand(k, q_words + 2) | |
222 | || !bn_wexpand(l, q_words + 2)) | |
c0caa945 P |
223 | goto err; |
224 | ||
0f113f3e MC |
225 | /* Get random k */ |
226 | do { | |
0f113f3e MC |
227 | if (dgst != NULL) { |
228 | /* | |
229 | * We calculate k from SHA512(private_key + H(message) + random). | |
230 | * This protects the private key from a weak PRNG. | |
231 | */ | |
232 | if (!BN_generate_dsa_nonce(k, dsa->q, dsa->priv_key, dgst, | |
233 | dlen, ctx)) | |
234 | goto err; | |
ddc6a5c8 | 235 | } else if (!BN_priv_rand_range(k, dsa->q)) |
0f113f3e MC |
236 | goto err; |
237 | } while (BN_is_zero(k)); | |
238 | ||
47ae05ba | 239 | BN_set_flags(k, BN_FLG_CONSTTIME); |
00496b64 | 240 | BN_set_flags(l, BN_FLG_CONSTTIME); |
47ae05ba | 241 | |
0f113f3e MC |
242 | if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { |
243 | if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, | |
d188a536 | 244 | dsa->lock, dsa->p, ctx)) |
0f113f3e MC |
245 | goto err; |
246 | } | |
247 | ||
248 | /* Compute r = (g^k mod p) mod q */ | |
249 | ||
5584f65a MC |
250 | /* |
251 | * We do not want timing information to leak the length of k, so we | |
c0caa945 P |
252 | * compute G^k using an equivalent scalar of fixed bit-length. |
253 | * | |
254 | * We unconditionally perform both of these additions to prevent a | |
255 | * small timing information leakage. We then choose the sum that is | |
256 | * one bit longer than the modulus. | |
257 | * | |
a9cfb8c2 | 258 | * There are some concerns about the efficacy of doing this. More |
c2969ff6 | 259 | * specifically refer to the discussion starting with: |
a9cfb8c2 P |
260 | * https://github.com/openssl/openssl/pull/7486#discussion_r228323705 |
261 | * The fix is to rework BN so these gymnastics aren't required. | |
5584f65a | 262 | */ |
c0caa945 | 263 | if (!BN_add(l, k, dsa->q) |
a9cfb8c2 | 264 | || !BN_add(k, l, dsa->q)) |
5584f65a | 265 | goto err; |
39994462 | 266 | |
a9cfb8c2 P |
267 | BN_consttime_swap(BN_is_bit_set(l, q_bits), k, l, q_words + 2); |
268 | ||
f943e640 | 269 | if ((dsa)->meth->bn_mod_exp != NULL) { |
033dc8fa | 270 | if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, k, dsa->p, ctx, |
f943e640 MC |
271 | dsa->method_mont_p)) |
272 | goto err; | |
273 | } else { | |
033dc8fa | 274 | if (!BN_mod_exp_mont(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p)) |
f943e640 MC |
275 | goto err; |
276 | } | |
277 | ||
0f113f3e MC |
278 | if (!BN_mod(r, r, dsa->q, ctx)) |
279 | goto err; | |
280 | ||
a9cfb8c2 | 281 | /* Compute part of 's = inv(k) (m + xr) mod q' */ |
415c3356 | 282 | if ((kinv = dsa_mod_inverse_fermat(k, dsa->q, ctx)) == NULL) |
0f113f3e MC |
283 | goto err; |
284 | ||
23a1d5e9 | 285 | BN_clear_free(*kinvp); |
0f113f3e MC |
286 | *kinvp = kinv; |
287 | kinv = NULL; | |
0f113f3e MC |
288 | ret = 1; |
289 | err: | |
706a13f1 | 290 | if (!ret) |
0f113f3e | 291 | DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB); |
23a1d5e9 | 292 | if (ctx != ctx_in) |
0f113f3e MC |
293 | BN_CTX_free(ctx); |
294 | BN_clear_free(k); | |
c0caa945 | 295 | BN_clear_free(l); |
706a13f1 | 296 | return ret; |
0f113f3e MC |
297 | } |
298 | ||
299 | static int dsa_do_verify(const unsigned char *dgst, int dgst_len, | |
300 | DSA_SIG *sig, DSA *dsa) | |
301 | { | |
302 | BN_CTX *ctx; | |
303 | BIGNUM *u1, *u2, *t1; | |
304 | BN_MONT_CTX *mont = NULL; | |
9267c11b | 305 | const BIGNUM *r, *s; |
0f113f3e MC |
306 | int ret = -1, i; |
307 | if (!dsa->p || !dsa->q || !dsa->g) { | |
308 | DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS); | |
309 | return -1; | |
310 | } | |
311 | ||
312 | i = BN_num_bits(dsa->q); | |
313 | /* fips 186-3 allows only different sizes for q */ | |
314 | if (i != 160 && i != 224 && i != 256) { | |
315 | DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE); | |
316 | return -1; | |
317 | } | |
318 | ||
319 | if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { | |
320 | DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE); | |
321 | return -1; | |
322 | } | |
323 | u1 = BN_new(); | |
324 | u2 = BN_new(); | |
325 | t1 = BN_new(); | |
326 | ctx = BN_CTX_new(); | |
90945fa3 | 327 | if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL) |
0f113f3e MC |
328 | goto err; |
329 | ||
9267c11b | 330 | DSA_SIG_get0(sig, &r, &s); |
706a13f1 DSH |
331 | |
332 | if (BN_is_zero(r) || BN_is_negative(r) || | |
333 | BN_ucmp(r, dsa->q) >= 0) { | |
0f113f3e MC |
334 | ret = 0; |
335 | goto err; | |
336 | } | |
706a13f1 DSH |
337 | if (BN_is_zero(s) || BN_is_negative(s) || |
338 | BN_ucmp(s, dsa->q) >= 0) { | |
0f113f3e MC |
339 | ret = 0; |
340 | goto err; | |
341 | } | |
342 | ||
343 | /* | |
344 | * Calculate W = inv(S) mod Q save W in u2 | |
345 | */ | |
706a13f1 | 346 | if ((BN_mod_inverse(u2, s, dsa->q, ctx)) == NULL) |
0f113f3e MC |
347 | goto err; |
348 | ||
349 | /* save M in u1 */ | |
350 | if (dgst_len > (i >> 3)) | |
351 | /* | |
352 | * if the digest length is greater than the size of q use the | |
353 | * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, | |
354 | * 4.2 | |
355 | */ | |
356 | dgst_len = (i >> 3); | |
357 | if (BN_bin2bn(dgst, dgst_len, u1) == NULL) | |
358 | goto err; | |
359 | ||
360 | /* u1 = M * w mod q */ | |
361 | if (!BN_mod_mul(u1, u1, u2, dsa->q, ctx)) | |
362 | goto err; | |
363 | ||
364 | /* u2 = r * w mod q */ | |
706a13f1 | 365 | if (!BN_mod_mul(u2, r, u2, dsa->q, ctx)) |
0f113f3e MC |
366 | goto err; |
367 | ||
368 | if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { | |
369 | mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, | |
d188a536 | 370 | dsa->lock, dsa->p, ctx); |
0f113f3e MC |
371 | if (!mont) |
372 | goto err; | |
373 | } | |
374 | ||
f943e640 MC |
375 | if (dsa->meth->dsa_mod_exp != NULL) { |
376 | if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->g, u1, dsa->pub_key, u2, | |
377 | dsa->p, ctx, mont)) | |
378 | goto err; | |
379 | } else { | |
380 | if (!BN_mod_exp2_mont(t1, dsa->g, u1, dsa->pub_key, u2, dsa->p, ctx, | |
381 | mont)) | |
382 | goto err; | |
383 | } | |
384 | ||
0f113f3e MC |
385 | /* let u1 = u1 mod q */ |
386 | if (!BN_mod(u1, t1, dsa->q, ctx)) | |
387 | goto err; | |
388 | ||
389 | /* | |
390 | * V is now in u1. If the signature is correct, it will be equal to R. | |
391 | */ | |
706a13f1 | 392 | ret = (BN_ucmp(u1, r) == 0); |
0f113f3e MC |
393 | |
394 | err: | |
395 | if (ret < 0) | |
396 | DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB); | |
23a1d5e9 RS |
397 | BN_CTX_free(ctx); |
398 | BN_free(u1); | |
399 | BN_free(u2); | |
400 | BN_free(t1); | |
26a7d938 | 401 | return ret; |
0f113f3e | 402 | } |
c0711f7f DSH |
403 | |
404 | static int dsa_init(DSA *dsa) | |
405 | { | |
0f113f3e | 406 | dsa->flags |= DSA_FLAG_CACHE_MONT_P; |
208fb891 | 407 | return 1; |
c0711f7f DSH |
408 | } |
409 | ||
410 | static int dsa_finish(DSA *dsa) | |
411 | { | |
23a1d5e9 | 412 | BN_MONT_CTX_free(dsa->method_mont_p); |
208fb891 | 413 | return 1; |
c0711f7f | 414 | } |
415c3356 P |
415 | |
416 | /* | |
417 | * Compute the inverse of k modulo q. | |
418 | * Since q is prime, Fermat's Little Theorem applies, which reduces this to | |
419 | * mod-exp operation. Both the exponent and modulus are public information | |
420 | * so a mod-exp that doesn't leak the base is sufficient. A newly allocated | |
421 | * BIGNUM is returned which the caller must free. | |
422 | */ | |
423 | static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q, | |
424 | BN_CTX *ctx) | |
425 | { | |
426 | BIGNUM *res = NULL; | |
427 | BIGNUM *r, *e; | |
428 | ||
429 | if ((r = BN_new()) == NULL) | |
430 | return NULL; | |
431 | ||
432 | BN_CTX_start(ctx); | |
433 | if ((e = BN_CTX_get(ctx)) != NULL | |
434 | && BN_set_word(r, 2) | |
435 | && BN_sub(e, q, r) | |
436 | && BN_mod_exp_mont(r, k, e, q, ctx, NULL)) | |
437 | res = r; | |
438 | else | |
439 | BN_free(r); | |
440 | BN_CTX_end(ctx); | |
441 | return res; | |
442 | } |