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