crypto/dsa/dsa_ossl.c

   1 /*
   2  * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (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 #include <stdio.h>
  11 #include "internal/cryptlib.h"
  12 #include "internal/bn_int.h"
  13 #include <openssl/bn.h>
  14 #include <openssl/sha.h>
  15 #include "dsa_locl.h"
  16 #include <openssl/asn1.h>
  17
  18 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
  19 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
  20                                     BIGNUM **rp);
  21 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
  22                           BIGNUM **rp, const unsigned char *dgst, int dlen);
  23 static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
  24                          DSA_SIG *sig, DSA *dsa);
  25 static int dsa_init(DSA *dsa);
  26 static int dsa_finish(DSA *dsa);
  27 static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q,
  28                                       BN_CTX *ctx);
  29
  30 static DSA_METHOD openssl_dsa_meth = {
  31     "OpenSSL DSA method",
  32     dsa_do_sign,
  33     dsa_sign_setup_no_digest,
  34     dsa_do_verify,
  35     NULL,                       /* dsa_mod_exp, */
  36     NULL,                       /* dsa_bn_mod_exp, */
  37     dsa_init,
  38     dsa_finish,
  39     DSA_FLAG_FIPS_METHOD,
  40     NULL,
  41     NULL,
  42     NULL
  43 };
  44
  45 static const DSA_METHOD *default_DSA_method = &openssl_dsa_meth;
  46
  47 void DSA_set_default_method(const DSA_METHOD *meth)
  48 {
  49     default_DSA_method = meth;
  50 }
  51
  52 const DSA_METHOD *DSA_get_default_method(void)
  53 {
  54     return default_DSA_method;
  55 }
  56
  57 const DSA_METHOD *DSA_OpenSSL(void)
  58 {
  59     return &openssl_dsa_meth;
  60 }
  61
  62 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
  63 {
  64     BIGNUM *kinv = NULL;
  65     BIGNUM *m, *blind, *blindm, *tmp;
  66     BN_CTX *ctx = NULL;
  67     int reason = ERR_R_BN_LIB;
  68     DSA_SIG *ret = NULL;
  69     int rv = 0;
  70
  71     if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) {
  72         reason = DSA_R_MISSING_PARAMETERS;
  73         goto err;
  74     }
  75     if (dsa->priv_key == NULL) {
  76         reason = DSA_R_MISSING_PRIVATE_KEY;
  77         goto err;
  78     }
  79
  80     ret = DSA_SIG_new();
  81     if (ret == NULL)
  82         goto err;
  83     ret->r = BN_new();
  84     ret->s = BN_new();
  85     if (ret->r == NULL || ret->s == NULL)
  86         goto err;
  87
  88     ctx = BN_CTX_new();
  89     if (ctx == NULL)
  90         goto err;
  91     m = BN_CTX_get(ctx);
  92     blind = BN_CTX_get(ctx);
  93     blindm = BN_CTX_get(ctx);
  94     tmp = BN_CTX_get(ctx);
  95     if (tmp == NULL)
  96         goto err;
  97
  98  redo:
  99     if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen))
 100         goto err;
 101
 102     if (dlen > BN_num_bytes(dsa->q))
 103         /*
 104          * if the digest length is greater than the size of q use the
 105          * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
 106          * 4.2
 107          */
 108         dlen = BN_num_bytes(dsa->q);
 109     if (BN_bin2bn(dgst, dlen, m) == NULL)
 110         goto err;
 111
 112     /*
 113      * The normal signature calculation is:
 114      *
 115      *   s := k^-1 * (m + r * priv_key) mod q
 116      *
 117      * We will blind this to protect against side channel attacks
 118      *
 119      *   s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod q
 120      */
 121
 122     /* Generate a blinding value */
 123     do {
 124         if (!BN_priv_rand(blind, BN_num_bits(dsa->q) - 1,
 125                           BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY))
 126             goto err;
 127     } while (BN_is_zero(blind));
 128     BN_set_flags(blind, BN_FLG_CONSTTIME);
 129     BN_set_flags(blindm, BN_FLG_CONSTTIME);
 130     BN_set_flags(tmp, BN_FLG_CONSTTIME);
 131
 132     /* tmp := blind * priv_key * r mod q */
 133     if (!BN_mod_mul(tmp, blind, dsa->priv_key, dsa->q, ctx))
 134         goto err;
 135     if (!BN_mod_mul(tmp, tmp, ret->r, dsa->q, ctx))
 136         goto err;
 137
 138     /* blindm := blind * m mod q */
 139     if (!BN_mod_mul(blindm, blind, m, dsa->q, ctx))
 140         goto err;
 141
 142     /* s : = (blind * priv_key * r) + (blind * m) mod q */
 143     if (!BN_mod_add_quick(ret->s, tmp, blindm, dsa->q))
 144         goto err;
 145
 146     /* s := s * k^-1 mod q */
 147     if (!BN_mod_mul(ret->s, ret->s, kinv, dsa->q, ctx))
 148         goto err;
 149
 150     /* s:= s * blind^-1 mod q */
 151     if (BN_mod_inverse(blind, blind, dsa->q, ctx) == NULL)
 152         goto err;
 153     if (!BN_mod_mul(ret->s, ret->s, blind, dsa->q, ctx))
 154         goto err;
 155
 156     /*
 157      * Redo if r or s is zero as required by FIPS 186-3: this is very
 158      * unlikely.
 159      */
 160     if (BN_is_zero(ret->r) || BN_is_zero(ret->s))
 161         goto redo;
 162
 163     rv = 1;
 164
 165  err:
 166     if (rv == 0) {
 167         DSAerr(DSA_F_DSA_DO_SIGN, reason);
 168         DSA_SIG_free(ret);
 169         ret = NULL;
 170     }
 171     BN_CTX_free(ctx);
 172     BN_clear_free(kinv);
 173     return ret;
 174 }
 175
 176 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in,
 177                                     BIGNUM **kinvp, BIGNUM **rp)
 178 {
 179     return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);
 180 }
 181
 182 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
 183                           BIGNUM **kinvp, BIGNUM **rp,
 184                           const unsigned char *dgst, int dlen)
 185 {
 186     BN_CTX *ctx = NULL;
 187     BIGNUM *k, *kinv = NULL, *r = *rp;
 188     BIGNUM *l;
 189     int ret = 0;
 190     int q_bits, q_words;
 191
 192     if (!dsa->p || !dsa->q || !dsa->g) {
 193         DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS);
 194         return 0;
 195     }
 196
 197     /* Reject obviously invalid parameters */
 198     if (BN_is_zero(dsa->p) || BN_is_zero(dsa->q) || BN_is_zero(dsa->g)) {
 199         DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_INVALID_PARAMETERS);
 200         return 0;
 201     }
 202     if (dsa->priv_key == NULL) {
 203         DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PRIVATE_KEY);
 204         return 0;
 205     }
 206
 207     k = BN_new();
 208     l = BN_new();
 209     if (k == NULL || l == NULL)
 210         goto err;
 211
 212     if (ctx_in == NULL) {
 213         if ((ctx = BN_CTX_new()) == NULL)
 214             goto err;
 215     } else
 216         ctx = ctx_in;
 217
 218     /* Preallocate space */
 219     q_bits = BN_num_bits(dsa->q);
 220     q_words = bn_get_top(dsa->q);
 221     if (!bn_wexpand(k, q_words + 2)
 222         || !bn_wexpand(l, q_words + 2))
 223         goto err;
 224
 225     /* Get random k */
 226     do {
 227         if (dgst != NULL) {
 228             /*
 229              * We calculate k from SHA512(private_key + H(message) + random).
 230              * This protects the private key from a weak PRNG.
 231              */
 232             if (!BN_generate_dsa_nonce(k, dsa->q, dsa->priv_key, dgst,
 233                                        dlen, ctx))
 234                 goto err;
 235         } else if (!BN_priv_rand_range(k, dsa->q))
 236             goto err;
 237     } while (BN_is_zero(k));
 238
 239     BN_set_flags(k, BN_FLG_CONSTTIME);
 240     BN_set_flags(l, BN_FLG_CONSTTIME);
 241
 242     if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
 243         if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
 244                                     dsa->lock, dsa->p, ctx))
 245             goto err;
 246     }
 247
 248     /* Compute r = (g^k mod p) mod q */
 249
 250     /*
 251      * We do not want timing information to leak the length of k, so we
 252      * compute G^k using an equivalent scalar of fixed bit-length.
 253      *
 254      * We unconditionally perform both of these additions to prevent a
 255      * small timing information leakage.  We then choose the sum that is
 256      * one bit longer than the modulus.
 257      *
 258      * There are some concerns about the efficacy of doing this.  More
 259      * specifically refer to the discussion starting with:
 260      *     https://github.com/openssl/openssl/pull/7486#discussion_r228323705
 261      * The fix is to rework BN so these gymnastics aren't required.
 262      */
 263     if (!BN_add(l, k, dsa->q)
 264         || !BN_add(k, l, dsa->q))
 265         goto err;
 266
 267     BN_consttime_swap(BN_is_bit_set(l, q_bits), k, l, q_words + 2);
 268
 269     if ((dsa)->meth->bn_mod_exp != NULL) {
 270             if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, k, dsa->p, ctx,
 271                                        dsa->method_mont_p))
 272                 goto err;
 273     } else {
 274             if (!BN_mod_exp_mont(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p))
 275                 goto err;
 276     }
 277
 278     if (!BN_mod(r, r, dsa->q, ctx))
 279         goto err;
 280
 281     /* Compute part of 's = inv(k) (m + xr) mod q' */
 282     if ((kinv = dsa_mod_inverse_fermat(k, dsa->q, ctx)) == NULL)
 283         goto err;
 284
 285     BN_clear_free(*kinvp);
 286     *kinvp = kinv;
 287     kinv = NULL;
 288     ret = 1;
 289  err:
 290     if (!ret)
 291         DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB);
 292     if (ctx != ctx_in)
 293         BN_CTX_free(ctx);
 294     BN_clear_free(k);
 295     BN_clear_free(l);
 296     return ret;
 297 }
 298
 299 static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
 300                          DSA_SIG *sig, DSA *dsa)
 301 {
 302     BN_CTX *ctx;
 303     BIGNUM *u1, *u2, *t1;
 304     BN_MONT_CTX *mont = NULL;
 305     const BIGNUM *r, *s;
 306     int ret = -1, i;
 307     if (!dsa->p || !dsa->q || !dsa->g) {
 308         DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS);
 309         return -1;
 310     }
 311
 312     i = BN_num_bits(dsa->q);
 313     /* fips 186-3 allows only different sizes for q */
 314     if (i != 160 && i != 224 && i != 256) {
 315         DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE);
 316         return -1;
 317     }
 318
 319     if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
 320         DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE);
 321         return -1;
 322     }
 323     u1 = BN_new();
 324     u2 = BN_new();
 325     t1 = BN_new();
 326     ctx = BN_CTX_new();
 327     if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL)
 328         goto err;
 329
 330     DSA_SIG_get0(sig, &r, &s);
 331
 332     if (BN_is_zero(r) || BN_is_negative(r) ||
 333         BN_ucmp(r, dsa->q) >= 0) {
 334         ret = 0;
 335         goto err;
 336     }
 337     if (BN_is_zero(s) || BN_is_negative(s) ||
 338         BN_ucmp(s, dsa->q) >= 0) {
 339         ret = 0;
 340         goto err;
 341     }
 342
 343     /*
 344      * Calculate W = inv(S) mod Q save W in u2
 345      */
 346     if ((BN_mod_inverse(u2, s, dsa->q, ctx)) == NULL)
 347         goto err;
 348
 349     /* save M in u1 */
 350     if (dgst_len > (i >> 3))
 351         /*
 352          * if the digest length is greater than the size of q use the
 353          * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
 354          * 4.2
 355          */
 356         dgst_len = (i >> 3);
 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, 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(&dsa->method_mont_p,
 370                                       dsa->lock, dsa->p, ctx);
 371         if (!mont)
 372             goto err;
 373     }
 374
 375     if (dsa->meth->dsa_mod_exp != NULL) {
 376         if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->g, u1, dsa->pub_key, u2,
 377                                     dsa->p, ctx, mont))
 378             goto err;
 379     } else {
 380         if (!BN_mod_exp2_mont(t1, dsa->g, u1, dsa->pub_key, u2, dsa->p, ctx,
 381                               mont))
 382             goto err;
 383     }
 384
 385     /* let u1 = u1 mod q */
 386     if (!BN_mod(u1, t1, dsa->q, ctx))
 387         goto err;
 388
 389     /*
 390      * V is now in u1.  If the signature is correct, it will be equal to R.
 391      */
 392     ret = (BN_ucmp(u1, r) == 0);
 393
 394  err:
 395     if (ret < 0)
 396         DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB);
 397     BN_CTX_free(ctx);
 398     BN_free(u1);
 399     BN_free(u2);
 400     BN_free(t1);
 401     return ret;
 402 }
 403
 404 static int dsa_init(DSA *dsa)
 405 {
 406     dsa->flags |= DSA_FLAG_CACHE_MONT_P;
 407     return 1;
 408 }
 409
 410 static int dsa_finish(DSA *dsa)
 411 {
 412     BN_MONT_CTX_free(dsa->method_mont_p);
 413     return 1;
 414 }
 415
 416 /*
 417  * Compute the inverse of k modulo q.
 418  * Since q is prime, Fermat's Little Theorem applies, which reduces this to
 419  * mod-exp operation.  Both the exponent and modulus are public information
 420  * so a mod-exp that doesn't leak the base is sufficient.  A newly allocated
 421  * BIGNUM is returned which the caller must free.
 422  */
 423 static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q,
 424                                       BN_CTX *ctx)
 425 {
 426     BIGNUM *res = NULL;
 427     BIGNUM *r, *e;
 428
 429     if ((r = BN_new()) == NULL)
 430         return NULL;
 431
 432     BN_CTX_start(ctx);
 433     if ((e = BN_CTX_get(ctx)) != NULL
 434             && BN_set_word(r, 2)
 435             && BN_sub(e, q, r)
 436             && BN_mod_exp_mont(r, k, e, q, ctx, NULL))
 437         res = r;
 438     else
 439         BN_free(r);
 440     BN_CTX_end(ctx);
 441     return res;
 442 }