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
53int	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
71typedef 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
83static 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 */
97feeSig 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;
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
192void 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 */
220unsigned 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 */
253feeReturn 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
332abort:
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 */
345feeReturn 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 */
371feeReturn 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
426abort:
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
443feeReturn feeSigVerifyNoProj(feeSig sig,
444	const unsigned char *data,
445	unsigned dataLen,
446	feePubKey pubKey);
447
448static void borrowPointProj(pointProj pt, unsigned maxDigits)
449{
450	pt->x = borrowGiant(maxDigits);
451	pt->y = borrowGiant(maxDigits);
452	pt->z = borrowGiant(maxDigits);
453}
454
455static void returnPointProj(pointProj pt)
456{
457	returnGiant(pt->x);
458	returnGiant(pt->y);
459	returnGiant(pt->z);
460}
461
462feeReturn 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 */
559feeReturn 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	}
639out:
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 */
655feeReturn 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}
675