1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4
5 #ifdef FREEBL_NO_DEPEND
6 #include "stubs.h"
7 #endif
8
9 #include "blapi.h"
10 #include "prerr.h"
11 #include "secerr.h"
12 #include "secmpi.h"
13 #include "secitem.h"
14 #include "mplogic.h"
15 #include "ec.h"
16 #include "ecl.h"
17
18 static const ECMethod kMethods[] = {
19 { ECCurve25519,
20 ec_Curve25519_pt_mul,
21 ec_Curve25519_pt_validate }
22 };
23
24 static const ECMethod *
ec_get_method_from_name(ECCurveName name)25 ec_get_method_from_name(ECCurveName name)
26 {
27 unsigned long i;
28 for (i = 0; i < sizeof(kMethods) / sizeof(kMethods[0]); ++i) {
29 if (kMethods[i].name == name) {
30 return &kMethods[i];
31 }
32 }
33 return NULL;
34 }
35
36 /*
37 * Returns true if pointP is the point at infinity, false otherwise
38 */
39 PRBool
ec_point_at_infinity(SECItem * pointP)40 ec_point_at_infinity(SECItem *pointP)
41 {
42 unsigned int i;
43
44 for (i = 1; i < pointP->len; i++) {
45 if (pointP->data[i] != 0x00)
46 return PR_FALSE;
47 }
48
49 return PR_TRUE;
50 }
51
52 /*
53 * Computes scalar point multiplication pointQ = k1 * G + k2 * pointP for
54 * the curve whose parameters are encoded in params with base point G.
55 */
56 SECStatus
ec_points_mul(const ECParams * params,const mp_int * k1,const mp_int * k2,const SECItem * pointP,SECItem * pointQ)57 ec_points_mul(const ECParams *params, const mp_int *k1, const mp_int *k2,
58 const SECItem *pointP, SECItem *pointQ)
59 {
60 mp_int Px, Py, Qx, Qy;
61 mp_int Gx, Gy, order, irreducible, a, b;
62 ECGroup *group = NULL;
63 SECStatus rv = SECFailure;
64 mp_err err = MP_OKAY;
65 unsigned int len;
66
67 #if EC_DEBUG
68 int i;
69 char mpstr[256];
70
71 printf("ec_points_mul: params [len=%d]:", params->DEREncoding.len);
72 for (i = 0; i < params->DEREncoding.len; i++)
73 printf("%02x:", params->DEREncoding.data[i]);
74 printf("\n");
75
76 if (k1 != NULL) {
77 mp_tohex((mp_int *)k1, mpstr);
78 printf("ec_points_mul: scalar k1: %s\n", mpstr);
79 mp_todecimal((mp_int *)k1, mpstr);
80 printf("ec_points_mul: scalar k1: %s (dec)\n", mpstr);
81 }
82
83 if (k2 != NULL) {
84 mp_tohex((mp_int *)k2, mpstr);
85 printf("ec_points_mul: scalar k2: %s\n", mpstr);
86 mp_todecimal((mp_int *)k2, mpstr);
87 printf("ec_points_mul: scalar k2: %s (dec)\n", mpstr);
88 }
89
90 if (pointP != NULL) {
91 printf("ec_points_mul: pointP [len=%d]:", pointP->len);
92 for (i = 0; i < pointP->len; i++)
93 printf("%02x:", pointP->data[i]);
94 printf("\n");
95 }
96 #endif
97
98 /* NOTE: We only support uncompressed points for now */
99 len = (((unsigned int)params->fieldID.size) + 7) >> 3;
100 if (pointP != NULL) {
101 if ((pointP->data[0] != EC_POINT_FORM_UNCOMPRESSED) ||
102 (pointP->len != (2 * len + 1))) {
103 PORT_SetError(SEC_ERROR_UNSUPPORTED_EC_POINT_FORM);
104 return SECFailure;
105 };
106 }
107
108 MP_DIGITS(&Px) = 0;
109 MP_DIGITS(&Py) = 0;
110 MP_DIGITS(&Qx) = 0;
111 MP_DIGITS(&Qy) = 0;
112 MP_DIGITS(&Gx) = 0;
113 MP_DIGITS(&Gy) = 0;
114 MP_DIGITS(&order) = 0;
115 MP_DIGITS(&irreducible) = 0;
116 MP_DIGITS(&a) = 0;
117 MP_DIGITS(&b) = 0;
118 CHECK_MPI_OK(mp_init(&Px));
119 CHECK_MPI_OK(mp_init(&Py));
120 CHECK_MPI_OK(mp_init(&Qx));
121 CHECK_MPI_OK(mp_init(&Qy));
122 CHECK_MPI_OK(mp_init(&Gx));
123 CHECK_MPI_OK(mp_init(&Gy));
124 CHECK_MPI_OK(mp_init(&order));
125 CHECK_MPI_OK(mp_init(&irreducible));
126 CHECK_MPI_OK(mp_init(&a));
127 CHECK_MPI_OK(mp_init(&b));
128
129 if ((k2 != NULL) && (pointP != NULL)) {
130 /* Initialize Px and Py */
131 CHECK_MPI_OK(mp_read_unsigned_octets(&Px, pointP->data + 1, (mp_size)len));
132 CHECK_MPI_OK(mp_read_unsigned_octets(&Py, pointP->data + 1 + len, (mp_size)len));
133 }
134
135 /* construct from named params, if possible */
136 if (params->name != ECCurve_noName) {
137 group = ECGroup_fromName(params->name);
138 }
139
140 if (group == NULL)
141 goto cleanup;
142
143 if ((k2 != NULL) && (pointP != NULL)) {
144 CHECK_MPI_OK(ECPoints_mul(group, k1, k2, &Px, &Py, &Qx, &Qy));
145 } else {
146 CHECK_MPI_OK(ECPoints_mul(group, k1, NULL, NULL, NULL, &Qx, &Qy));
147 }
148
149 /* Construct the SECItem representation of point Q */
150 pointQ->data[0] = EC_POINT_FORM_UNCOMPRESSED;
151 CHECK_MPI_OK(mp_to_fixlen_octets(&Qx, pointQ->data + 1,
152 (mp_size)len));
153 CHECK_MPI_OK(mp_to_fixlen_octets(&Qy, pointQ->data + 1 + len,
154 (mp_size)len));
155
156 rv = SECSuccess;
157
158 #if EC_DEBUG
159 printf("ec_points_mul: pointQ [len=%d]:", pointQ->len);
160 for (i = 0; i < pointQ->len; i++)
161 printf("%02x:", pointQ->data[i]);
162 printf("\n");
163 #endif
164
165 cleanup:
166 ECGroup_free(group);
167 mp_clear(&Px);
168 mp_clear(&Py);
169 mp_clear(&Qx);
170 mp_clear(&Qy);
171 mp_clear(&Gx);
172 mp_clear(&Gy);
173 mp_clear(&order);
174 mp_clear(&irreducible);
175 mp_clear(&a);
176 mp_clear(&b);
177 if (err) {
178 MP_TO_SEC_ERROR(err);
179 rv = SECFailure;
180 }
181
182 return rv;
183 }
184
185 /* Generates a new EC key pair. The private key is a supplied
186 * value and the public key is the result of performing a scalar
187 * point multiplication of that value with the curve's base point.
188 */
189 SECStatus
ec_NewKey(ECParams * ecParams,ECPrivateKey ** privKey,const unsigned char * privKeyBytes,int privKeyLen)190 ec_NewKey(ECParams *ecParams, ECPrivateKey **privKey,
191 const unsigned char *privKeyBytes, int privKeyLen)
192 {
193 SECStatus rv = SECFailure;
194 PLArenaPool *arena;
195 ECPrivateKey *key;
196 mp_int k;
197 mp_err err = MP_OKAY;
198 int len;
199
200 #if EC_DEBUG
201 printf("ec_NewKey called\n");
202 #endif
203 MP_DIGITS(&k) = 0;
204
205 if (!ecParams || ecParams->name == ECCurve_noName ||
206 !privKey || !privKeyBytes || privKeyLen <= 0) {
207 PORT_SetError(SEC_ERROR_INVALID_ARGS);
208 return SECFailure;
209 }
210
211 /* Initialize an arena for the EC key. */
212 if (!(arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE)))
213 return SECFailure;
214
215 key = (ECPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(ECPrivateKey));
216 if (!key) {
217 PORT_FreeArena(arena, PR_TRUE);
218 return SECFailure;
219 }
220
221 /* Set the version number (SEC 1 section C.4 says it should be 1) */
222 SECITEM_AllocItem(arena, &key->version, 1);
223 key->version.data[0] = 1;
224
225 /* Copy all of the fields from the ECParams argument to the
226 * ECParams structure within the private key.
227 */
228 key->ecParams.arena = arena;
229 key->ecParams.type = ecParams->type;
230 key->ecParams.fieldID.size = ecParams->fieldID.size;
231 key->ecParams.fieldID.type = ecParams->fieldID.type;
232 if (ecParams->fieldID.type == ec_field_GFp ||
233 ecParams->fieldID.type == ec_field_plain) {
234 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.prime,
235 &ecParams->fieldID.u.prime));
236 } else {
237 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.fieldID.u.poly,
238 &ecParams->fieldID.u.poly));
239 }
240 key->ecParams.fieldID.k1 = ecParams->fieldID.k1;
241 key->ecParams.fieldID.k2 = ecParams->fieldID.k2;
242 key->ecParams.fieldID.k3 = ecParams->fieldID.k3;
243 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.a,
244 &ecParams->curve.a));
245 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.b,
246 &ecParams->curve.b));
247 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curve.seed,
248 &ecParams->curve.seed));
249 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.base,
250 &ecParams->base));
251 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.order,
252 &ecParams->order));
253 key->ecParams.cofactor = ecParams->cofactor;
254 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.DEREncoding,
255 &ecParams->DEREncoding));
256 key->ecParams.name = ecParams->name;
257 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->ecParams.curveOID,
258 &ecParams->curveOID));
259
260 SECITEM_AllocItem(arena, &key->publicValue, EC_GetPointSize(ecParams));
261 len = ecParams->order.len;
262 SECITEM_AllocItem(arena, &key->privateValue, len);
263
264 /* Copy private key */
265 if (privKeyLen >= len) {
266 memcpy(key->privateValue.data, privKeyBytes, len);
267 } else {
268 memset(key->privateValue.data, 0, (len - privKeyLen));
269 memcpy(key->privateValue.data + (len - privKeyLen), privKeyBytes, privKeyLen);
270 }
271
272 /* Compute corresponding public key */
273
274 /* Use curve specific code for point multiplication */
275 if (ecParams->fieldID.type == ec_field_plain) {
276 const ECMethod *method = ec_get_method_from_name(ecParams->name);
277 if (method == NULL || method->mul == NULL) {
278 /* unknown curve */
279 rv = SECFailure;
280 goto cleanup;
281 }
282 rv = method->mul(&key->publicValue, &key->privateValue, NULL);
283 goto done;
284 }
285
286 CHECK_MPI_OK(mp_init(&k));
287 CHECK_MPI_OK(mp_read_unsigned_octets(&k, key->privateValue.data,
288 (mp_size)len));
289
290 rv = ec_points_mul(ecParams, &k, NULL, NULL, &(key->publicValue));
291 if (rv != SECSuccess) {
292 goto cleanup;
293 }
294
295 done:
296 *privKey = key;
297
298 cleanup:
299 mp_clear(&k);
300 if (rv) {
301 PORT_FreeArena(arena, PR_TRUE);
302 }
303
304 #if EC_DEBUG
305 printf("ec_NewKey returning %s\n",
306 (rv == SECSuccess) ? "success" : "failure");
307 #endif
308
309 return rv;
310 }
311
312 /* Generates a new EC key pair. The private key is a supplied
313 * random value (in seed) and the public key is the result of
314 * performing a scalar point multiplication of that value with
315 * the curve's base point.
316 */
317 SECStatus
EC_NewKeyFromSeed(ECParams * ecParams,ECPrivateKey ** privKey,const unsigned char * seed,int seedlen)318 EC_NewKeyFromSeed(ECParams *ecParams, ECPrivateKey **privKey,
319 const unsigned char *seed, int seedlen)
320 {
321 SECStatus rv = SECFailure;
322 rv = ec_NewKey(ecParams, privKey, seed, seedlen);
323 return rv;
324 }
325
326 /* Generate a random private key using the algorithm A.4.1 of ANSI X9.62,
327 * modified a la FIPS 186-2 Change Notice 1 to eliminate the bias in the
328 * random number generator.
329 *
330 * Parameters
331 * - order: a buffer that holds the curve's group order
332 * - len: the length in octets of the order buffer
333 *
334 * Return Value
335 * Returns a buffer of len octets that holds the private key. The caller
336 * is responsible for freeing the buffer with PORT_ZFree.
337 */
338 static unsigned char *
ec_GenerateRandomPrivateKey(const unsigned char * order,int len)339 ec_GenerateRandomPrivateKey(const unsigned char *order, int len)
340 {
341 SECStatus rv = SECSuccess;
342 mp_err err;
343 unsigned char *privKeyBytes = NULL;
344 mp_int privKeyVal, order_1, one;
345
346 MP_DIGITS(&privKeyVal) = 0;
347 MP_DIGITS(&order_1) = 0;
348 MP_DIGITS(&one) = 0;
349 CHECK_MPI_OK(mp_init(&privKeyVal));
350 CHECK_MPI_OK(mp_init(&order_1));
351 CHECK_MPI_OK(mp_init(&one));
352
353 /* Generates 2*len random bytes using the global random bit generator
354 * (which implements Algorithm 1 of FIPS 186-2 Change Notice 1) then
355 * reduces modulo the group order.
356 */
357 if ((privKeyBytes = PORT_Alloc(2 * len)) == NULL)
358 goto cleanup;
359 CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(privKeyBytes, 2 * len));
360 CHECK_MPI_OK(mp_read_unsigned_octets(&privKeyVal, privKeyBytes, 2 * len));
361 CHECK_MPI_OK(mp_read_unsigned_octets(&order_1, order, len));
362 CHECK_MPI_OK(mp_set_int(&one, 1));
363 CHECK_MPI_OK(mp_sub(&order_1, &one, &order_1));
364 CHECK_MPI_OK(mp_mod(&privKeyVal, &order_1, &privKeyVal));
365 CHECK_MPI_OK(mp_add(&privKeyVal, &one, &privKeyVal));
366 CHECK_MPI_OK(mp_to_fixlen_octets(&privKeyVal, privKeyBytes, len));
367 memset(privKeyBytes + len, 0, len);
368 cleanup:
369 mp_clear(&privKeyVal);
370 mp_clear(&order_1);
371 mp_clear(&one);
372 if (err < MP_OKAY) {
373 MP_TO_SEC_ERROR(err);
374 rv = SECFailure;
375 }
376 if (rv != SECSuccess && privKeyBytes) {
377 PORT_ZFree(privKeyBytes, 2 * len);
378 privKeyBytes = NULL;
379 }
380 return privKeyBytes;
381 }
382
383 /* Generates a new EC key pair. The private key is a random value and
384 * the public key is the result of performing a scalar point multiplication
385 * of that value with the curve's base point.
386 */
387 SECStatus
EC_NewKey(ECParams * ecParams,ECPrivateKey ** privKey)388 EC_NewKey(ECParams *ecParams, ECPrivateKey **privKey)
389 {
390 SECStatus rv = SECFailure;
391 int len;
392 unsigned char *privKeyBytes = NULL;
393
394 if (!ecParams || ecParams->name == ECCurve_noName || !privKey) {
395 PORT_SetError(SEC_ERROR_INVALID_ARGS);
396 return SECFailure;
397 }
398
399 len = ecParams->order.len;
400 privKeyBytes = ec_GenerateRandomPrivateKey(ecParams->order.data, len);
401 if (privKeyBytes == NULL)
402 goto cleanup;
403 /* generate public key */
404 CHECK_SEC_OK(ec_NewKey(ecParams, privKey, privKeyBytes, len));
405
406 cleanup:
407 if (privKeyBytes) {
408 PORT_ZFree(privKeyBytes, len);
409 }
410 #if EC_DEBUG
411 printf("EC_NewKey returning %s\n",
412 (rv == SECSuccess) ? "success" : "failure");
413 #endif
414
415 return rv;
416 }
417
418 /* Validates an EC public key as described in Section 5.2.2 of
419 * X9.62. The ECDH primitive when used without the cofactor does
420 * not address small subgroup attacks, which may occur when the
421 * public key is not valid. These attacks can be prevented by
422 * validating the public key before using ECDH.
423 */
424 SECStatus
EC_ValidatePublicKey(ECParams * ecParams,SECItem * publicValue)425 EC_ValidatePublicKey(ECParams *ecParams, SECItem *publicValue)
426 {
427 mp_int Px, Py;
428 ECGroup *group = NULL;
429 SECStatus rv = SECFailure;
430 mp_err err = MP_OKAY;
431 unsigned int len;
432
433 if (!ecParams || ecParams->name == ECCurve_noName ||
434 !publicValue || !publicValue->len) {
435 PORT_SetError(SEC_ERROR_INVALID_ARGS);
436 return SECFailure;
437 }
438
439 /* Uses curve specific code for point validation. */
440 if (ecParams->fieldID.type == ec_field_plain) {
441 const ECMethod *method = ec_get_method_from_name(ecParams->name);
442 if (method == NULL || method->validate == NULL) {
443 /* unknown curve */
444 PORT_SetError(SEC_ERROR_INVALID_ARGS);
445 return SECFailure;
446 }
447 return method->validate(publicValue);
448 }
449
450 /* NOTE: We only support uncompressed points for now */
451 len = (((unsigned int)ecParams->fieldID.size) + 7) >> 3;
452 if (publicValue->data[0] != EC_POINT_FORM_UNCOMPRESSED) {
453 PORT_SetError(SEC_ERROR_UNSUPPORTED_EC_POINT_FORM);
454 return SECFailure;
455 } else if (publicValue->len != (2 * len + 1)) {
456 PORT_SetError(SEC_ERROR_BAD_KEY);
457 return SECFailure;
458 }
459
460 MP_DIGITS(&Px) = 0;
461 MP_DIGITS(&Py) = 0;
462 CHECK_MPI_OK(mp_init(&Px));
463 CHECK_MPI_OK(mp_init(&Py));
464
465 /* Initialize Px and Py */
466 CHECK_MPI_OK(mp_read_unsigned_octets(&Px, publicValue->data + 1, (mp_size)len));
467 CHECK_MPI_OK(mp_read_unsigned_octets(&Py, publicValue->data + 1 + len, (mp_size)len));
468
469 /* construct from named params */
470 group = ECGroup_fromName(ecParams->name);
471 if (group == NULL) {
472 /*
473 * ECGroup_fromName fails if ecParams->name is not a valid
474 * ECCurveName value, or if we run out of memory, or perhaps
475 * for other reasons. Unfortunately if ecParams->name is a
476 * valid ECCurveName value, we don't know what the right error
477 * code should be because ECGroup_fromName doesn't return an
478 * error code to the caller. Set err to MP_UNDEF because
479 * that's what ECGroup_fromName uses internally.
480 */
481 if ((ecParams->name <= ECCurve_noName) ||
482 (ecParams->name >= ECCurve_pastLastCurve)) {
483 err = MP_BADARG;
484 } else {
485 err = MP_UNDEF;
486 }
487 goto cleanup;
488 }
489
490 /* validate public point */
491 if ((err = ECPoint_validate(group, &Px, &Py)) < MP_YES) {
492 if (err == MP_NO) {
493 PORT_SetError(SEC_ERROR_BAD_KEY);
494 rv = SECFailure;
495 err = MP_OKAY; /* don't change the error code */
496 }
497 goto cleanup;
498 }
499
500 rv = SECSuccess;
501
502 cleanup:
503 ECGroup_free(group);
504 mp_clear(&Px);
505 mp_clear(&Py);
506 if (err) {
507 MP_TO_SEC_ERROR(err);
508 rv = SECFailure;
509 }
510 return rv;
511 }
512
513 /*
514 ** Performs an ECDH key derivation by computing the scalar point
515 ** multiplication of privateValue and publicValue (with or without the
516 ** cofactor) and returns the x-coordinate of the resulting elliptic
517 ** curve point in derived secret. If successful, derivedSecret->data
518 ** is set to the address of the newly allocated buffer containing the
519 ** derived secret, and derivedSecret->len is the size of the secret
520 ** produced. It is the caller's responsibility to free the allocated
521 ** buffer containing the derived secret.
522 */
523 SECStatus
ECDH_Derive(SECItem * publicValue,ECParams * ecParams,SECItem * privateValue,PRBool withCofactor,SECItem * derivedSecret)524 ECDH_Derive(SECItem *publicValue,
525 ECParams *ecParams,
526 SECItem *privateValue,
527 PRBool withCofactor,
528 SECItem *derivedSecret)
529 {
530 SECStatus rv = SECFailure;
531 unsigned int len = 0;
532 SECItem pointQ = { siBuffer, NULL, 0 };
533 mp_int k; /* to hold the private value */
534 mp_int cofactor;
535 mp_err err = MP_OKAY;
536 #if EC_DEBUG
537 int i;
538 #endif
539
540 if (!publicValue || !publicValue->len ||
541 !ecParams || ecParams->name == ECCurve_noName ||
542 !privateValue || !privateValue->len || !derivedSecret) {
543 PORT_SetError(SEC_ERROR_INVALID_ARGS);
544 return SECFailure;
545 }
546
547 /*
548 * Make sure the point is on the requested curve to avoid
549 * certain small subgroup attacks.
550 */
551 if (EC_ValidatePublicKey(ecParams, publicValue) != SECSuccess) {
552 PORT_SetError(SEC_ERROR_BAD_KEY);
553 return SECFailure;
554 }
555
556 /* Perform curve specific multiplication using ECMethod */
557 if (ecParams->fieldID.type == ec_field_plain) {
558 const ECMethod *method;
559 memset(derivedSecret, 0, sizeof(*derivedSecret));
560 derivedSecret = SECITEM_AllocItem(NULL, derivedSecret, EC_GetPointSize(ecParams));
561 if (derivedSecret == NULL) {
562 PORT_SetError(SEC_ERROR_NO_MEMORY);
563 return SECFailure;
564 }
565 method = ec_get_method_from_name(ecParams->name);
566 if (method == NULL || method->validate == NULL ||
567 method->mul == NULL) {
568 PORT_SetError(SEC_ERROR_UNSUPPORTED_ELLIPTIC_CURVE);
569 return SECFailure;
570 }
571 rv = method->mul(derivedSecret, privateValue, publicValue);
572 if (rv != SECSuccess) {
573 SECITEM_ZfreeItem(derivedSecret, PR_FALSE);
574 }
575 return rv;
576 }
577
578 /*
579 * We fail if the public value is the point at infinity, since
580 * this produces predictable results.
581 */
582 if (ec_point_at_infinity(publicValue)) {
583 PORT_SetError(SEC_ERROR_BAD_KEY);
584 return SECFailure;
585 }
586
587 MP_DIGITS(&k) = 0;
588 memset(derivedSecret, 0, sizeof *derivedSecret);
589 len = (ecParams->fieldID.size + 7) >> 3;
590 pointQ.len = EC_GetPointSize(ecParams);
591 if ((pointQ.data = PORT_Alloc(pointQ.len)) == NULL)
592 goto cleanup;
593
594 CHECK_MPI_OK(mp_init(&k));
595 CHECK_MPI_OK(mp_read_unsigned_octets(&k, privateValue->data,
596 (mp_size)privateValue->len));
597
598 if (withCofactor && (ecParams->cofactor != 1)) {
599 /* multiply k with the cofactor */
600 MP_DIGITS(&cofactor) = 0;
601 CHECK_MPI_OK(mp_init(&cofactor));
602 mp_set(&cofactor, ecParams->cofactor);
603 CHECK_MPI_OK(mp_mul(&k, &cofactor, &k));
604 }
605
606 /* Multiply our private key and peer's public point */
607 if (ec_points_mul(ecParams, NULL, &k, publicValue, &pointQ) != SECSuccess) {
608 goto cleanup;
609 }
610 if (ec_point_at_infinity(&pointQ)) {
611 PORT_SetError(SEC_ERROR_BAD_KEY); /* XXX better error code? */
612 goto cleanup;
613 }
614
615 /* Allocate memory for the derived secret and copy
616 * the x co-ordinate of pointQ into it.
617 */
618 SECITEM_AllocItem(NULL, derivedSecret, len);
619 memcpy(derivedSecret->data, pointQ.data + 1, len);
620
621 rv = SECSuccess;
622
623 #if EC_DEBUG
624 printf("derived_secret:\n");
625 for (i = 0; i < derivedSecret->len; i++)
626 printf("%02x:", derivedSecret->data[i]);
627 printf("\n");
628 #endif
629
630 cleanup:
631 mp_clear(&k);
632
633 if (err) {
634 MP_TO_SEC_ERROR(err);
635 }
636
637 if (pointQ.data) {
638 PORT_ZFree(pointQ.data, pointQ.len);
639 }
640
641 return rv;
642 }
643
644 /* Computes the ECDSA signature (a concatenation of two values r and s)
645 * on the digest using the given key and the random value kb (used in
646 * computing s).
647 */
648 SECStatus
ECDSA_SignDigestWithSeed(ECPrivateKey * key,SECItem * signature,const SECItem * digest,const unsigned char * kb,const int kblen)649 ECDSA_SignDigestWithSeed(ECPrivateKey *key, SECItem *signature,
650 const SECItem *digest, const unsigned char *kb, const int kblen)
651 {
652 SECStatus rv = SECFailure;
653 mp_int x1;
654 mp_int d, k; /* private key, random integer */
655 mp_int r, s; /* tuple (r, s) is the signature */
656 mp_int t; /* holding tmp values */
657 mp_int n;
658 mp_int ar; /* blinding value */
659 mp_err err = MP_OKAY;
660 ECParams *ecParams = NULL;
661 SECItem kGpoint = { siBuffer, NULL, 0 };
662 int flen = 0; /* length in bytes of the field size */
663 unsigned olen; /* length in bytes of the base point order */
664 unsigned obits; /* length in bits of the base point order */
665 unsigned char *t2 = NULL;
666
667 #if EC_DEBUG
668 char mpstr[256];
669 #endif
670
671 /* Initialize MPI integers. */
672 /* must happen before the first potential call to cleanup */
673 MP_DIGITS(&x1) = 0;
674 MP_DIGITS(&d) = 0;
675 MP_DIGITS(&k) = 0;
676 MP_DIGITS(&r) = 0;
677 MP_DIGITS(&s) = 0;
678 MP_DIGITS(&n) = 0;
679 MP_DIGITS(&t) = 0;
680 MP_DIGITS(&ar) = 0;
681
682 /* Check args */
683 if (!key || !signature || !digest || !kb || (kblen < 0)) {
684 PORT_SetError(SEC_ERROR_INVALID_ARGS);
685 goto cleanup;
686 }
687
688 ecParams = &(key->ecParams);
689 flen = (ecParams->fieldID.size + 7) >> 3;
690 olen = ecParams->order.len;
691 if (signature->data == NULL) {
692 /* a call to get the signature length only */
693 goto finish;
694 }
695 if (signature->len < 2 * olen) {
696 PORT_SetError(SEC_ERROR_OUTPUT_LEN);
697 goto cleanup;
698 }
699
700 CHECK_MPI_OK(mp_init(&x1));
701 CHECK_MPI_OK(mp_init(&d));
702 CHECK_MPI_OK(mp_init(&k));
703 CHECK_MPI_OK(mp_init(&r));
704 CHECK_MPI_OK(mp_init(&s));
705 CHECK_MPI_OK(mp_init(&n));
706 CHECK_MPI_OK(mp_init(&t));
707 CHECK_MPI_OK(mp_init(&ar));
708
709 SECITEM_TO_MPINT(ecParams->order, &n);
710 SECITEM_TO_MPINT(key->privateValue, &d);
711
712 CHECK_MPI_OK(mp_read_unsigned_octets(&k, kb, kblen));
713 /* Make sure k is in the interval [1, n-1] */
714 if ((mp_cmp_z(&k) <= 0) || (mp_cmp(&k, &n) >= 0)) {
715 #if EC_DEBUG
716 printf("k is outside [1, n-1]\n");
717 mp_tohex(&k, mpstr);
718 printf("k : %s \n", mpstr);
719 mp_tohex(&n, mpstr);
720 printf("n : %s \n", mpstr);
721 #endif
722 PORT_SetError(SEC_ERROR_NEED_RANDOM);
723 goto cleanup;
724 }
725
726 /*
727 ** We do not want timing information to leak the length of k,
728 ** so we compute k*G using an equivalent scalar of fixed
729 ** bit-length.
730 ** Fix based on patch for ECDSA timing attack in the paper
731 ** by Billy Bob Brumley and Nicola Tuveri at
732 ** http://eprint.iacr.org/2011/232
733 **
734 ** How do we convert k to a value of a fixed bit-length?
735 ** k starts off as an integer satisfying 0 <= k < n. Hence,
736 ** n <= k+n < 2n, which means k+n has either the same number
737 ** of bits as n or one more bit than n. If k+n has the same
738 ** number of bits as n, the second addition ensures that the
739 ** final value has exactly one more bit than n. Thus, we
740 ** always end up with a value that exactly one more bit than n.
741 */
742 CHECK_MPI_OK(mp_add(&k, &n, &k));
743 if (mpl_significant_bits(&k) <= mpl_significant_bits(&n)) {
744 CHECK_MPI_OK(mp_add(&k, &n, &k));
745 }
746
747 /*
748 ** ANSI X9.62, Section 5.3.2, Step 2
749 **
750 ** Compute kG
751 */
752 kGpoint.len = EC_GetPointSize(ecParams);
753 kGpoint.data = PORT_Alloc(kGpoint.len);
754 if ((kGpoint.data == NULL) ||
755 (ec_points_mul(ecParams, &k, NULL, NULL, &kGpoint) != SECSuccess))
756 goto cleanup;
757
758 /*
759 ** ANSI X9.62, Section 5.3.3, Step 1
760 **
761 ** Extract the x co-ordinate of kG into x1
762 */
763 CHECK_MPI_OK(mp_read_unsigned_octets(&x1, kGpoint.data + 1,
764 (mp_size)flen));
765
766 /*
767 ** ANSI X9.62, Section 5.3.3, Step 2
768 **
769 ** r = x1 mod n NOTE: n is the order of the curve
770 */
771 CHECK_MPI_OK(mp_mod(&x1, &n, &r));
772
773 /*
774 ** ANSI X9.62, Section 5.3.3, Step 3
775 **
776 ** verify r != 0
777 */
778 if (mp_cmp_z(&r) == 0) {
779 PORT_SetError(SEC_ERROR_NEED_RANDOM);
780 goto cleanup;
781 }
782
783 /*
784 ** ANSI X9.62, Section 5.3.3, Step 4
785 **
786 ** s = (k**-1 * (HASH(M) + d*r)) mod n
787 */
788 SECITEM_TO_MPINT(*digest, &s); /* s = HASH(M) */
789
790 /* In the definition of EC signing, digests are truncated
791 * to the length of n in bits.
792 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
793 CHECK_MPI_OK((obits = mpl_significant_bits(&n)));
794 if (digest->len * 8 > obits) {
795 mpl_rsh(&s, &s, digest->len * 8 - obits);
796 }
797
798 #if EC_DEBUG
799 mp_todecimal(&n, mpstr);
800 printf("n : %s (dec)\n", mpstr);
801 mp_todecimal(&d, mpstr);
802 printf("d : %s (dec)\n", mpstr);
803 mp_tohex(&x1, mpstr);
804 printf("x1: %s\n", mpstr);
805 mp_todecimal(&s, mpstr);
806 printf("digest: %s (decimal)\n", mpstr);
807 mp_todecimal(&r, mpstr);
808 printf("r : %s (dec)\n", mpstr);
809 mp_tohex(&r, mpstr);
810 printf("r : %s\n", mpstr);
811 #endif
812
813 if ((t2 = PORT_Alloc(2 * ecParams->order.len)) == NULL) {
814 rv = SECFailure;
815 goto cleanup;
816 }
817 if (RNG_GenerateGlobalRandomBytes(t2, 2 * ecParams->order.len) != SECSuccess) {
818 PORT_SetError(SEC_ERROR_NEED_RANDOM);
819 rv = SECFailure;
820 goto cleanup;
821 }
822 CHECK_MPI_OK(mp_read_unsigned_octets(&t, t2, 2 * ecParams->order.len)); /* t <-$ Zn */
823 PORT_Memset(t2, 0, 2 * ecParams->order.len);
824 if (RNG_GenerateGlobalRandomBytes(t2, 2 * ecParams->order.len) != SECSuccess) {
825 PORT_SetError(SEC_ERROR_NEED_RANDOM);
826 rv = SECFailure;
827 goto cleanup;
828 }
829 CHECK_MPI_OK(mp_read_unsigned_octets(&ar, t2, 2 * ecParams->order.len)); /* ar <-$ Zn */
830
831 /* Using mp_invmod on k directly would leak bits from k. */
832 CHECK_MPI_OK(mp_mul(&k, &ar, &k)); /* k = k * ar */
833 CHECK_MPI_OK(mp_mulmod(&k, &t, &n, &k)); /* k = k * t mod n */
834 CHECK_MPI_OK(mp_invmod(&k, &n, &k)); /* k = k**-1 mod n */
835 CHECK_MPI_OK(mp_mulmod(&k, &t, &n, &k)); /* k = k * t mod n */
836 /* To avoid leaking secret bits here the addition is blinded. */
837 CHECK_MPI_OK(mp_mul(&d, &ar, &t)); /* t = d * ar */
838 CHECK_MPI_OK(mp_mulmod(&t, &r, &n, &d)); /* d = t * r mod n */
839 CHECK_MPI_OK(mp_mulmod(&s, &ar, &n, &t)); /* t = s * ar mod n */
840 CHECK_MPI_OK(mp_add(&t, &d, &s)); /* s = t + d */
841 CHECK_MPI_OK(mp_mulmod(&s, &k, &n, &s)); /* s = s * k mod n */
842
843 #if EC_DEBUG
844 mp_todecimal(&s, mpstr);
845 printf("s : %s (dec)\n", mpstr);
846 mp_tohex(&s, mpstr);
847 printf("s : %s\n", mpstr);
848 #endif
849
850 /*
851 ** ANSI X9.62, Section 5.3.3, Step 5
852 **
853 ** verify s != 0
854 */
855 if (mp_cmp_z(&s) == 0) {
856 PORT_SetError(SEC_ERROR_NEED_RANDOM);
857 goto cleanup;
858 }
859
860 /*
861 **
862 ** Signature is tuple (r, s)
863 */
864 CHECK_MPI_OK(mp_to_fixlen_octets(&r, signature->data, olen));
865 CHECK_MPI_OK(mp_to_fixlen_octets(&s, signature->data + olen, olen));
866 finish:
867 signature->len = 2 * olen;
868
869 rv = SECSuccess;
870 err = MP_OKAY;
871 cleanup:
872 mp_clear(&x1);
873 mp_clear(&d);
874 mp_clear(&k);
875 mp_clear(&r);
876 mp_clear(&s);
877 mp_clear(&n);
878 mp_clear(&t);
879 mp_clear(&ar);
880
881 if (t2) {
882 PORT_Free(t2);
883 }
884
885 if (kGpoint.data) {
886 PORT_ZFree(kGpoint.data, kGpoint.len);
887 }
888
889 if (err) {
890 MP_TO_SEC_ERROR(err);
891 rv = SECFailure;
892 }
893
894 #if EC_DEBUG
895 printf("ECDSA signing with seed %s\n",
896 (rv == SECSuccess) ? "succeeded" : "failed");
897 #endif
898
899 return rv;
900 }
901
902 /*
903 ** Computes the ECDSA signature on the digest using the given key
904 ** and a random seed.
905 */
906 SECStatus
ECDSA_SignDigest(ECPrivateKey * key,SECItem * signature,const SECItem * digest)907 ECDSA_SignDigest(ECPrivateKey *key, SECItem *signature, const SECItem *digest)
908 {
909 SECStatus rv = SECFailure;
910 int len;
911 unsigned char *kBytes = NULL;
912
913 if (!key) {
914 PORT_SetError(SEC_ERROR_INVALID_ARGS);
915 return SECFailure;
916 }
917
918 /* Generate random value k */
919 len = key->ecParams.order.len;
920 kBytes = ec_GenerateRandomPrivateKey(key->ecParams.order.data, len);
921 if (kBytes == NULL)
922 goto cleanup;
923
924 /* Generate ECDSA signature with the specified k value */
925 rv = ECDSA_SignDigestWithSeed(key, signature, digest, kBytes, len);
926
927 cleanup:
928 if (kBytes) {
929 PORT_ZFree(kBytes, len);
930 }
931
932 #if EC_DEBUG
933 printf("ECDSA signing %s\n",
934 (rv == SECSuccess) ? "succeeded" : "failed");
935 #endif
936
937 return rv;
938 }
939
940 /*
941 ** Checks the signature on the given digest using the key provided.
942 **
943 ** The key argument must represent a valid EC public key (a point on
944 ** the relevant curve). If it is not a valid point, then the behavior
945 ** of this function is undefined. In cases where a public key might
946 ** not be valid, use EC_ValidatePublicKey to check.
947 */
948 SECStatus
ECDSA_VerifyDigest(ECPublicKey * key,const SECItem * signature,const SECItem * digest)949 ECDSA_VerifyDigest(ECPublicKey *key, const SECItem *signature,
950 const SECItem *digest)
951 {
952 SECStatus rv = SECFailure;
953 mp_int r_, s_; /* tuple (r', s') is received signature) */
954 mp_int c, u1, u2, v; /* intermediate values used in verification */
955 mp_int x1;
956 mp_int n;
957 mp_err err = MP_OKAY;
958 ECParams *ecParams = NULL;
959 SECItem pointC = { siBuffer, NULL, 0 };
960 int slen; /* length in bytes of a half signature (r or s) */
961 int flen; /* length in bytes of the field size */
962 unsigned olen; /* length in bytes of the base point order */
963 unsigned obits; /* length in bits of the base point order */
964
965 #if EC_DEBUG
966 char mpstr[256];
967 printf("ECDSA verification called\n");
968 #endif
969
970 /* Initialize MPI integers. */
971 /* must happen before the first potential call to cleanup */
972 MP_DIGITS(&r_) = 0;
973 MP_DIGITS(&s_) = 0;
974 MP_DIGITS(&c) = 0;
975 MP_DIGITS(&u1) = 0;
976 MP_DIGITS(&u2) = 0;
977 MP_DIGITS(&x1) = 0;
978 MP_DIGITS(&v) = 0;
979 MP_DIGITS(&n) = 0;
980
981 /* Check args */
982 if (!key || !signature || !digest) {
983 PORT_SetError(SEC_ERROR_INVALID_ARGS);
984 goto cleanup;
985 }
986
987 ecParams = &(key->ecParams);
988 flen = (ecParams->fieldID.size + 7) >> 3;
989 olen = ecParams->order.len;
990 if (signature->len == 0 || signature->len % 2 != 0 ||
991 signature->len > 2 * olen) {
992 PORT_SetError(SEC_ERROR_INPUT_LEN);
993 goto cleanup;
994 }
995 slen = signature->len / 2;
996
997 /*
998 * The incoming point has been verified in sftk_handlePublicKeyObject.
999 */
1000
1001 SECITEM_AllocItem(NULL, &pointC, EC_GetPointSize(ecParams));
1002 if (pointC.data == NULL) {
1003 goto cleanup;
1004 }
1005
1006 CHECK_MPI_OK(mp_init(&r_));
1007 CHECK_MPI_OK(mp_init(&s_));
1008 CHECK_MPI_OK(mp_init(&c));
1009 CHECK_MPI_OK(mp_init(&u1));
1010 CHECK_MPI_OK(mp_init(&u2));
1011 CHECK_MPI_OK(mp_init(&x1));
1012 CHECK_MPI_OK(mp_init(&v));
1013 CHECK_MPI_OK(mp_init(&n));
1014
1015 /*
1016 ** Convert received signature (r', s') into MPI integers.
1017 */
1018 CHECK_MPI_OK(mp_read_unsigned_octets(&r_, signature->data, slen));
1019 CHECK_MPI_OK(mp_read_unsigned_octets(&s_, signature->data + slen, slen));
1020
1021 /*
1022 ** ANSI X9.62, Section 5.4.2, Steps 1 and 2
1023 **
1024 ** Verify that 0 < r' < n and 0 < s' < n
1025 */
1026 SECITEM_TO_MPINT(ecParams->order, &n);
1027 if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||
1028 mp_cmp(&r_, &n) >= 0 || mp_cmp(&s_, &n) >= 0) {
1029 PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
1030 goto cleanup; /* will return rv == SECFailure */
1031 }
1032
1033 /*
1034 ** ANSI X9.62, Section 5.4.2, Step 3
1035 **
1036 ** c = (s')**-1 mod n
1037 */
1038 CHECK_MPI_OK(mp_invmod(&s_, &n, &c)); /* c = (s')**-1 mod n */
1039
1040 /*
1041 ** ANSI X9.62, Section 5.4.2, Step 4
1042 **
1043 ** u1 = ((HASH(M')) * c) mod n
1044 */
1045 SECITEM_TO_MPINT(*digest, &u1); /* u1 = HASH(M) */
1046
1047 /* In the definition of EC signing, digests are truncated
1048 * to the length of n in bits.
1049 * (see SEC 1 "Elliptic Curve Digit Signature Algorithm" section 4.1.*/
1050 CHECK_MPI_OK((obits = mpl_significant_bits(&n)));
1051 if (digest->len * 8 > obits) { /* u1 = HASH(M') */
1052 mpl_rsh(&u1, &u1, digest->len * 8 - obits);
1053 }
1054
1055 #if EC_DEBUG
1056 mp_todecimal(&r_, mpstr);
1057 printf("r_: %s (dec)\n", mpstr);
1058 mp_todecimal(&s_, mpstr);
1059 printf("s_: %s (dec)\n", mpstr);
1060 mp_todecimal(&c, mpstr);
1061 printf("c : %s (dec)\n", mpstr);
1062 mp_todecimal(&u1, mpstr);
1063 printf("digest: %s (dec)\n", mpstr);
1064 #endif
1065
1066 CHECK_MPI_OK(mp_mulmod(&u1, &c, &n, &u1)); /* u1 = u1 * c mod n */
1067
1068 /*
1069 ** ANSI X9.62, Section 5.4.2, Step 4
1070 **
1071 ** u2 = ((r') * c) mod n
1072 */
1073 CHECK_MPI_OK(mp_mulmod(&r_, &c, &n, &u2));
1074
1075 /*
1076 ** ANSI X9.62, Section 5.4.3, Step 1
1077 **
1078 ** Compute u1*G + u2*Q
1079 ** Here, A = u1.G B = u2.Q and C = A + B
1080 ** If the result, C, is the point at infinity, reject the signature
1081 */
1082 if (ec_points_mul(ecParams, &u1, &u2, &key->publicValue, &pointC) != SECSuccess) {
1083 rv = SECFailure;
1084 goto cleanup;
1085 }
1086 if (ec_point_at_infinity(&pointC)) {
1087 PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
1088 rv = SECFailure;
1089 goto cleanup;
1090 }
1091
1092 CHECK_MPI_OK(mp_read_unsigned_octets(&x1, pointC.data + 1, flen));
1093
1094 /*
1095 ** ANSI X9.62, Section 5.4.4, Step 2
1096 **
1097 ** v = x1 mod n
1098 */
1099 CHECK_MPI_OK(mp_mod(&x1, &n, &v));
1100
1101 #if EC_DEBUG
1102 mp_todecimal(&r_, mpstr);
1103 printf("r_: %s (dec)\n", mpstr);
1104 mp_todecimal(&v, mpstr);
1105 printf("v : %s (dec)\n", mpstr);
1106 #endif
1107
1108 /*
1109 ** ANSI X9.62, Section 5.4.4, Step 3
1110 **
1111 ** Verification: v == r'
1112 */
1113 if (mp_cmp(&v, &r_)) {
1114 PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
1115 rv = SECFailure; /* Signature failed to verify. */
1116 } else {
1117 rv = SECSuccess; /* Signature verified. */
1118 }
1119
1120 #if EC_DEBUG
1121 mp_todecimal(&u1, mpstr);
1122 printf("u1: %s (dec)\n", mpstr);
1123 mp_todecimal(&u2, mpstr);
1124 printf("u2: %s (dec)\n", mpstr);
1125 mp_tohex(&x1, mpstr);
1126 printf("x1: %s\n", mpstr);
1127 mp_todecimal(&v, mpstr);
1128 printf("v : %s (dec)\n", mpstr);
1129 #endif
1130
1131 cleanup:
1132 mp_clear(&r_);
1133 mp_clear(&s_);
1134 mp_clear(&c);
1135 mp_clear(&u1);
1136 mp_clear(&u2);
1137 mp_clear(&x1);
1138 mp_clear(&v);
1139 mp_clear(&n);
1140
1141 if (pointC.data)
1142 SECITEM_ZfreeItem(&pointC, PR_FALSE);
1143 if (err) {
1144 MP_TO_SEC_ERROR(err);
1145 rv = SECFailure;
1146 }
1147
1148 #if EC_DEBUG
1149 printf("ECDSA verification %s\n",
1150 (rv == SECSuccess) ? "succeeded" : "failed");
1151 #endif
1152
1153 return rv;
1154 }
1155