1 /* Written by Nils Larsch for the OpenSSL project. */ 2 /* ==================================================================== 3 * Copyright (c) 2000-2003 The OpenSSL Project. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * 17 * 3. All advertising materials mentioning features or use of this 18 * software must display the following acknowledgment: 19 * "This product includes software developed by the OpenSSL Project 20 * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 21 * 22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23 * endorse or promote products derived from this software without 24 * prior written permission. For written permission, please contact 25 * licensing (at) OpenSSL.org. 26 * 27 * 5. Products derived from this software may not be called "OpenSSL" 28 * nor may "OpenSSL" appear in their names without prior written 29 * permission of the OpenSSL Project. 30 * 31 * 6. Redistributions of any form whatsoever must retain the following 32 * acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47 * OF THE POSSIBILITY OF SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This product includes cryptographic software written by Eric Young 51 * (eay (at) cryptsoft.com). This product includes software written by Tim 52 * Hudson (tjh (at) cryptsoft.com). */ 53 54 #include <openssl/ec.h> 55 56 #include <limits.h> 57 #include <string.h> 58 59 #include <openssl/bytestring.h> 60 #include <openssl/bn.h> 61 #include <openssl/err.h> 62 #include <openssl/mem.h> 63 #include <openssl/nid.h> 64 65 #include "internal.h" 66 #include "../bytestring/internal.h" 67 #include "../internal.h" 68 69 70 static const uint8_t kParametersTag = 71 CBS_ASN1_CONSTRUCTED | CBS_ASN1_CONTEXT_SPECIFIC | 0; 72 static const uint8_t kPublicKeyTag = 73 CBS_ASN1_CONSTRUCTED | CBS_ASN1_CONTEXT_SPECIFIC | 1; 74 75 EC_KEY *EC_KEY_parse_private_key(CBS *cbs, const EC_GROUP *group) { 76 CBS ec_private_key, private_key; 77 uint64_t version; 78 if (!CBS_get_asn1(cbs, &ec_private_key, CBS_ASN1_SEQUENCE) || 79 !CBS_get_asn1_uint64(&ec_private_key, &version) || 80 version != 1 || 81 !CBS_get_asn1(&ec_private_key, &private_key, CBS_ASN1_OCTETSTRING)) { 82 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 83 return NULL; 84 } 85 86 /* Parse the optional parameters field. */ 87 EC_GROUP *inner_group = NULL; 88 EC_KEY *ret = NULL; 89 if (CBS_peek_asn1_tag(&ec_private_key, kParametersTag)) { 90 /* Per SEC 1, as an alternative to omitting it, one is allowed to specify 91 * this field and put in a NULL to mean inheriting this value. This was 92 * omitted in a previous version of this logic without problems, so leave it 93 * unimplemented. */ 94 CBS child; 95 if (!CBS_get_asn1(&ec_private_key, &child, kParametersTag)) { 96 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 97 goto err; 98 } 99 inner_group = EC_KEY_parse_parameters(&child); 100 if (inner_group == NULL) { 101 goto err; 102 } 103 if (group == NULL) { 104 group = inner_group; 105 } else if (EC_GROUP_cmp(group, inner_group, NULL) != 0) { 106 /* If a group was supplied externally, it must match. */ 107 OPENSSL_PUT_ERROR(EC, EC_R_GROUP_MISMATCH); 108 goto err; 109 } 110 if (CBS_len(&child) != 0) { 111 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 112 goto err; 113 } 114 } 115 116 if (group == NULL) { 117 OPENSSL_PUT_ERROR(EC, EC_R_MISSING_PARAMETERS); 118 goto err; 119 } 120 121 ret = EC_KEY_new(); 122 if (ret == NULL || !EC_KEY_set_group(ret, group)) { 123 goto err; 124 } 125 126 /* Although RFC 5915 specifies the length of the key, OpenSSL historically 127 * got this wrong, so accept any length. See upstream's 128 * 30cd4ff294252c4b6a4b69cbef6a5b4117705d22. */ 129 ret->priv_key = 130 BN_bin2bn(CBS_data(&private_key), CBS_len(&private_key), NULL); 131 ret->pub_key = EC_POINT_new(group); 132 if (ret->priv_key == NULL || ret->pub_key == NULL) { 133 goto err; 134 } 135 136 if (BN_cmp(ret->priv_key, EC_GROUP_get0_order(group)) >= 0) { 137 OPENSSL_PUT_ERROR(EC, EC_R_WRONG_ORDER); 138 goto err; 139 } 140 141 if (CBS_peek_asn1_tag(&ec_private_key, kPublicKeyTag)) { 142 CBS child, public_key; 143 uint8_t padding; 144 if (!CBS_get_asn1(&ec_private_key, &child, kPublicKeyTag) || 145 !CBS_get_asn1(&child, &public_key, CBS_ASN1_BITSTRING) || 146 /* As in a SubjectPublicKeyInfo, the byte-encoded public key is then 147 * encoded as a BIT STRING with bits ordered as in the DER encoding. */ 148 !CBS_get_u8(&public_key, &padding) || 149 padding != 0 || 150 /* Explicitly check |public_key| is non-empty to save the conversion 151 * form later. */ 152 CBS_len(&public_key) == 0 || 153 !EC_POINT_oct2point(group, ret->pub_key, CBS_data(&public_key), 154 CBS_len(&public_key), NULL) || 155 CBS_len(&child) != 0) { 156 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 157 goto err; 158 } 159 160 /* Save the point conversion form. 161 * TODO(davidben): Consider removing this. */ 162 ret->conv_form = (point_conversion_form_t)(CBS_data(&public_key)[0] & ~0x01); 163 } else { 164 /* Compute the public key instead. */ 165 if (!EC_POINT_mul(group, ret->pub_key, ret->priv_key, NULL, NULL, NULL)) { 166 goto err; 167 } 168 /* Remember the original private-key-only encoding. 169 * TODO(davidben): Consider removing this. */ 170 ret->enc_flag |= EC_PKEY_NO_PUBKEY; 171 } 172 173 if (CBS_len(&ec_private_key) != 0) { 174 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 175 goto err; 176 } 177 178 /* Ensure the resulting key is valid. */ 179 if (!EC_KEY_check_key(ret)) { 180 goto err; 181 } 182 183 EC_GROUP_free(inner_group); 184 return ret; 185 186 err: 187 EC_KEY_free(ret); 188 EC_GROUP_free(inner_group); 189 return NULL; 190 } 191 192 int EC_KEY_marshal_private_key(CBB *cbb, const EC_KEY *key, 193 unsigned enc_flags) { 194 if (key == NULL || key->group == NULL || key->priv_key == NULL) { 195 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER); 196 return 0; 197 } 198 199 CBB ec_private_key, private_key; 200 if (!CBB_add_asn1(cbb, &ec_private_key, CBS_ASN1_SEQUENCE) || 201 !CBB_add_asn1_uint64(&ec_private_key, 1 /* version */) || 202 !CBB_add_asn1(&ec_private_key, &private_key, CBS_ASN1_OCTETSTRING) || 203 !BN_bn2cbb_padded(&private_key, 204 BN_num_bytes(EC_GROUP_get0_order(key->group)), 205 key->priv_key)) { 206 OPENSSL_PUT_ERROR(EC, EC_R_ENCODE_ERROR); 207 return 0; 208 } 209 210 if (!(enc_flags & EC_PKEY_NO_PARAMETERS)) { 211 CBB child; 212 if (!CBB_add_asn1(&ec_private_key, &child, kParametersTag) || 213 !EC_KEY_marshal_curve_name(&child, key->group) || 214 !CBB_flush(&ec_private_key)) { 215 OPENSSL_PUT_ERROR(EC, EC_R_ENCODE_ERROR); 216 return 0; 217 } 218 } 219 220 /* TODO(fork): replace this flexibility with sensible default? */ 221 if (!(enc_flags & EC_PKEY_NO_PUBKEY) && key->pub_key != NULL) { 222 CBB child, public_key; 223 if (!CBB_add_asn1(&ec_private_key, &child, kPublicKeyTag) || 224 !CBB_add_asn1(&child, &public_key, CBS_ASN1_BITSTRING) || 225 /* As in a SubjectPublicKeyInfo, the byte-encoded public key is then 226 * encoded as a BIT STRING with bits ordered as in the DER encoding. */ 227 !CBB_add_u8(&public_key, 0 /* padding */) || 228 !EC_POINT_point2cbb(&public_key, key->group, key->pub_key, 229 key->conv_form, NULL) || 230 !CBB_flush(&ec_private_key)) { 231 OPENSSL_PUT_ERROR(EC, EC_R_ENCODE_ERROR); 232 return 0; 233 } 234 } 235 236 if (!CBB_flush(cbb)) { 237 OPENSSL_PUT_ERROR(EC, EC_R_ENCODE_ERROR); 238 return 0; 239 } 240 241 return 1; 242 } 243 244 /* is_unsigned_integer returns one if |cbs| is a valid unsigned DER INTEGER and 245 * zero otherwise. */ 246 static int is_unsigned_integer(const CBS *cbs) { 247 if (CBS_len(cbs) == 0) { 248 return 0; 249 } 250 uint8_t byte = CBS_data(cbs)[0]; 251 if ((byte & 0x80) || 252 (byte == 0 && CBS_len(cbs) > 1 && (CBS_data(cbs)[1] & 0x80) == 0)) { 253 /* Negative or not minimally-encoded. */ 254 return 0; 255 } 256 return 1; 257 } 258 259 /* kPrimeFieldOID is the encoding of 1.2.840.10045.1.1. */ 260 static const uint8_t kPrimeField[] = {0x2a, 0x86, 0x48, 0xce, 0x3d, 0x01, 0x01}; 261 262 static int parse_explicit_prime_curve(CBS *in, CBS *out_prime, CBS *out_a, 263 CBS *out_b, CBS *out_base_x, 264 CBS *out_base_y, CBS *out_order) { 265 /* See RFC 3279, section 2.3.5. Note that RFC 3279 calls this structure an 266 * ECParameters while RFC 5480 calls it a SpecifiedECDomain. */ 267 CBS params, field_id, field_type, curve, base; 268 uint64_t version; 269 if (!CBS_get_asn1(in, ¶ms, CBS_ASN1_SEQUENCE) || 270 !CBS_get_asn1_uint64(¶ms, &version) || 271 version != 1 || 272 !CBS_get_asn1(¶ms, &field_id, CBS_ASN1_SEQUENCE) || 273 !CBS_get_asn1(&field_id, &field_type, CBS_ASN1_OBJECT) || 274 CBS_len(&field_type) != sizeof(kPrimeField) || 275 OPENSSL_memcmp(CBS_data(&field_type), kPrimeField, sizeof(kPrimeField)) != 0 || 276 !CBS_get_asn1(&field_id, out_prime, CBS_ASN1_INTEGER) || 277 !is_unsigned_integer(out_prime) || 278 CBS_len(&field_id) != 0 || 279 !CBS_get_asn1(¶ms, &curve, CBS_ASN1_SEQUENCE) || 280 !CBS_get_asn1(&curve, out_a, CBS_ASN1_OCTETSTRING) || 281 !CBS_get_asn1(&curve, out_b, CBS_ASN1_OCTETSTRING) || 282 /* |curve| has an optional BIT STRING seed which we ignore. */ 283 !CBS_get_asn1(¶ms, &base, CBS_ASN1_OCTETSTRING) || 284 !CBS_get_asn1(¶ms, out_order, CBS_ASN1_INTEGER) || 285 !is_unsigned_integer(out_order)) { 286 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 287 return 0; 288 } 289 290 /* |params| has an optional cofactor which we ignore. With the optional seed 291 * in |curve|, a group already has arbitrarily many encodings. Parse enough to 292 * uniquely determine the curve. */ 293 294 /* Require that the base point use uncompressed form. */ 295 uint8_t form; 296 if (!CBS_get_u8(&base, &form) || form != POINT_CONVERSION_UNCOMPRESSED) { 297 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FORM); 298 return 0; 299 } 300 301 if (CBS_len(&base) % 2 != 0) { 302 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 303 return 0; 304 } 305 size_t field_len = CBS_len(&base) / 2; 306 CBS_init(out_base_x, CBS_data(&base), field_len); 307 CBS_init(out_base_y, CBS_data(&base) + field_len, field_len); 308 309 return 1; 310 } 311 312 /* integers_equal returns one if |a| and |b| are equal, up to leading zeros, and 313 * zero otherwise. */ 314 static int integers_equal(const CBS *a, const uint8_t *b, size_t b_len) { 315 /* Remove leading zeros from |a| and |b|. */ 316 CBS a_copy = *a; 317 while (CBS_len(&a_copy) > 0 && CBS_data(&a_copy)[0] == 0) { 318 CBS_skip(&a_copy, 1); 319 } 320 while (b_len > 0 && b[0] == 0) { 321 b++; 322 b_len--; 323 } 324 return CBS_mem_equal(&a_copy, b, b_len); 325 } 326 327 EC_GROUP *EC_KEY_parse_curve_name(CBS *cbs) { 328 CBS named_curve; 329 if (!CBS_get_asn1(cbs, &named_curve, CBS_ASN1_OBJECT)) { 330 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 331 return NULL; 332 } 333 334 /* Look for a matching curve. */ 335 unsigned i; 336 for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) { 337 const struct built_in_curve *curve = &OPENSSL_built_in_curves[i]; 338 if (CBS_len(&named_curve) == curve->oid_len && 339 OPENSSL_memcmp(CBS_data(&named_curve), curve->oid, curve->oid_len) == 0) { 340 return EC_GROUP_new_by_curve_name(curve->nid); 341 } 342 } 343 344 OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP); 345 return NULL; 346 } 347 348 int EC_KEY_marshal_curve_name(CBB *cbb, const EC_GROUP *group) { 349 int nid = EC_GROUP_get_curve_name(group); 350 if (nid == NID_undef) { 351 OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP); 352 return 0; 353 } 354 355 unsigned i; 356 for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) { 357 const struct built_in_curve *curve = &OPENSSL_built_in_curves[i]; 358 if (curve->nid == nid) { 359 CBB child; 360 return CBB_add_asn1(cbb, &child, CBS_ASN1_OBJECT) && 361 CBB_add_bytes(&child, curve->oid, curve->oid_len) && 362 CBB_flush(cbb); 363 } 364 } 365 366 OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP); 367 return 0; 368 } 369 370 EC_GROUP *EC_KEY_parse_parameters(CBS *cbs) { 371 if (!CBS_peek_asn1_tag(cbs, CBS_ASN1_SEQUENCE)) { 372 return EC_KEY_parse_curve_name(cbs); 373 } 374 375 /* OpenSSL sometimes produces ECPrivateKeys with explicitly-encoded versions 376 * of named curves. 377 * 378 * TODO(davidben): Remove support for this. */ 379 CBS prime, a, b, base_x, base_y, order; 380 if (!parse_explicit_prime_curve(cbs, &prime, &a, &b, &base_x, &base_y, 381 &order)) { 382 return NULL; 383 } 384 385 /* Look for a matching prime curve. */ 386 unsigned i; 387 for (i = 0; OPENSSL_built_in_curves[i].nid != NID_undef; i++) { 388 const struct built_in_curve *curve = &OPENSSL_built_in_curves[i]; 389 const unsigned param_len = curve->data->param_len; 390 /* |curve->data->data| is ordered p, a, b, x, y, order, each component 391 * zero-padded up to the field length. Although SEC 1 states that the 392 * Field-Element-to-Octet-String conversion also pads, OpenSSL mis-encodes 393 * |a| and |b|, so this comparison must allow omitting leading zeros. (This 394 * is relevant for P-521 whose |b| has a leading 0.) */ 395 if (integers_equal(&prime, curve->data->data, param_len) && 396 integers_equal(&a, curve->data->data + param_len, param_len) && 397 integers_equal(&b, curve->data->data + param_len * 2, param_len) && 398 integers_equal(&base_x, curve->data->data + param_len * 3, param_len) && 399 integers_equal(&base_y, curve->data->data + param_len * 4, param_len) && 400 integers_equal(&order, curve->data->data + param_len * 5, param_len)) { 401 return EC_GROUP_new_by_curve_name(curve->nid); 402 } 403 } 404 405 OPENSSL_PUT_ERROR(EC, EC_R_UNKNOWN_GROUP); 406 return NULL; 407 } 408 409 EC_KEY *d2i_ECPrivateKey(EC_KEY **out, const uint8_t **inp, long len) { 410 /* This function treats its |out| parameter differently from other |d2i| 411 * functions. If supplied, take the group from |*out|. */ 412 const EC_GROUP *group = NULL; 413 if (out != NULL && *out != NULL) { 414 group = EC_KEY_get0_group(*out); 415 } 416 417 if (len < 0) { 418 OPENSSL_PUT_ERROR(EC, EC_R_DECODE_ERROR); 419 return NULL; 420 } 421 CBS cbs; 422 CBS_init(&cbs, *inp, (size_t)len); 423 EC_KEY *ret = EC_KEY_parse_private_key(&cbs, group); 424 if (ret == NULL) { 425 return NULL; 426 } 427 if (out != NULL) { 428 EC_KEY_free(*out); 429 *out = ret; 430 } 431 *inp = CBS_data(&cbs); 432 return ret; 433 } 434 435 int i2d_ECPrivateKey(const EC_KEY *key, uint8_t **outp) { 436 CBB cbb; 437 if (!CBB_init(&cbb, 0) || 438 !EC_KEY_marshal_private_key(&cbb, key, EC_KEY_get_enc_flags(key))) { 439 CBB_cleanup(&cbb); 440 return -1; 441 } 442 return CBB_finish_i2d(&cbb, outp); 443 } 444 445 EC_KEY *d2i_ECParameters(EC_KEY **out_key, const uint8_t **inp, long len) { 446 if (len < 0) { 447 return NULL; 448 } 449 450 CBS cbs; 451 CBS_init(&cbs, *inp, (size_t)len); 452 EC_GROUP *group = EC_KEY_parse_parameters(&cbs); 453 if (group == NULL) { 454 return NULL; 455 } 456 457 EC_KEY *ret = EC_KEY_new(); 458 if (ret == NULL || !EC_KEY_set_group(ret, group)) { 459 EC_GROUP_free(group); 460 EC_KEY_free(ret); 461 return NULL; 462 } 463 EC_GROUP_free(group); 464 465 if (out_key != NULL) { 466 EC_KEY_free(*out_key); 467 *out_key = ret; 468 } 469 *inp = CBS_data(&cbs); 470 return ret; 471 } 472 473 int i2d_ECParameters(const EC_KEY *key, uint8_t **outp) { 474 if (key == NULL || key->group == NULL) { 475 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER); 476 return -1; 477 } 478 479 CBB cbb; 480 if (!CBB_init(&cbb, 0) || 481 !EC_KEY_marshal_curve_name(&cbb, key->group)) { 482 CBB_cleanup(&cbb); 483 return -1; 484 } 485 return CBB_finish_i2d(&cbb, outp); 486 } 487 488 EC_KEY *o2i_ECPublicKey(EC_KEY **keyp, const uint8_t **inp, long len) { 489 EC_KEY *ret = NULL; 490 491 if (keyp == NULL || *keyp == NULL || (*keyp)->group == NULL) { 492 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER); 493 return NULL; 494 } 495 ret = *keyp; 496 if (ret->pub_key == NULL && 497 (ret->pub_key = EC_POINT_new(ret->group)) == NULL) { 498 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE); 499 return NULL; 500 } 501 if (!EC_POINT_oct2point(ret->group, ret->pub_key, *inp, len, NULL)) { 502 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB); 503 return NULL; 504 } 505 /* save the point conversion form */ 506 ret->conv_form = (point_conversion_form_t)(*inp[0] & ~0x01); 507 *inp += len; 508 return ret; 509 } 510 511 int i2o_ECPublicKey(const EC_KEY *key, uint8_t **outp) { 512 size_t buf_len = 0; 513 int new_buffer = 0; 514 515 if (key == NULL) { 516 OPENSSL_PUT_ERROR(EC, ERR_R_PASSED_NULL_PARAMETER); 517 return 0; 518 } 519 520 buf_len = EC_POINT_point2oct(key->group, key->pub_key, key->conv_form, NULL, 521 0, NULL); 522 523 if (outp == NULL || buf_len == 0) { 524 /* out == NULL => just return the length of the octet string */ 525 return buf_len; 526 } 527 528 if (*outp == NULL) { 529 *outp = OPENSSL_malloc(buf_len); 530 if (*outp == NULL) { 531 OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE); 532 return 0; 533 } 534 new_buffer = 1; 535 } 536 if (!EC_POINT_point2oct(key->group, key->pub_key, key->conv_form, *outp, 537 buf_len, NULL)) { 538 OPENSSL_PUT_ERROR(EC, ERR_R_EC_LIB); 539 if (new_buffer) { 540 OPENSSL_free(*outp); 541 *outp = NULL; 542 } 543 return 0; 544 } 545 546 if (!new_buffer) { 547 *outp += buf_len; 548 } 549 return buf_len; 550 } 551
