fips/dsa/fips_dsa_ossl.c

   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
  74 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, FIPS_DSA_SIZE_T dlen,
  75                             DSA *dsa);
  76 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
  77                           BIGNUM **rp);
  78 static int dsa_do_verify(const unsigned char *dgst, FIPS_DSA_SIZE_T dgst_len,
  79                          DSA_SIG *sig, DSA *dsa);
  80 static int dsa_init(DSA *dsa);
  81 static int dsa_finish(DSA *dsa);
  82 static 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);
  85 static 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
  88 static 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
 102 int 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
 117 const DSA_METHOD *DSA_OpenSSL(void)
 118 {
 119     return &openssl_dsa_meth;
 120 }
 121
 122 static 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
 202 static 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
 300 static 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
 421 static int dsa_init(DSA *dsa)
 422 {
 423     FIPS_selftest_check();
 424     dsa->flags |= DSA_FLAG_CACHE_MONT_P;
 425     return (1);
 426 }
 427
 428 static 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
 435 static 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
 442 static 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
 450 static void *dummy = &dummy;
 451
 452 #endif                          /* ndef OPENSSL_FIPS */