X-Git-Url: https://git.saurik.com/apple/security.git/blobdiff_plain/80e2389990082500d76eb566d4946be3e786c3ef..d8f41ccd20de16f8ebe2ccc84d47bf1cb2b26bbb:/Security/libsecurity_cryptkit/lib/feeDigitalSignature.c diff --git a/Security/libsecurity_cryptkit/lib/feeDigitalSignature.c b/Security/libsecurity_cryptkit/lib/feeDigitalSignature.c new file mode 100644 index 00000000..0fdc48a9 --- /dev/null +++ b/Security/libsecurity_cryptkit/lib/feeDigitalSignature.c @@ -0,0 +1,674 @@ +/* Copyright (c) 1998,2011,2014 Apple Inc. All Rights Reserved. + * + * NOTICE: USE OF THE MATERIALS ACCOMPANYING THIS NOTICE IS SUBJECT + * TO THE TERMS OF THE SIGNED "FAST ELLIPTIC ENCRYPTION (FEE) REFERENCE + * SOURCE CODE EVALUATION AGREEMENT" BETWEEN APPLE, INC. AND THE + * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE, + * INC. ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL + * EXPOSE YOU TO LIABILITY. + *************************************************************************** + * + * feeDigitalSignature.c + * + * Revision History + * ---------------- + * 10/06/98 ap + * Changed to compile with C++. + * 9 Sep 98 at NeXT + * Major changes to use projective elliptic algebra for + * Weierstrass curves. + * 15 Jan 97 at NeXT + * FEE_SIG_VERSION = 3 (removed code for compatibilty with all older + * versions). + * Was modg(), is curveOrderJustify() + * Use plus curve for ellipic algebra per IEEE standards + * 22 Aug 96 at NeXT + * Ported guts of Blaine Garst's NSFEEDigitalSignature.m to C. + */ + +#include "ckconfig.h" +#include "feeTypes.h" +#include "feePublicKey.h" +#include "feePublicKeyPrivate.h" +#include "feeDigitalSignature.h" +#include "giantIntegers.h" +#include "elliptic.h" +#include "feeRandom.h" +#include "curveParams.h" +#include "falloc.h" +#include "ckutilities.h" +#include "feeDebug.h" +#include "platform.h" +#include "byteRep.h" +#include "feeECDSA.h" +#if CRYPTKIT_DER_ENABLE +#include "CryptKitDER.h" +#endif + +#include +#include "ellipticProj.h" + +#define SIG_DEBUG 0 +#if SIG_DEBUG +int sigDebug=1; // tweakable at runtime via debugger +#endif // SIG_DEBUG + +#define SIG_CURVE DEFAULT_CURVE + +/* + * true : justify randGiant to [2, x1OrderPlus-2] + * false : no truncate or mod of randGiant + */ +#define RAND_JUST_X1_ORDER_PLUS 1 + +#define FEE_SIG_VERSION 4 +#define FEE_SIG_VERSION_MIN 4 + +#ifndef max +#define max(a,b) ((a)>(b)? (a) : (b)) +#endif // max + +typedef struct { + giant PmX; // m 'o' P1; m = random + #if CRYPTKIT_ELL_PROJ_ENABLE + giant PmY; // y-coord of m 'o' P1 if we're + // using projective coords + #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ + + giant u; + giant randGiant; // random m as giant - only known + // when signing +} sigInst; + +static sigInst *sinstAlloc() +{ + sigInst *sinst = (sigInst*) fmalloc(sizeof(sigInst)); + + bzero(sinst, sizeof(sigInst)); + return sinst; +} + +/* + * Create new feeSig object, including a random large integer 'randGiant' for + * possible use in salting a feeHash object, and 'PmX', equal to + * randGiant 'o' P1. Note that this is not called when *verifying* a + * signature, only when signing. + */ +feeSig feeSigNewWithKey( + feePubKey pubKey, + feeRandFcn randFcn, /* optional */ + void *randRef) +{ + sigInst *sinst = sinstAlloc(); + feeRand frand; + unsigned char *randBytes; + unsigned randBytesLen; + curveParams *cp; + + if(pubKey == NULL) { + return NULL; + } + cp = feePubKeyCurveParams(pubKey); + if(cp == NULL) { + return NULL; + } + + /* + * Generate random m, a little larger than key size, save as randGiant + */ + randBytesLen = (feePubKeyBitsize(pubKey) / 8) + 1; + randBytes = (unsigned char*) fmalloc(randBytesLen); + if(randFcn) { + randFcn(randRef, randBytes, randBytesLen); + } + else { + frand = feeRandAlloc(); + feeRandBytes(frand, randBytes, randBytesLen); + feeRandFree(frand); + } + sinst->randGiant = giant_with_data(randBytes, randBytesLen); + memset(randBytes, 0, randBytesLen); + ffree(randBytes); + + #if FEE_DEBUG + if(isZero(sinst->randGiant)) { + printf("feeSigNewWithKey: randGiant = 0!\n"); + } + #endif // FEE_DEBUG + + /* + * Justify randGiant to be in [2, x1OrderPlus] + */ + x1OrderPlusJustify(sinst->randGiant, cp); + + /* PmX := randGiant 'o' P1 */ + sinst->PmX = newGiant(cp->maxDigits); + + #if CRYPTKIT_ELL_PROJ_ENABLE + + if(cp->curveType == FCT_Weierstrass) { + + pointProjStruct pt0; + + sinst->PmY = newGiant(cp->maxDigits); + + /* cook up pt0 as P1 */ + pt0.x = sinst->PmX; + pt0.y = sinst->PmY; + pt0.z = borrowGiant(cp->maxDigits); + gtog(cp->x1Plus, pt0.x); + gtog(cp->y1Plus, pt0.y); + int_to_giant(1, pt0.z); + + /* pt0 := P1 'o' randGiant */ + ellMulProjSimple(&pt0, sinst->randGiant, cp); + + returnGiant(pt0.z); + } + else { + if(SIG_CURVE == CURVE_PLUS) { + gtog(cp->x1Plus, sinst->PmX); + } + else { + gtog(cp->x1Minus, sinst->PmX); + } + elliptic_simple(sinst->PmX, sinst->randGiant, cp); + } + #else /* CRYPTKIT_ELL_PROJ_ENABLE */ + + if(SIG_CURVE == CURVE_PLUS) { + gtog(cp->x1Plus, sinst->PmX); + } + else { + gtog(cp->x1Minus, sinst->PmX); + } + elliptic_simple(sinst->PmX, sinst->randGiant, cp); + + #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ + + return sinst; +} + +void feeSigFree(feeSig sig) +{ + sigInst *sinst = (sigInst*) sig; + + if(sinst->PmX) { + clearGiant(sinst->PmX); + freeGiant(sinst->PmX); + } + #if CRYPTKIT_ELL_PROJ_ENABLE + if(sinst->PmY) { + clearGiant(sinst->PmY); + freeGiant(sinst->PmY); + } + #endif /* CRYPTKIT_ELL_PROJ_ENABLE */ + if(sinst->u) { + clearGiant(sinst->u); + freeGiant(sinst->u); + } + if(sinst->randGiant) { + clearGiant(sinst->randGiant); + freeGiant(sinst->randGiant); + } + ffree(sinst); +} + +/* + * Obtain Pm after feeSigNewWithKey() or feeSigParse() + */ +unsigned char *feeSigPm(feeSig sig, + unsigned *PmLen) +{ + sigInst *sinst = (sigInst*) sig; + unsigned char *Pm; + + if(sinst->PmX == NULL) { + dbgLog(("feeSigPm: no PmX!\n")); + return NULL; + } + else { + Pm = mem_from_giant(sinst->PmX, PmLen); + #if SIG_DEBUG + if(sigDebug) + { + int i; + + printf("Pm : "); printGiant(sinst->PmX); + printf("PmData: "); + for(i=0; i<*PmLen; i++) { + printf("%x:", Pm[i]); + } + printf("\n"); + } + #endif // SIG_DEBUG + } + return Pm; +} + +/* + * Sign specified block of data (most likely a hash result) using + * specified feePubKey. + */ +feeReturn feeSigSign(feeSig sig, + const unsigned char *data, // data to be signed + unsigned dataLen, // in bytes + feePubKey pubKey) +{ + sigInst *sinst = (sigInst*) sig; + giant messageGiant = NULL; + unsigned maxlen; + giant privGiant; + unsigned privGiantBytes; + feeReturn frtn = FR_Success; + unsigned randBytesLen; + unsigned uDigits; // alloc'd digits in sinst->u + curveParams *cp; + + if(pubKey == NULL) { + return FR_BadPubKey; + } + cp = feePubKeyCurveParams(pubKey); + if(cp == NULL) { + return FR_BadPubKey; + } + + privGiant = feePubKeyPrivData(pubKey); + if(privGiant == NULL) { + dbgLog(("Attempt to Sign without private data\n")); + frtn = FR_IllegalArg; + goto abort; + } + privGiantBytes = abs(privGiant->sign) * GIANT_BYTES_PER_DIGIT; + + /* + * Note PmX = m 'o' P1. + * Get message/digest as giant. May be significantly different + * in size from pubKey's basePrime. + */ + messageGiant = giant_with_data(data, dataLen); // M(text) + randBytesLen = feePubKeyBitsize(pubKey) / 8; + maxlen = max(randBytesLen, dataLen); + + /* leave plenty of room.... */ + uDigits = (3 * (privGiantBytes + maxlen)) / GIANT_BYTES_PER_DIGIT; + sinst->u = newGiant(uDigits); + gtog(privGiant, sinst->u); // u := ourPri + mulg(messageGiant, sinst->u); // u *= M(text) + addg(sinst->randGiant, sinst->u); // u += m + + /* + * Paranoia: we're using the curveParams from the caller's pubKey; + * this cp will have a valid x1OrderPlusRecip if pubKey is the same + * as the one passed to feeSigNewWithKey() (since feeSigNewWithKey + * called x1OrderPlusJustify()). But the caller could conceivably be + * using a different instance of their pubKey, in which case + * the key's cp->x1OrderPlusRecip may not be valid. + */ + calcX1OrderPlusRecip(cp); + + /* u := u mod x1OrderPlus */ + #if SIG_DEBUG + if(sigDebug) { + printf("sigSign:\n"); + printf("u pre-modg : "); + printGiant(sinst->u); + } + #endif + modg_via_recip(cp->x1OrderPlus, cp->x1OrderPlusRecip, sinst->u); + + #if SIG_DEBUG + if(sigDebug) { + printf("privGiant : "); + printGiant(privGiant); + printf("u : "); + printGiant(sinst->u); + printf("messageGiant: "); + printGiant(messageGiant); + printf("curveParams :\n"); + printCurveParams(cp); + } + #endif // SIG_DEBUG +abort: + if(messageGiant) { + freeGiant(messageGiant); + } + return frtn; +} + +/* + * Given a feeSig processed by feeSigSign, obtain a malloc'd byte + * array representing the signature. + * See ByteRep.doc for info on the format of the signature string; + * PLEASE UPDATE THIS DOCUMENT WHEN YOU MAKE CHANGES TO THE STRING FORMAT. + */ +feeReturn feeSigData(feeSig sig, + unsigned char **sigData, // IGNORED....malloc'd and RETURNED + unsigned *sigDataLen) // RETURNED +{ + sigInst *sinst = (sigInst*) sig; + + #if CRYPTKIT_DER_ENABLE + return feeDEREncodeElGamalSignature(sinst->u, sinst->PmX, sigData, sigDataLen); + #else + *sigDataLen = lengthOfByteRepSig(sinst->u, sinst->PmX); + *sigData = (unsigned char*) fmalloc(*sigDataLen); + sigToByteRep(FEE_SIG_MAGIC, + FEE_SIG_VERSION, + FEE_SIG_VERSION_MIN, + sinst->u, + sinst->PmX, + *sigData); + return FR_Success; + #endif +} + +/* + * Obtain a feeSig object by parsing an existing signature block. + * Note that if Pm is used to salt a hash of the signed data, this must + * function must be called prior to hashing. + */ +feeReturn feeSigParse(const unsigned char *sigData, + size_t sigDataLen, + feeSig *sig) // RETURNED +{ + sigInst *sinst = NULL; + feeReturn frtn; + #if !CRYPTKIT_DER_ENABLE + int version; + int magic; + int minVersion; + int rtn; + #endif + + sinst = sinstAlloc(); + #if CRYPTKIT_DER_ENABLE + frtn = feeDERDecodeElGamalSignature(sigData, sigDataLen, &sinst->u, &sinst->PmX); + if(frtn) { + goto abort; + } + #else + rtn = byteRepToSig(sigData, + sigDataLen, + FEE_SIG_VERSION, + &magic, + &version, + &minVersion, + &sinst->u, + &sinst->PmX); + if(rtn == 0) { + frtn = FR_BadSignatureFormat; + goto abort; + } + switch(magic) { + case FEE_ECDSA_MAGIC: + frtn = FR_WrongSignatureType; // ECDSA! + goto abort; + case FEE_SIG_MAGIC: + break; // proceed + default: + frtn = FR_BadSignatureFormat; + goto abort; + } + #endif /* CRYPTKIT_DER_ENABLE */ + + #if SIG_DEBUG + if(sigDebug) { + printf("sigParse: \n"); + printf("u: "); + printGiant(sinst->u); + } + #endif // SIG_DEBUG + + *sig = sinst; + return FR_Success; + +abort: + if(sinst) { + feeSigFree(sinst); + } + return frtn; +} + +/* + * Verify signature, obtained via feeSigParse, for specified + * data (most likely a hash result) and feePubKey. Returns non-zero if + * signature valid. + */ + +#define LOG_BAD_SIG 0 + +#if CRYPTKIT_ELL_PROJ_ENABLE + +feeReturn feeSigVerifyNoProj(feeSig sig, + const unsigned char *data, + unsigned dataLen, + feePubKey pubKey); + +static void borrowPointProj(pointProj pt, unsigned maxDigits) +{ + pt->x = borrowGiant(maxDigits); + pt->y = borrowGiant(maxDigits); + pt->z = borrowGiant(maxDigits); +} + +static void returnPointProj(pointProj pt) +{ + returnGiant(pt->x); + returnGiant(pt->y); + returnGiant(pt->z); +} + +feeReturn feeSigVerify(feeSig sig, + const unsigned char *data, + unsigned dataLen, + feePubKey pubKey) +{ + pointProjStruct Q; + giant messageGiant = NULL; + pointProjStruct scratch; + sigInst *sinst = (sigInst*) sig; + feeReturn frtn; + curveParams *cp; + key origKey; // may be plus or minus key + + if(sinst->PmX == NULL) { + dbgLog(("sigVerify without parse!\n")); + return FR_IllegalArg; + } + + cp = feePubKeyCurveParams(pubKey); + if(cp->curveType != FCT_Weierstrass) { + return feeSigVerifyNoProj(sig, data, dataLen, pubKey); + } + + borrowPointProj(&Q, cp->maxDigits); + borrowPointProj(&scratch, cp->maxDigits); + + /* + * Q := P1 + */ + gtog(cp->x1Plus, Q.x); + gtog(cp->y1Plus, Q.y); + int_to_giant(1, Q.z); + + messageGiant = giant_with_data(data, dataLen); // M(ciphertext) + + /* Q := u 'o' P1 */ + ellMulProjSimple(&Q, sinst->u, cp); + + /* scratch := theirPub */ + origKey = feePubKeyPlusCurve(pubKey); + gtog(origKey->x, scratch.x); + gtog(origKey->y, scratch.y); + int_to_giant(1, scratch.z); + + #if SIG_DEBUG + if(sigDebug) { + printf("verify origKey:\n"); + printKey(origKey); + printf("messageGiant: "); + printGiant(messageGiant); + printf("curveParams:\n"); + printCurveParams(cp); + } + #endif // SIG_DEBUG + + /* scratch := M 'o' theirPub */ + ellMulProjSimple(&scratch, messageGiant, cp); + + #if SIG_DEBUG + if(sigDebug) { + printf("signature_compare, with\n"); + printf("p0 = Q:\n"); + printGiant(Q.x); + printf("p1 = Pm:\n"); + printGiant(sinst->PmX); + printf("p2 = scratch = R:\n"); + printGiant(scratch.x); + } + #endif // SIG_DEBUG + + if(signature_compare(Q.x, sinst->PmX, scratch.x, cp)) { + + frtn = FR_InvalidSignature; + #if LOG_BAD_SIG + printf("***yup, bad sig***\n"); + #endif // LOG_BAD_SIG + } + else { + frtn = FR_Success; + } + freeGiant(messageGiant); + + returnPointProj(&Q); + returnPointProj(&scratch); + return frtn; +} + +#else /* CRYPTKIT_ELL_PROJ_ENABLE */ + +#define feeSigVerifyNoProj(s, d, l, k) feeSigVerify(s, d, l, k) + +#endif /* CRYPTKIT_ELL_PROJ_ENABLE */ + +/* + * FEE_SIG_USING_PROJ true : this is the "no Weierstrass" case + * feeSigVerifyNoProj false : this is redefined to feeSigVerify + */ +feeReturn feeSigVerifyNoProj(feeSig sig, + const unsigned char *data, + unsigned dataLen, + feePubKey pubKey) +{ + giant Q = NULL; + giant messageGiant = NULL; + giant scratch = NULL; + sigInst *sinst = (sigInst*) sig; + feeReturn frtn; + curveParams *cp; + key origKey; // may be plus or minus key + + if(sinst->PmX == NULL) { + dbgLog(("sigVerify without parse!\n")); + frtn = FR_IllegalArg; + goto out; + } + + cp = feePubKeyCurveParams(pubKey); + Q = newGiant(cp->maxDigits); + + /* + * pick a key (+/-) + * Q := P1 + */ + if(SIG_CURVE == CURVE_PLUS) { + origKey = feePubKeyPlusCurve(pubKey); + gtog(cp->x1Plus, Q); + } + else { + origKey = feePubKeyMinusCurve(pubKey); + gtog(cp->x1Minus, Q); + } + + messageGiant = giant_with_data(data, dataLen); // M(ciphertext) + + /* Q := u 'o' P1 */ + elliptic_simple(Q, sinst->u, cp); + + /* scratch := theirPub */ + scratch = newGiant(cp->maxDigits); + gtog(origKey->x, scratch); + + #if SIG_DEBUG + if(sigDebug) { + printf("verify origKey:\n"); + printKey(origKey); + printf("messageGiant: "); + printGiant(messageGiant); + printf("curveParams:\n"); + printCurveParams(cp); + } + #endif // SIG_DEBUG + + /* scratch := M 'o' theirPub */ + elliptic_simple(scratch, messageGiant, cp); + + #if SIG_DEBUG + if(sigDebug) { + printf("signature_compare, with\n"); + printf("p0 = Q:\n"); + printGiant(Q); + printf("p1 = Pm:\n"); + printGiant(sinst->PmX); + printf("p2 = scratch = R:\n"); + printGiant(scratch); + } + #endif // SIG_DEBUG + + if(signature_compare(Q, sinst->PmX, scratch, cp)) { + + frtn = FR_InvalidSignature; + #if LOG_BAD_SIG + printf("***yup, bad sig***\n"); + #endif // LOG_BAD_SIG + } + else { + frtn = FR_Success; + } +out: + if(messageGiant != NULL) { + freeGiant(messageGiant); + } + if(Q != NULL) { + freeGiant(Q); + } + if(scratch != NULL) { + freeGiant(scratch); + } + return frtn; +} + +/* + * For given key, calculate maximum signature size. + */ +feeReturn feeSigSize( + feePubKey pubKey, + unsigned *maxSigLen) +{ + /* For now, assume that u and Pm.x in the signature are + * same size as the key's associated curveParams->basePrime. + * We might have to pad this a bit.... + */ + curveParams *cp = feePubKeyCurveParams(pubKey); + + if(cp == NULL) { + return FR_BadPubKey; + } + #if CRYPTKIT_DER_ENABLE + *maxSigLen = feeSizeOfDERSig(cp->basePrime, cp->basePrime); + #else + *maxSigLen = (unsigned)lengthOfByteRepSig(cp->basePrime, cp->basePrime); + #endif + return FR_Success; +}