1 /* $OpenBSD: dsa_ossl.c,v 1.56 2024/05/11 06:43:50 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_local.h"
70 #include "dsa_local.h"
71
72 /*
73 * Since DSA parameters are entirely arbitrary and checking them to be
74 * consistent is very expensive, we cannot do so on every sign operation.
75 * Instead, cap the number of retries so we do not loop indefinitely if
76 * the generator of the multiplicative group happens to be nilpotent.
77 * The probability of needing a retry with valid parameters is negligible,
78 * so trying 32 times is amply enough.
79 */
80 #define DSA_MAX_SIGN_ITERATIONS 32
81
82 static DSA_SIG *
dsa_do_sign(const unsigned char * dgst,int dlen,DSA * dsa)83 dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
84 {
85 BIGNUM *b = NULL, *bm = NULL, *bxr = NULL, *binv = NULL, *m = NULL;
86 BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
87 BN_CTX *ctx = NULL;
88 int reason = ERR_R_BN_LIB;
89 DSA_SIG *ret = NULL;
90 int attempts = 0;
91 int noredo = 0;
92
93 if (!dsa_check_key(dsa)) {
94 reason = DSA_R_INVALID_PARAMETERS;
95 goto err;
96 }
97
98 if ((s = BN_new()) == NULL)
99 goto err;
100
101 if ((ctx = BN_CTX_new()) == NULL)
102 goto err;
103
104 BN_CTX_start(ctx);
105
106 if ((b = BN_CTX_get(ctx)) == NULL)
107 goto err;
108 if ((binv = BN_CTX_get(ctx)) == NULL)
109 goto err;
110 if ((bm = BN_CTX_get(ctx)) == NULL)
111 goto err;
112 if ((bxr = BN_CTX_get(ctx)) == NULL)
113 goto err;
114 if ((m = BN_CTX_get(ctx)) == NULL)
115 goto err;
116
117 /*
118 * If the digest length is greater than N (the bit length of q), the
119 * leftmost N bits of the digest shall be used, see FIPS 186-3, 4.2.
120 * In this case the digest length is given in bytes.
121 */
122 if (dlen > BN_num_bytes(dsa->q))
123 dlen = BN_num_bytes(dsa->q);
124 if (BN_bin2bn(dgst, dlen, m) == NULL)
125 goto err;
126
127 redo:
128 if (dsa->kinv == NULL || dsa->r == NULL) {
129 if (!DSA_sign_setup(dsa, ctx, &kinv, &r))
130 goto err;
131 } else {
132 kinv = dsa->kinv;
133 dsa->kinv = NULL;
134 r = dsa->r;
135 dsa->r = NULL;
136 noredo = 1;
137 }
138
139 /*
140 * Compute:
141 *
142 * s = inv(k)(m + xr) mod q
143 *
144 * In order to reduce the possibility of a side-channel attack, the
145 * following is calculated using a blinding value:
146 *
147 * s = inv(b)(bm + bxr)inv(k) mod q
148 *
149 * Where b is a random value in the range [1, q).
150 */
151 if (!bn_rand_interval(b, 1, dsa->q))
152 goto err;
153 if (BN_mod_inverse_ct(binv, b, dsa->q, ctx) == NULL)
154 goto err;
155
156 if (!BN_mod_mul(bxr, b, dsa->priv_key, dsa->q, ctx)) /* bx */
157 goto err;
158 if (!BN_mod_mul(bxr, bxr, r, dsa->q, ctx)) /* bxr */
159 goto err;
160 if (!BN_mod_mul(bm, b, m, dsa->q, ctx)) /* bm */
161 goto err;
162 if (!BN_mod_add(s, bxr, bm, dsa->q, ctx)) /* s = bm + bxr */
163 goto err;
164 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) /* s = b(m + xr)k^-1 */
165 goto err;
166 if (!BN_mod_mul(s, s, binv, dsa->q, ctx)) /* s = (m + xr)k^-1 */
167 goto err;
168
169 /*
170 * Redo if r or s is zero as required by FIPS 186-3: this is very
171 * unlikely.
172 */
173 if (BN_is_zero(r) || BN_is_zero(s)) {
174 if (noredo) {
175 reason = DSA_R_NEED_NEW_SETUP_VALUES;
176 goto err;
177 }
178 if (++attempts > DSA_MAX_SIGN_ITERATIONS) {
179 reason = DSA_R_INVALID_PARAMETERS;
180 goto err;
181 }
182 goto redo;
183 }
184
185 if ((ret = DSA_SIG_new()) == NULL) {
186 reason = ERR_R_MALLOC_FAILURE;
187 goto err;
188 }
189 ret->r = r;
190 ret->s = s;
191
192 err:
193 if (!ret) {
194 DSAerror(reason);
195 BN_free(r);
196 BN_free(s);
197 }
198 BN_CTX_end(ctx);
199 BN_CTX_free(ctx);
200 BN_free(kinv);
201
202 return ret;
203 }
204
205 static int
dsa_sign_setup(DSA * dsa,BN_CTX * ctx_in,BIGNUM ** kinvp,BIGNUM ** rp)206 dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
207 {
208 BIGNUM *k = NULL, *l = NULL, *m = NULL, *kinv = NULL, *r = NULL;
209 BN_CTX *ctx = NULL;
210 int q_bits;
211 int ret = 0;
212
213 if (!dsa_check_key(dsa))
214 goto err;
215
216 if ((r = BN_new()) == NULL)
217 goto err;
218
219 if ((ctx = ctx_in) == NULL)
220 ctx = BN_CTX_new();
221 if (ctx == NULL)
222 goto err;
223
224 BN_CTX_start(ctx);
225
226 if ((k = BN_CTX_get(ctx)) == NULL)
227 goto err;
228 if ((l = BN_CTX_get(ctx)) == NULL)
229 goto err;
230 if ((m = BN_CTX_get(ctx)) == NULL)
231 goto err;
232
233 /* Preallocate space */
234 q_bits = BN_num_bits(dsa->q);
235 if (!BN_set_bit(k, q_bits) ||
236 !BN_set_bit(l, q_bits) ||
237 !BN_set_bit(m, q_bits))
238 goto err;
239
240 if (!bn_rand_interval(k, 1, dsa->q))
241 goto err;
242
243 BN_set_flags(k, BN_FLG_CONSTTIME);
244
245 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
246 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
247 CRYPTO_LOCK_DSA, dsa->p, ctx))
248 goto err;
249 }
250
251 /* Compute r = (g^k mod p) mod q */
252
253 /*
254 * We do not want timing information to leak the length of k,
255 * so we compute G^k using an equivalent exponent of fixed
256 * bit-length.
257 *
258 * We unconditionally perform both of these additions to prevent a
259 * small timing information leakage. We then choose the sum that is
260 * one bit longer than the modulus.
261 *
262 * TODO: revisit the bn_copy aiming for a memory access agnostic
263 * conditional copy.
264 */
265
266 if (!BN_add(l, k, dsa->q) ||
267 !BN_add(m, l, dsa->q) ||
268 !bn_copy(k, BN_num_bits(l) > q_bits ? l : m))
269 goto err;
270
271 if (!BN_mod_exp_mont_ct(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p))
272 goto err;
273
274 if (!BN_mod_ct(r, r, dsa->q, ctx))
275 goto err;
276
277 /* Compute part of 's = inv(k) (m + xr) mod q' */
278 if ((kinv = BN_mod_inverse_ct(NULL, k, dsa->q, ctx)) == NULL)
279 goto err;
280
281 BN_free(*kinvp);
282 *kinvp = kinv;
283 kinv = NULL;
284
285 BN_free(*rp);
286 *rp = r;
287
288 ret = 1;
289
290 err:
291 if (!ret) {
292 DSAerror(ERR_R_BN_LIB);
293 BN_free(r);
294 }
295 BN_CTX_end(ctx);
296 if (ctx != ctx_in)
297 BN_CTX_free(ctx);
298
299 return ret;
300 }
301
302 static int
dsa_do_verify(const unsigned char * dgst,int dgst_len,DSA_SIG * sig,DSA * dsa)303 dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
304 {
305 BIGNUM *u1 = NULL, *u2 = NULL, *t1 = NULL;
306 BN_CTX *ctx = NULL;
307 BN_MONT_CTX *mont = NULL;
308 int qbits;
309 int ret = -1;
310
311 if (!dsa_check_key(dsa))
312 goto err;
313
314 if ((ctx = BN_CTX_new()) == NULL)
315 goto err;
316
317 BN_CTX_start(ctx);
318
319 if ((u1 = BN_CTX_get(ctx)) == NULL)
320 goto err;
321 if ((u2 = BN_CTX_get(ctx)) == NULL)
322 goto err;
323 if ((t1 = BN_CTX_get(ctx)) == NULL)
324 goto err;
325
326 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
327 BN_ucmp(sig->r, dsa->q) >= 0) {
328 ret = 0;
329 goto err;
330 }
331 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) ||
332 BN_ucmp(sig->s, dsa->q) >= 0) {
333 ret = 0;
334 goto err;
335 }
336
337 /* Calculate w = inv(s) mod q, saving w in u2. */
338 if ((BN_mod_inverse_ct(u2, sig->s, dsa->q, ctx)) == NULL)
339 goto err;
340
341 /*
342 * If the digest length is greater than the size of q use the
343 * BN_num_bits(dsa->q) leftmost bits of the digest, see FIPS 186-4, 4.2.
344 */
345 qbits = BN_num_bits(dsa->q);
346 if (dgst_len > (qbits >> 3))
347 dgst_len = (qbits >> 3);
348
349 /* Save m in u1. */
350 if (BN_bin2bn(dgst, dgst_len, u1) == NULL)
351 goto err;
352
353 /* u1 = m * w mod q */
354 if (!BN_mod_mul(u1, u1, u2, dsa->q, ctx))
355 goto err;
356
357 /* u2 = r * w mod q */
358 if (!BN_mod_mul(u2, sig->r, u2, dsa->q, ctx))
359 goto err;
360
361 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
362 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
363 CRYPTO_LOCK_DSA, dsa->p, ctx);
364 if (!mont)
365 goto err;
366 }
367
368 if (!BN_mod_exp2_mont(t1, dsa->g, u1, dsa->pub_key, u2, dsa->p,
369 ctx, mont))
370 goto err;
371
372 /* let u1 = u1 mod q */
373 if (!BN_mod_ct(u1, t1, dsa->q, ctx))
374 goto err;
375
376 /* v is in u1 - if the signature is correct, it will be equal to r. */
377 ret = BN_ucmp(u1, sig->r) == 0;
378
379 err:
380 if (ret < 0)
381 DSAerror(ERR_R_BN_LIB);
382 BN_CTX_end(ctx);
383 BN_CTX_free(ctx);
384
385 return ret;
386 }
387
388 static int
dsa_init(DSA * dsa)389 dsa_init(DSA *dsa)
390 {
391 dsa->flags |= DSA_FLAG_CACHE_MONT_P;
392 return 1;
393 }
394
395 static int
dsa_finish(DSA * dsa)396 dsa_finish(DSA *dsa)
397 {
398 BN_MONT_CTX_free(dsa->method_mont_p);
399 return 1;
400 }
401
402 static const DSA_METHOD openssl_dsa_meth = {
403 .name = "OpenSSL DSA method",
404 .dsa_do_sign = dsa_do_sign,
405 .dsa_sign_setup = dsa_sign_setup,
406 .dsa_do_verify = dsa_do_verify,
407 .init = dsa_init,
408 .finish = dsa_finish,
409 };
410
411 const DSA_METHOD *
DSA_OpenSSL(void)412 DSA_OpenSSL(void)
413 {
414 return &openssl_dsa_meth;
415 }
416 LCRYPTO_ALIAS(DSA_OpenSSL);
417
418 DSA_SIG *
DSA_SIG_new(void)419 DSA_SIG_new(void)
420 {
421 return calloc(1, sizeof(DSA_SIG));
422 }
423 LCRYPTO_ALIAS(DSA_SIG_new);
424
425 void
DSA_SIG_free(DSA_SIG * sig)426 DSA_SIG_free(DSA_SIG *sig)
427 {
428 if (sig == NULL)
429 return;
430
431 BN_free(sig->r);
432 BN_free(sig->s);
433 free(sig);
434 }
435 LCRYPTO_ALIAS(DSA_SIG_free);
436
437 int
DSA_sign_setup(DSA * dsa,BN_CTX * ctx_in,BIGNUM ** kinvp,BIGNUM ** rp)438 DSA_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp)
439 {
440 return dsa->meth->dsa_sign_setup(dsa, ctx_in, kinvp, rp);
441 }
442 LCRYPTO_ALIAS(DSA_sign_setup);
443
444 DSA_SIG *
DSA_do_sign(const unsigned char * dgst,int dlen,DSA * dsa)445 DSA_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
446 {
447 return dsa->meth->dsa_do_sign(dgst, dlen, dsa);
448 }
449 LCRYPTO_ALIAS(DSA_do_sign);
450
451 int
DSA_do_verify(const unsigned char * dgst,int dgst_len,DSA_SIG * sig,DSA * dsa)452 DSA_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa)
453 {
454 return dsa->meth->dsa_do_verify(dgst, dgst_len, sig, dsa);
455 }
456 LCRYPTO_ALIAS(DSA_do_verify);
457