]> git.saurik.com Git - apple/security.git/blob - OSX/libsecurity_cryptkit/lib/feeDigitalSignature.c
Security-58286.51.6.tar.gz
[apple/security.git] / OSX / libsecurity_cryptkit / lib / feeDigitalSignature.c
1 /* Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved.
2 *
3 * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT
4 * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE
5 * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE
6 * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE,
7 * INC. ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
8 * EXPOSE YOU TO LIABILITY.
9 ***************************************************************************
10 *
11 * feeDigitalSignature.c
12 *
13 * Revision History
14 * ----------------
15 * 10/06/98 ap
16 * Changed to compile with C++.
17 * 9 Sep 98 at NeXT
18 * Major changes to use projective elliptic algebra for
19 * Weierstrass curves.
20 * 15 Jan 97 at NeXT
21 * FEE_SIG_VERSION = 3 (removed code for compatibilty with all older
22 * versions).
23 * Was modg(), is curveOrderJustify()
24 * Use plus curve for ellipic algebra per IEEE standards
25 * 22 Aug 96 at NeXT
26 * Ported guts of Blaine Garst's NSFEEDigitalSignature.m to C.
27 */
28
29 #include "ckconfig.h"
30 #include "feeTypes.h"
31 #include "feePublicKey.h"
32 #include "feePublicKeyPrivate.h"
33 #include "feeDigitalSignature.h"
34 #include "giantIntegers.h"
35 #include "elliptic.h"
36 #include "feeRandom.h"
37 #include "curveParams.h"
38 #include "falloc.h"
39 #include "ckutilities.h"
40 #include "feeDebug.h"
41 #include "platform.h"
42 #include "byteRep.h"
43 #include "feeECDSA.h"
44 #if CRYPTKIT_DER_ENABLE
45 #include "CryptKitDER.h"
46 #endif
47
48 #include <stdlib.h>
49 #include "ellipticProj.h"
50
51 #define SIG_DEBUG 0
52 #if SIG_DEBUG
53 int sigDebug=1; // tweakable at runtime via debugger
54 #endif // SIG_DEBUG
55
56 #define SIG_CURVE DEFAULT_CURVE
57
58 /*
59 * true : justify randGiant to [2, x1OrderPlus-2]
60 * false : no truncate or mod of randGiant
61 */
62 #define RAND_JUST_X1_ORDER_PLUS 1
63
64 #define FEE_SIG_VERSION 4
65 #define FEE_SIG_VERSION_MIN 4
66
67 #ifndef max
68 #define max(a,b) ((a)>(b)? (a) : (b))
69 #endif // max
70
71 typedef struct {
72 giant PmX; // m 'o' P1; m = random
73 #if CRYPTKIT_ELL_PROJ_ENABLE
74 giant PmY; // y-coord of m 'o' P1 if we're
75 // using projective coords
76 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
77
78 giant u;
79 giant randGiant; // random m as giant - only known
80 // when signing
81 } sigInst;
82
83 static sigInst *sinstAlloc()
84 {
85 sigInst *sinst = (sigInst*) fmalloc(sizeof(sigInst));
86
87 bzero(sinst, sizeof(sigInst));
88 return sinst;
89 }
90
91 /*
92 * Create new feeSig object, including a random large integer 'randGiant' for
93 * possible use in salting a feeHash object, and 'PmX', equal to
94 * randGiant 'o' P1. Note that this is not called when *verifying* a
95 * signature, only when signing.
96 */
97 feeSig feeSigNewWithKey(
98 feePubKey pubKey,
99 feeRandFcn randFcn, /* optional */
100 void *randRef)
101 {
102 sigInst *sinst = sinstAlloc();
103 feeRand frand;
104 unsigned char *randBytes;
105 unsigned randBytesLen;
106 curveParams *cp;
107
108 if(pubKey == NULL) {
109 return NULL;
110 }
111 cp = feePubKeyCurveParams(pubKey);
112 if(cp == NULL) {
113 return NULL;
114 }
115
116 /*
117 * Generate random m, a little larger than key size, save as randGiant
118 */
119 randBytesLen = (feePubKeyBitsize(pubKey) / 8) + 1 + 8; // +8bytes (64bits) to reduce the biais when with reduction mod prime. Per FIPS186-4 - "Using Extra Random Bits"
120 randBytes = (unsigned char*) fmalloc(randBytesLen);
121 if(randFcn) {
122 randFcn(randRef, randBytes, randBytesLen);
123 }
124 else {
125 frand = feeRandAlloc();
126 feeRandBytes(frand, randBytes, randBytesLen);
127 feeRandFree(frand);
128 }
129 sinst->randGiant = giant_with_data(randBytes, randBytesLen);
130 memset(randBytes, 0, randBytesLen);
131 ffree(randBytes);
132
133 #if FEE_DEBUG
134 if(isZero(sinst->randGiant)) {
135 printf("feeSigNewWithKey: randGiant = 0!\n");
136 }
137 #endif // FEE_DEBUG
138
139 /*
140 * Justify randGiant to be in [2, x1OrderPlus]
141 */
142 x1OrderPlusJustify(sinst->randGiant, cp);
143
144 /* PmX := randGiant 'o' P1 */
145 sinst->PmX = newGiant(cp->maxDigits);
146
147 #if CRYPTKIT_ELL_PROJ_ENABLE
148
149 if(cp->curveType == FCT_Weierstrass) {
150
151 pointProjStruct pt0;
152
153 sinst->PmY = newGiant(cp->maxDigits);
154
155 /* cook up pt0 as P1 */
156 pt0.x = sinst->PmX;
157 pt0.y = sinst->PmY;
158 pt0.z = borrowGiant(cp->maxDigits);
159 gtog(cp->x1Plus, pt0.x);
160 gtog(cp->y1Plus, pt0.y);
161 int_to_giant(1, pt0.z);
162
163 /* pt0 := P1 'o' randGiant */
164 ellMulProjSimple(&pt0, sinst->randGiant, cp);
165
166 returnGiant(pt0.z);
167 }
168 else {
169 #pragma clang diagnostic push
170 #pragma clang diagnostic ignored "-Wunreachable-code"
171 if(SIG_CURVE == CURVE_PLUS) {
172 gtog(cp->x1Plus, sinst->PmX);
173 }
174 else {
175 gtog(cp->x1Minus, sinst->PmX);
176 }
177 #pragma clang diagnostic pop
178 elliptic_simple(sinst->PmX, sinst->randGiant, cp);
179 }
180 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
181
182 if(SIG_CURVE == CURVE_PLUS) {
183 gtog(cp->x1Plus, sinst->PmX);
184 }
185 else {
186 gtog(cp->x1Minus, sinst->PmX);
187 }
188 elliptic_simple(sinst->PmX, sinst->randGiant, cp);
189
190 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
191
192 return sinst;
193 }
194
195 void feeSigFree(feeSig sig)
196 {
197 sigInst *sinst = (sigInst*) sig;
198
199 if(sinst->PmX) {
200 clearGiant(sinst->PmX);
201 freeGiant(sinst->PmX);
202 }
203 #if CRYPTKIT_ELL_PROJ_ENABLE
204 if(sinst->PmY) {
205 clearGiant(sinst->PmY);
206 freeGiant(sinst->PmY);
207 }
208 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
209 if(sinst->u) {
210 clearGiant(sinst->u);
211 freeGiant(sinst->u);
212 }
213 if(sinst->randGiant) {
214 clearGiant(sinst->randGiant);
215 freeGiant(sinst->randGiant);
216 }
217 ffree(sinst);
218 }
219
220 /*
221 * Obtain Pm after feeSigNewWithKey() or feeSigParse()
222 */
223 unsigned char *feeSigPm(feeSig sig,
224 unsigned *PmLen)
225 {
226 sigInst *sinst = (sigInst*) sig;
227 unsigned char *Pm;
228
229 if(sinst->PmX == NULL) {
230 dbgLog(("feeSigPm: no PmX!\n"));
231 return NULL;
232 }
233 else {
234 Pm = mem_from_giant(sinst->PmX, PmLen);
235 #if SIG_DEBUG
236 if(sigDebug)
237 {
238 int i;
239
240 printf("Pm : "); printGiant(sinst->PmX);
241 printf("PmData: ");
242 for(i=0; i<*PmLen; i++) {
243 printf("%x:", Pm[i]);
244 }
245 printf("\n");
246 }
247 #endif // SIG_DEBUG
248 }
249 return Pm;
250 }
251
252 /*
253 * Sign specified block of data (most likely a hash result) using
254 * specified feePubKey.
255 */
256 feeReturn feeSigSign(feeSig sig,
257 const unsigned char *data, // data to be signed
258 unsigned dataLen, // in bytes
259 feePubKey pubKey)
260 {
261 sigInst *sinst = (sigInst*) sig;
262 giant messageGiant = NULL;
263 unsigned maxlen;
264 giant privGiant;
265 unsigned privGiantBytes;
266 feeReturn frtn = FR_Success;
267 unsigned randBytesLen;
268 unsigned uDigits; // alloc'd digits in sinst->u
269 curveParams *cp;
270
271 if(pubKey == NULL) {
272 return FR_BadPubKey;
273 }
274 cp = feePubKeyCurveParams(pubKey);
275 if(cp == NULL) {
276 return FR_BadPubKey;
277 }
278
279 privGiant = feePubKeyPrivData(pubKey);
280 if(privGiant == NULL) {
281 dbgLog(("Attempt to Sign without private data\n"));
282 frtn = FR_IllegalArg;
283 goto abort;
284 }
285 privGiantBytes = abs(privGiant->sign) * GIANT_BYTES_PER_DIGIT;
286
287 /*
288 * Note PmX = m 'o' P1.
289 * Get message/digest as giant. May be significantly different
290 * in size from pubKey's basePrime.
291 */
292 messageGiant = giant_with_data(data, dataLen); // M(text)
293 randBytesLen = feePubKeyBitsize(pubKey) / 8;
294 maxlen = max(randBytesLen, dataLen);
295
296 /* leave plenty of room.... */
297 uDigits = (3 * (privGiantBytes + maxlen)) / GIANT_BYTES_PER_DIGIT;
298 sinst->u = newGiant(uDigits);
299 gtog(privGiant, sinst->u); // u := ourPri
300 mulg(messageGiant, sinst->u); // u *= M(text)
301 addg(sinst->randGiant, sinst->u); // u += m
302
303 /*
304 * Paranoia: we're using the curveParams from the caller's pubKey;
305 * this cp will have a valid x1OrderPlusRecip if pubKey is the same
306 * as the one passed to feeSigNewWithKey() (since feeSigNewWithKey
307 * called x1OrderPlusJustify()). But the caller could conceivably be
308 * using a different instance of their pubKey, in which case
309 * the key's cp->x1OrderPlusRecip may not be valid.
310 */
311 calcX1OrderPlusRecip(cp);
312
313 /* u := u mod x1OrderPlus */
314 #if SIG_DEBUG
315 if(sigDebug) {
316 printf("sigSign:\n");
317 printf("u pre-modg : ");
318 printGiant(sinst->u);
319 }
320 #endif
321 modg_via_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip, sinst->u);
322
323 #if SIG_DEBUG
324 if(sigDebug) {
325 printf("privGiant : ");
326 printGiant(privGiant);
327 printf("u : ");
328 printGiant(sinst->u);
329 printf("messageGiant: ");
330 printGiant(messageGiant);
331 printf("curveParams :\n");
332 printCurveParams(cp);
333 }
334 #endif // SIG_DEBUG
335 abort:
336 if(messageGiant) {
337 freeGiant(messageGiant);
338 }
339 return frtn;
340 }
341
342 /*
343 * Given a feeSig processed by feeSigSign, obtain a malloc'd byte
344 * array representing the signature.
345 * See ByteRep.doc for info on the format of the signature string;
346 * PLEASE UPDATE THIS DOCUMENT WHEN YOU MAKE CHANGES TO THE STRING FORMAT.
347 */
348 feeReturn feeSigData(feeSig sig,
349 unsigned char **sigData, // IGNORED....malloc'd and RETURNED
350 unsigned *sigDataLen) // RETURNED
351 {
352 sigInst *sinst = (sigInst*) sig;
353
354 #if CRYPTKIT_DER_ENABLE
355 return feeDEREncodeElGamalSignature(sinst->u, sinst->PmX, sigData, sigDataLen);
356 #else
357 *sigDataLen = lengthOfByteRepSig(sinst->u, sinst->PmX);
358 *sigData = (unsigned char*) fmalloc(*sigDataLen);
359 sigToByteRep(FEE_SIG_MAGIC,
360 FEE_SIG_VERSION,
361 FEE_SIG_VERSION_MIN,
362 sinst->u,
363 sinst->PmX,
364 *sigData);
365 return FR_Success;
366 #endif
367 }
368
369 /*
370 * Obtain a feeSig object by parsing an existing signature block.
371 * Note that if Pm is used to salt a hash of the signed data, this must
372 * function must be called prior to hashing.
373 */
374 feeReturn feeSigParse(const unsigned char *sigData,
375 size_t sigDataLen,
376 feeSig *sig) // RETURNED
377 {
378 sigInst *sinst = NULL;
379 feeReturn frtn;
380 #if !CRYPTKIT_DER_ENABLE
381 int version;
382 int magic;
383 int minVersion;
384 int rtn;
385 #endif
386
387 sinst = sinstAlloc();
388 #if CRYPTKIT_DER_ENABLE
389 frtn = feeDERDecodeElGamalSignature(sigData, sigDataLen, &sinst->u, &sinst->PmX);
390 if(frtn) {
391 goto abort;
392 }
393 #else
394 rtn = byteRepToSig(sigData,
395 sigDataLen,
396 FEE_SIG_VERSION,
397 &magic,
398 &version,
399 &minVersion,
400 &sinst->u,
401 &sinst->PmX);
402 if(rtn == 0) {
403 frtn = FR_BadSignatureFormat;
404 goto abort;
405 }
406 switch(magic) {
407 case FEE_ECDSA_MAGIC:
408 frtn = FR_WrongSignatureType; // ECDSA!
409 goto abort;
410 case FEE_SIG_MAGIC:
411 break; // proceed
412 default:
413 frtn = FR_BadSignatureFormat;
414 goto abort;
415 }
416 #endif /* CRYPTKIT_DER_ENABLE */
417
418 #if SIG_DEBUG
419 if(sigDebug) {
420 printf("sigParse: \n");
421 printf("u: ");
422 printGiant(sinst->u);
423 }
424 #endif // SIG_DEBUG
425
426 *sig = sinst;
427 return FR_Success;
428
429 abort:
430 if(sinst) {
431 feeSigFree(sinst);
432 }
433 return frtn;
434 }
435
436 /*
437 * Verify signature, obtained via feeSigParse, for specified
438 * data (most likely a hash result) and feePubKey. Returns non-zero if
439 * signature valid.
440 */
441
442 #define LOG_BAD_SIG 0
443
444 #if CRYPTKIT_ELL_PROJ_ENABLE
445
446 feeReturn feeSigVerifyNoProj(feeSig sig,
447 const unsigned char *data,
448 unsigned dataLen,
449 feePubKey pubKey);
450
451 static void borrowPointProj(pointProj pt, unsigned maxDigits)
452 {
453 pt->x = borrowGiant(maxDigits);
454 pt->y = borrowGiant(maxDigits);
455 pt->z = borrowGiant(maxDigits);
456 }
457
458 static void returnPointProj(pointProj pt)
459 {
460 returnGiant(pt->x);
461 returnGiant(pt->y);
462 returnGiant(pt->z);
463 }
464
465 feeReturn feeSigVerify(feeSig sig,
466 const unsigned char *data,
467 unsigned dataLen,
468 feePubKey pubKey)
469 {
470 pointProjStruct Q;
471 giant messageGiant = NULL;
472 pointProjStruct scratch;
473 sigInst *sinst = (sigInst*) sig;
474 feeReturn frtn;
475 curveParams *cp;
476 key origKey; // may be plus or minus key
477
478 if(sinst->PmX == NULL) {
479 dbgLog(("sigVerify without parse!\n"));
480 return FR_IllegalArg;
481 }
482
483 cp = feePubKeyCurveParams(pubKey);
484 if(cp->curveType != FCT_Weierstrass) {
485 return feeSigVerifyNoProj(sig, data, dataLen, pubKey);
486 }
487
488 borrowPointProj(&Q, cp->maxDigits);
489 borrowPointProj(&scratch, cp->maxDigits);
490
491 /*
492 * Q := P1
493 */
494 gtog(cp->x1Plus, Q.x);
495 gtog(cp->y1Plus, Q.y);
496 int_to_giant(1, Q.z);
497
498 messageGiant = giant_with_data(data, dataLen); // M(ciphertext)
499
500 /* Q := u 'o' P1 */
501 ellMulProjSimple(&Q, sinst->u, cp);
502
503 /* scratch := theirPub */
504 origKey = feePubKeyPlusCurve(pubKey);
505 gtog(origKey->x, scratch.x);
506 gtog(origKey->y, scratch.y);
507 int_to_giant(1, scratch.z);
508
509 #if SIG_DEBUG
510 if(sigDebug) {
511 printf("verify origKey:\n");
512 printKey(origKey);
513 printf("messageGiant: ");
514 printGiant(messageGiant);
515 printf("curveParams:\n");
516 printCurveParams(cp);
517 }
518 #endif // SIG_DEBUG
519
520 /* scratch := M 'o' theirPub */
521 ellMulProjSimple(&scratch, messageGiant, cp);
522
523 #if SIG_DEBUG
524 if(sigDebug) {
525 printf("signature_compare, with\n");
526 printf("p0 = Q:\n");
527 printGiant(Q.x);
528 printf("p1 = Pm:\n");
529 printGiant(sinst->PmX);
530 printf("p2 = scratch = R:\n");
531 printGiant(scratch.x);
532 }
533 #endif // SIG_DEBUG
534
535 if(signature_compare(Q.x, sinst->PmX, scratch.x, cp)) {
536
537 frtn = FR_InvalidSignature;
538 #if LOG_BAD_SIG
539 printf("***yup, bad sig***\n");
540 #endif // LOG_BAD_SIG
541 }
542 else {
543 frtn = FR_Success;
544 }
545 freeGiant(messageGiant);
546
547 returnPointProj(&Q);
548 returnPointProj(&scratch);
549 return frtn;
550 }
551
552 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
553
554 #define feeSigVerifyNoProj(s, d, l, k) feeSigVerify(s, d, l, k)
555
556 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
557
558 /*
559 * FEE_SIG_USING_PROJ true : this is the "no Weierstrass" case
560 * feeSigVerifyNoProj false : this is redefined to feeSigVerify
561 */
562 feeReturn feeSigVerifyNoProj(feeSig sig,
563 const unsigned char *data,
564 unsigned dataLen,
565 feePubKey pubKey)
566 {
567 giant Q = NULL;
568 giant messageGiant = NULL;
569 giant scratch = NULL;
570 sigInst *sinst = (sigInst*) sig;
571 feeReturn frtn;
572 curveParams *cp;
573 key origKey; // may be plus or minus key
574
575 if(sinst->PmX == NULL) {
576 dbgLog(("sigVerify without parse!\n"));
577 frtn = FR_IllegalArg;
578 goto out;
579 }
580
581 cp = feePubKeyCurveParams(pubKey);
582 Q = newGiant(cp->maxDigits);
583
584 /*
585 * pick a key (+/-)
586 * Q := P1
587 */
588 #pragma clang diagnostic push
589 #pragma clang diagnostic ignored "-Wunreachable-code"
590 if(SIG_CURVE == CURVE_PLUS) {
591 origKey = feePubKeyPlusCurve(pubKey);
592 gtog(cp->x1Plus, Q);
593 }
594 else {
595 origKey = feePubKeyMinusCurve(pubKey);
596 gtog(cp->x1Minus, Q);
597 }
598 #pragma clang diagnostic pop
599
600 messageGiant = giant_with_data(data, dataLen); // M(ciphertext)
601
602 /* Q := u 'o' P1 */
603 elliptic_simple(Q, sinst->u, cp);
604
605 /* scratch := theirPub */
606 scratch = newGiant(cp->maxDigits);
607 gtog(origKey->x, scratch);
608
609 #if SIG_DEBUG
610 if(sigDebug) {
611 printf("verify origKey:\n");
612 printKey(origKey);
613 printf("messageGiant: ");
614 printGiant(messageGiant);
615 printf("curveParams:\n");
616 printCurveParams(cp);
617 }
618 #endif // SIG_DEBUG
619
620 /* scratch := M 'o' theirPub */
621 elliptic_simple(scratch, messageGiant, cp);
622
623 #if SIG_DEBUG
624 if(sigDebug) {
625 printf("signature_compare, with\n");
626 printf("p0 = Q:\n");
627 printGiant(Q);
628 printf("p1 = Pm:\n");
629 printGiant(sinst->PmX);
630 printf("p2 = scratch = R:\n");
631 printGiant(scratch);
632 }
633 #endif // SIG_DEBUG
634
635 if(signature_compare(Q, sinst->PmX, scratch, cp)) {
636
637 frtn = FR_InvalidSignature;
638 #if LOG_BAD_SIG
639 printf("***yup, bad sig***\n");
640 #endif // LOG_BAD_SIG
641 }
642 else {
643 frtn = FR_Success;
644 }
645 out:
646 if(messageGiant != NULL) {
647 freeGiant(messageGiant);
648 }
649 if(Q != NULL) {
650 freeGiant(Q);
651 }
652 if(scratch != NULL) {
653 freeGiant(scratch);
654 }
655 return frtn;
656 }
657
658 /*
659 * For given key, calculate maximum signature size.
660 */
661 feeReturn feeSigSize(
662 feePubKey pubKey,
663 unsigned *maxSigLen)
664 {
665 /* For now, assume that u and Pm.x in the signature are
666 * same size as the key's associated curveParams->basePrime.
667 * We might have to pad this a bit....
668 */
669 curveParams *cp = feePubKeyCurveParams(pubKey);
670
671 if(cp == NULL) {
672 return FR_BadPubKey;
673 }
674 #if CRYPTKIT_DER_ENABLE
675 *maxSigLen = feeSizeOfDERSig(cp->basePrime, cp->basePrime);
676 #else
677 *maxSigLen = (unsigned)lengthOfByteRepSig(cp->basePrime, cp->basePrime);
678 #endif
679 return FR_Success;
680 }