ecs_ossl.c revision 337982
1/* crypto/ecdsa/ecs_ossl.c */ 2/* 3 * Written by Nils Larsch for the OpenSSL project 4 */ 5/* ==================================================================== 6 * Copyright (c) 1998-2018 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. All advertising materials mentioning features or use of this 21 * software must display the following acknowledgment: 22 * "This product includes software developed by the OpenSSL Project 23 * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 24 * 25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26 * endorse or promote products derived from this software without 27 * prior written permission. For written permission, please contact 28 * openssl-core@OpenSSL.org. 29 * 30 * 5. Products derived from this software may not be called "OpenSSL" 31 * nor may "OpenSSL" appear in their names without prior written 32 * permission of the OpenSSL Project. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50 * OF THE POSSIBILITY OF SUCH DAMAGE. 51 * ==================================================================== 52 * 53 * This product includes cryptographic software written by Eric Young 54 * (eay@cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh@cryptsoft.com). 56 * 57 */ 58 59#include "ecs_locl.h" 60#include <openssl/err.h> 61#include <openssl/obj_mac.h> 62#include <openssl/bn.h> 63#include "bn_int.h" 64 65static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, 66 const BIGNUM *, const BIGNUM *, 67 EC_KEY *eckey); 68static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 69 BIGNUM **rp); 70static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 71 const ECDSA_SIG *sig, EC_KEY *eckey); 72 73static ECDSA_METHOD openssl_ecdsa_meth = { 74 "OpenSSL ECDSA method", 75 ecdsa_do_sign, 76 ecdsa_sign_setup, 77 ecdsa_do_verify, 78#if 0 79 NULL, /* init */ 80 NULL, /* finish */ 81#endif 82 0, /* flags */ 83 NULL /* app_data */ 84}; 85 86const ECDSA_METHOD *ECDSA_OpenSSL(void) 87{ 88 return &openssl_ecdsa_meth; 89} 90 91static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 92 BIGNUM **rp) 93{ 94 BN_CTX *ctx = NULL; 95 BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL; 96 EC_POINT *tmp_point = NULL; 97 const EC_GROUP *group; 98 int ret = 0; 99 int order_bits; 100 101 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { 102 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER); 103 return 0; 104 } 105 106 if (ctx_in == NULL) { 107 if ((ctx = BN_CTX_new()) == NULL) { 108 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); 109 return 0; 110 } 111 } else 112 ctx = ctx_in; 113 114 k = BN_new(); /* this value is later returned in *kinvp */ 115 r = BN_new(); /* this value is later returned in *rp */ 116 order = BN_new(); 117 X = BN_new(); 118 if (!k || !r || !order || !X) { 119 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); 120 goto err; 121 } 122 if ((tmp_point = EC_POINT_new(group)) == NULL) { 123 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 124 goto err; 125 } 126 if (!EC_GROUP_get_order(group, order, ctx)) { 127 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 128 goto err; 129 } 130 131 /* Preallocate space */ 132 order_bits = BN_num_bits(order); 133 if (!BN_set_bit(k, order_bits) 134 || !BN_set_bit(r, order_bits) 135 || !BN_set_bit(X, order_bits)) 136 goto err; 137 138 do { 139 /* get random k */ 140 do 141 if (!BN_rand_range(k, order)) { 142 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, 143 ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 144 goto err; 145 } 146 while (BN_is_zero(k)) ; 147 148 /* 149 * We do not want timing information to leak the length of k, so we 150 * compute G*k using an equivalent scalar of fixed bit-length. 151 * 152 * We unconditionally perform both of these additions to prevent a 153 * small timing information leakage. We then choose the sum that is 154 * one bit longer than the order. This guarantees the code 155 * path used in the constant time implementations elsewhere. 156 * 157 * TODO: revisit the BN_copy aiming for a memory access agnostic 158 * conditional copy. 159 */ 160 if (!BN_add(r, k, order) 161 || !BN_add(X, r, order) 162 || !BN_copy(k, BN_num_bits(r) > order_bits ? r : X)) 163 goto err; 164 165 /* compute r the x-coordinate of generator * k */ 166 if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { 167 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 168 goto err; 169 } 170 if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == 171 NID_X9_62_prime_field) { 172 if (!EC_POINT_get_affine_coordinates_GFp 173 (group, tmp_point, X, NULL, ctx)) { 174 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 175 goto err; 176 } 177 } 178#ifndef OPENSSL_NO_EC2M 179 else { /* NID_X9_62_characteristic_two_field */ 180 181 if (!EC_POINT_get_affine_coordinates_GF2m(group, 182 tmp_point, X, NULL, 183 ctx)) { 184 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); 185 goto err; 186 } 187 } 188#endif 189 if (!BN_nnmod(r, X, order, ctx)) { 190 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 191 goto err; 192 } 193 } 194 while (BN_is_zero(r)); 195 196 /* compute the inverse of k */ 197 if (EC_GROUP_get_mont_data(group) != NULL) { 198 /* 199 * We want inverse in constant time, therefore we utilize the fact 200 * order must be prime and use Fermats Little Theorem instead. 201 */ 202 if (!BN_set_word(X, 2)) { 203 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 204 goto err; 205 } 206 if (!BN_mod_sub(X, order, X, order, ctx)) { 207 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 208 goto err; 209 } 210 BN_set_flags(X, BN_FLG_CONSTTIME); 211 if (!BN_mod_exp_mont_consttime 212 (k, k, X, order, ctx, EC_GROUP_get_mont_data(group))) { 213 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 214 goto err; 215 } 216 } else { 217 if (!BN_mod_inverse(k, k, order, ctx)) { 218 ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); 219 goto err; 220 } 221 } 222 223 /* clear old values if necessary */ 224 if (*rp != NULL) 225 BN_clear_free(*rp); 226 if (*kinvp != NULL) 227 BN_clear_free(*kinvp); 228 /* save the pre-computed values */ 229 *rp = r; 230 *kinvp = k; 231 ret = 1; 232 err: 233 if (!ret) { 234 if (k != NULL) 235 BN_clear_free(k); 236 if (r != NULL) 237 BN_clear_free(r); 238 } 239 if (ctx_in == NULL) 240 BN_CTX_free(ctx); 241 if (order != NULL) 242 BN_free(order); 243 if (tmp_point != NULL) 244 EC_POINT_free(tmp_point); 245 if (X) 246 BN_clear_free(X); 247 return (ret); 248} 249 250static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 251 const BIGNUM *in_kinv, const BIGNUM *in_r, 252 EC_KEY *eckey) 253{ 254 int ok = 0, i; 255 BIGNUM *kinv = NULL, *s, *m = NULL, *order = NULL; 256 const BIGNUM *ckinv; 257 BN_CTX *ctx = NULL; 258 const EC_GROUP *group; 259 ECDSA_SIG *ret; 260 ECDSA_DATA *ecdsa; 261 const BIGNUM *priv_key; 262 BN_MONT_CTX *mont_data; 263 264 ecdsa = ecdsa_check(eckey); 265 group = EC_KEY_get0_group(eckey); 266 priv_key = EC_KEY_get0_private_key(eckey); 267 268 if (group == NULL || priv_key == NULL || ecdsa == NULL) { 269 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER); 270 return NULL; 271 } 272 273 ret = ECDSA_SIG_new(); 274 if (!ret) { 275 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 276 return NULL; 277 } 278 s = ret->s; 279 280 if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || 281 (m = BN_new()) == NULL) { 282 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 283 goto err; 284 } 285 286 if (!EC_GROUP_get_order(group, order, ctx)) { 287 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB); 288 goto err; 289 } 290 mont_data = EC_GROUP_get_mont_data(group); 291 292 i = BN_num_bits(order); 293 /* 294 * Need to truncate digest if it is too long: first truncate whole bytes. 295 */ 296 if (8 * dgst_len > i) 297 dgst_len = (i + 7) / 8; 298 if (!BN_bin2bn(dgst, dgst_len, m)) { 299 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 300 goto err; 301 } 302 /* If still too long truncate remaining bits with a shift */ 303 if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { 304 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 305 goto err; 306 } 307 do { 308 if (in_kinv == NULL || in_r == NULL) { 309 if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) { 310 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_ECDSA_LIB); 311 goto err; 312 } 313 ckinv = kinv; 314 } else { 315 ckinv = in_kinv; 316 if (BN_copy(ret->r, in_r) == NULL) { 317 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); 318 goto err; 319 } 320 } 321 322 /* 323 * With only one multiplicant being in Montgomery domain 324 * multiplication yields real result without post-conversion. 325 * Also note that all operations but last are performed with 326 * zero-padded vectors. Last operation, BN_mod_mul_montgomery 327 * below, returns user-visible value with removed zero padding. 328 */ 329 if (!bn_to_mont_fixed_top(s, ret->r, mont_data, ctx) 330 || !bn_mul_mont_fixed_top(s, s, priv_key, mont_data, ctx)) { 331 goto err; 332 } 333 if (!bn_mod_add_fixed_top(s, s, m, order)) { 334 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 335 goto err; 336 } 337 /* 338 * |s| can still be larger than modulus, because |m| can be. In 339 * such case we count on Montgomery reduction to tie it up. 340 */ 341 if (!bn_to_mont_fixed_top(s, s, mont_data, ctx) 342 || !BN_mod_mul_montgomery(s, s, ckinv, mont_data, ctx)) { 343 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); 344 goto err; 345 } 346 if (BN_is_zero(s)) { 347 /* 348 * if kinv and r have been supplied by the caller don't to 349 * generate new kinv and r values 350 */ 351 if (in_kinv != NULL && in_r != NULL) { 352 ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, 353 ECDSA_R_NEED_NEW_SETUP_VALUES); 354 goto err; 355 } 356 } else 357 /* s != 0 => we have a valid signature */ 358 break; 359 } 360 while (1); 361 362 ok = 1; 363 err: 364 if (!ok) { 365 ECDSA_SIG_free(ret); 366 ret = NULL; 367 } 368 if (ctx) 369 BN_CTX_free(ctx); 370 if (m) 371 BN_clear_free(m); 372 if (order) 373 BN_free(order); 374 if (kinv) 375 BN_clear_free(kinv); 376 return ret; 377} 378 379static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 380 const ECDSA_SIG *sig, EC_KEY *eckey) 381{ 382 int ret = -1, i; 383 BN_CTX *ctx; 384 BIGNUM *order, *u1, *u2, *m, *X; 385 EC_POINT *point = NULL; 386 const EC_GROUP *group; 387 const EC_POINT *pub_key; 388 389 /* check input values */ 390 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 391 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) { 392 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS); 393 return -1; 394 } 395 396 ctx = BN_CTX_new(); 397 if (!ctx) { 398 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); 399 return -1; 400 } 401 BN_CTX_start(ctx); 402 order = BN_CTX_get(ctx); 403 u1 = BN_CTX_get(ctx); 404 u2 = BN_CTX_get(ctx); 405 m = BN_CTX_get(ctx); 406 X = BN_CTX_get(ctx); 407 if (!X) { 408 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 409 goto err; 410 } 411 412 if (!EC_GROUP_get_order(group, order, ctx)) { 413 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 414 goto err; 415 } 416 417 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 418 BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 419 BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) { 420 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE); 421 ret = 0; /* signature is invalid */ 422 goto err; 423 } 424 /* calculate tmp1 = inv(S) mod order */ 425 if (!BN_mod_inverse(u2, sig->s, order, ctx)) { 426 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 427 goto err; 428 } 429 /* digest -> m */ 430 i = BN_num_bits(order); 431 /* 432 * Need to truncate digest if it is too long: first truncate whole bytes. 433 */ 434 if (8 * dgst_len > i) 435 dgst_len = (i + 7) / 8; 436 if (!BN_bin2bn(dgst, dgst_len, m)) { 437 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 438 goto err; 439 } 440 /* If still too long truncate remaining bits with a shift */ 441 if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { 442 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 443 goto err; 444 } 445 /* u1 = m * tmp mod order */ 446 if (!BN_mod_mul(u1, m, u2, order, ctx)) { 447 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 448 goto err; 449 } 450 /* u2 = r * w mod q */ 451 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { 452 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 453 goto err; 454 } 455 456 if ((point = EC_POINT_new(group)) == NULL) { 457 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); 458 goto err; 459 } 460 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 461 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 462 goto err; 463 } 464 if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == 465 NID_X9_62_prime_field) { 466 if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, ctx)) { 467 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 468 goto err; 469 } 470 } 471#ifndef OPENSSL_NO_EC2M 472 else { /* NID_X9_62_characteristic_two_field */ 473 474 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, X, NULL, ctx)) { 475 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); 476 goto err; 477 } 478 } 479#endif 480 if (!BN_nnmod(u1, X, order, ctx)) { 481 ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); 482 goto err; 483 } 484 /* if the signature is correct u1 is equal to sig->r */ 485 ret = (BN_ucmp(u1, sig->r) == 0); 486 err: 487 BN_CTX_end(ctx); 488 BN_CTX_free(ctx); 489 if (point) 490 EC_POINT_free(point); 491 return ret; 492} 493