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