crypto/ec/ecdsa_ossl.c

   1 /*
   2  * Copyright 2002-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 <string.h>
  11 #include <openssl/err.h>
  12 #include <openssl/obj_mac.h>
  13 #include <openssl/rand.h>
  14 #include "internal/bn_int.h"
  15 #include "ec_lcl.h"
  16
  17 int ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
  18                           BIGNUM **rp)
  19 {
  20     if (eckey->group->meth->ecdsa_sign_setup == NULL) {
  21         ECerr(EC_F_OSSL_ECDSA_SIGN_SETUP, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA);
  22         return 0;
  23     }
  24
  25     return eckey->group->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp);
  26 }
  27
  28 ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len,
  29                                const BIGNUM *in_kinv, const BIGNUM *in_r,
  30                                EC_KEY *eckey)
  31 {
  32     if (eckey->group->meth->ecdsa_sign_sig == NULL) {
  33         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA);
  34         return NULL;
  35     }
  36
  37     return eckey->group->meth->ecdsa_sign_sig(dgst, dgst_len,
  38                                               in_kinv, in_r, eckey);
  39 }
  40
  41 int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len,
  42                           const ECDSA_SIG *sig, EC_KEY *eckey)
  43 {
  44     if (eckey->group->meth->ecdsa_verify_sig == NULL) {
  45         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA);
  46         return 0;
  47     }
  48
  49     return eckey->group->meth->ecdsa_verify_sig(dgst, dgst_len, sig, eckey);
  50 }
  51
  52 int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen,
  53                     unsigned char *sig, unsigned int *siglen,
  54                     const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey)
  55 {
  56     ECDSA_SIG *s;
  57
  58     s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey);
  59     if (s == NULL) {
  60         *siglen = 0;
  61         return 0;
  62     }
  63     *siglen = i2d_ECDSA_SIG(s, &sig);
  64     ECDSA_SIG_free(s);
  65     return 1;
  66 }
  67
  68 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
  69                             BIGNUM **kinvp, BIGNUM **rp,
  70                             const unsigned char *dgst, int dlen)
  71 {
  72     BN_CTX *ctx = NULL;
  73     BIGNUM *k = NULL, *r = NULL, *X = NULL;
  74     const BIGNUM *order;
  75     EC_POINT *tmp_point = NULL;
  76     const EC_GROUP *group;
  77     int ret = 0;
  78     int order_bits;
  79     const BIGNUM *priv_key;
  80
  81     if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
  82         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
  83         return 0;
  84     }
  85     if ((priv_key = EC_KEY_get0_private_key(eckey)) == NULL) {
  86         ECerr(EC_F_ECDSA_SIGN_SETUP, EC_R_MISSING_PRIVATE_KEY);
  87         return 0;
  88     }
  89
  90     if (!EC_KEY_can_sign(eckey)) {
  91         ECerr(EC_F_ECDSA_SIGN_SETUP, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
  92         return 0;
  93     }
  94
  95     if ((ctx = ctx_in) == NULL) {
  96         if ((ctx = BN_CTX_new_ex(eckey->libctx)) == NULL) {
  97             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
  98             return 0;
  99         }
 100     }
 101
 102     k = BN_secure_new();        /* this value is later returned in *kinvp */
 103     r = BN_new();               /* this value is later returned in *rp */
 104     X = BN_new();
 105     if (k == NULL || r == NULL || X == NULL) {
 106         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
 107         goto err;
 108     }
 109     if ((tmp_point = EC_POINT_new(group)) == NULL) {
 110         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 111         goto err;
 112     }
 113     order = EC_GROUP_get0_order(group);
 114
 115     /* Preallocate space */
 116     order_bits = BN_num_bits(order);
 117     if (!BN_set_bit(k, order_bits)
 118         || !BN_set_bit(r, order_bits)
 119         || !BN_set_bit(X, order_bits))
 120         goto err;
 121
 122     do {
 123         /* get random k */
 124         do {
 125             if (dgst != NULL) {
 126                 if (!BN_generate_dsa_nonce(k, order, priv_key,
 127                                            dgst, dlen, ctx)) {
 128                     ECerr(EC_F_ECDSA_SIGN_SETUP,
 129                           EC_R_RANDOM_NUMBER_GENERATION_FAILED);
 130                     goto err;
 131                 }
 132             } else {
 133                 if (!BN_priv_rand_range_ex(k, order, ctx)) {
 134                     ECerr(EC_F_ECDSA_SIGN_SETUP,
 135                           EC_R_RANDOM_NUMBER_GENERATION_FAILED);
 136                     goto err;
 137                 }
 138             }
 139         } while (BN_is_zero(k));
 140
 141         /* compute r the x-coordinate of generator * k */
 142         if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
 143             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 144             goto err;
 145         }
 146
 147         if (!EC_POINT_get_affine_coordinates(group, tmp_point, X, NULL, ctx)) {
 148             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
 149             goto err;
 150         }
 151
 152         if (!BN_nnmod(r, X, order, ctx)) {
 153             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 154             goto err;
 155         }
 156     } while (BN_is_zero(r));
 157
 158     /* compute the inverse of k */
 159     if (!ec_group_do_inverse_ord(group, k, k, ctx)) {
 160         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
 161         goto err;
 162     }
 163
 164     /* clear old values if necessary */
 165     BN_clear_free(*rp);
 166     BN_clear_free(*kinvp);
 167     /* save the pre-computed values  */
 168     *rp = r;
 169     *kinvp = k;
 170     ret = 1;
 171  err:
 172     if (!ret) {
 173         BN_clear_free(k);
 174         BN_clear_free(r);
 175     }
 176     if (ctx != ctx_in)
 177         BN_CTX_free(ctx);
 178     EC_POINT_free(tmp_point);
 179     BN_clear_free(X);
 180     return ret;
 181 }
 182
 183 int ecdsa_simple_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
 184                             BIGNUM **rp)
 185 {
 186     return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0);
 187 }
 188
 189 ECDSA_SIG *ecdsa_simple_sign_sig(const unsigned char *dgst, int dgst_len,
 190                                  const BIGNUM *in_kinv, const BIGNUM *in_r,
 191                                  EC_KEY *eckey)
 192 {
 193     int ok = 0, i;
 194     BIGNUM *kinv = NULL, *s, *m = NULL;
 195     const BIGNUM *order, *ckinv;
 196     BN_CTX *ctx = NULL;
 197     const EC_GROUP *group;
 198     ECDSA_SIG *ret;
 199     const BIGNUM *priv_key;
 200
 201     group = EC_KEY_get0_group(eckey);
 202     priv_key = EC_KEY_get0_private_key(eckey);
 203
 204     if (group == NULL) {
 205         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_PASSED_NULL_PARAMETER);
 206         return NULL;
 207     }
 208     if (priv_key == NULL) {
 209         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, EC_R_MISSING_PRIVATE_KEY);
 210         return NULL;
 211     }
 212
 213     if (!EC_KEY_can_sign(eckey)) {
 214         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
 215         return NULL;
 216     }
 217
 218     ret = ECDSA_SIG_new();
 219     if (ret == NULL) {
 220         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_MALLOC_FAILURE);
 221         return NULL;
 222     }
 223     ret->r = BN_new();
 224     ret->s = BN_new();
 225     if (ret->r == NULL || ret->s == NULL) {
 226         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_MALLOC_FAILURE);
 227         goto err;
 228     }
 229     s = ret->s;
 230
 231     if ((ctx = BN_CTX_new_ex(eckey->libctx)) == NULL
 232         || (m = BN_new()) == NULL) {
 233         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_MALLOC_FAILURE);
 234         goto err;
 235     }
 236
 237     order = EC_GROUP_get0_order(group);
 238     i = BN_num_bits(order);
 239     /*
 240      * Need to truncate digest if it is too long: first truncate whole bytes.
 241      */
 242     if (8 * dgst_len > i)
 243         dgst_len = (i + 7) / 8;
 244     if (!BN_bin2bn(dgst, dgst_len, m)) {
 245         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_BN_LIB);
 246         goto err;
 247     }
 248     /* If still too long, truncate remaining bits with a shift */
 249     if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
 250         ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_BN_LIB);
 251         goto err;
 252     }
 253     do {
 254         if (in_kinv == NULL || in_r == NULL) {
 255             if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) {
 256                 ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_ECDSA_LIB);
 257                 goto err;
 258             }
 259             ckinv = kinv;
 260         } else {
 261             ckinv = in_kinv;
 262             if (BN_copy(ret->r, in_r) == NULL) {
 263                 ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_MALLOC_FAILURE);
 264                 goto err;
 265             }
 266         }
 267
 268         /*
 269          * With only one multiplicant being in Montgomery domain
 270          * multiplication yields real result without post-conversion.
 271          * Also note that all operations but last are performed with
 272          * zero-padded vectors. Last operation, BN_mod_mul_montgomery
 273          * below, returns user-visible value with removed zero padding.
 274          */
 275         if (!bn_to_mont_fixed_top(s, ret->r, group->mont_data, ctx)
 276             || !bn_mul_mont_fixed_top(s, s, priv_key, group->mont_data, ctx)) {
 277             ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_BN_LIB);
 278             goto err;
 279         }
 280         if (!bn_mod_add_fixed_top(s, s, m, order)) {
 281             ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_BN_LIB);
 282             goto err;
 283         }
 284         /*
 285          * |s| can still be larger than modulus, because |m| can be. In
 286          * such case we count on Montgomery reduction to tie it up.
 287          */
 288         if (!bn_to_mont_fixed_top(s, s, group->mont_data, ctx)
 289             || !BN_mod_mul_montgomery(s, s, ckinv, group->mont_data, ctx)) {
 290             ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, ERR_R_BN_LIB);
 291             goto err;
 292         }
 293
 294         if (BN_is_zero(s)) {
 295             /*
 296              * if kinv and r have been supplied by the caller, don't
 297              * generate new kinv and r values
 298              */
 299             if (in_kinv != NULL && in_r != NULL) {
 300                 ECerr(EC_F_ECDSA_SIMPLE_SIGN_SIG, EC_R_NEED_NEW_SETUP_VALUES);
 301                 goto err;
 302             }
 303         } else {
 304             /* s != 0 => we have a valid signature */
 305             break;
 306         }
 307     } while (1);
 308
 309     ok = 1;
 310  err:
 311     if (!ok) {
 312         ECDSA_SIG_free(ret);
 313         ret = NULL;
 314     }
 315     BN_CTX_free(ctx);
 316     BN_clear_free(m);
 317     BN_clear_free(kinv);
 318     return ret;
 319 }
 320
 321 /*-
 322  * returns
 323  *      1: correct signature
 324  *      0: incorrect signature
 325  *     -1: error
 326  */
 327 int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len,
 328                       const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)
 329 {
 330     ECDSA_SIG *s;
 331     const unsigned char *p = sigbuf;
 332     unsigned char *der = NULL;
 333     int derlen = -1;
 334     int ret = -1;
 335
 336     s = ECDSA_SIG_new();
 337     if (s == NULL)
 338         return ret;
 339     if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL)
 340         goto err;
 341     /* Ensure signature uses DER and doesn't have trailing garbage */
 342     derlen = i2d_ECDSA_SIG(s, &der);
 343     if (derlen != sig_len || memcmp(sigbuf, der, derlen) != 0)
 344         goto err;
 345     ret = ECDSA_do_verify(dgst, dgst_len, s, eckey);
 346  err:
 347     OPENSSL_clear_free(der, derlen);
 348     ECDSA_SIG_free(s);
 349     return ret;
 350 }
 351
 352 int ecdsa_simple_verify_sig(const unsigned char *dgst, int dgst_len,
 353                             const ECDSA_SIG *sig, EC_KEY *eckey)
 354 {
 355     int ret = -1, i;
 356     BN_CTX *ctx;
 357     const BIGNUM *order;
 358     BIGNUM *u1, *u2, *m, *X;
 359     EC_POINT *point = NULL;
 360     const EC_GROUP *group;
 361     const EC_POINT *pub_key;
 362
 363     /* check input values */
 364     if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
 365         (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) {
 366         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, EC_R_MISSING_PARAMETERS);
 367         return -1;
 368     }
 369
 370     if (!EC_KEY_can_sign(eckey)) {
 371         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
 372         return -1;
 373     }
 374
 375     ctx = BN_CTX_new_ex(eckey->libctx);
 376     if (ctx == NULL) {
 377         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_MALLOC_FAILURE);
 378         return -1;
 379     }
 380     BN_CTX_start(ctx);
 381     u1 = BN_CTX_get(ctx);
 382     u2 = BN_CTX_get(ctx);
 383     m = BN_CTX_get(ctx);
 384     X = BN_CTX_get(ctx);
 385     if (X == NULL) {
 386         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 387         goto err;
 388     }
 389
 390     order = EC_GROUP_get0_order(group);
 391     if (order == NULL) {
 392         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_EC_LIB);
 393         goto err;
 394     }
 395
 396     if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
 397         BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) ||
 398         BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) {
 399         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, EC_R_BAD_SIGNATURE);
 400         ret = 0;                /* signature is invalid */
 401         goto err;
 402     }
 403     /* calculate tmp1 = inv(S) mod order */
 404     if (!ec_group_do_inverse_ord(group, u2, sig->s, ctx)) {
 405         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 406         goto err;
 407     }
 408     /* digest -> m */
 409     i = BN_num_bits(order);
 410     /*
 411      * Need to truncate digest if it is too long: first truncate whole bytes.
 412      */
 413     if (8 * dgst_len > i)
 414         dgst_len = (i + 7) / 8;
 415     if (!BN_bin2bn(dgst, dgst_len, m)) {
 416         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 417         goto err;
 418     }
 419     /* If still too long truncate remaining bits with a shift */
 420     if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
 421         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 422         goto err;
 423     }
 424     /* u1 = m * tmp mod order */
 425     if (!BN_mod_mul(u1, m, u2, order, ctx)) {
 426         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 427         goto err;
 428     }
 429     /* u2 = r * w mod q */
 430     if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) {
 431         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 432         goto err;
 433     }
 434
 435     if ((point = EC_POINT_new(group)) == NULL) {
 436         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_MALLOC_FAILURE);
 437         goto err;
 438     }
 439     if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) {
 440         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_EC_LIB);
 441         goto err;
 442     }
 443
 444     if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, ctx)) {
 445         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_EC_LIB);
 446         goto err;
 447     }
 448
 449     if (!BN_nnmod(u1, X, order, ctx)) {
 450         ECerr(EC_F_ECDSA_SIMPLE_VERIFY_SIG, ERR_R_BN_LIB);
 451         goto err;
 452     }
 453     /*  if the signature is correct u1 is equal to sig->r */
 454     ret = (BN_ucmp(u1, sig->r) == 0);
 455  err:
 456     BN_CTX_end(ctx);
 457     BN_CTX_free(ctx);
 458     EC_POINT_free(point);
 459     return ret;
 460 }