Security/libsecurity_cryptkit/lib/feeFEED.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  * FeeFEED.c - generic, portable FEED encryption object, expanionless version
  12  *
  13  * Revision History
  14  * ----------------
  15  * 10/06/98             ap
  16  *      Changed to compile with C++.
  17  * 20 Jan 1998 at Apple
  18  *      Mods for primeType == PT_GENERAL case.
  19  * 12 Jun 1997 at Apple
  20  *      Was curveOrderJustify(), is lesserX1OrderJustify()
  21  * 31 Mar 1997 at Apple
  22  *      Fixed initialRS leak
  23  *  3 Mar 1997 at Apple
  24  *      Trimmed plainBlockSize by one byte if q mod 8 = 0
  25  * 30 Jan 1997 at NeXT
  26  *      Created.
  27  */
  28
  29 /*
  30  * FIXME - a reusable init function would be nice (i.e., free up
  31  * session-dependent state and re-init it)...
  32  */
  33 #include "ckconfig.h"
  34
  35 #if     CRYPTKIT_ASYMMETRIC_ENABLE
  36
  37 #include "feeTypes.h"
  38 #include "feeFEED.h"
  39 #include "feeFEEDExp.h"
  40 #include "feePublicKey.h"
  41 #include "feePublicKeyPrivate.h"
  42 #include "elliptic.h"
  43 #include "falloc.h"
  44 #include "feeRandom.h"
  45 #include "ckutilities.h"
  46 #include "feeFunctions.h"
  47 #include "platform.h"
  48 #include "curveParams.h"
  49 #include "feeDebug.h"
  50 #include <stdlib.h>
  51 #include <stdio.h>
  52
  53 #define FEED_DEBUG      0
  54 #define BUFFER_DEBUG    0
  55 #if             BUFFER_DEBUG
  56 #define bprintf(s)      printf s
  57 #else
  58 #define bprintf(s)
  59 #endif
  60
  61 /*
  62  * Minimum combined size of random r and s, in bytes. For small q sizes,
  63  * r and s may be even smaller, but we never truncate them to smaller than
  64  * this.
  65  * This must be kept in sync with constant of same name in FEED.java.
  66  */
  67 #define RS_MIN_SIZE     16
  68
  69 /*
  70  * Private data.
  71  */
  72 typedef struct {
  73         curveParams             *cp;
  74
  75         /*
  76          * the clues are initially (r * ourPriv * theirPub(+/-)).
  77          */
  78         giant                   cluePlus;
  79         giant                   clueMinus;
  80
  81         /*
  82          * sPlus and sMinus are based on the random s generated at encrypt
  83          * time. Values are s * x1{Plus,Minus}.
  84          */
  85         giant                   sPlus;
  86         giant                   sMinus;
  87         giant                   r;                                      /* random, generated at encrypt time */
  88         unsigned                plainBlockSize;         /* plaintext block size */
  89         unsigned                cipherBlockSize;        /* ciphertext block size */
  90         unsigned char   *initialRS;                     /* initial random R,S as bytes */
  91         unsigned                initialRSSize;          /* in bytes */
  92         feeFEEDExp              feedExp;                        /* for encr/decr r+s params */
  93
  94         /*
  95          * The first few blocks of ciphertext in a stream are the 2:1-FEED
  96          * encrypted r and s parameters. While decrypting, we stash incoming
  97          * ciphertext in rsCtext until we get enough ciphertext to decrypt
  98          * initialRS. RsBlockCount keeps a running count of the
  99          * cipherBlocks received. When rsBlockCount == rsSizeCipherBlocks, we
 100          * FEEDExp-decrypt rsCtext to get r and s (actually, to get
 101          * initialRS; r and s are extraced later in initFromRS()).
 102          *
 103          * During encrypt, if rsBlockCount is zero, the first thing we send as
 104          * ciphertext is the FEED-encrypted initialRS.
 105          */
 106         unsigned char   *rsCtext;                       /* buffer for encrypted initialRS */
 107         unsigned                rsBlockCount;           /* running total of incoming rs
 108                                                                                  *   cipherblocks */
 109
 110         int                     forEncrypt;                     /* added for feeFEED*TextSize() */
 111
 112         /*
 113          * These are calculated at init time - for encrypt and
 114          * decrypt - as an optimization.
 115          */
 116         unsigned                rsCtextSize;            /* number of meaningful bytes in
 117                                                                                  *   rsCtext */
 118         unsigned                rsSizeCipherBlocks;     /* # of our cipherblocks holding
 119                                                                                  *   rsCtext */
 120
 121         /*
 122          * temporary variables used for encrypt/decrypt. The values in these
 123          * are not needed to be kept from block to block; we just
 124          * alloc them once per lifetime of a feeFEED object as an optimization.
 125          */
 126         giant                   xp;                                     /* plaintext */
 127         giant                   xm;                                     /* ciphertext */
 128         giant                   tmp1;                           /* scratch */
 129         giant                   tmp2;                           /* scratch */
 130 } feedInst;
 131
 132 /*
 133  * "zero residue" indicator.
 134  */
 135 #define RESID_ZERO      0xff
 136
 137 /*
 138  * cons up:
 139  *      cluePlus(0)
 140  *      clueMinus(0)
 141  *      sPlus
 142  *      sMinus
 143  *      r
 144  * Assumes:
 145  *      cluePlus = clueMinus = ourPriv * theirPub
 146  *      initialRS
 147  *      initialRSSize
 148  *      cp
 149  *
 150  * Called at feeFEEDNewWithPubKey while encrypting, or upon decrypting
 151  * first block of data.
 152  */
 153 static feeReturn initFromRS(feedInst *finst)
 154 {
 155         giant s;
 156         unsigned rSize = finst->initialRSSize / 2;
 157
 158         #if     FEED_DEBUG
 159         if((finst->initialRS == NULL) ||
 160            (finst->cp == NULL) ||
 161            (finst->cluePlus == NULL) ||
 162            (finst->clueMinus == NULL) ||
 163            (finst->initialRSSize == 0)) {
 164                 dbgLog(("initFromRS: resource shortage\n"));
 165                 return FR_Internal;
 166         }
 167         #endif  // FEED_DEBUG
 168
 169         finst->r = giant_with_data(finst->initialRS, rSize);
 170         s = giant_with_data(finst->initialRS+rSize, rSize);
 171
 172         #if     FEED_DEBUG
 173         if(isZero(finst->r)) {
 174                 printf("initFromRS: r = 0! initialRSSize = %d; encr = %s\n",
 175                         finst->initialRSSize,
 176                         (finst->rsCtext == NULL) ? "TRUE" : "FALSE");
 177         }
 178         if(isZero(s)) {
 179                 printf("initFromRS: s = 0! initialRSSize = %d; encr = %s\n",
 180                         finst->initialRSSize,
 181                         (finst->rsCtext == NULL) ? "TRUE" : "FALSE");
 182         }
 183         #endif  // FEE_DEBUG
 184         /*
 185          * Justify r and s to be in [2, minimumX1Order].
 186          */
 187         lesserX1OrderJustify(finst->r, finst->cp);
 188         lesserX1OrderJustify(s, finst->cp);
 189
 190         /*
 191          * sPlus  = s * x1Plus
 192          * sMinus = s * x1Minus
 193          */
 194         finst->sPlus = newGiant(finst->cp->maxDigits);
 195         finst->sMinus = newGiant(finst->cp->maxDigits);
 196         gtog(finst->cp->x1Plus, finst->sPlus);
 197         elliptic_simple(finst->sPlus, s, finst->cp);
 198         gtog(finst->cp->x1Minus, finst->sMinus);
 199         elliptic_simple(finst->sMinus, s, finst->cp);
 200
 201         /*
 202          * And finally, the initial clues. They are currently set to
 203          * ourPriv * theirPub.
 204          */
 205         #if     FEED_DEBUG
 206         printf("cluePlus : "); printGiant(finst->cluePlus);
 207         printf("clueMinus: "); printGiant(finst->clueMinus);
 208         #endif  // FEED_EEBUG
 209
 210         elliptic_simple(finst->cluePlus, finst->r, finst->cp);
 211         elliptic_simple(finst->clueMinus, finst->r, finst->cp);
 212
 213         #if     FEED_DEBUG
 214         printf("r        : "); printGiant(finst->r);
 215         printf("s        : "); printGiant(s);
 216         printf("sPlus    : "); printGiant(finst->sPlus);
 217         printf("sMinus   : "); printGiant(finst->sMinus);
 218         printf("cluePlus : "); printGiant(finst->cluePlus);
 219         printf("clueMinus: "); printGiant(finst->clueMinus);
 220         #endif  // FEED_DEBUG
 221
 222         freeGiant(s);
 223         return FR_Success;
 224 }
 225
 226 /*
 227  * Alloc and init a feeFEED object associated with specified public and
 228  * private keys.
 229  */
 230 feeFEED feeFEEDNewWithPubKey(feePubKey myPrivKey,
 231         feePubKey theirPubKey,
 232         int forEncrypt,                 // 0 ==> decrypt   1 ==> encrypt
 233         feeRandFcn randFcn,             // optional
 234         void *randRef)
 235 {
 236         feedInst                *finst;
 237         giant                   privGiant;
 238         key                             k;
 239         unsigned                expPlainSize;
 240         unsigned                expCipherSize;
 241         unsigned                expBlocks;
 242
 243         if(!curveParamsEquivalent(feePubKeyCurveParams(theirPubKey),
 244                     feePubKeyCurveParams(myPrivKey))) {
 245                 dbgLog(("feeFEEDNewWithPubKey: Incompatible Keys\n"));
 246                 return NULL;
 247         }
 248         finst = (feedInst*) fmalloc(sizeof(feedInst));
 249         bzero(finst, sizeof(feedInst));
 250         finst->forEncrypt = forEncrypt;
 251         finst->cp = curveParamsCopy(feePubKeyCurveParams(theirPubKey));
 252         finst->rsBlockCount = 0;
 253         finst->xp = newGiant(finst->cp->maxDigits);
 254         finst->xm = newGiant(finst->cp->maxDigits);
 255         finst->tmp1 = newGiant(finst->cp->maxDigits);
 256         if(forEncrypt) {
 257             finst->tmp2 = newGiant(finst->cp->maxDigits);
 258         }
 259
 260         /*
 261          * cluePlus  = ourPriv * theirPub+
 262          * clueMinus = ourPriv * theirPub-
 263          */
 264         finst->cluePlus  = newGiant(finst->cp->maxDigits);
 265         finst->clueMinus = newGiant(finst->cp->maxDigits);
 266         privGiant = feePubKeyPrivData(myPrivKey);
 267         if(privGiant == NULL) {
 268                 dbgLog(("feeFEEDNewWithPubKey: no private key\n"));
 269                 goto abort;
 270         }
 271         k = feePubKeyPlusCurve(theirPubKey);
 272         gtog(k->x, finst->cluePlus);                    // cluePlus = theirPub+
 273         elliptic_simple(finst->cluePlus, privGiant, finst->cp);
 274         k = feePubKeyMinusCurve(theirPubKey);
 275         gtog(k->x, finst->clueMinus);                   // theirPub-
 276         elliptic_simple(finst->clueMinus, privGiant, finst->cp);
 277
 278         /*
 279          * Set up block sizes.
 280          */
 281         if(finst->cp->primeType == FPT_General) {
 282             unsigned blen = bitlen(finst->cp->basePrime);
 283
 284             finst->plainBlockSize = blen / 8;
 285             if((blen & 0x7) == 0) {
 286                 /*
 287                  * round down some more...
 288                  */
 289                 finst->plainBlockSize--;
 290             }
 291         }
 292         else {
 293             finst->plainBlockSize = finst->cp->q / 8;
 294             if(((finst->cp->q & 0x7) == 0) && (finst->cp->k > 0)) {
 295                 /*
 296                  * Special case, with q mod 8 == 0. Here we have to
 297                  * trim back the plainBlockSize by one byte.
 298                  */
 299                 finst->plainBlockSize--;
 300             }
 301         }
 302         finst->cipherBlockSize = finst->cp->minBytes + 1;
 303
 304         /*
 305          * the size of initialRS is subject to tweaking - if we make it
 306          * not a multiple of plainBlockSize, we save one FEEDExp cipherBlock
 307          * in our ciphertext.
 308          */
 309         finst->initialRSSize = finst->plainBlockSize * 2;
 310         if(finst->initialRSSize > RS_MIN_SIZE) {
 311             unsigned minPlainBlocks;
 312             unsigned maxSize;
 313
 314             /*
 315              * How many plainblocks to hold RS_MIN_SIZE?
 316              */
 317             minPlainBlocks = (RS_MIN_SIZE + finst->plainBlockSize - 1) /
 318                 finst->plainBlockSize;
 319
 320             /*
 321              * Max size = that many plainblocks, less 2 bytes (to avoid
 322              * extra residue block).
 323              */
 324             maxSize = minPlainBlocks * finst->plainBlockSize - 2;
 325
 326             /*
 327              * But don't bother with more than 2 plainblocks worth
 328              */
 329             if(finst->initialRSSize > maxSize) {
 330                 finst->initialRSSize = maxSize;
 331             }
 332         }
 333         /* else leave it alone, that's small enough */
 334
 335         if(forEncrypt) {
 336                 feeRand frand = NULL;
 337
 338                 /*
 339                  * Encrypt-capable FEEDExp object
 340                  */
 341                 finst->feedExp = feeFEEDExpNewWithPubKey(theirPubKey,
 342                         randFcn,
 343                         randRef);
 344                 if(finst->feedExp == NULL) {
 345                         goto abort;
 346                 }
 347
 348                 /*
 349                  * Generate initial r and s data.
 350                  */
 351                 finst->initialRS = (unsigned char*) fmalloc(finst->initialRSSize);
 352                 if(randFcn != NULL) {
 353                         randFcn(randRef, finst->initialRS, finst->initialRSSize);
 354                 }
 355                 else {
 356                         frand = feeRandAlloc();
 357                         feeRandBytes(frand, finst->initialRS, finst->initialRSSize);
 358                         feeRandFree(frand);
 359                 }
 360                 if(initFromRS(finst)) {
 361                         goto abort;
 362                 }
 363         }
 364         else {
 365                 /*
 366                  * Decrypt-capable FEEDExp object
 367                  */
 368                 finst->feedExp = feeFEEDExpNewWithPubKey(myPrivKey,
 369                         randFcn,
 370                         randRef);
 371                 if(finst->feedExp == NULL) {
 372                         goto abort;
 373                 }
 374
 375         }
 376
 377         /*
 378          * Figure out how many of our cipherblocks it takes to hold
 379          * a FEEDExp-encrypted initialRS. If initialRSSize is an exact
 380          * multiple of expPlainSize, we get an additional feedExp
 381          * residue block.
 382          */
 383         expPlainSize = feeFEEDExpPlainBlockSize(finst->feedExp);
 384         expCipherSize = feeFEEDExpCipherBlockSize(finst->feedExp);
 385         expBlocks = (finst->initialRSSize + expPlainSize - 1) /
 386                 expPlainSize;
 387         if((finst->initialRSSize % expPlainSize) == 0) {
 388                 expBlocks++;
 389         }
 390
 391         /*
 392          * Total meaningful bytes of encrypted initialRS
 393          */
 394         finst->rsCtextSize = expBlocks * expCipherSize;
 395
 396         /*
 397          * Number of our cipherblocks it takes to hold rsCtextSize
 398          */
 399         finst->rsSizeCipherBlocks = (finst->rsCtextSize +
 400                 finst->cipherBlockSize - 1) / finst->cipherBlockSize;
 401         if(!forEncrypt) {
 402             finst->rsCtext = (unsigned char*) fmalloc(finst->rsSizeCipherBlocks *
 403                 finst->cipherBlockSize);
 404         }
 405
 406         /*
 407          * Sanity check...
 408          */
 409         #if     FEED_DEBUG
 410         {
 411             unsigned fexpBlockSize = feeFEEDExpCipherBlockSize(finst->feedExp);
 412
 413             /*
 414              * FEEDExp has one more giant in ciphertext, plaintext is
 415              * same size
 416              */
 417             if((finst->cipherBlockSize + finst->cp->minBytes) !=
 418                         fexpBlockSize) {
 419                 dbgLog(("feeFEEDNewWithPubKey: FEEDExp CBlock Size "
 420                         "screwup\n"));
 421                 goto abort;
 422             }
 423             fexpBlockSize = feeFEEDExpPlainBlockSize(finst->feedExp);
 424             if(fexpBlockSize != finst->plainBlockSize) {
 425                 dbgLog(("feeFEEDNewWithPubKey: FEEDExp PBlock Size "
 426                         "screwup\n"));
 427                 goto abort;
 428             }
 429         }
 430         #endif  // FEED_DEBUG
 431
 432         return finst;
 433
 434 abort:
 435         feeFEEDFree(finst);
 436         return NULL;
 437 }
 438
 439 void feeFEEDFree(feeFEED feed)
 440 {
 441         feedInst *finst = (feedInst*) feed;
 442
 443         if(finst->cp) {
 444                 freeCurveParams(finst->cp);
 445         }
 446         if(finst->initialRS) {
 447                 ffree(finst->initialRS);
 448         }
 449         if(finst->cluePlus) {
 450                 freeGiant(finst->cluePlus);
 451         }
 452         if(finst->clueMinus) {
 453                 freeGiant(finst->clueMinus);
 454         }
 455         if(finst->sPlus) {
 456                 freeGiant(finst->sPlus);
 457         }
 458         if(finst->sMinus) {
 459                 freeGiant(finst->sMinus);
 460         }
 461         if(finst->r) {
 462                 freeGiant(finst->r);
 463         }
 464         if(finst->feedExp) {
 465                 feeFEEDExpFree(finst->feedExp);
 466         }
 467         if(finst->rsCtext) {
 468                 ffree(finst->rsCtext);
 469         }
 470         if(finst->xp) {
 471                 freeGiant(finst->xp);
 472         }
 473         if(finst->xm) {
 474                 freeGiant(finst->xm);
 475         }
 476         if(finst->tmp1) {
 477                 freeGiant(finst->tmp1);
 478         }
 479         if(finst->tmp2) {
 480                 freeGiant(finst->tmp2);
 481         }
 482         ffree(finst);
 483 }
 484
 485 unsigned feeFEEDPlainBlockSize(feeFEED feed)
 486 {
 487         feedInst *finst = (feedInst *) feed;
 488
 489         return finst->plainBlockSize;
 490 }
 491
 492 unsigned feeFEEDCipherBlockSize(feeFEED feed)
 493 {
 494         feedInst *finst = (feedInst *) feed;
 495
 496         return finst->cipherBlockSize;
 497 }
 498
 499 /*
 500  * Calculate size of buffer currently needed to encrypt one block of
 501  * plaintext. Also used to calculate required input during decrypt
 502  * to get any output.
 503  */
 504 unsigned feeFEEDCipherBufSize(feeFEED feed,
 505          int finalBlock)
 506 {
 507         feedInst *finst = (feedInst *) feed;
 508         unsigned blocks = 1;                    // always at least one block of ciphertext
 509
 510         if(finst->rsBlockCount == 0) {
 511                 /* haven't sent/seen encrypted RS yet */
 512                 blocks += finst->rsSizeCipherBlocks;
 513         }
 514
 515         if(finalBlock) {
 516                 /* only needed if ptext is aligned, but tell caller to malloc */
 517                 blocks++;
 518         }
 519         bprintf(("$$$ feeFEEDCipherBufSize( %s, %s): rtn 0x%x\n",
 520                 finst->forEncrypt ? "encrypt" : "decrypt",
 521                 finalBlock ? " final" : "!final",
 522                 blocks * finst->cipherBlockSize));
 523         return blocks * finst->cipherBlockSize;
 524 }
 525
 526 /*
 527  * Return the size of ciphertext currently needed to encrypt specified
 528  * size of plaintext. Also can be used to calculate size of ciphertext
 529  * which can be decrypted into specified size of plaintext.
 530  */
 531 unsigned feeFEEDCipherTextSize(feeFEED feed,
 532         unsigned        plainTextSize,
 533         int             finalBlock)
 534 {
 535         feedInst *finst = (feedInst *) feed;
 536
 537         /* how many blocks of plaintext? */
 538         unsigned blocks = (plainTextSize + finst->plainBlockSize - 1) /
 539                 finst->plainBlockSize;
 540
 541         if(finst->forEncrypt) {
 542                 /* have we generated RS? */
 543                 if(finst->rsBlockCount == 0) {
 544                         /* haven't sent encrypted RS yet */
 545                         blocks += finst->rsSizeCipherBlocks;
 546                 }
 547
 548                 /* final? residue? */
 549                 if(finalBlock) {
 550                         if((plainTextSize % finst->plainBlockSize) == 0) {
 551                                 blocks++;
 552                         }
 553                 }
 554         }       /* encrypting */
 555         else {
 556                 /*
 557                  * Decrypting - how much ciphertext can we decrypt safely into
 558                  * specified plaintext? Add in RS if we haven't seen it all
 559                  * yet.
 560                  */
 561                 #if BUFFER_DEBUG
 562                 if(finst->rsBlockCount > finst->rsSizeCipherBlocks) {
 563                         printf("******HEY! rsBlockCount overflow! (blockCount %d rsSize %d)\n",
 564                                 finst->rsBlockCount, finst->rsSizeCipherBlocks);
 565                 }
 566                 #endif
 567                 blocks += (finst->rsSizeCipherBlocks - finst->rsBlockCount);
 568         }
 569         bprintf(("$$$ feeFEEDCipherTextSize(%s, %s, 0x%x): rtn 0x%x\n",
 570                 finst->forEncrypt ? "encrypt" : "decrypt",
 571                 finalBlock ? " final" : "!final",
 572                 plainTextSize, blocks * finst->cipherBlockSize));
 573         return blocks * finst->cipherBlockSize;
 574 }
 575
 576 /*
 577  * Return the size of plaintext currently needed to decrypt specified size
 578  * of ciphertext. Also can be used to calculate size of plaintext
 579  * which can be encrypted into specified size of ciphertext.
 580  */
 581 unsigned feeFEEDPlainTextSize(feeFEED feed,
 582         unsigned        cipherTextSize,
 583         int             finalBlock)                     // ignored if !forEncrypt
 584 {
 585         feedInst *finst = (feedInst *) feed;
 586
 587         /* start with basic cipher block count */
 588         unsigned cipherBlocks = (cipherTextSize + finst->cipherBlockSize - 1) /
 589                 finst->cipherBlockSize;
 590
 591         /* where are we in the RS stream? */
 592         unsigned rsBlocksToGo = finst->rsSizeCipherBlocks - finst->rsBlockCount;
 593         if(finst->forEncrypt) {
 594                 /*
 595                  * Encrypting, seeking plaintext size we can encrypt given
 596                  * a specified size of ciphertext.
 597                  */
 598                 if(rsBlocksToGo >= cipherBlocks) {
 599                         /* no room! next encrypt would overflow ctext buffer! */
 600                         return 0;
 601                 }
 602                 cipherBlocks -= rsBlocksToGo;
 603
 604                 /* another constraint - residue */
 605                 if(finalBlock) {
 606                         if(cipherBlocks) {
 607                                 /* skip if already zero... */
 608                                 cipherBlocks--;
 609                         }
 610                 }
 611         }       /* encrypting */
 612         else {
 613                 /* decrypting */
 614                 if(rsBlocksToGo >= cipherBlocks) {
 615                         /* still processing RS, no plaintext will be generated. Play it real
 616                          * safe and just tell caller one block. */
 617                         cipherBlocks = 1;
 618                 }
 619                 else {
 620                         /* diminish by size of RS to be gobbled with no output */
 621                         cipherBlocks -= rsBlocksToGo;
 622                 }
 623         }
 624         bprintf(("$$$ feeFEEDPlainTextSize( %s, %s, 0x%x): rtn 0x%x\n",
 625                 finst->forEncrypt ? "encrypt" : "decrypt",
 626                 finalBlock ? " final" : "!final",
 627                 cipherTextSize, cipherBlocks * finst->plainBlockSize));
 628         return cipherBlocks * finst->plainBlockSize;
 629 }
 630
 631 /*
 632  * Bits in last byte of cipherblock
 633  */
 634 #define CLUE_BIT                0x01    /* 1 ==> plus curve */
 635 #define CLUE_PLUS               0x01
 636 #define CLUE_MINUS              0x00
 637 #define PARITY_BIT              0x02    /* 1 ==> plus 's' arg to elliptic_add() */
 638 #define PARITY_PLUS             0x02
 639 #define PARITY_MINUS    0x00
 640
 641 /*
 642  * Encrypt a block or less of data. Caller malloc's cipherText.
 643  * Generates up to feeFEEDCipherBufSize() bytes of ciphertext.
 644  */
 645 feeReturn feeFEEDEncryptBlock(feeFEED feed,
 646         const unsigned char *plainText,
 647         unsigned plainTextLen,
 648         unsigned char *cipherText,
 649         unsigned *cipherTextLen,                // RETURNED
 650         int finalBlock)
 651 {
 652         feedInst                *finst = (feedInst *) feed;
 653         unsigned                ctextLen = 0;
 654         feeReturn               frtn = FR_Success;
 655         int                             whichCurve;
 656         giant                   thisClue;               // not alloc'd or freed
 657         giant                   thisS;                  // ditto
 658         unsigned char   clueByte;
 659
 660         if(plainTextLen > finst->plainBlockSize) {
 661                 return FR_IllegalArg;
 662         }
 663         if((plainTextLen < finst->plainBlockSize) && !finalBlock) {
 664                 return FR_IllegalArg;
 665         }
 666         if(finst->initialRS == NULL) {
 667                 /*
 668                  * Init'd for decrypt?
 669                  */
 670                 return FR_IllegalArg;
 671         }
 672
 673         /*
 674          * First block - encrypt initialRS via FEEDExp
 675          */
 676         if(finst->rsBlockCount == 0) {
 677             unsigned char *thisCtext;   // malloc's by FEEDExp
 678             unsigned padLen;
 679
 680             if(finst->initialRS == NULL) {
 681                 /*
 682                  * init'd for decrypt or reused
 683                  */
 684                 dbgLog(("feeFEEDEncryptBlock: NULL initialRS!\n"));
 685                 return FR_IllegalArg;
 686             }
 687
 688             frtn = feeFEEDExpEncrypt(finst->feedExp,
 689                     finst->initialRS,
 690                     finst->initialRSSize,
 691                     &thisCtext,
 692                     &ctextLen);
 693             if(frtn) {
 694                     /*
 695                      * Should never happen...
 696                      */
 697                     dbgLog(("feeFEEDEncryptBlock: error writing encrypted"
 698                             " initialRS (%s)\n", feeReturnString(frtn)));
 699                     return FR_Internal;
 700             }
 701             bcopy(thisCtext, cipherText, ctextLen);
 702             cipherText += ctextLen;
 703             ffree(thisCtext);
 704
 705             finst->rsBlockCount = finst->rsSizeCipherBlocks;
 706             padLen = finst->cipherBlockSize -
 707                 (ctextLen % finst->cipherBlockSize);    // zeros to write
 708
 709             #if         0       /* FEED_DEBUG */
 710
 711             /*
 712              * Hard-coded assumptions and tests about initRSSize...
 713              * Currently we assume that initRSSize % expBlockSize = 0
 714              */
 715             if((ctextLen / finst->cipherBlockSize) != 5) {
 716                 dbgLog(("feeFEEDEncryptBlock: cipherblock size screwup (1)\n"));
 717                 return FR_Internal;
 718             }
 719             if(padLen != 3) {
 720                 dbgLog(("feeFEEDEncryptBlock: cipherblock size screwup (2)\n"));
 721                 return FR_Internal;
 722             }
 723             #endif      // FEED_DEBUG
 724
 725             /*
 726              * pad to multiple of (our) cipherblock size.
 727              */
 728             while(padLen) {
 729                 *cipherText++ = 0;
 730                 ctextLen++;
 731                 padLen--;
 732             }
 733         }
 734
 735         /*
 736          * plaintext to giant xp
 737          */
 738         if(finalBlock) {
 739                 unsigned char *ptext = (unsigned char*) fmalloc(finst->plainBlockSize);
 740                 bzero(ptext, finst->plainBlockSize);
 741                 if(plainTextLen) {
 742                         /*
 743                          * skip for empty block with resid length 0
 744                          */
 745                         bcopy(plainText, ptext, plainTextLen);
 746                 }
 747                 if(plainTextLen < finst->plainBlockSize) {
 748                     if(plainTextLen == 0) {
 749                         /*
 750                          * Special case - resid block with no actual plaintext.
 751                          * Can't actually write zero here; it screws up
 752                          * deserializing the giant during decrypt
 753                          */
 754                         ptext[finst->plainBlockSize - 1] = RESID_ZERO;
 755                                 bprintf(("=== FEED encrypt: RESID_ZERO\n"));
 756                     }
 757                     else {
 758                                 ptext[finst->plainBlockSize - 1] = plainTextLen;
 759                                 bprintf(("=== FEED encrypt: resid len 0x%x\n", plainTextLen));
 760                     }
 761                 }
 762                 /*
 763                  * else handle evenly aligned case (i.e., finalBlock true
 764                  * and (plainTextLen ==  plainBlockSize)) below...
 765                  */
 766                 deserializeGiant(ptext, finst->xp, finst->plainBlockSize);
 767                 ffree(ptext);
 768         }
 769         else {
 770                 deserializeGiant(plainText, finst->xp, plainTextLen);
 771         }
 772
 773         /*
 774          * encrypt xp
 775          *     xm = xp + clue(+/-)
 776          * determine parity needed to restore xp
 777          *     parity = ((xm + clue(+/-) == xp) ? 1 : -1
 778          * and adjust clue
 779          *     clue[n+1] = r * clue[n] + (s * P1)
 780          */
 781         whichCurve = which_curve(finst->xp, finst->cp);
 782         if(whichCurve == CURVE_PLUS) {
 783                 thisClue = finst->cluePlus;
 784                 thisS    = finst->sPlus;
 785                 clueByte = CLUE_PLUS;
 786         }
 787         else {
 788                 thisClue = finst->clueMinus;
 789                 thisS    = finst->sMinus;
 790                 clueByte = CLUE_MINUS;
 791         }
 792         // calculate xm
 793         elliptic_add(thisClue, finst->xp, finst->xm, finst->cp, SIGN_PLUS);
 794         // save xm + clue in tmp1
 795         elliptic_add(finst->xm, thisClue, finst->tmp1, finst->cp, SIGN_PLUS);
 796         // Adjust clue
 797         elliptic_simple(thisClue, finst->r, finst->cp);
 798         gtog(thisClue, finst->tmp2);
 799         elliptic_add(finst->tmp2, thisS, thisClue, finst->cp, SIGN_PLUS);
 800
 801         /*
 802          * Calculate parity
 803          */
 804         if(gcompg(finst->tmp1, finst->xp) == 0) {
 805                 clueByte |= PARITY_PLUS;
 806         }
 807
 808         /*
 809          * Ciphertext = (xm, clueByte)
 810          */
 811         serializeGiant(finst->xm, cipherText, finst->cp->minBytes);
 812         cipherText += finst->cp->minBytes;
 813         ctextLen += finst->cp->minBytes;
 814         *cipherText++ = clueByte;
 815         ctextLen++;
 816
 817         #if     FEED_DEBUG
 818         printf("encrypt  clue %d\n", clueByte);
 819         printf("  xp : "); printGiant(finst->xp);
 820         printf("  xm : "); printGiant(finst->xm);
 821         printf("  cluePlus  :"); printGiant(finst->cluePlus);
 822         printf("  clueMinus :"); printGiant(finst->clueMinus);
 823         #endif  // FEED_DEBUG
 824
 825         if(finalBlock && (plainTextLen == finst->plainBlockSize)) {
 826                /*
 827                 * Special case: finalBlock true, plainTextLen == blockSize.
 828                 * In this case we generate one more block of ciphertext,
 829                 * with a resid length of zero.
 830                 */
 831                 unsigned moreCipher;                    // additional cipherLen
 832
 833                 frtn = feeFEEDEncryptBlock(feed,
 834                         NULL,                           // plainText not used
 835                         0,                              // resid
 836                         cipherText,                     // append...
 837                         &moreCipher,
 838                         1);
 839                 if(frtn == FR_Success) {
 840                         ctextLen += moreCipher;
 841                 }
 842         }
 843         bprintf(("=== FEED encryptBlock ptextLen 0x%x  ctextLen 0x%x\n",
 844                 plainTextLen, ctextLen));
 845
 846         *cipherTextLen = ctextLen;
 847         return frtn;
 848 }
 849
 850 /*
 851  * Decrypt (exactly) a block of data. Caller malloc's plainText. Always
 852  * generates feeFEEDPlainBlockSize of plaintext, unless finalBlock is
 853  * non-zero (in which case feeFEEDPlainBlockSize or less bytes of plainText are
 854  * generated).
 855  */
 856 feeReturn feeFEEDDecryptBlock(feeFEED feed,
 857         const unsigned char *cipherText,
 858         unsigned cipherTextLen,
 859         unsigned char *plainText,
 860         unsigned *plainTextLen,                 // RETURNED
 861         int finalBlock)
 862 {
 863         feedInst        *finst = (feedInst *) feed;
 864         feeReturn       frtn = FR_Success;
 865         unsigned char   clueByte;
 866         giant           thisClue;               // not alloc'd
 867         giant           thisS;                  // ditto
 868         int             parity;
 869
 870         if(finst->rsCtext == NULL) {
 871                 /*
 872                  * Init'd for encrypt?
 873                  */
 874                 return FR_IllegalArg;
 875         }
 876         if(cipherTextLen != finst->cipherBlockSize) {
 877                 dbgLog(("feeFEEDDecryptBlock: bad cipherTextLen\n"));
 878                 return FR_IllegalArg;
 879         }
 880         if(finst->rsBlockCount < finst->rsSizeCipherBlocks) {
 881                 /*
 882                  * Processing initialRS, FEEDExp-encrypted
 883                  */
 884                 unsigned char *rsPtr = finst->rsCtext +
 885                         (finst->rsBlockCount * finst->cipherBlockSize);
 886                 unsigned feedExpCipherSize;
 887
 888                 if(finalBlock) {
 889                     dbgLog(("feeFEEDDecryptBlock: incomplete initialRS\n"));
 890                     return FR_BadCipherText;
 891                 }
 892                 bcopy(cipherText, rsPtr, finst->cipherBlockSize);
 893                 finst->rsBlockCount++;
 894                 if(finst->rsBlockCount < finst->rsSizeCipherBlocks) {
 895                     /*
 896                      * Not done with this yet...
 897                      */
 898                         bprintf(("=== FEED Decrypt: gobbled 0x%x bytes ctext, no ptext (1)\n",
 899                                 cipherTextLen));
 900                     *plainTextLen = 0;
 901                     return FR_Success;
 902                 }
 903
 904                 #if     FEED_DEBUG
 905                 if((finst->rsBlockCount * finst->cipherBlockSize) <
 906                                 finst->rsCtextSize) {
 907                     dbgLog(("feeFEEDDecryptBlock: rsCtextSize underflow!\n"));
 908                     return FR_Internal;
 909                 }
 910                 #endif  // FEED_DEBUG
 911
 912                 /*
 913                  * OK, we should have the FEEDExp ciphertext for initialRS
 914                  * in rsCtext. Note the last few bytes are extra; we don't
 915                  * pass them to FEEDExp.
 916                  */
 917                 feedExpCipherSize = feeFEEDCipherBlockSize(finst->feedExp);
 918                 frtn = feeFEEDExpDecrypt(finst->feedExp,
 919                         finst->rsCtext,
 920                         finst->rsCtextSize,
 921                         &finst->initialRS,
 922                         &finst->initialRSSize);
 923                 if(frtn) {
 924                     dbgLog(("feeFEEDDecryptBlock: error decrypting "
 925                         "initialRS (%s)\n", feeReturnString(frtn)));
 926                     return FR_BadCipherText;
 927                 }
 928
 929                 /*
 930                  * we already know how long this should be...
 931                  */
 932                 if(finst->initialRSSize != finst->initialRSSize) {
 933                     dbgLog(("feeFEEDDecryptBlock: initialRS sync error\n"));
 934                     return FR_BadCipherText;
 935                 }
 936
 937                 /*
 938                  * Set up clues
 939                  */
 940                 if(initFromRS(finst)) {
 941                     dbgLog(("feeFEEDDecryptBlock: bad initialRS\n"));
 942                     return FR_BadCipherText;
 943                 }
 944                 else {
 945                     /*
 946                      * Normal completion of last cipherblock containing
 947                      * initialRS.
 948                      */
 949                         bprintf(("=== FEED Decrypt: gobbled 0x%x bytes ctext, no ptext (2)\n",
 950                                 cipherTextLen));
 951                     *plainTextLen = 0;
 952                     return FR_Success;
 953                 }
 954         }
 955
 956         /*
 957          * grab xm and clueByte from cipherText
 958          */
 959         deserializeGiant(cipherText, finst->xm, finst->cp->minBytes);
 960         cipherText += finst->cp->minBytes;
 961         clueByte = *cipherText;
 962
 963         if((clueByte & CLUE_BIT) == CLUE_PLUS) {
 964                 thisClue = finst->cluePlus;
 965                 thisS = finst->sPlus;
 966         }
 967         else {
 968                 thisClue = finst->clueMinus;
 969                 thisS = finst->sMinus;
 970         }
 971         if((clueByte & PARITY_BIT) == PARITY_PLUS) {
 972                 parity = SIGN_PLUS;
 973         }
 974         else {
 975                 parity = SIGN_MINUS;
 976         }
 977
 978         /*
 979          * recover xp
 980          *     xp = xm + clue(+/-) w/parity
 981          * adjust clue
 982          *     clue[n+1] = r * clue[n] + (s * P1)
 983          */
 984         elliptic_add(thisClue, finst->xm, finst->xp, finst->cp, parity);
 985
 986         elliptic_simple(thisClue, finst->r, finst->cp);
 987         gtog(thisClue, finst->tmp1);
 988         elliptic_add(finst->tmp1, thisS, thisClue, finst->cp, SIGN_PLUS);
 989
 990         /*
 991          * plaintext in xp
 992          */
 993         #if     FEED_DEBUG
 994         printf("decrypt  clue %d\n", clueByte);
 995         printf("  xp : "); printGiant(finst->xp);
 996         printf("  xm : "); printGiant(finst->xm);
 997         printf("  cluePlus  :"); printGiant(finst->cluePlus);
 998         printf("  clueMinus :"); printGiant(finst->clueMinus);
 999         #endif  // FEED_DEBUG
1000
1001         if(finalBlock) {
1002                 /*
1003                  * Snag data from xp in order to find out how much to move to
1004                  * *plainText
1005                  */
1006                 unsigned char *ptext = (unsigned char*) fmalloc(finst->plainBlockSize);
1007
1008                 serializeGiant(finst->xp, ptext, finst->plainBlockSize);
1009                 *plainTextLen = ptext[finst->plainBlockSize - 1];
1010                 if(*plainTextLen == RESID_ZERO) {
1011                         bprintf(("=== FEED Decrypt: RESID_ZERO\n"));
1012                         *plainTextLen = 0;
1013                 }
1014                 else if(*plainTextLen > (finst->plainBlockSize - 1)) {
1015                         dbgLog(("feeFEEDDecryptBlock: ptext overflow!\n"));
1016                         bprintf(("feeFEEDDecryptBlock: ptext overflow!\n"));
1017                         frtn = FR_BadCipherText;
1018                 }
1019                 else {
1020                         bprintf(("=== FEED Decrypt: resid len 0x%x\n", *plainTextLen));
1021                         bcopy(ptext, plainText, *plainTextLen);
1022                 }
1023                 ffree(ptext);
1024         }
1025         else {
1026                 *plainTextLen = finst->plainBlockSize;
1027                 serializeGiant(finst->xp, plainText, *plainTextLen);
1028         }
1029         bprintf(("=== FEED decryptBlock ptextLen 0x%x  ctextLen 0x%x\n",
1030                 *plainTextLen, cipherTextLen));
1031
1032         return frtn;
1033 }
1034
1035 /*
1036  * Convenience routines to encrypt & decrypt multi-block data.
1037  */
1038 feeReturn feeFEEDEncrypt(feeFEED feed,
1039         const unsigned char *plainText,
1040         unsigned plainTextLen,
1041         unsigned char **cipherText,             // malloc'd and RETURNED
1042         unsigned *cipherTextLen)                // RETURNED
1043 {
1044         const unsigned char     *ptext;                 // per block
1045         unsigned                        ptextLen;               // total to go
1046         unsigned                        thisPtextLen;           // per block
1047         unsigned char           *ctext;                 // per block
1048         unsigned                        ctextLen;               // per block
1049         unsigned char           *ctextResult;           // to return
1050         unsigned                        ctextResultLen;         // size of ctextResult
1051         unsigned char           *ctextPtr;
1052         unsigned                        ctextLenTotal;          // running total
1053         feeReturn                       frtn;
1054         int                                     finalBlock;
1055         unsigned                        numBlocks;
1056         unsigned                        plainBlockSize;
1057         #if     FEE_DEBUG
1058         unsigned                expectedCtextSize;
1059
1060         expectedCtextSize = feeFEEDCipherTextSize(feed, plainTextLen, 1);
1061         #endif
1062
1063         if(plainTextLen == 0) {
1064                 dbgLog(("feeFEEDDecrypt: NULL plainText\n"));
1065                 return FR_IllegalArg;
1066         }
1067
1068         ptext = plainText;
1069         ptextLen = plainTextLen;
1070         ctext = (unsigned char*) fmalloc(feeFEEDCipherBufSize(feed, 1));
1071         plainBlockSize = feeFEEDPlainBlockSize(feed);
1072         numBlocks = (plainTextLen + plainBlockSize - 1)/plainBlockSize;
1073
1074         /*
1075          * Calculate the worst-case size needed to hold all of the ciphertext
1076          */
1077         ctextResultLen = feeFEEDCipherTextSize(feed, plainTextLen, 1);
1078         ctextResult = (unsigned char*) fmalloc(ctextResultLen);
1079         ctextPtr = ctextResult;
1080         ctextLenTotal = 0;
1081
1082         while(1) {
1083                 if(ptextLen <= plainBlockSize) {
1084                         finalBlock = 1;
1085                         thisPtextLen = ptextLen;
1086                 }
1087                 else {
1088                         finalBlock = 0;
1089                         thisPtextLen = plainBlockSize;
1090                 }
1091                 frtn = feeFEEDEncryptBlock(feed,
1092                         ptext,
1093                         thisPtextLen,
1094                         ctext,
1095                         &ctextLen,
1096                         finalBlock);
1097                 if(frtn) {
1098                         dbgLog(("feeFEEDEncrypt: encrypt error: %s\n",
1099                                 feeReturnString(frtn)));
1100                         break;
1101                 }
1102                 if(ctextLen == 0) {
1103                         dbgLog(("feeFEEDEncrypt: null ciphertext\n"));
1104                         frtn = FR_Internal;
1105                         break;
1106                 }
1107                 bcopy(ctext, ctextPtr, ctextLen);
1108                 ctextLenTotal += ctextLen;
1109                 if(ctextLenTotal > ctextResultLen) {
1110                         dbgLog(("feeFEEDEncrypt: ciphertext overflow\n"));
1111                         frtn = FR_Internal;
1112                         break;
1113                 }
1114                 if(finalBlock) {
1115                         break;
1116                 }
1117                 ctextPtr += ctextLen;
1118                 ptext += thisPtextLen;
1119                 ptextLen -= thisPtextLen;
1120         }
1121
1122         ffree(ctext);
1123         if(frtn) {
1124                 ffree(ctextResult);
1125                 *cipherText = NULL;
1126                 *cipherTextLen = 0;
1127         }
1128         else {
1129                 *cipherText = ctextResult;
1130                 *cipherTextLen = ctextLenTotal;
1131                 #if     FEE_DEBUG
1132                 if(expectedCtextSize != ctextLenTotal) {
1133                     printf("feeFEEDEncrypt: feeFEEDCipherTextSize error!\n");
1134                     printf("ptext %d  exp ctext %d  actual ctext %d\n",
1135                         plainTextLen,
1136                         expectedCtextSize,
1137                         ctextLenTotal);
1138                 }
1139                 #endif  // FEE_DEBUG
1140         }
1141         return frtn;
1142
1143 }
1144
1145 feeReturn feeFEEDDecrypt(feeFEED feed,
1146         const unsigned char *cipherText,
1147         unsigned cipherTextLen,
1148         unsigned char **plainText,              // malloc'd and RETURNED
1149         unsigned *plainTextLen)                 // RETURNED
1150 {
1151         const unsigned char     *ctext;
1152         unsigned                ctextLen;               // total to go
1153         unsigned char           *ptext;                 // per block
1154         unsigned                ptextLen;               // per block
1155         unsigned char           *ptextResult;           // to return
1156         unsigned char           *ptextPtr;
1157         unsigned                ptextLenTotal;          // running total
1158         feeReturn               frtn = FR_Success;
1159         int                     finalBlock;
1160         unsigned                numBlocks;
1161         unsigned                plainBlockSize = feeFEEDPlainBlockSize(feed);
1162         unsigned                cipherBlockSize = feeFEEDCipherBlockSize(feed);
1163
1164         if(cipherTextLen % cipherBlockSize) {
1165                 dbgLog(("feeFEEDDecrypt: unaligned cipherText\n"));
1166                 return FR_BadCipherText;
1167         }
1168         if(cipherTextLen == 0) {
1169                 dbgLog(("feeFEEDDecrypt: NULL cipherText\n"));
1170                 return FR_BadCipherText;
1171         }
1172
1173         ptext = (unsigned char*) fmalloc(plainBlockSize);
1174         ctext = cipherText;
1175         ctextLen = cipherTextLen;
1176         numBlocks = cipherTextLen / cipherBlockSize;
1177         ptextResult = (unsigned char*) fmalloc(plainBlockSize * numBlocks);
1178         ptextPtr = ptextResult;
1179         ptextLenTotal = 0;
1180
1181         while(ctextLen) {
1182                 if(ctextLen == cipherBlockSize) {
1183                     finalBlock = 1;
1184                 }
1185                 else {
1186                     finalBlock = 0;
1187                 }
1188                 frtn = feeFEEDDecryptBlock(feed,
1189                         ctext,
1190                         cipherBlockSize,
1191                         ptext,
1192                         &ptextLen,
1193                         finalBlock);
1194                 if(frtn) {
1195                         dbgLog(("feeFEEDDecryptBlock: %s\n",
1196                                 feeReturnString(frtn)));
1197                         break;
1198                 }
1199                 if(ptextLen) {
1200                         if(ptextLen > plainBlockSize) {
1201                             dbgLog(("feeFEEDDecrypt: ptext overflow!\n"));
1202                             frtn = FR_Internal;
1203                             break;
1204                         }
1205                         bcopy(ptext, ptextPtr, ptextLen);
1206                         ptextPtr += ptextLen;
1207                         ptextLenTotal += ptextLen;
1208                 }
1209                 /*
1210                  * note ptextLen == 0 is normal termination case for
1211                  * plainTextLen % plainBlockSize == 0.
1212                  * Also expected for first 4 blocks of ciphertext;
1213                  * proceed (we break when ctextLen is exhausted).
1214                  */
1215                 ctext += cipherBlockSize;
1216                 ctextLen -= cipherBlockSize;
1217         }
1218
1219         ffree(ptext);
1220         if(frtn) {
1221                 ffree(ptextResult);
1222                 *plainText = NULL;
1223                 *plainTextLen = 0;
1224         }
1225         else {
1226                 *plainText = ptextResult;
1227                 *plainTextLen = ptextLenTotal;
1228         }
1229         return frtn;
1230
1231 }
1232
1233 #endif  /* CRYPTKIT_ASYMMETRIC_ENABLE */