1 | /* |
2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
3 | * |
4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
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 |
8 | */ |
9 | |
10 | #include <stdio.h> |
11 | #include "internal/cryptlib.h" |
12 | #include "crypto/bn.h" |
13 | #include <openssl/bn.h> |
14 | #include <openssl/sha.h> |
15 | #include "dsa_local.h" |
16 | #include <openssl/asn1.h> |
17 | |
18 | static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa); |
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); |
25 | static int dsa_init(DSA *dsa); |
26 | static int dsa_finish(DSA *dsa); |
27 | static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q, |
28 | BN_CTX *ctx); |
29 | |
30 | static DSA_METHOD openssl_dsa_meth = { |
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 |
43 | }; |
44 | |
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 | |
57 | const DSA_METHOD *DSA_OpenSSL(void) |
58 | { |
59 | return &openssl_dsa_meth; |
60 | } |
61 | |
62 | static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) |
63 | { |
64 | BIGNUM *kinv = NULL; |
65 | BIGNUM *m, *blind, *blindm, *tmp; |
66 | BN_CTX *ctx = NULL; |
67 | int reason = ERR_R_BN_LIB; |
68 | DSA_SIG *ret = NULL; |
69 | int rv = 0; |
70 | |
71 | if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) { |
72 | reason = DSA_R_MISSING_PARAMETERS; |
73 | goto err; |
74 | } |
75 | if (dsa->priv_key == NULL) { |
76 | reason = DSA_R_MISSING_PRIVATE_KEY; |
77 | goto err; |
78 | } |
79 | |
80 | ret = DSA_SIG_new(); |
81 | if (ret == NULL) |
82 | goto err; |
83 | ret->r = BN_new(); |
84 | ret->s = BN_new(); |
85 | if (ret->r == NULL || ret->s == NULL) |
86 | goto err; |
87 | |
88 | ctx = BN_CTX_new(); |
89 | if (ctx == NULL) |
90 | goto err; |
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 | |
98 | redo: |
99 | if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen)) |
100 | goto err; |
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 | |
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)) |
126 | goto err; |
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 */ |
147 | if (!BN_mod_mul(ret->s, ret->s, kinv, dsa->q, ctx)) |
148 | goto err; |
149 | |
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 | |
156 | /* |
157 | * Redo if r or s is zero as required by FIPS 186-3: this is very |
158 | * unlikely. |
159 | */ |
160 | if (BN_is_zero(ret->r) || BN_is_zero(ret->s)) |
161 | goto redo; |
162 | |
163 | rv = 1; |
164 | |
165 | err: |
166 | if (rv == 0) { |
167 | DSAerr(DSA_F_DSA_DO_SIGN, reason); |
168 | DSA_SIG_free(ret); |
169 | ret = NULL; |
170 | } |
171 | BN_CTX_free(ctx); |
172 | BN_clear_free(kinv); |
173 | return ret; |
174 | } |
175 | |
176 | static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, |
177 | BIGNUM **kinvp, BIGNUM **rp) |
178 | { |
179 | return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0); |
180 | } |
181 | |
182 | static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, |
183 | BIGNUM **kinvp, BIGNUM **rp, |
184 | const unsigned char *dgst, int dlen) |
185 | { |
186 | BN_CTX *ctx = NULL; |
187 | BIGNUM *k, *kinv = NULL, *r = *rp; |
188 | BIGNUM *l; |
189 | int ret = 0; |
190 | int q_bits, q_words; |
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 | |
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 | } |
202 | if (dsa->priv_key == NULL) { |
203 | DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PRIVATE_KEY); |
204 | return 0; |
205 | } |
206 | |
207 | k = BN_new(); |
208 | l = BN_new(); |
209 | if (k == NULL || l == NULL) |
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 | |
218 | /* Preallocate space */ |
219 | q_bits = BN_num_bits(dsa->q); |
220 | q_words = bn_get_top(dsa->q); |
221 | if (!bn_wexpand(k, q_words + 2) |
222 | || !bn_wexpand(l, q_words + 2)) |
223 | goto err; |
224 | |
225 | /* Get random k */ |
226 | do { |
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; |
235 | } else if (!BN_priv_rand_range(k, dsa->q)) |
236 | goto err; |
237 | } while (BN_is_zero(k)); |
238 | |
239 | BN_set_flags(k, BN_FLG_CONSTTIME); |
240 | BN_set_flags(l, BN_FLG_CONSTTIME); |
241 | |
242 | if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { |
243 | if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, |
244 | dsa->lock, dsa->p, ctx)) |
245 | goto err; |
246 | } |
247 | |
248 | /* Compute r = (g^k mod p) mod q */ |
249 | |
250 | /* |
251 | * We do not want timing information to leak the length of k, so we |
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 | * |
258 | * There are some concerns about the efficacy of doing this. More |
259 | * specifically refer to the discussion starting with: |
260 | * https://github.com/openssl/openssl/pull/7486#discussion_r228323705 |
261 | * The fix is to rework BN so these gymnastics aren't required. |
262 | */ |
263 | if (!BN_add(l, k, dsa->q) |
264 | || !BN_add(k, l, dsa->q)) |
265 | goto err; |
266 | |
267 | BN_consttime_swap(BN_is_bit_set(l, q_bits), k, l, q_words + 2); |
268 | |
269 | if ((dsa)->meth->bn_mod_exp != NULL) { |
270 | if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, k, dsa->p, ctx, |
271 | dsa->method_mont_p)) |
272 | goto err; |
273 | } else { |
274 | if (!BN_mod_exp_mont(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p)) |
275 | goto err; |
276 | } |
277 | |
278 | if (!BN_mod(r, r, dsa->q, ctx)) |
279 | goto err; |
280 | |
281 | /* Compute part of 's = inv(k) (m + xr) mod q' */ |
282 | if ((kinv = dsa_mod_inverse_fermat(k, dsa->q, ctx)) == NULL) |
283 | goto err; |
284 | |
285 | BN_clear_free(*kinvp); |
286 | *kinvp = kinv; |
287 | kinv = NULL; |
288 | ret = 1; |
289 | err: |
290 | if (!ret) |
291 | DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB); |
292 | if (ctx != ctx_in) |
293 | BN_CTX_free(ctx); |
294 | BN_clear_free(k); |
295 | BN_clear_free(l); |
296 | return ret; |
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; |
305 | const BIGNUM *r, *s; |
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(); |
327 | if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL) |
328 | goto err; |
329 | |
330 | DSA_SIG_get0(sig, &r, &s); |
331 | |
332 | if (BN_is_zero(r) || BN_is_negative(r) || |
333 | BN_ucmp(r, dsa->q) >= 0) { |
334 | ret = 0; |
335 | goto err; |
336 | } |
337 | if (BN_is_zero(s) || BN_is_negative(s) || |
338 | BN_ucmp(s, dsa->q) >= 0) { |
339 | ret = 0; |
340 | goto err; |
341 | } |
342 | |
343 | /* |
344 | * Calculate W = inv(S) mod Q save W in u2 |
345 | */ |
346 | if ((BN_mod_inverse(u2, s, dsa->q, ctx)) == NULL) |
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 */ |
365 | if (!BN_mod_mul(u2, r, u2, dsa->q, ctx)) |
366 | goto err; |
367 | |
368 | if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { |
369 | mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, |
370 | dsa->lock, dsa->p, ctx); |
371 | if (!mont) |
372 | goto err; |
373 | } |
374 | |
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 | |
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 | */ |
392 | ret = (BN_ucmp(u1, r) == 0); |
393 | |
394 | err: |
395 | if (ret < 0) |
396 | DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB); |
397 | BN_CTX_free(ctx); |
398 | BN_free(u1); |
399 | BN_free(u2); |
400 | BN_free(t1); |
401 | return ret; |
402 | } |
403 | |
404 | static int dsa_init(DSA *dsa) |
405 | { |
406 | dsa->flags |= DSA_FLAG_CACHE_MONT_P; |
407 | return 1; |
408 | } |
409 | |
410 | static int dsa_finish(DSA *dsa) |
411 | { |
412 | BN_MONT_CTX_free(dsa->method_mont_p); |
413 | return 1; |
414 | } |
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 | } |
443 | |