libsecurity_comcryption/lib/comcryptPriv.c

   1 /*
   2         File:           comcryptPriv.c
   3
   4         Contains:       private routines for comcryption library.
   5
   6         Written by:     Doug Mitchell
   7
   8         Copyright:      (c) 1997 by Apple Computer, Inc., all rights reserved.
   9
  10         Change History (most recent first):
  11
  12                 05/28/98        dpm             Added platform-dependent ascMalloc and ascFree
  13                 12/23/97        dpm             Added keyHash(), used result to initialize
  14                                                                 nybbleDex and queue.
  15                 12/18/97        dpm             Improved queue initialization.
  16                 12/03/97        dpm             Added queue lookahead; various optimizations.
  17                 11/13/97        dpm             Created; broke out from comcryption.c
  18
  19         To Do:
  20 */
  21
  22 #include "comcryptPriv.h"
  23 #include <stdio.h>
  24 #include <string.h>
  25 #include <stdlib.h>
  26 #ifdef  macintosh
  27 #include <MacMemory.h>
  28 #endif
  29
  30 /* if NULL, use our own */
  31 comMallocExternFcn *comMallocExt = NULL;
  32 comFreeExternFcn *comFreeExt = NULL;
  33
  34 #if             COM_STATS
  35 comStats _comStats;
  36
  37 void resetComStats()
  38 {
  39         memset(&_comStats, 0, sizeof(comStats));
  40 }
  41
  42 void getComStats(comStats *stats)
  43 {
  44         *stats = _comStats;
  45 }
  46
  47 #else   /*COM_STATS*/
  48
  49 #define incrComStat(stat, num)
  50
  51 #endif  /*COM_STATS*/
  52
  53 /*
  54  * Generate a symbol permutation from the key.
  55  */
  56 void key_perm(
  57         const unsigned char *key,
  58         int                             keybytes,
  59         unsigned char           *map,
  60         unsigned char           *invmap)
  61 {
  62     int i, j, tmp, sum;
  63
  64     for(sum = 0, j = 0; j < keybytes; j++) {
  65                 sum += key[j];
  66         }
  67         for(j=0; j < 256; j++) {
  68                 map[j] = j;
  69         }
  70         for(j=0; j < 255; j++) {
  71                 i = (key[j % keybytes] + j*sum) & 0xff;
  72                 tmp = map[i];
  73                 map[i] = map[j];
  74                 map[j] = tmp;
  75         }
  76         for(j=0; j<256; j++) {
  77                 invmap[map[j]] = j;
  78         }
  79 }
  80
  81 int keybyte(
  82         const unsigned char *key,
  83         int                             keybytes,
  84         int                             index)
  85 {
  86     return((int) key[index % keybytes]);
  87 }
  88
  89 int keynybble(
  90         const unsigned char *key,
  91         int                             keybytes,
  92         int                             index)
  93 {
  94         int i = index % (2*keybytes);
  95         int j;
  96
  97     j = key[i>>1];              /* Which byte. */
  98     if(i & 1) j >>= 4;  /* Which nybble. */
  99     return(j & 0xf);
 100 }
 101
 102 /*
 103  * Hash a key array.
 104  */
 105
 106 #define HASH_SEED       3
 107 #define HASH_REDUCE     1023
 108
 109 static unsigned keyHash(const unsigned char *key, unsigned keylen)
 110 {
 111         unsigned x = HASH_SEED;  /* Any seed in [1,p-1].  Like SEED = 3. */
 112         unsigned ctr;
 113
 114         for(ctr=0; ctr<keylen; ctr++) {
 115                 x = (x * (key[ctr] + (ctr & HASH_REDUCE) + 1)) % HASH_PRIME;
 116         }
 117         return x;
 118 }
 119
 120 void mallocCodeBufs(comcryptBuf *cbuf)
 121 {
 122         /*
 123          * calculate required buffer sizes.
 124          *
 125          * Assume max required codeBuf size is the max size of ciphertext needed
 126          * to decrypt one block of plaintext.
 127          */
 128         cbuf->codeBufSize = comcryptMaxOutBufSize(NULL,
 129                 CC_BLOCK_SIZE,
 130                 CCOP_COMCRYPT,
 131                 1);
 132         cbuf->codeBuf = (unsigned char *)ascMalloc(cbuf->codeBufSize);
 133
 134         /*
 135          * max size needed for level2Buf is the MaxOutBufSize of comcrypting
 136          * a whole block of byte code. Note we assume that MaxOutBufSize(n) >= n.
 137          */
 138         cbuf->level2BufSize = comcryptMaxOutBufSize(NULL,
 139                 MAX_TOKENS,                             // one byte per token
 140                 CCOP_COMCRYPT,
 141                 1);
 142         cbuf->level2Buf = (unsigned char *)ascMalloc(cbuf->level2BufSize);
 143
 144         cbuf->queue = (queueElt *)ascMalloc(sizeof(queueElt) * QLEN);
 145
 146         #if             QUEUE_LOOKAHEAD
 147         /*
 148          * Might want to do this dynamically, though that requires the malloc
 149          * of the lookAhead buffer to be done in initCodeBufs(), not here (at
 150          * comcryptAlloc() time).
 151          *
 152          * FIXME : should do the malloc of lookAhead buffer lazily for
 153          * non-Mac platforms.
 154          */
 155         cbuf->lookAhead = (unsigned char *)ascMalloc(LOOKAHEAD_SIZE);
 156         #else   /* QUEUE_LOOKAHEAD */
 157         cbuf->lookAhead = NULL;
 158         #endif  /* QUEUE_LOOKAHEAD */
 159
 160         /*
 161          * This maybe should also be done dynamically, lazily...
 162          */
 163         cbuf->sigArray = (unsigned *)ascMalloc((MAX_TOKENS + 1) * sizeof(unsigned));
 164 }
 165
 166 void initCodeBufs(
 167         comcryptBuf *cbuf,
 168         const unsigned char *key,
 169         unsigned keyLen,
 170         unsigned char laEnable,
 171         unsigned char sigSeqEnable)
 172 {
 173         unsigned ct;
 174         unsigned qval;
 175         unsigned char khash = (unsigned char)keyHash(key, keyLen);
 176
 177         cbuf->nybbleDex = khash;
 178
 179         if(laEnable) {
 180                 memset(cbuf->lookAhead, 0, LOOKAHEAD_SIZE);
 181         }
 182
 183         laprintf(("initing queue and lookahead\n"));
 184
 185         for(ct=0; ct<QLEN; ct++) {
 186                 /*
 187                  * New queue init 23 Dec - init from khash
 188                  */
 189                 unsigned short sbyte = ct ^ khash;
 190                 qval = (sbyte << 8) | ct;
 191                 cbuf->queue[ct] = qval;
 192                 if(laEnable) {
 193                         markInQueue(cbuf, qval, 1);
 194                 }
 195         }
 196         // note cbuf->nybbleDex = khash on return...
 197
 198         cbuf->f1 = F1_DEFAULT;
 199         cbuf->f2 = F2_DEFAULT;
 200         cbuf->jmatchThresh = THRESH_2LEVEL_JMATCH_DEF;
 201         cbuf->minByteCode  = THRESH_2LEVEL_NUMBYTECODES_DEF;
 202         if(sigSeqEnable) {
 203                 initSigSequence(cbuf, key, keyLen);
 204         }
 205 }
 206
 207 void freeCodeBufs(comcryptBuf *cbuf)
 208 {
 209         if(cbuf->queue != NULL) {
 210                 ascFree(cbuf->queue);
 211         }
 212         if(cbuf->codeBuf != NULL) {
 213                 ascFree(cbuf->codeBuf);
 214         }
 215         if(cbuf->level2Buf != NULL) {
 216                 ascFree(cbuf->level2Buf);
 217         }
 218         if(cbuf->nextBuf != NULL) {
 219                 freeCodeBufs(cbuf->nextBuf);
 220                 ascFree(cbuf->nextBuf);
 221                 cbuf->nextBuf = NULL;
 222         }
 223         if(cbuf->lookAhead != NULL) {
 224                 ascFree(cbuf->lookAhead);
 225         }
 226         if(cbuf->sigArray != NULL) {
 227                 ascFree(cbuf->sigArray);
 228         }
 229 }
 230
 231 void serializeInt(
 232         unsigned i,
 233         unsigned char *buf)
 234 {
 235         buf[0] = (unsigned char)(i >> 24);
 236         buf[1] = (unsigned char)(i >> 16);
 237         buf[2] = (unsigned char)(i >> 8);
 238         buf[3] = (unsigned char)(i & 0xff);
 239 }
 240
 241 unsigned deserializeInt(unsigned char *buf)
 242 {
 243         unsigned i;
 244
 245         i  = ((unsigned)buf[0]) << 24;
 246         i |= ((unsigned)buf[1]) << 16;
 247         i |= ((unsigned)buf[2]) << 8;
 248         i |= buf[3];
 249         return i;
 250 }
 251
 252 #if             COM_PARAM_ENABLE
 253
 254 unsigned getF1(comcryptObj cobj)
 255 {
 256         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 257
 258         return cpriv->cbuf.f1;
 259 }
 260
 261 void setF1(comcryptObj cobj, unsigned f1)
 262 {
 263         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 264
 265         cpriv->cbuf.f1 = f1;
 266         if(cpriv->cbuf.nextBuf != NULL) {
 267                 cpriv->cbuf.nextBuf->f1 = f1;
 268         }
 269 }
 270
 271 unsigned getF2(comcryptObj cobj)
 272 {
 273         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 274
 275         return cpriv->cbuf.f2;
 276 }
 277
 278 void setF2(comcryptObj cobj, unsigned f2)
 279 {
 280         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 281
 282         cpriv->cbuf.f2 = f2;
 283         if(cpriv->cbuf.nextBuf != NULL) {
 284                 cpriv->cbuf.nextBuf->f2 = f2;
 285         }
 286 }
 287
 288 unsigned getJmatchThresh(comcryptObj cobj)
 289 {
 290         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 291
 292         return cpriv->cbuf.jmatchThresh;
 293 }
 294
 295 void setJmatchThresh(comcryptObj cobj, unsigned jmatchThresh)
 296 {
 297         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 298
 299         cpriv->cbuf.jmatchThresh = jmatchThresh;
 300         if(cpriv->cbuf.nextBuf != NULL) {
 301                 cpriv->cbuf.nextBuf->jmatchThresh = jmatchThresh;
 302         }
 303 }
 304
 305 unsigned getMinByteCode(comcryptObj cobj)
 306 {
 307         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 308
 309         return cpriv->cbuf.minByteCode;
 310 }
 311
 312 void setMinByteCode(comcryptObj cobj, unsigned minByteCode)
 313 {
 314         comcryptPriv *cpriv = (comcryptPriv *)cobj;
 315
 316         cpriv->cbuf.minByteCode = minByteCode;
 317         if(cpriv->cbuf.nextBuf != NULL) {
 318                 cpriv->cbuf.nextBuf->minByteCode = minByteCode;
 319         }
 320 }
 321
 322 #endif  /*COM_PARAM_ENABLE*/
 323
 324
 325 #if             COM_LA_DEBUG
 326
 327 /*
 328  * Verify integrity of lookahead w.r.t. queue.
 329  */
 330 int testLookAhead(comcryptBuf *cbuf, int i1, int i2)
 331 {
 332         unsigned i;
 333
 334         if(!cbuf->laEnable) {
 335                 return 0;
 336         }
 337         for(i=0; i<QLEN; i++) {
 338                 if(!inQueue(cbuf, cbuf->queue[i])) {
 339                         printf("aaagh, corrupted lookahead - in queue[], !inQueue()\n");
 340                         printf("i=0x%x   i1=0x%x   i2=0x%x\n",
 341                                 i, i1, i2);
 342                         printf("\n");
 343                         exit(1);
 344                 }
 345         }
 346         //return initTestLookAhead(cbuf);
 347         return 0;
 348 }
 349
 350 int initTestLookAhead(comcryptBuf *cbuf)
 351 {
 352         #if             QUEUE_LOOKAHEAD_BIT
 353
 354         unsigned codeWord = 0;
 355         unsigned char bit;
 356         unsigned short byte;
 357         unsigned char *la = cbuf->lookAhead;
 358
 359         for(byte=0; byte<LOOKAHEAD_SIZE; byte++) {
 360                 for(bit=1; bit!=0; bit<<=1) {
 361                         if(la[byte] & bit) {
 362                                 /*
 363                                  * in lookahead, make sure it's in queue[]
 364                                  */
 365                                 int i;
 366                                 int found = 0;
 367
 368                                 for(i=0; i<QLEN; i++) {
 369                                         if(cbuf->queue[i] == codeWord) {
 370                                                 found = 1;
 371                                                 break;
 372                                         }
 373                                 }
 374                                 if(!found) {
 375                                         printf("***corrupted init lookahead - in l.a., "
 376                                                 "not in queue[]\n");
 377                                         printf("codeWord 0x%x\n", codeWord);
 378                                         printf("\n");
 379                                         exit(1);
 380                                 }
 381                         }
 382                         codeWord++;
 383                 }
 384         }
 385
 386         #endif  /* QUEUE_LOOKAHEAD_BIT */
 387         return 0;
 388 }
 389
 390 #endif  /* COM_LA_DEBUG */
 391
 392 void initSigSequence(comcryptBuf *cbuf,
 393         const unsigned char *key,
 394         unsigned keyLen)
 395 {
 396     unsigned seed = IN_OFFSET;
 397         unsigned j;
 398
 399     for(j=0; j<keyLen; j++) {
 400                 seed += key[j];
 401     }
 402     seed %= HASH_PRIME;
 403     if(seed == 0) {
 404                 seed = IN_OFFSET;
 405         }
 406         cbuf->sigArray[0] = (unsigned short)seed;
 407 }
 408
 409 #if     0
 410 /*
 411  * Called once per token bit, after processing the token.
 412  */
 413 void nextSigWord(comcryptBuf *cbuf,
 414         unsigned sigDex,                        // same as tokenDex
 415         unsigned match,
 416         unsigned above)                         // jabove, keyabove
 417 {
 418         unsigned offset;
 419         unsigned short *sigArray = cbuf->sigArray;
 420
 421         #if             COM_DEBUG
 422         if(sigDex == 0) {
 423                 printf("nextSigWord underflow\n");
 424                 exit(1);
 425         }
 426         if(sigDex > MAX_TOKENS) {
 427                 printf("nextSigWord overflow\n");
 428                 exit(1);
 429         }
 430         #endif
 431
 432         if(match) {
 433                 offset = IN_OFFSET;
 434         }
 435         else {
 436                 offset = OUT_OFFSET;
 437         }
 438 #if             1
 439         sigArray[sigDex] = (sigArray[sigDex-1] * (above + offset)) % HASH_PRIME;
 440 #endif
 441 }
 442 #endif
 443
 444 /*
 445  * Obfuscate a block of ciphertext.
 446  */
 447 void sigMunge(comcryptBuf *cbuf,
 448         const unsigned char *tokenPtr,
 449         unsigned numTokens,
 450         unsigned char *byteCodePtr,
 451         unsigned char *longCodePtr)
 452 {
 453         unsigned char tokenBit = 0x01;
 454         unsigned token;
 455         unsigned short sig;
 456
 457         for(token=0; token<numTokens; token++) {
 458                 sig = cbuf->sigArray[token];
 459                 if(*tokenPtr & tokenBit) {
 460                         /* no match - munge longCode - written MSB first */
 461                         *longCodePtr++ ^= (unsigned char)(sig >> 8);
 462                         *longCodePtr++ ^= (unsigned char)sig;
 463                 }
 464                 else {
 465                         /* match - munge byteCode */
 466                         *byteCodePtr++ ^= (unsigned char)sig;
 467                 }
 468                 tokenBit <<= 1;
 469                 if(tokenBit == 0) {
 470                         tokenBit = 0x01;
 471                         tokenPtr++;
 472                 }
 473         }
 474 }
 475
 476
 477 /*
 478  * All this can be optimized and tailored to specific platforms, of course...
 479  */
 480
 481 void *ascMalloc(unsigned size)
 482 {
 483         #ifdef  macintosh
 484
 485         Handle h;
 486         OSErr err;
 487         Ptr p;
 488
 489         #endif  /* mac */
 490
 491         if(comMallocExt != NULL) {
 492                 return (comMallocExt)(size);
 493         }
 494
 495         #ifdef  macintosh
 496
 497         h = nil;
 498         err = errSecSuccess;
 499
 500         h = NewHandleSys(size);         // system heap is not paged
 501         do{
 502                 HLockHi(h);                     // will move low in system heap
 503                 err = MemError();
 504                 if( err != errSecSuccess ) break;
 505                 p = *h;
 506         }while(0);
 507         if( err != errSecSuccess ){
 508             return NULL;
 509         }
 510         return p;
 511
 512         #else   /* others...*/
 513         return malloc(size);
 514         #endif
 515 }
 516
 517 void ascFree(void *data)
 518 {
 519         #ifdef macintosh
 520         Handle h;
 521         #endif
 522
 523         if(comFreeExt != NULL) {
 524                 (comFreeExt)(data);
 525                 return;
 526         }
 527
 528         #ifdef macintosh
 529         if( data != nil ){
 530                 h = RecoverHandle((Ptr) data);
 531                 DisposeHandle(h);
 532         }
 533
 534         #else   /* others */
 535         free(data);
 536         #endif
 537 }