OSX/libsecurity_comcryption/lib/comcryptPriv.c

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