1 /* $OpenBSD: dsa_ossl.c,v 1.44 2022/02/24 08:35:45 tb Exp $ */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved.
4 *
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
8 *
9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA,
12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution
19 * as the author of the parts of the library used.
20 * This can be in the form of a textual message at program startup or
21 * in documentation (online or textual) provided with the package.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
26 * 1. Redistributions of source code must retain the copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * "This product includes cryptographic software written by
34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from
38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE.
52 *
53 * The licence and distribution terms for any publically available version or
54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.]
57 */
58
59 /* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
60
61 #include <stdio.h>
62
63 #include <openssl/asn1.h>
64 #include <openssl/bn.h>
65 #include <openssl/dsa.h>
66 #include <openssl/err.h>
67 #include <openssl/sha.h>
68
69 #include "bn_lcl.h"
70 #include "dsa_locl.h"
71
72 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
73 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
74 BIGNUM **rp);
75 static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig,
76 DSA *dsa);
77 static int dsa_init(DSA *dsa);
78 static int dsa_finish(DSA *dsa);
79
80 static DSA_METHOD openssl_dsa_meth = {
81 .name = "OpenSSL DSA method",
82 .dsa_do_sign = dsa_do_sign,
83 .dsa_sign_setup = dsa_sign_setup,
84 .dsa_do_verify = dsa_do_verify,
85 .init = dsa_init,
86 .finish = dsa_finish,
87 };
88
89 const DSA_METHOD *
DSA_OpenSSL(void)90 DSA_OpenSSL(void)
91 {
92 return &openssl_dsa_meth;
93 }
94
95 static DSA_SIG *
dsa_do_sign(const unsigned char * dgst,int dlen,DSA * dsa)96 dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
97 {
98 BIGNUM b, bm, bxr, binv, m, *kinv = NULL, *r = NULL, *s = NULL;
99 BN_CTX *ctx = NULL;
100 int reason = ERR_R_BN_LIB;
101 DSA_SIG *ret = NULL;
102 int noredo = 0;
103
104 BN_init(&b);
105 BN_init(&binv);
106 BN_init(&bm);
107 BN_init(&bxr);
108 BN_init(&m);
109
110 if (!dsa->p || !dsa->q || !dsa->g) {
111 reason = DSA_R_MISSING_PARAMETERS;
112 goto err;
113 }
114
115 s = BN_new();
116 if (s == NULL)
117 goto err;
118 ctx = BN_CTX_new();
119 if (ctx == NULL)
120 goto err;
121
122 /*
123 * If the digest length is greater than N (the bit length of q), the
124 * leftmost N bits of the digest shall be used, see FIPS 186-3, 4.2.
125 * In this case the digest length is given in bytes.
126 */
127 if (dlen > BN_num_bytes(dsa->q))
128 dlen = BN_num_bytes(dsa->q);
129 if (BN_bin2bn(dgst, dlen, &m) == NULL)
130 goto err;
131
132 redo:
133 if (dsa->kinv == NULL || dsa->r == NULL) {
134 if (!DSA_sign_setup(dsa, ctx, &kinv, &r))
135 goto err;
136 } else {
137 kinv = dsa->kinv;
138 dsa->kinv = NULL;
139 r = dsa->r;
140 dsa->r = NULL;
141 noredo = 1;
142 }
143
144 /*
145 * Compute:
146 *
147 * s = inv(k)(m + xr) mod q
148 *
149 * In order to reduce the possibility of a side-channel attack, the
150 * following is calculated using a blinding value:
151 *
152 * s = inv(b)(bm + bxr)inv(k) mod q
153 *
154 * Where b is a random value in the range [1, q).
155 */
156 if (!bn_rand_interval(&b, BN_value_one(), dsa->q))
157 goto err;
158 if (BN_mod_inverse_ct(&binv, &b, dsa->q, ctx) == NULL)
159 goto err;
160
161 if (!BN_mod_mul(&bxr, &b, dsa->priv_key, dsa->q, ctx)) /* bx */
162 goto err;
163 if (!BN_mod_mul(&bxr, &bxr, r, dsa->q, ctx)) /* bxr */
164 goto err;
165 if (!BN_mod_mul(&bm, &b, &m, dsa->q, ctx)) /* bm */
166 goto err;
167 if (!BN_mod_add(s, &bxr, &bm, dsa->q, ctx)) /* s = bm + bxr */
168 goto err;
169 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) /* s = b(m + xr)k^-1 */
170 goto err;
171 if (!BN_mod_mul(s, s, &binv, dsa->q, ctx)) /* s = (m + xr)k^-1 */
172 goto err;
173
174 /*
175 * Redo if r or s is zero as required by FIPS 186-3: this is very
176 * unlikely.
177 */
178 if (BN_is_zero(r) || BN_is_zero(s)) {
179 if (noredo) {
180 reason = DSA_R_NEED_NEW_SETUP_VALUES;
181 goto err;
182 }
183 goto redo;
184 }
185
186 if ((ret = DSA_SIG_new()) == NULL) {
187 reason = ERR_R_MALLOC_FAILURE;
188 goto err;
189 }
190 ret->r = r;
191 ret->s = s;
192
193 err:
194 if (!ret) {
195 DSAerror(reason);
196 BN_free(r);
197 BN_free(s);
198 }
199 BN_CTX_free(ctx);
200 BN_clear_free(&b);
201 BN_clear_free(&bm);
202 BN_clear_free(&bxr);
203 BN_clear_free(&binv);
204 BN_clear_free(&m);
205 BN_clear_free(kinv);
206
207 return ret;
208 }
209
210 static int
dsa_sign_setup(DSA * dsa,BN_CTX * ctx_in,BIGNUM ** kinvp,BIGNUM ** rp)211 dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
212 {
213 BN_CTX *ctx;
214 BIGNUM k, l, m, *kinv = NULL, *r = NULL;
215 int q_bits, ret = 0;
216
217 if (!dsa->p || !dsa->q || !dsa->g) {
218 DSAerror(DSA_R_MISSING_PARAMETERS);
219 return 0;
220 }
221
222 BN_init(&k);
223 BN_init(&l);
224 BN_init(&m);
225
226 if (ctx_in == NULL) {
227 if ((ctx = BN_CTX_new()) == NULL)
228 goto err;
229 } else
230 ctx = ctx_in;
231
232 if ((r = BN_new()) == NULL)
233 goto err;
234
235 /* Preallocate space */
236 q_bits = BN_num_bits(dsa->q);
237 if (!BN_set_bit(&k, q_bits) ||
238 !BN_set_bit(&l, q_bits) ||
239 !BN_set_bit(&m, q_bits))
240 goto err;
241
242 if (!bn_rand_interval(&k, BN_value_one(), dsa->q))
243 goto err;
244
245 BN_set_flags(&k, BN_FLG_CONSTTIME);
246
247 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
248 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
249 CRYPTO_LOCK_DSA, dsa->p, ctx))
250 goto err;
251 }
252
253 /* Compute r = (g^k mod p) mod q */
254
255 /*
256 * We do not want timing information to leak the length of k,
257 * so we compute G^k using an equivalent exponent of fixed
258 * bit-length.
259 *
260 * We unconditionally perform both of these additions to prevent a
261 * small timing information leakage. We then choose the sum that is
262 * one bit longer than the modulus.
263 *
264 * TODO: revisit the BN_copy aiming for a memory access agnostic
265 * conditional copy.
266 */
267
268 if (!BN_add(&l, &k, dsa->q) ||
269 !BN_add(&m, &l, dsa->q) ||
270 !BN_copy(&k, BN_num_bits(&l) > q_bits ? &l : &m))
271 goto err;
272
273 if (dsa->meth->bn_mod_exp != NULL) {
274 if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, &k, dsa->p, ctx,
275 dsa->method_mont_p))
276 goto err;
277 } else {
278 if (!BN_mod_exp_mont_ct(r, dsa->g, &k, dsa->p, ctx,
279 dsa->method_mont_p))
280 goto err;
281 }
282
283 if (!BN_mod_ct(r, r, dsa->q, ctx))
284 goto err;
285
286 /* Compute part of 's = inv(k) (m + xr) mod q' */
287 if ((kinv = BN_mod_inverse_ct(NULL, &k, dsa->q, ctx)) == NULL)
288 goto err;
289
290 BN_clear_free(*kinvp);
291 *kinvp = kinv;
292 kinv = NULL;
293 BN_clear_free(*rp);
294 *rp = r;
295
296 ret = 1;
297
298 err:
299 if (!ret) {
300 DSAerror(ERR_R_BN_LIB);
301 BN_clear_free(r);
302 }
303 if (ctx_in == NULL)
304 BN_CTX_free(ctx);
305 BN_clear_free(&k);
306 BN_clear_free(&l);
307 BN_clear_free(&m);
308
309 return ret;
310 }
311
312 static int
dsa_do_verify(const unsigned char * dgst,int dgst_len,DSA_SIG * sig,DSA * dsa)313 dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
314 {
315 BN_CTX *ctx;
316 BIGNUM u1, u2, t1;
317 BN_MONT_CTX *mont = NULL;
318 int qbits;
319 int ret = -1;
320
321 if (!dsa->p || !dsa->q || !dsa->g) {
322 DSAerror(DSA_R_MISSING_PARAMETERS);
323 return -1;
324 }
325
326 /* FIPS 186-3 allows only three different sizes for q. */
327 qbits = BN_num_bits(dsa->q);
328 if (qbits != 160 && qbits != 224 && qbits != 256) {
329 DSAerror(DSA_R_BAD_Q_VALUE);
330 return -1;
331 }
332 if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
333 DSAerror(DSA_R_MODULUS_TOO_LARGE);
334 return -1;
335 }
336
337 BN_init(&u1);
338 BN_init(&u2);
339 BN_init(&t1);
340
341 if ((ctx = BN_CTX_new()) == NULL)
342 goto err;
343
344 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
345 BN_ucmp(sig->r, dsa->q) >= 0) {
346 ret = 0;
347 goto err;
348 }
349 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
350 BN_ucmp(sig->s, dsa->q) >= 0) {
351 ret = 0;
352 goto err;
353 }
354
355 /* Calculate w = inv(s) mod q, saving w in u2. */
356 if ((BN_mod_inverse_ct(&u2, sig->s, dsa->q, ctx)) == NULL)
357 goto err;
358
359 /*
360 * If the digest length is greater than the size of q use the
361 * BN_num_bits(dsa->q) leftmost bits of the digest, see FIPS 186-3, 4.2.
362 */
363 if (dgst_len > (qbits >> 3))
364 dgst_len = (qbits >> 3);
365
366 /* Save m in u1. */
367 if (BN_bin2bn(dgst, dgst_len, &u1) == NULL)
368 goto err;
369
370 /* u1 = m * w mod q */
371 if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx))
372 goto err;
373
374 /* u2 = r * w mod q */
375 if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx))
376 goto err;
377
378 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
379 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
380 CRYPTO_LOCK_DSA, dsa->p, ctx);
381 if (!mont)
382 goto err;
383 }
384
385 if (dsa->meth->dsa_mod_exp != NULL) {
386 if (!dsa->meth->dsa_mod_exp(dsa, &t1, dsa->g, &u1, dsa->pub_key,
387 &u2, dsa->p, ctx, mont))
388 goto err;
389 } else {
390 if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2,
391 dsa->p, ctx, mont))
392 goto err;
393 }
394
395 /* BN_copy(&u1,&t1); */
396 /* let u1 = u1 mod q */
397 if (!BN_mod_ct(&u1, &t1, dsa->q, ctx))
398 goto err;
399
400 /* v is in u1 - if the signature is correct, it will be equal to r. */
401 ret = BN_ucmp(&u1, sig->r) == 0;
402
403 err:
404 if (ret < 0)
405 DSAerror(ERR_R_BN_LIB);
406 BN_CTX_free(ctx);
407 BN_free(&u1);
408 BN_free(&u2);
409 BN_free(&t1);
410
411 return ret;
412 }
413
414 static int
dsa_init(DSA * dsa)415 dsa_init(DSA *dsa)
416 {
417 dsa->flags |= DSA_FLAG_CACHE_MONT_P;
418 return 1;
419 }
420
421 static int
dsa_finish(DSA * dsa)422 dsa_finish(DSA *dsa)
423 {
424 BN_MONT_CTX_free(dsa->method_mont_p);
425 return 1;
426 }
427
428