]> git.saurik.com Git - apple/security.git/blob - OSX/libsecurity_cryptkit/lib/feeDigitalSignature.c
Security-57336.1.9.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 if(SIG_CURVE == CURVE_PLUS) {
170 gtog(cp->x1Plus, sinst->PmX);
171 }
172 else {
173 gtog(cp->x1Minus, sinst->PmX);
174 }
175 elliptic_simple(sinst->PmX, sinst->randGiant, cp);
176 }
177 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
178
179 if(SIG_CURVE == CURVE_PLUS) {
180 gtog(cp->x1Plus, sinst->PmX);
181 }
182 else {
183 gtog(cp->x1Minus, sinst->PmX);
184 }
185 elliptic_simple(sinst->PmX, sinst->randGiant, cp);
186
187 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
188
189 return sinst;
190 }
191
192 void feeSigFree(feeSig sig)
193 {
194 sigInst *sinst = (sigInst*) sig;
195
196 if(sinst->PmX) {
197 clearGiant(sinst->PmX);
198 freeGiant(sinst->PmX);
199 }
200 #if CRYPTKIT_ELL_PROJ_ENABLE
201 if(sinst->PmY) {
202 clearGiant(sinst->PmY);
203 freeGiant(sinst->PmY);
204 }
205 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
206 if(sinst->u) {
207 clearGiant(sinst->u);
208 freeGiant(sinst->u);
209 }
210 if(sinst->randGiant) {
211 clearGiant(sinst->randGiant);
212 freeGiant(sinst->randGiant);
213 }
214 ffree(sinst);
215 }
216
217 /*
218 * Obtain Pm after feeSigNewWithKey() or feeSigParse()
219 */
220 unsigned char *feeSigPm(feeSig sig,
221 unsigned *PmLen)
222 {
223 sigInst *sinst = (sigInst*) sig;
224 unsigned char *Pm;
225
226 if(sinst->PmX == NULL) {
227 dbgLog(("feeSigPm: no PmX!\n"));
228 return NULL;
229 }
230 else {
231 Pm = mem_from_giant(sinst->PmX, PmLen);
232 #if SIG_DEBUG
233 if(sigDebug)
234 {
235 int i;
236
237 printf("Pm : "); printGiant(sinst->PmX);
238 printf("PmData: ");
239 for(i=0; i<*PmLen; i++) {
240 printf("%x:", Pm[i]);
241 }
242 printf("\n");
243 }
244 #endif // SIG_DEBUG
245 }
246 return Pm;
247 }
248
249 /*
250 * Sign specified block of data (most likely a hash result) using
251 * specified feePubKey.
252 */
253 feeReturn feeSigSign(feeSig sig,
254 const unsigned char *data, // data to be signed
255 unsigned dataLen, // in bytes
256 feePubKey pubKey)
257 {
258 sigInst *sinst = (sigInst*) sig;
259 giant messageGiant = NULL;
260 unsigned maxlen;
261 giant privGiant;
262 unsigned privGiantBytes;
263 feeReturn frtn = FR_Success;
264 unsigned randBytesLen;
265 unsigned uDigits; // alloc'd digits in sinst->u
266 curveParams *cp;
267
268 if(pubKey == NULL) {
269 return FR_BadPubKey;
270 }
271 cp = feePubKeyCurveParams(pubKey);
272 if(cp == NULL) {
273 return FR_BadPubKey;
274 }
275
276 privGiant = feePubKeyPrivData(pubKey);
277 if(privGiant == NULL) {
278 dbgLog(("Attempt to Sign without private data\n"));
279 frtn = FR_IllegalArg;
280 goto abort;
281 }
282 privGiantBytes = abs(privGiant->sign) * GIANT_BYTES_PER_DIGIT;
283
284 /*
285 * Note PmX = m 'o' P1.
286 * Get message/digest as giant. May be significantly different
287 * in size from pubKey's basePrime.
288 */
289 messageGiant = giant_with_data(data, dataLen); // M(text)
290 randBytesLen = feePubKeyBitsize(pubKey) / 8;
291 maxlen = max(randBytesLen, dataLen);
292
293 /* leave plenty of room.... */
294 uDigits = (3 * (privGiantBytes + maxlen)) / GIANT_BYTES_PER_DIGIT;
295 sinst->u = newGiant(uDigits);
296 gtog(privGiant, sinst->u); // u := ourPri
297 mulg(messageGiant, sinst->u); // u *= M(text)
298 addg(sinst->randGiant, sinst->u); // u += m
299
300 /*
301 * Paranoia: we're using the curveParams from the caller's pubKey;
302 * this cp will have a valid x1OrderPlusRecip if pubKey is the same
303 * as the one passed to feeSigNewWithKey() (since feeSigNewWithKey
304 * called x1OrderPlusJustify()). But the caller could conceivably be
305 * using a different instance of their pubKey, in which case
306 * the key's cp->x1OrderPlusRecip may not be valid.
307 */
308 calcX1OrderPlusRecip(cp);
309
310 /* u := u mod x1OrderPlus */
311 #if SIG_DEBUG
312 if(sigDebug) {
313 printf("sigSign:\n");
314 printf("u pre-modg : ");
315 printGiant(sinst->u);
316 }
317 #endif
318 modg_via_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip, sinst->u);
319
320 #if SIG_DEBUG
321 if(sigDebug) {
322 printf("privGiant : ");
323 printGiant(privGiant);
324 printf("u : ");
325 printGiant(sinst->u);
326 printf("messageGiant: ");
327 printGiant(messageGiant);
328 printf("curveParams :\n");
329 printCurveParams(cp);
330 }
331 #endif // SIG_DEBUG
332 abort:
333 if(messageGiant) {
334 freeGiant(messageGiant);
335 }
336 return frtn;
337 }
338
339 /*
340 * Given a feeSig processed by feeSigSign, obtain a malloc'd byte
341 * array representing the signature.
342 * See ByteRep.doc for info on the format of the signature string;
343 * PLEASE UPDATE THIS DOCUMENT WHEN YOU MAKE CHANGES TO THE STRING FORMAT.
344 */
345 feeReturn feeSigData(feeSig sig,
346 unsigned char **sigData, // IGNORED....malloc'd and RETURNED
347 unsigned *sigDataLen) // RETURNED
348 {
349 sigInst *sinst = (sigInst*) sig;
350
351 #if CRYPTKIT_DER_ENABLE
352 return feeDEREncodeElGamalSignature(sinst->u, sinst->PmX, sigData, sigDataLen);
353 #else
354 *sigDataLen = lengthOfByteRepSig(sinst->u, sinst->PmX);
355 *sigData = (unsigned char*) fmalloc(*sigDataLen);
356 sigToByteRep(FEE_SIG_MAGIC,
357 FEE_SIG_VERSION,
358 FEE_SIG_VERSION_MIN,
359 sinst->u,
360 sinst->PmX,
361 *sigData);
362 return FR_Success;
363 #endif
364 }
365
366 /*
367 * Obtain a feeSig object by parsing an existing signature block.
368 * Note that if Pm is used to salt a hash of the signed data, this must
369 * function must be called prior to hashing.
370 */
371 feeReturn feeSigParse(const unsigned char *sigData,
372 size_t sigDataLen,
373 feeSig *sig) // RETURNED
374 {
375 sigInst *sinst = NULL;
376 feeReturn frtn;
377 #if !CRYPTKIT_DER_ENABLE
378 int version;
379 int magic;
380 int minVersion;
381 int rtn;
382 #endif
383
384 sinst = sinstAlloc();
385 #if CRYPTKIT_DER_ENABLE
386 frtn = feeDERDecodeElGamalSignature(sigData, sigDataLen, &sinst->u, &sinst->PmX);
387 if(frtn) {
388 goto abort;
389 }
390 #else
391 rtn = byteRepToSig(sigData,
392 sigDataLen,
393 FEE_SIG_VERSION,
394 &magic,
395 &version,
396 &minVersion,
397 &sinst->u,
398 &sinst->PmX);
399 if(rtn == 0) {
400 frtn = FR_BadSignatureFormat;
401 goto abort;
402 }
403 switch(magic) {
404 case FEE_ECDSA_MAGIC:
405 frtn = FR_WrongSignatureType; // ECDSA!
406 goto abort;
407 case FEE_SIG_MAGIC:
408 break; // proceed
409 default:
410 frtn = FR_BadSignatureFormat;
411 goto abort;
412 }
413 #endif /* CRYPTKIT_DER_ENABLE */
414
415 #if SIG_DEBUG
416 if(sigDebug) {
417 printf("sigParse: \n");
418 printf("u: ");
419 printGiant(sinst->u);
420 }
421 #endif // SIG_DEBUG
422
423 *sig = sinst;
424 return FR_Success;
425
426 abort:
427 if(sinst) {
428 feeSigFree(sinst);
429 }
430 return frtn;
431 }
432
433 /*
434 * Verify signature, obtained via feeSigParse, for specified
435 * data (most likely a hash result) and feePubKey. Returns non-zero if
436 * signature valid.
437 */
438
439 #define LOG_BAD_SIG 0
440
441 #if CRYPTKIT_ELL_PROJ_ENABLE
442
443 feeReturn feeSigVerifyNoProj(feeSig sig,
444 const unsigned char *data,
445 unsigned dataLen,
446 feePubKey pubKey);
447
448 static void borrowPointProj(pointProj pt, unsigned maxDigits)
449 {
450 pt->x = borrowGiant(maxDigits);
451 pt->y = borrowGiant(maxDigits);
452 pt->z = borrowGiant(maxDigits);
453 }
454
455 static void returnPointProj(pointProj pt)
456 {
457 returnGiant(pt->x);
458 returnGiant(pt->y);
459 returnGiant(pt->z);
460 }
461
462 feeReturn feeSigVerify(feeSig sig,
463 const unsigned char *data,
464 unsigned dataLen,
465 feePubKey pubKey)
466 {
467 pointProjStruct Q;
468 giant messageGiant = NULL;
469 pointProjStruct scratch;
470 sigInst *sinst = (sigInst*) sig;
471 feeReturn frtn;
472 curveParams *cp;
473 key origKey; // may be plus or minus key
474
475 if(sinst->PmX == NULL) {
476 dbgLog(("sigVerify without parse!\n"));
477 return FR_IllegalArg;
478 }
479
480 cp = feePubKeyCurveParams(pubKey);
481 if(cp->curveType != FCT_Weierstrass) {
482 return feeSigVerifyNoProj(sig, data, dataLen, pubKey);
483 }
484
485 borrowPointProj(&Q, cp->maxDigits);
486 borrowPointProj(&scratch, cp->maxDigits);
487
488 /*
489 * Q := P1
490 */
491 gtog(cp->x1Plus, Q.x);
492 gtog(cp->y1Plus, Q.y);
493 int_to_giant(1, Q.z);
494
495 messageGiant = giant_with_data(data, dataLen); // M(ciphertext)
496
497 /* Q := u 'o' P1 */
498 ellMulProjSimple(&Q, sinst->u, cp);
499
500 /* scratch := theirPub */
501 origKey = feePubKeyPlusCurve(pubKey);
502 gtog(origKey->x, scratch.x);
503 gtog(origKey->y, scratch.y);
504 int_to_giant(1, scratch.z);
505
506 #if SIG_DEBUG
507 if(sigDebug) {
508 printf("verify origKey:\n");
509 printKey(origKey);
510 printf("messageGiant: ");
511 printGiant(messageGiant);
512 printf("curveParams:\n");
513 printCurveParams(cp);
514 }
515 #endif // SIG_DEBUG
516
517 /* scratch := M 'o' theirPub */
518 ellMulProjSimple(&scratch, messageGiant, cp);
519
520 #if SIG_DEBUG
521 if(sigDebug) {
522 printf("signature_compare, with\n");
523 printf("p0 = Q:\n");
524 printGiant(Q.x);
525 printf("p1 = Pm:\n");
526 printGiant(sinst->PmX);
527 printf("p2 = scratch = R:\n");
528 printGiant(scratch.x);
529 }
530 #endif // SIG_DEBUG
531
532 if(signature_compare(Q.x, sinst->PmX, scratch.x, cp)) {
533
534 frtn = FR_InvalidSignature;
535 #if LOG_BAD_SIG
536 printf("***yup, bad sig***\n");
537 #endif // LOG_BAD_SIG
538 }
539 else {
540 frtn = FR_Success;
541 }
542 freeGiant(messageGiant);
543
544 returnPointProj(&Q);
545 returnPointProj(&scratch);
546 return frtn;
547 }
548
549 #else /* CRYPTKIT_ELL_PROJ_ENABLE */
550
551 #define feeSigVerifyNoProj(s, d, l, k) feeSigVerify(s, d, l, k)
552
553 #endif /* CRYPTKIT_ELL_PROJ_ENABLE */
554
555 /*
556 * FEE_SIG_USING_PROJ true : this is the "no Weierstrass" case
557 * feeSigVerifyNoProj false : this is redefined to feeSigVerify
558 */
559 feeReturn feeSigVerifyNoProj(feeSig sig,
560 const unsigned char *data,
561 unsigned dataLen,
562 feePubKey pubKey)
563 {
564 giant Q = NULL;
565 giant messageGiant = NULL;
566 giant scratch = NULL;
567 sigInst *sinst = (sigInst*) sig;
568 feeReturn frtn;
569 curveParams *cp;
570 key origKey; // may be plus or minus key
571
572 if(sinst->PmX == NULL) {
573 dbgLog(("sigVerify without parse!\n"));
574 frtn = FR_IllegalArg;
575 goto out;
576 }
577
578 cp = feePubKeyCurveParams(pubKey);
579 Q = newGiant(cp->maxDigits);
580
581 /*
582 * pick a key (+/-)
583 * Q := P1
584 */
585 if(SIG_CURVE == CURVE_PLUS) {
586 origKey = feePubKeyPlusCurve(pubKey);
587 gtog(cp->x1Plus, Q);
588 }
589 else {
590 origKey = feePubKeyMinusCurve(pubKey);
591 gtog(cp->x1Minus, Q);
592 }
593
594 messageGiant = giant_with_data(data, dataLen); // M(ciphertext)
595
596 /* Q := u 'o' P1 */
597 elliptic_simple(Q, sinst->u, cp);
598
599 /* scratch := theirPub */
600 scratch = newGiant(cp->maxDigits);
601 gtog(origKey->x, scratch);
602
603 #if SIG_DEBUG
604 if(sigDebug) {
605 printf("verify origKey:\n");
606 printKey(origKey);
607 printf("messageGiant: ");
608 printGiant(messageGiant);
609 printf("curveParams:\n");
610 printCurveParams(cp);
611 }
612 #endif // SIG_DEBUG
613
614 /* scratch := M 'o' theirPub */
615 elliptic_simple(scratch, messageGiant, cp);
616
617 #if SIG_DEBUG
618 if(sigDebug) {
619 printf("signature_compare, with\n");
620 printf("p0 = Q:\n");
621 printGiant(Q);
622 printf("p1 = Pm:\n");
623 printGiant(sinst->PmX);
624 printf("p2 = scratch = R:\n");
625 printGiant(scratch);
626 }
627 #endif // SIG_DEBUG
628
629 if(signature_compare(Q, sinst->PmX, scratch, cp)) {
630
631 frtn = FR_InvalidSignature;
632 #if LOG_BAD_SIG
633 printf("***yup, bad sig***\n");
634 #endif // LOG_BAD_SIG
635 }
636 else {
637 frtn = FR_Success;
638 }
639 out:
640 if(messageGiant != NULL) {
641 freeGiant(messageGiant);
642 }
643 if(Q != NULL) {
644 freeGiant(Q);
645 }
646 if(scratch != NULL) {
647 freeGiant(scratch);
648 }
649 return frtn;
650 }
651
652 /*
653 * For given key, calculate maximum signature size.
654 */
655 feeReturn feeSigSize(
656 feePubKey pubKey,
657 unsigned *maxSigLen)
658 {
659 /* For now, assume that u and Pm.x in the signature are
660 * same size as the key's associated curveParams->basePrime.
661 * We might have to pad this a bit....
662 */
663 curveParams *cp = feePubKeyCurveParams(pubKey);
664
665 if(cp == NULL) {
666 return FR_BadPubKey;
667 }
668 #if CRYPTKIT_DER_ENABLE
669 *maxSigLen = feeSizeOfDERSig(cp->basePrime, cp->basePrime);
670 #else
671 *maxSigLen = (unsigned)lengthOfByteRepSig(cp->basePrime, cp->basePrime);
672 #endif
673 return FR_Success;
674 }