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