crypto/dsa/dsa_ossl.c

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