fips_dsa_ossl.c revision 296465 
1/* crypto/dsa/dsa_ossl.c */
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#include <openssl/bn.h>
63#include <openssl/dsa.h>
64#include <openssl/rand.h>
65#include <openssl/asn1.h>
66#include <openssl/err.h>
67#ifndef OPENSSL_NO_ENGINE
68# include <openssl/engine.h>
69#endif
70#include <openssl/fips.h>
71
72#ifdef OPENSSL_FIPS
73
74static DSA_SIG *dsa_do_sign(const unsigned char *dgst, FIPS_DSA_SIZE_T dlen,
75                            DSA *dsa);
76static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
77                          BIGNUM **rp);
78static int dsa_do_verify(const unsigned char *dgst, FIPS_DSA_SIZE_T dgst_len,
79                         DSA_SIG *sig, DSA *dsa);
80static int dsa_init(DSA *dsa);
81static int dsa_finish(DSA *dsa);
82static int dsa_mod_exp(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
83                       BIGNUM *a2, BIGNUM *p2, BIGNUM *m, BN_CTX *ctx,
84                       BN_MONT_CTX *in_mont);
85static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
86                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx);
87
88static const DSA_METHOD openssl_dsa_meth = {
89    "OpenSSL FIPS DSA method",
90    dsa_do_sign,
91    dsa_sign_setup,
92    dsa_do_verify,
93    dsa_mod_exp,
94    dsa_bn_mod_exp,
95    dsa_init,
96    dsa_finish,
97    DSA_FLAG_FIPS_METHOD,
98    NULL
99};
100
101# if 0
102int FIPS_dsa_check(struct dsa_st *dsa)
103{
104    if (dsa->meth != &openssl_dsa_meth
105        || dsa->meth->dsa_do_sign != dsa_do_sign
106        || dsa->meth->dsa_sign_setup != dsa_sign_setup
107        || dsa->meth->dsa_mod_exp != dsa_mod_exp
108        || dsa->meth->bn_mod_exp != dsa_bn_mod_exp
109        || dsa->meth->init != dsa_init || dsa->meth->finish != dsa_finish) {
110        FIPSerr(FIPS_F_FIPS_DSA_CHECK, FIPS_R_NON_FIPS_METHOD);
111        return 0;
112    }
113    return 1;
114}
115# endif
116
117const DSA_METHOD *DSA_OpenSSL(void)
118{
119    return &openssl_dsa_meth;
120}
121
122static DSA_SIG *dsa_do_sign(const unsigned char *dgst, FIPS_DSA_SIZE_T dlen,
123                            DSA *dsa)
124{
125    BIGNUM *kinv = NULL, *r = NULL, *s = NULL;
126    BIGNUM m;
127    BIGNUM xr;
128    BN_CTX *ctx = NULL;
129    int i, reason = ERR_R_BN_LIB;
130    DSA_SIG *ret = NULL;
131
132    if (FIPS_selftest_failed()) {
133        FIPSerr(FIPS_F_DSA_DO_SIGN, FIPS_R_FIPS_SELFTEST_FAILED);
134        return NULL;
135    }
136
137    if (FIPS_mode()
138        && (BN_num_bits(dsa->p) < OPENSSL_DSA_FIPS_MIN_MODULUS_BITS)) {
139        DSAerr(DSA_F_DSA_DO_SIGN, DSA_R_KEY_SIZE_TOO_SMALL);
140        return NULL;
141    }
142
143    BN_init(&m);
144    BN_init(&xr);
145
146    if (!dsa->p || !dsa->q || !dsa->g) {
147        reason = DSA_R_MISSING_PARAMETERS;
148        goto err;
149    }
150
151    s = BN_new();
152    if (s == NULL)
153        goto err;
154
155    i = BN_num_bytes(dsa->q);   /* should be 20 */
156    if ((dlen > i) || (dlen > 50)) {
157        reason = DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE;
158        goto err;
159    }
160
161    ctx = BN_CTX_new();
162    if (ctx == NULL)
163        goto err;
164
165    if (!dsa->meth->dsa_sign_setup(dsa, ctx, &kinv, &r))
166        goto err;
167
168    if (BN_bin2bn(dgst, dlen, &m) == NULL)
169        goto err;
170
171    /* Compute  s = inv(k) (m + xr) mod q */
172    if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx))
173        goto err;               /* s = xr */
174    if (!BN_add(s, &xr, &m))
175        goto err;               /* s = m + xr */
176    if (BN_cmp(s, dsa->q) > 0)
177        BN_sub(s, s, dsa->q);
178    if (!BN_mod_mul(s, s, kinv, dsa->q, ctx))
179        goto err;
180
181    ret = DSA_SIG_new();
182    if (ret == NULL)
183        goto err;
184    ret->r = r;
185    ret->s = s;
186
187 err:
188    if (!ret) {
189        DSAerr(DSA_F_DSA_DO_SIGN, reason);
190        BN_free(r);
191        BN_free(s);
192    }
193    if (ctx != NULL)
194        BN_CTX_free(ctx);
195    BN_clear_free(&m);
196    BN_clear_free(&xr);
197    if (kinv != NULL)           /* dsa->kinv is NULL now if we used it */
198        BN_clear_free(kinv);
199    return (ret);
200}
201
202static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
203                          BIGNUM **rp)
204{
205    BN_CTX *ctx;
206    BIGNUM k, kq, *K, *kinv = NULL, *r = NULL;
207    int ret = 0;
208
209    if (!dsa->p || !dsa->q || !dsa->g) {
210        DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS);
211        return 0;
212    }
213
214    BN_init(&k);
215    BN_init(&kq);
216
217    if (ctx_in == NULL) {
218        if ((ctx = BN_CTX_new()) == NULL)
219            goto err;
220    } else
221        ctx = ctx_in;
222
223    if ((r = BN_new()) == NULL)
224        goto err;
225
226    /* Get random k */
227    do
228        if (!BN_rand_range(&k, dsa->q))
229            goto err;
230    while (BN_is_zero(&k)) ;
231    if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
232        BN_set_flags(&k, BN_FLG_CONSTTIME);
233    }
234
235    if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
236        if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p,
237                                    CRYPTO_LOCK_DSA, dsa->p, ctx))
238            goto err;
239    }
240
241    /* Compute r = (g^k mod p) mod q */
242
243    if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) {
244        if (!BN_copy(&kq, &k))
245            goto err;
246
247        /*
248         * We do not want timing information to leak the length of k, so we
249         * compute g^k using an equivalent exponent of fixed length. (This
250         * is a kludge that we need because the BN_mod_exp_mont() does not
251         * let us specify the desired timing behaviour.)
252         */
253
254        if (!BN_add(&kq, &kq, dsa->q))
255            goto err;
256        if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) {
257            if (!BN_add(&kq, &kq, dsa->q))
258                goto err;
259        }
260
261        K = &kq;
262    } else {
263        K = &k;
264    }
265    if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, K, dsa->p, ctx,
266                               (BN_MONT_CTX *)dsa->method_mont_p))
267        goto err;
268    if (!BN_mod(r, r, dsa->q, ctx))
269        goto err;
270
271    /* Compute  part of 's = inv(k) (m + xr) mod q' */
272    if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL)
273        goto err;
274
275    if (*kinvp != NULL)
276        BN_clear_free(*kinvp);
277    *kinvp = kinv;
278    kinv = NULL;
279    if (*rp != NULL)
280        BN_clear_free(*rp);
281    *rp = r;
282    ret = 1;
283 err:
284    if (!ret) {
285        DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB);
286        if (kinv != NULL)
287            BN_clear_free(kinv);
288        if (r != NULL)
289            BN_clear_free(r);
290    }
291    if (ctx_in == NULL)
292        BN_CTX_free(ctx);
293    if (kinv != NULL)
294        BN_clear_free(kinv);
295    BN_clear_free(&k);
296    BN_clear_free(&kq);
297    return (ret);
298}
299
300static int dsa_do_verify(const unsigned char *dgst, FIPS_DSA_SIZE_T dgst_len,
301                         DSA_SIG *sig, DSA *dsa)
302{
303    BN_CTX *ctx;
304    BIGNUM u1, u2, t1;
305    BN_MONT_CTX *mont = NULL;
306    int ret = -1;
307
308    if (!dsa->p || !dsa->q || !dsa->g) {
309        DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS);
310        return -1;
311    }
312
313    if (FIPS_selftest_failed()) {
314        FIPSerr(FIPS_F_DSA_DO_VERIFY, FIPS_R_FIPS_SELFTEST_FAILED);
315        return -1;
316    }
317
318    if (BN_num_bits(dsa->q) != 160) {
319        DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE);
320        return -1;
321    }
322
323    if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
324        DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE);
325        return -1;
326    }
327
328    if (FIPS_mode()
329        && (BN_num_bits(dsa->p) < OPENSSL_DSA_FIPS_MIN_MODULUS_BITS)) {
330        DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_KEY_SIZE_TOO_SMALL);
331        return -1;
332    }
333
334    BN_init(&u1);
335    BN_init(&u2);
336    BN_init(&t1);
337
338    if ((ctx = BN_CTX_new()) == NULL)
339        goto err;
340
341    if (BN_is_zero(sig->r) || sig->r->neg || BN_ucmp(sig->r, dsa->q) >= 0) {
342        ret = 0;
343        goto err;
344    }
345    if (BN_is_zero(sig->s) || sig->s->neg || BN_ucmp(sig->s, dsa->q) >= 0) {
346        ret = 0;
347        goto err;
348    }
349
350    /*
351     * Calculate W = inv(S) mod Q save W in u2
352     */
353    if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL)
354        goto err;
355
356    /* save M in u1 */
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, sig->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((BN_MONT_CTX **)&dsa->method_mont_p,
370                                      CRYPTO_LOCK_DSA, dsa->p, ctx);
371        if (!mont)
372            goto err;
373    }
374# if 0
375    {
376        BIGNUM t2;
377
378        BN_init(&t2);
379        /* v = ( g^u1 * y^u2 mod p ) mod q */
380        /* let t1 = g ^ u1 mod p */
381        if (!BN_mod_exp_mont(&t1, dsa->g, &u1, dsa->p, ctx, mont))
382            goto err;
383        /* let t2 = y ^ u2 mod p */
384        if (!BN_mod_exp_mont(&t2, dsa->pub_key, &u2, dsa->p, ctx, mont))
385            goto err;
386        /* let u1 = t1 * t2 mod p */
387        if (!BN_mod_mul(&u1, &t1, &t2, dsa->p, ctx))
388            goto err_bn;
389        BN_free(&t2);
390    }
391    /* let u1 = u1 mod q */
392    if (!BN_mod(&u1, &u1, dsa->q, ctx))
393        goto err;
394# else
395    {
396        if (!dsa->meth->dsa_mod_exp(dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2,
397                                    dsa->p, ctx, mont))
398            goto err;
399        /* BN_copy(&u1,&t1); */
400        /* let u1 = u1 mod q */
401        if (!BN_mod(&u1, &t1, dsa->q, ctx))
402            goto err;
403    }
404# endif
405    /*
406     * V is now in u1.  If the signature is correct, it will be equal to R.
407     */
408    ret = (BN_ucmp(&u1, sig->r) == 0);
409
410 err:
411    if (ret != 1)
412        DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB);
413    if (ctx != NULL)
414        BN_CTX_free(ctx);
415    BN_free(&u1);
416    BN_free(&u2);
417    BN_free(&t1);
418    return (ret);
419}
420
421static int dsa_init(DSA *dsa)
422{
423    FIPS_selftest_check();
424    dsa->flags |= DSA_FLAG_CACHE_MONT_P;
425    return (1);
426}
427
428static int dsa_finish(DSA *dsa)
429{
430    if (dsa->method_mont_p)
431        BN_MONT_CTX_free((BN_MONT_CTX *)dsa->method_mont_p);
432    return (1);
433}
434
435static int dsa_mod_exp(DSA *dsa, BIGNUM *rr, BIGNUM *a1, BIGNUM *p1,
436                       BIGNUM *a2, BIGNUM *p2, BIGNUM *m, BN_CTX *ctx,
437                       BN_MONT_CTX *in_mont)
438{
439    return BN_mod_exp2_mont(rr, a1, p1, a2, p2, m, ctx, in_mont);
440}
441
442static int dsa_bn_mod_exp(DSA *dsa, BIGNUM *r, BIGNUM *a, const BIGNUM *p,
443                          const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx)
444{
445    return BN_mod_exp_mont(r, a, p, m, ctx, m_ctx);
446}
447
448#else                           /* ndef OPENSSL_FIPS */
449
450static void *dummy = &dummy;
451
452#endif                          /* ndef OPENSSL_FIPS */
453