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