Useless header include of openssl/rand.h
[openssl.git] / crypto / dsa / dsa_ossl.c
1 /*
2  * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (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 /* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
11
12 #include <stdio.h>
13 #include "internal/cryptlib.h"
14 #include <openssl/bn.h>
15 #include <openssl/sha.h>
16 #include "dsa_locl.h"
17 #include <openssl/asn1.h>
18
19 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
20 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
21                                     BIGNUM **rp);
22 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
23                           BIGNUM **rp, const unsigned char *dgst, int dlen);
24 static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
25                          DSA_SIG *sig, DSA *dsa);
26 static int dsa_init(DSA *dsa);
27 static int dsa_finish(DSA *dsa);
28
29 static DSA_METHOD openssl_dsa_meth = {
30     "OpenSSL DSA method",
31     dsa_do_sign,
32     dsa_sign_setup_no_digest,
33     dsa_do_verify,
34     NULL,                       /* dsa_mod_exp, */
35     NULL,                       /* dsa_bn_mod_exp, */
36     dsa_init,
37     dsa_finish,
38     DSA_FLAG_FIPS_METHOD,
39     NULL,
40     NULL,
41     NULL
42 };
43
44 const DSA_METHOD *DSA_OpenSSL(void)
45 {
46     return &openssl_dsa_meth;
47 }
48
49 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
50 {
51     BIGNUM *kinv = NULL;
52     BIGNUM *m;
53     BIGNUM *xr;
54     BIGNUM *r, *s;
55     BN_CTX *ctx = NULL;
56     int reason = ERR_R_BN_LIB;
57     DSA_SIG *ret = NULL;
58     int rv = 0;
59
60     m = BN_new();
61     xr = BN_new();
62     if (m == NULL || xr == NULL)
63         goto err;
64
65     if (!dsa->p || !dsa->q || !dsa->g) {
66         reason = DSA_R_MISSING_PARAMETERS;
67         goto err;
68     }
69
70     ret = DSA_SIG_new();
71     if (ret == NULL)
72         goto err;
73
74     DSA_SIG_get0(&r, &s, ret);
75
76     ctx = BN_CTX_new();
77     if (ctx == NULL)
78         goto err;
79  redo:
80     if (!dsa_sign_setup(dsa, ctx, &kinv, &r, dgst, dlen))
81         goto err;
82
83     if (dlen > BN_num_bytes(dsa->q))
84         /*
85          * if the digest length is greater than the size of q use the
86          * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
87          * 4.2
88          */
89         dlen = BN_num_bytes(dsa->q);
90     if (BN_bin2bn(dgst, dlen, m) == NULL)
91         goto err;
92
93     /* Compute  s = inv(k) (m + xr) mod q */
94     if (!BN_mod_mul(xr, dsa->priv_key, r, dsa->q, ctx))
95         goto err;               /* s = xr */
96     if (!BN_add(s, xr, m))
97         goto err;               /* s = m + xr */
98     if (BN_cmp(s, dsa->q) > 0)
99         if (!BN_sub(s, s, dsa->q))
100             goto err;
101     if (!BN_mod_mul(s, s, kinv, dsa->q, ctx))
102         goto err;
103
104     /*
105      * Redo if r or s is zero as required by FIPS 186-3: this is very
106      * unlikely.
107      */
108     if (BN_is_zero(r) || BN_is_zero(s))
109         goto redo;
110
111     rv = 1;
112
113  err:
114     if (rv == 0) {
115         DSAerr(DSA_F_DSA_DO_SIGN, reason);
116         DSA_SIG_free(ret);
117         ret = NULL;
118     }
119     BN_CTX_free(ctx);
120     BN_clear_free(m);
121     BN_clear_free(xr);
122     BN_clear_free(kinv);
123     return ret;
124 }
125
126 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in,
127                                     BIGNUM **kinvp, BIGNUM **rp)
128 {
129     return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);
130 }
131
132 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
133                           BIGNUM **kinvp, BIGNUM **rp,
134                           const unsigned char *dgst, int dlen)
135 {
136     BN_CTX *ctx = NULL;
137     BIGNUM *k, *kinv = NULL, *r = *rp;
138     int ret = 0;
139
140     if (!dsa->p || !dsa->q || !dsa->g) {
141         DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS);
142         return 0;
143     }
144
145     k = BN_new();
146     if (k == NULL)
147         goto err;
148
149     if (ctx_in == NULL) {
150         if ((ctx = BN_CTX_new()) == NULL)
151             goto err;
152     } else
153         ctx = ctx_in;
154
155     /* Get random k */
156     do {
157         if (dgst != NULL) {
158             /*
159              * We calculate k from SHA512(private_key + H(message) + random).
160              * This protects the private key from a weak PRNG.
161              */
162             if (!BN_generate_dsa_nonce(k, dsa->q, dsa->priv_key, dgst,
163                                        dlen, ctx))
164                 goto err;
165         } else if (!BN_rand_range(k, dsa->q))
166             goto err;
167     } while (BN_is_zero(k));
168
169     BN_set_flags(k, BN_FLG_CONSTTIME);
170
171     if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
172         if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
173                                     dsa->lock, dsa->p, ctx))
174             goto err;
175     }
176
177     /* Compute r = (g^k mod p) mod q */
178
179     /*
180      * We do not want timing information to leak the length of k, so we
181      * compute g^k using an equivalent exponent of fixed length. (This
182      * is a kludge that we need because the BN_mod_exp_mont() does not
183      * let us specify the desired timing behaviour.)
184      */
185
186     if (!BN_add(k, k, dsa->q))
187         goto err;
188     if (BN_num_bits(k) <= BN_num_bits(dsa->q)) {
189         if (!BN_add(k, k, dsa->q))
190             goto err;
191     }
192
193     if ((dsa)->meth->bn_mod_exp != NULL) {
194             if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, k, dsa->p, ctx,
195                                        dsa->method_mont_p))
196                 goto err;
197     } else {
198             if (!BN_mod_exp_mont(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p))
199                 goto err;
200     }
201
202     if (!BN_mod(r, r, dsa->q, ctx))
203         goto err;
204
205     /* Compute  part of 's = inv(k) (m + xr) mod q' */
206     if ((kinv = BN_mod_inverse(NULL, k, dsa->q, ctx)) == NULL)
207         goto err;
208
209     BN_clear_free(*kinvp);
210     *kinvp = kinv;
211     kinv = NULL;
212     ret = 1;
213  err:
214     if (!ret)
215         DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB);
216     if (ctx != ctx_in)
217         BN_CTX_free(ctx);
218     BN_clear_free(k);
219     return ret;
220 }
221
222 static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
223                          DSA_SIG *sig, DSA *dsa)
224 {
225     BN_CTX *ctx;
226     BIGNUM *u1, *u2, *t1;
227     BN_MONT_CTX *mont = NULL;
228     BIGNUM *r, *s;
229     int ret = -1, i;
230     if (!dsa->p || !dsa->q || !dsa->g) {
231         DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS);
232         return -1;
233     }
234
235     i = BN_num_bits(dsa->q);
236     /* fips 186-3 allows only different sizes for q */
237     if (i != 160 && i != 224 && i != 256) {
238         DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE);
239         return -1;
240     }
241
242     if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
243         DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE);
244         return -1;
245     }
246     u1 = BN_new();
247     u2 = BN_new();
248     t1 = BN_new();
249     ctx = BN_CTX_new();
250     if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL)
251         goto err;
252
253     DSA_SIG_get0(&r, &s, sig);
254
255     if (BN_is_zero(r) || BN_is_negative(r) ||
256         BN_ucmp(r, dsa->q) >= 0) {
257         ret = 0;
258         goto err;
259     }
260     if (BN_is_zero(s) || BN_is_negative(s) ||
261         BN_ucmp(s, dsa->q) >= 0) {
262         ret = 0;
263         goto err;
264     }
265
266     /*
267      * Calculate W = inv(S) mod Q save W in u2
268      */
269     if ((BN_mod_inverse(u2, s, dsa->q, ctx)) == NULL)
270         goto err;
271
272     /* save M in u1 */
273     if (dgst_len > (i >> 3))
274         /*
275          * if the digest length is greater than the size of q use the
276          * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
277          * 4.2
278          */
279         dgst_len = (i >> 3);
280     if (BN_bin2bn(dgst, dgst_len, u1) == NULL)
281         goto err;
282
283     /* u1 = M * w mod q */
284     if (!BN_mod_mul(u1, u1, u2, dsa->q, ctx))
285         goto err;
286
287     /* u2 = r * w mod q */
288     if (!BN_mod_mul(u2, r, u2, dsa->q, ctx))
289         goto err;
290
291     if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
292         mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
293                                       dsa->lock, dsa->p, ctx);
294         if (!mont)
295             goto err;
296     }
297
298     if (dsa->meth->dsa_mod_exp != NULL) {
299         if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->g, u1, dsa->pub_key, u2,
300                                     dsa->p, ctx, mont))
301             goto err;
302     } else {
303         if (!BN_mod_exp2_mont(t1, dsa->g, u1, dsa->pub_key, u2, dsa->p, ctx,
304                               mont))
305             goto err;
306     }
307
308     /* let u1 = u1 mod q */
309     if (!BN_mod(u1, t1, dsa->q, ctx))
310         goto err;
311
312     /*
313      * V is now in u1.  If the signature is correct, it will be equal to R.
314      */
315     ret = (BN_ucmp(u1, r) == 0);
316
317  err:
318     if (ret < 0)
319         DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB);
320     BN_CTX_free(ctx);
321     BN_free(u1);
322     BN_free(u2);
323     BN_free(t1);
324     return (ret);
325 }
326
327 static int dsa_init(DSA *dsa)
328 {
329     dsa->flags |= DSA_FLAG_CACHE_MONT_P;
330     return (1);
331 }
332
333 static int dsa_finish(DSA *dsa)
334 {
335     BN_MONT_CTX_free(dsa->method_mont_p);
336     return (1);
337 }