[331] | 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 | /* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */
|
---|
| 11 |
|
---|
| 12 | #include <stdio.h>
|
---|
| 13 | #include "internal/cryptlib.h"
|
---|
| 14 | #include <openssl/bn.h>
|
---|
| 15 | #include <openssl/sha.h>
|
---|
| 16 | #include "dsa_locl.h"
|
---|
| 17 | #include <openssl/asn1.h>
|
---|
| 18 |
|
---|
| 19 | static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa);
|
---|
| 20 | static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
|
---|
| 21 | BIGNUM **rp);
|
---|
| 22 | static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp,
|
---|
| 23 | BIGNUM **rp, const unsigned char *dgst, int dlen);
|
---|
| 24 | static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
|
---|
| 25 | DSA_SIG *sig, DSA *dsa);
|
---|
| 26 | static int dsa_init(DSA *dsa);
|
---|
| 27 | static int dsa_finish(DSA *dsa);
|
---|
| 28 |
|
---|
| 29 | static DSA_METHOD openssl_dsa_meth = {
|
---|
| 30 | "OpenSSL DSA method",
|
---|
| 31 | dsa_do_sign,
|
---|
| 32 | dsa_sign_setup_no_digest,
|
---|
| 33 | dsa_do_verify,
|
---|
| 34 | NULL, /* dsa_mod_exp, */
|
---|
| 35 | NULL, /* dsa_bn_mod_exp, */
|
---|
| 36 | dsa_init,
|
---|
| 37 | dsa_finish,
|
---|
| 38 | DSA_FLAG_FIPS_METHOD,
|
---|
| 39 | NULL,
|
---|
| 40 | NULL,
|
---|
| 41 | NULL
|
---|
| 42 | };
|
---|
| 43 |
|
---|
| 44 | const DSA_METHOD *DSA_OpenSSL(void)
|
---|
| 45 | {
|
---|
| 46 | return &openssl_dsa_meth;
|
---|
| 47 | }
|
---|
| 48 |
|
---|
| 49 | static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa)
|
---|
| 50 | {
|
---|
| 51 | BIGNUM *kinv = NULL;
|
---|
| 52 | BIGNUM *m;
|
---|
| 53 | BIGNUM *xr;
|
---|
| 54 | BN_CTX *ctx = NULL;
|
---|
| 55 | int reason = ERR_R_BN_LIB;
|
---|
| 56 | DSA_SIG *ret = NULL;
|
---|
| 57 | int rv = 0;
|
---|
| 58 |
|
---|
| 59 | m = BN_new();
|
---|
| 60 | xr = BN_new();
|
---|
| 61 | if (m == NULL || xr == NULL)
|
---|
| 62 | goto err;
|
---|
| 63 |
|
---|
| 64 | if (!dsa->p || !dsa->q || !dsa->g) {
|
---|
| 65 | reason = DSA_R_MISSING_PARAMETERS;
|
---|
| 66 | goto err;
|
---|
| 67 | }
|
---|
| 68 |
|
---|
| 69 | ret = DSA_SIG_new();
|
---|
| 70 | if (ret == NULL)
|
---|
| 71 | goto err;
|
---|
| 72 | ret->r = BN_new();
|
---|
| 73 | ret->s = BN_new();
|
---|
| 74 | if (ret->r == NULL || ret->s == NULL)
|
---|
| 75 | goto err;
|
---|
| 76 |
|
---|
| 77 | ctx = BN_CTX_new();
|
---|
| 78 | if (ctx == NULL)
|
---|
| 79 | goto err;
|
---|
| 80 | redo:
|
---|
| 81 | if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen))
|
---|
| 82 | goto err;
|
---|
| 83 |
|
---|
| 84 | if (dlen > BN_num_bytes(dsa->q))
|
---|
| 85 | /*
|
---|
| 86 | * if the digest length is greater than the size of q use the
|
---|
| 87 | * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
|
---|
| 88 | * 4.2
|
---|
| 89 | */
|
---|
| 90 | dlen = BN_num_bytes(dsa->q);
|
---|
| 91 | if (BN_bin2bn(dgst, dlen, m) == NULL)
|
---|
| 92 | goto err;
|
---|
| 93 |
|
---|
| 94 | /* Compute s = inv(k) (m + xr) mod q */
|
---|
| 95 | if (!BN_mod_mul(xr, dsa->priv_key, ret->r, dsa->q, ctx))
|
---|
| 96 | goto err; /* s = xr */
|
---|
| 97 | if (!BN_add(ret->s, xr, m))
|
---|
| 98 | goto err; /* s = m + xr */
|
---|
| 99 | if (BN_cmp(ret->s, dsa->q) > 0)
|
---|
| 100 | if (!BN_sub(ret->s, ret->s, dsa->q))
|
---|
| 101 | goto err;
|
---|
| 102 | if (!BN_mod_mul(ret->s, ret->s, kinv, dsa->q, ctx))
|
---|
| 103 | goto err;
|
---|
| 104 |
|
---|
| 105 | /*
|
---|
| 106 | * Redo if r or s is zero as required by FIPS 186-3: this is very
|
---|
| 107 | * unlikely.
|
---|
| 108 | */
|
---|
| 109 | if (BN_is_zero(ret->r) || BN_is_zero(ret->s))
|
---|
| 110 | goto redo;
|
---|
| 111 |
|
---|
| 112 | rv = 1;
|
---|
| 113 |
|
---|
| 114 | err:
|
---|
| 115 | if (rv == 0) {
|
---|
| 116 | DSAerr(DSA_F_DSA_DO_SIGN, reason);
|
---|
| 117 | DSA_SIG_free(ret);
|
---|
| 118 | ret = NULL;
|
---|
| 119 | }
|
---|
| 120 | BN_CTX_free(ctx);
|
---|
| 121 | BN_clear_free(m);
|
---|
| 122 | BN_clear_free(xr);
|
---|
| 123 | BN_clear_free(kinv);
|
---|
| 124 | return ret;
|
---|
| 125 | }
|
---|
| 126 |
|
---|
| 127 | static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in,
|
---|
| 128 | BIGNUM **kinvp, BIGNUM **rp)
|
---|
| 129 | {
|
---|
| 130 | return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0);
|
---|
| 131 | }
|
---|
| 132 |
|
---|
| 133 | static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in,
|
---|
| 134 | BIGNUM **kinvp, BIGNUM **rp,
|
---|
| 135 | const unsigned char *dgst, int dlen)
|
---|
| 136 | {
|
---|
| 137 | BN_CTX *ctx = NULL;
|
---|
| 138 | BIGNUM *k, *kinv = NULL, *r = *rp;
|
---|
| 139 | int ret = 0;
|
---|
| 140 |
|
---|
| 141 | if (!dsa->p || !dsa->q || !dsa->g) {
|
---|
| 142 | DSAerr(DSA_F_DSA_SIGN_SETUP, DSA_R_MISSING_PARAMETERS);
|
---|
| 143 | return 0;
|
---|
| 144 | }
|
---|
| 145 |
|
---|
| 146 | k = BN_new();
|
---|
| 147 | if (k == NULL)
|
---|
| 148 | goto err;
|
---|
| 149 |
|
---|
| 150 | if (ctx_in == NULL) {
|
---|
| 151 | if ((ctx = BN_CTX_new()) == NULL)
|
---|
| 152 | goto err;
|
---|
| 153 | } else
|
---|
| 154 | ctx = ctx_in;
|
---|
| 155 |
|
---|
| 156 | /* Get random k */
|
---|
| 157 | do {
|
---|
| 158 | if (dgst != NULL) {
|
---|
| 159 | /*
|
---|
| 160 | * We calculate k from SHA512(private_key + H(message) + random).
|
---|
| 161 | * This protects the private key from a weak PRNG.
|
---|
| 162 | */
|
---|
| 163 | if (!BN_generate_dsa_nonce(k, dsa->q, dsa->priv_key, dgst,
|
---|
| 164 | dlen, ctx))
|
---|
| 165 | goto err;
|
---|
| 166 | } else if (!BN_rand_range(k, dsa->q))
|
---|
| 167 | goto err;
|
---|
| 168 | } while (BN_is_zero(k));
|
---|
| 169 |
|
---|
| 170 | BN_set_flags(k, BN_FLG_CONSTTIME);
|
---|
| 171 |
|
---|
| 172 | if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
|
---|
| 173 | if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p,
|
---|
| 174 | dsa->lock, dsa->p, ctx))
|
---|
| 175 | goto err;
|
---|
| 176 | }
|
---|
| 177 |
|
---|
| 178 | /* Compute r = (g^k mod p) mod q */
|
---|
| 179 |
|
---|
| 180 | /*
|
---|
| 181 | * We do not want timing information to leak the length of k, so we
|
---|
| 182 | * compute g^k using an equivalent exponent of fixed length. (This
|
---|
| 183 | * is a kludge that we need because the BN_mod_exp_mont() does not
|
---|
| 184 | * let us specify the desired timing behaviour.)
|
---|
| 185 | */
|
---|
| 186 |
|
---|
| 187 | if (!BN_add(k, k, dsa->q))
|
---|
| 188 | goto err;
|
---|
| 189 | if (BN_num_bits(k) <= BN_num_bits(dsa->q)) {
|
---|
| 190 | if (!BN_add(k, k, dsa->q))
|
---|
| 191 | goto err;
|
---|
| 192 | }
|
---|
| 193 |
|
---|
| 194 | if ((dsa)->meth->bn_mod_exp != NULL) {
|
---|
| 195 | if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, k, dsa->p, ctx,
|
---|
| 196 | dsa->method_mont_p))
|
---|
| 197 | goto err;
|
---|
| 198 | } else {
|
---|
| 199 | if (!BN_mod_exp_mont(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p))
|
---|
| 200 | goto err;
|
---|
| 201 | }
|
---|
| 202 |
|
---|
| 203 | if (!BN_mod(r, r, dsa->q, ctx))
|
---|
| 204 | goto err;
|
---|
| 205 |
|
---|
| 206 | /* Compute part of 's = inv(k) (m + xr) mod q' */
|
---|
| 207 | if ((kinv = BN_mod_inverse(NULL, k, dsa->q, ctx)) == NULL)
|
---|
| 208 | goto err;
|
---|
| 209 |
|
---|
| 210 | BN_clear_free(*kinvp);
|
---|
| 211 | *kinvp = kinv;
|
---|
| 212 | kinv = NULL;
|
---|
| 213 | ret = 1;
|
---|
| 214 | err:
|
---|
| 215 | if (!ret)
|
---|
| 216 | DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB);
|
---|
| 217 | if (ctx != ctx_in)
|
---|
| 218 | BN_CTX_free(ctx);
|
---|
| 219 | BN_clear_free(k);
|
---|
| 220 | return ret;
|
---|
| 221 | }
|
---|
| 222 |
|
---|
| 223 | static int dsa_do_verify(const unsigned char *dgst, int dgst_len,
|
---|
| 224 | DSA_SIG *sig, DSA *dsa)
|
---|
| 225 | {
|
---|
| 226 | BN_CTX *ctx;
|
---|
| 227 | BIGNUM *u1, *u2, *t1;
|
---|
| 228 | BN_MONT_CTX *mont = NULL;
|
---|
| 229 | const BIGNUM *r, *s;
|
---|
| 230 | int ret = -1, i;
|
---|
| 231 | if (!dsa->p || !dsa->q || !dsa->g) {
|
---|
| 232 | DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS);
|
---|
| 233 | return -1;
|
---|
| 234 | }
|
---|
| 235 |
|
---|
| 236 | i = BN_num_bits(dsa->q);
|
---|
| 237 | /* fips 186-3 allows only different sizes for q */
|
---|
| 238 | if (i != 160 && i != 224 && i != 256) {
|
---|
| 239 | DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE);
|
---|
| 240 | return -1;
|
---|
| 241 | }
|
---|
| 242 |
|
---|
| 243 | if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) {
|
---|
| 244 | DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE);
|
---|
| 245 | return -1;
|
---|
| 246 | }
|
---|
| 247 | u1 = BN_new();
|
---|
| 248 | u2 = BN_new();
|
---|
| 249 | t1 = BN_new();
|
---|
| 250 | ctx = BN_CTX_new();
|
---|
| 251 | if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL)
|
---|
| 252 | goto err;
|
---|
| 253 |
|
---|
| 254 | DSA_SIG_get0(sig, &r, &s);
|
---|
| 255 |
|
---|
| 256 | if (BN_is_zero(r) || BN_is_negative(r) ||
|
---|
| 257 | BN_ucmp(r, dsa->q) >= 0) {
|
---|
| 258 | ret = 0;
|
---|
| 259 | goto err;
|
---|
| 260 | }
|
---|
| 261 | if (BN_is_zero(s) || BN_is_negative(s) ||
|
---|
| 262 | BN_ucmp(s, dsa->q) >= 0) {
|
---|
| 263 | ret = 0;
|
---|
| 264 | goto err;
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 | /*
|
---|
| 268 | * Calculate W = inv(S) mod Q save W in u2
|
---|
| 269 | */
|
---|
| 270 | if ((BN_mod_inverse(u2, s, dsa->q, ctx)) == NULL)
|
---|
| 271 | goto err;
|
---|
| 272 |
|
---|
| 273 | /* save M in u1 */
|
---|
| 274 | if (dgst_len > (i >> 3))
|
---|
| 275 | /*
|
---|
| 276 | * if the digest length is greater than the size of q use the
|
---|
| 277 | * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3,
|
---|
| 278 | * 4.2
|
---|
| 279 | */
|
---|
| 280 | dgst_len = (i >> 3);
|
---|
| 281 | if (BN_bin2bn(dgst, dgst_len, u1) == NULL)
|
---|
| 282 | goto err;
|
---|
| 283 |
|
---|
| 284 | /* u1 = M * w mod q */
|
---|
| 285 | if (!BN_mod_mul(u1, u1, u2, dsa->q, ctx))
|
---|
| 286 | goto err;
|
---|
| 287 |
|
---|
| 288 | /* u2 = r * w mod q */
|
---|
| 289 | if (!BN_mod_mul(u2, r, u2, dsa->q, ctx))
|
---|
| 290 | goto err;
|
---|
| 291 |
|
---|
| 292 | if (dsa->flags & DSA_FLAG_CACHE_MONT_P) {
|
---|
| 293 | mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p,
|
---|
| 294 | dsa->lock, dsa->p, ctx);
|
---|
| 295 | if (!mont)
|
---|
| 296 | goto err;
|
---|
| 297 | }
|
---|
| 298 |
|
---|
| 299 | if (dsa->meth->dsa_mod_exp != NULL) {
|
---|
| 300 | if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->g, u1, dsa->pub_key, u2,
|
---|
| 301 | dsa->p, ctx, mont))
|
---|
| 302 | goto err;
|
---|
| 303 | } else {
|
---|
| 304 | if (!BN_mod_exp2_mont(t1, dsa->g, u1, dsa->pub_key, u2, dsa->p, ctx,
|
---|
| 305 | mont))
|
---|
| 306 | goto err;
|
---|
| 307 | }
|
---|
| 308 |
|
---|
| 309 | /* let u1 = u1 mod q */
|
---|
| 310 | if (!BN_mod(u1, t1, dsa->q, ctx))
|
---|
| 311 | goto err;
|
---|
| 312 |
|
---|
| 313 | /*
|
---|
| 314 | * V is now in u1. If the signature is correct, it will be equal to R.
|
---|
| 315 | */
|
---|
| 316 | ret = (BN_ucmp(u1, r) == 0);
|
---|
| 317 |
|
---|
| 318 | err:
|
---|
| 319 | if (ret < 0)
|
---|
| 320 | DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB);
|
---|
| 321 | BN_CTX_free(ctx);
|
---|
| 322 | BN_free(u1);
|
---|
| 323 | BN_free(u2);
|
---|
| 324 | BN_free(t1);
|
---|
| 325 | return (ret);
|
---|
| 326 | }
|
---|
| 327 |
|
---|
| 328 | static int dsa_init(DSA *dsa)
|
---|
| 329 | {
|
---|
| 330 | dsa->flags |= DSA_FLAG_CACHE_MONT_P;
|
---|
| 331 | return (1);
|
---|
| 332 | }
|
---|
| 333 |
|
---|
| 334 | static int dsa_finish(DSA *dsa)
|
---|
| 335 | {
|
---|
| 336 | BN_MONT_CTX_free(dsa->method_mont_p);
|
---|
| 337 | return (1);
|
---|
| 338 | }
|
---|