Security/libsecurity_comcryption/lib/comcryptPriv.h

   1 /*
   2  * Copyright (c) 1997,2011,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 #ifndef _COMCRYPT_PRIV_H_
  26 #define _COMCRYPT_PRIV_H_
  27
  28 #include "comcryption.h"
  29 #include "comDebug.h"
  30
  31 #ifdef __cplusplus
  32 extern "C" {
  33 #endif
  34
  35 extern comMallocExternFcn *comMallocExt;
  36 extern comFreeExternFcn *comFreeExt;
  37
  38 /*
  39  * type of element in comcryptBuf.queue[]. Making this an unsigned int gives
  40  * a slight performance improvement on the i486 platform, but it does use up
  41  * more memory.
  42  */
  43 typedef unsigned queueElt;
  44
  45 /*
  46  * Enable queue lookahead via comcryptBuf.lookAhead[]. This is currently
  47  * just the default value for comcryptBuf.laEnable.
  48  */
  49 #define QUEUE_LOOKAHEAD         1
  50
  51 /*
  52  * lookahead queue is bit array if 1, else byte array.
  53  * FIXME - this will most likely be a hard-coded 1 for Mac and
  54  * dynamically configurable for other platforms.
  55  */
  56 #define QUEUE_LOOKAHEAD_BIT     1
  57
  58 /*
  59  * Size of lookAhead buffer in bytes.
  60  */
  61 #if             QUEUE_LOOKAHEAD_BIT
  62 /*
  63  * 1 bit per potential queueElt value.
  64  */
  65 #define LOOKAHEAD_SIZE          (1 << ((2 * 8) - 3))
  66 #else   /* QUEUE_LOOKAHEAD_BIT */
  67 /*
  68  * One byte per queueElt value; avoids shifts and masks in accessing
  69  * array elements at the cost of additional memory.
  70  */
  71 #define LOOKAHEAD_SIZE          (1 << (2 * 8))
  72 #endif  /* QUEUE_LOOKAHEAD_BIT */
  73
  74 /*
  75  * When true, optimize away the cost of the keynybble() call on a hit
  76  * on queue[0].
  77  */
  78 #define SKIP_NIBBLE_ON_QUEUE_0          1
  79
  80 /*
  81  * pre-malloc'd buffers, one per level of comcryption. This allows each level
  82  * to maintain its own queue state machine as well as its own comcryption
  83  * parameters.
  84  */
  85 typedef struct _comcryptBuf {
  86         queueElt                                        *queue;                 // mallocd, QLEN elements
  87         unsigned                                        nybbleDex;              // index for keynybble()
  88         struct _comcryptBuf                     *nextBuf;               // for recursion
  89
  90         /*
  91          * Used to temporarily store bytecode fragments during comcryption and
  92          * partial blocks during decomcryption.
  93          */
  94         unsigned char                           *codeBuf;
  95         unsigned                                        codeBufSize;    // malloc'd size of codeBuf
  96         unsigned                                        codeBufLength;  // valid bytes in codeBuf
  97
  98         /*
  99          * Buffer for two-level comcryption. During comcryption, 2nd level
 100          * comcrypted bytecode is placed here. During decomcryption, the result
 101          * of decomcrytping the 2nd level bytecode is placed here.
 102          */
 103         unsigned char                           *level2Buf;
 104         unsigned                                        level2BufSize;  // malloc'd size of level2Buf
 105
 106         /*
 107          * comcryption parameters, may (eventually) be different for different
 108          * levels. Tweakable, for now, only via private API in comDebug.h.
 109          */
 110         unsigned                                        f1;
 111         unsigned                                        f2;
 112         unsigned                                        jmatchThresh;   // max avg jmatch for 2 level
 113         unsigned                                        minByteCode;    // min numByteCodes for 2 level
 114
 115         /*
 116          * Bit map, one bit per potential value in queue[]; 1 means "this value
 117          * is somewhere in queue[]"
 118          */
 119         unsigned char                           *lookAhead;
 120
 121         /*
 122          * Signature Sequence array - to be Xord with ciphertext
 123          * size = MAX_TOKENS
 124          */
 125         unsigned                                        *sigArray;
 126 } comcryptBuf;
 127
 128
 129 /*
 130  * Private struct associated with client's comcryptObj.
 131  */
 132 typedef struct {
 133         unsigned char                   *key;
 134         unsigned                                keybytes;                       // valid bytes in *key
 135         comcryptOptimize                optimize;                       // CCO_SIZE, etc.
 136         unsigned char                   *map;
 137         unsigned char                   *invmap;
 138         unsigned                                version;                        // from ciphertext
 139         unsigned                                versionBytes;           // valid bytes in version;
 140                                                                                                 //   also nonzero on comcrypt
 141                                                                                                 //   means version has been
 142                                                                                                 //   written
 143         unsigned                                spareBytes;                     // # ciphertext header spare
 144                                                                                                 //   bytes skipped
 145         comcryptBuf                             cbuf;
 146
 147         /*
 148          * To save a tiny bit of memory, these could/should be bits, but
 149          * we examine some of them on every code word, so we'll expand them into
 150          * bytes...
 151          */
 152         unsigned char                           laEnable;               // lookahead enable
 153         unsigned char                           sigSeqEnable;   // signature sequence enable
 154         unsigned char                           level2enable;   // 2-level comcryption
 155
 156 } comcryptPriv;
 157
 158
 159 /*
 160  * Block and buffer sizes. Subject to tweaking...
 161  */
 162 #define CC_BLOCK_SIZE           256                                             /* bytes of plaintext */
 163
 164 /*
 165  * For comcryptMaxInBufSize(CCOP_COMCRYPT), if outBufSize exceeds this
 166  * threshhold, truncate the max inBufSize so that
 167  * inBufSize = 0 mod CC_BLOCK_SIZE.
 168  */
 169 #define INBUF_TRUNC_THRESH      (16 * 1024)
 170
 171 /*
 172  * Macros to calculate number of token bits and bytes associated with
 173  * a quantity of plaintext (in bytes)
 174  */
 175 #define TOKEN_BITS_FROM_PTEXT(pt)                       ((pt + 1) >> 1)
 176 #define TOKEN_BYTES_FROM_PTEXT(pt)                      ((pt + 15) >> 4)
 177 #define TOKEN_BYTES_FROM_TOKEN_BITS(tb)         ((tb + 7) >> 3)
 178
 179 /*
 180  * Max number of token bits or code fragments in a block
 181  */
 182 #define MAX_TOKENS                              (CC_BLOCK_SIZE / 2)
 183
 184 /*
 185  * Size of comcryptBuf.queue[].
 186  */
 187 #define QLEN                                    256
 188
 189 /*
 190  * FIXME - some info on these constants?
 191  */
 192 #define F1_DEFAULT                              12
 193 #define F2_DEFAULT                              12
 194 #define ABOVE(F2)                               ((F2 * QLEN) >> 4)
 195
 196 /*
 197  * Constants for obfuscation via signature sequence.
 198  */
 199 #define HASH_Q          19
 200 #define HASH_PRIME      ((1<<HASH_Q)-1)         /* Must be prime less than 2^19. */
 201 #define IN_OFFSET       3                                       /* Must be in [1,255]. */
 202 #define OUT_OFFSET      5                                       /* Must be in [1,255]. */
 203
 204 /*
 205  * Ciphertext structure:
 206  *
 207  *   4 bytes of version
 208  *   4 bytes spare
 209  *   n blocks, format described below
 210  */
 211 #define VERSION_3_Dec_97                0xc0de0003
 212 #define VERSION_BYTES                   4
 213 #define SPARE_BYTES                             4
 214 #define CTEXT_HDR_SIZE                  (VERSION_BYTES + SPARE_BYTES)
 215
 216 /*
 217  * Format of CBD_SINGLE block
 218  *
 219  *              block description (see CBD_xxx, below)
 220  *              number of longCodes
 221  *              number of tokens - optional, absent if CBD_FULL_BLOCK
 222  *              token array
 223  *              longCode array
 224  *              byteCode array - length implied from number of longCodes, tokens
 225  *
 226  * Format of CBD_DOUBLE block
 227  *
 228  *              block description (see CBD_xxx, below)
 229  *              number of longCodes
 230  *              number of tokens - optional, absent if CBD_FULL_BLOCK
 231  *              token array
 232  *              longCode array
 233  *              length of 2nd level comcrypted byte code to follow
 234  *              2nd level comcrypted byte code array
 235  */
 236
 237 /*
 238  * Offsets (block-relative) of ciphertext components. All fields are byte-wide.
 239  * This limits block size to < 512 (the limiting case is a whole block of
 240  * bytecodes or a whole block of longcodes). Changing the counts to
 241  * two bytes would add flexibility and is necessary for block sizes of 512
 242  * or greater, but it would cost up to 3 bytes per block.
 243  */
 244 #define CTBO_BLOCK_DESC                 0x00    /* descriptor bits, see below */
 245 #define CTBO_NUM_LONG_CODES             0x01    /* in 16-bit words */
 246
 247 /*
 248  * if block[CTBO_BLOCK_DESC] & CBD_FULL_BLOCK, the following byte
 249  * is deleted (actually, implied) and subsequent fields are moved
 250  * up one byte. This saves one byte per block for most blocks.
 251  */
 252 #define CTBO_NUM_TOKENS                 0x02
 253
 254 /*
 255  * Offsets of remaining fields not constant; they depend on CBD_FULL_BLOCK and
 256  * CBD_SINGLE/CBD_DOUBLE.
 257  */
 258
 259 /*
 260  * Min block size - blockDesc, numLongCodes, numTokens, one token byte,
 261  * one bytecode
 262  */
 263 #define MIN_CBLOCK_SIZE                 5       /* min cipherblock size */
 264
 265 /*
 266  * Max block size - blockDesc, numLongCodes, full block's tokens, and
 267  * a full block of longcodes
 268  */
 269 #define MAX_CBLOCK_SIZE                 (2 +                            \
 270                 TOKEN_BYTES_FROM_PTEXT(CC_BLOCK_SIZE) +         \
 271                 CC_BLOCK_SIZE)
 272
 273 /*
 274  * Bits in block[CTBO_BLOCK_DESC]
 275  */
 276 #define CBD_MAGIC                               0xd0    /* high nibble must be 0xd */
 277 #define CBD_MAGIC_MASK                  0xf0
 278 #define CBD_BLOCK_TYPE_MASK             0x01
 279 #define CBD_SINGLE                              0x00    /* single-level comcrypt */
 280 #define CBD_DOUBLE                              0x01    /* double-level comcrypt */
 281 #define CBD_ODD_MASK                    0x02
 282 #define CBD_ODD                                 0x02    /* last code maps to single */
 283                                                                                 /*   (odd) byte */
 284 #define CBD_EVEN                                0x00
 285 #define CBD_FULL_BLOCK_MASK             0x04
 286 #define CBD_FULL_BLOCK                  0x04    /* expands to CC_BLOCK_SIZE, also  */
 287                                                                                 /* implies no CTBO_NUM_TOKENS byte
 288                                                                                  * in block */
 289 /*
 290  * Defining this non-zero limits effective key size to 40 bits for export
 291  */
 292 #define COMCRYPT_EXPORT_ONLY    0
 293 #define EXPORT_KEY_SIZE                 5               /* in bytes */
 294
 295 /*
 296  * Threshholds for performing 2-level comcrypt
 297  */
 298 #define THRESH_2LEVEL_JMATCH_DEF                40              /* max average jmatch */
 299 #define THRESH_2LEVEL_NUMBYTECODES_DEF  30              /* min number of bytecodes */
 300
 301
 302 /*
 303  * Private routines in comcryptPriv.c
 304  */
 305 extern void key_perm(
 306         const unsigned char *key,
 307         int                             keybytes,
 308         unsigned char           *map,
 309         unsigned char           *invmap);
 310 extern int keybyte(
 311         const unsigned char *key,
 312         int                             keybytes,
 313         int                             index);
 314 extern int keynybble(
 315         const unsigned char *key,
 316         int                             keybytes,
 317         int                             index);
 318 extern void mallocCodeBufs(comcryptBuf *cbufs);
 319 extern void freeCodeBufs(comcryptBuf *cbufs);
 320 extern void initCodeBufs(
 321         comcryptBuf *cbuf,
 322         const unsigned char *key,
 323         unsigned keyLen,
 324         unsigned char laEnable,
 325         unsigned char sigSeqEnable);
 326 #if     0
 327 extern void serializeShort(
 328         unsigned short s,
 329         unsigned char *buf);
 330 unsigned short deserializeShort(unsigned char *buf);
 331 #endif  /*0*/
 332 void serializeInt(
 333         unsigned i,
 334         unsigned char *buf);
 335 unsigned deserializeInt(unsigned char *buf);
 336 void initSigSequence(comcryptBuf *cbuf,
 337         const unsigned char *key,
 338         unsigned keyLen);
 339 void sigMunge(comcryptBuf *cbuf,
 340         const unsigned char *tokenPtr,
 341         unsigned numTokens,
 342         unsigned char *byteCodePtr,
 343         unsigned char *longCodePtr);
 344 #if             0
 345 void nextSigWord(comcryptBuf *cbuf,
 346         unsigned sigDex,                        // same as tokenDex
 347         unsigned match,
 348         unsigned above);
 349 #endif
 350
 351 #if             COM_LA_DEBUG
 352 extern int testLookAhead(comcryptBuf *cbuf, int i1, int i2);
 353 extern int initTestLookAhead(comcryptBuf *cbuf);
 354 #else   /*COM_LA_DEBUG*/
 355 #define testLookAhead(cbuf, i1, i2)
 356 #define initTestLookAhead(cbuf)
 357 #endif  /* COM_LA_DEBUG */
 358
 359 /*
 360  * Routines written as macros solely for performance reasons
 361  */
 362
 363 /*
 364  * try a couple different mersenne mods...
 365  */
 366 #define MOD_HASH(x) {                                                   \
 367         while(x > HASH_PRIME) {                                         \
 368                 x = (x >> HASH_Q) + (x & HASH_PRIME);   \
 369         }                                                                                       \
 370 }
 371
 372 /*
 373  * Haven't gotten this to work for the Mac yet...
 374  */
 375 #ifdef  NeXT
 376 #define SIG_WORD_INLINE 1
 377 #else   /*NeXT*/
 378 #define SIG_WORD_INLINE 0
 379 #endif
 380
 381 #if             SIG_WORD_INLINE
 382
 383 static inline void nextSigWord(comcryptBuf *cbuf,
 384         unsigned sigDex,                        // same as tokenDex
 385         unsigned match,
 386         unsigned above)                         // (jabove, keyabove) + nibbleDex
 387 {
 388         unsigned offset;
 389         unsigned *sigArray = cbuf->sigArray;
 390
 391         #if             COM_DEBUG
 392         if(sigDex == 0) {
 393                 printf("nextSigWord underflow\n");
 394                 exit(1);
 395         }
 396         if(sigDex > MAX_TOKENS) {
 397                 printf("nextSigWord overflow\n");
 398                 exit(1);
 399         }
 400         #endif
 401
 402         if(match) {
 403                 offset = IN_OFFSET;
 404         }
 405         else {
 406                 offset = OUT_OFFSET;
 407         }
 408         sigArray[sigDex] = sigArray[sigDex-1] * (above + offset);
 409         MOD_HASH(sigArray[sigDex]);
 410 }
 411
 412 #else   /*SIG_WORD_INLINE*/
 413
 414 #define nextSigWord(cbuf, sigDex, match, above) {                                       \
 415         unsigned offset = (match ? IN_OFFSET : OUT_OFFSET);                             \
 416         unsigned *sigArray = cbuf->sigArray;                                                    \
 417         unsigned result = (sigArray[sigDex-1] * (above + offset));              \
 418         MOD_HASH(result);                                                                                               \
 419         sigArray[sigDex] = result;                                                                              \
 420 }
 421
 422 #endif  /*SIG_WORD_INLINE*/
 423
 424 /*
 425  * Inline serializeShort(), deserializeShort()
 426  */
 427 #define serializeShort(s, buf)                  \
 428         buf[0] = (unsigned char)(s >> 8);       \
 429         buf[1] = (unsigned char)(s);            \
 430
 431 #define deserializeShort(s, buf)                \
 432         s = ((unsigned short)buf[0]) << 8;      \
 433         s |= buf[1];                                            \
 434
 435
 436 /*
 437  * General purpose macros for accessing bit arrays. Used for accessing
 438  * token bits and lookahead array bits if QUEUE_LOOKAHEAD_BIT = 1.
 439  */
 440 #define MARK_BIT_ARRAY(cp, index, val) {                                                \
 441         unsigned char bit = 1 << (index & 7);                                           \
 442         unsigned char *bytePtr = &cp[index>>3];                                         \
 443         if(val) {                                                                                                       \
 444                 *bytePtr |= bit;                                                                                \
 445         }                                                                                                                       \
 446         else {                                                                                                          \
 447                 *bytePtr &= ~bit;                                                                               \
 448         }                                                                                                                       \
 449 }
 450 #define GET_BIT_ARRAY(cp, index)                                                                \
 451         (cp[index >> 3] & (1 << (index & 7)))
 452
 453 #define getToken(tokenPtr, tokenDex)                            \
 454         GET_BIT_ARRAY(tokenPtr, tokenDex)
 455
 456 #define updateToken(tokenPtr, tokenDex, tokenBit)       \
 457         MARK_BIT_ARRAY(tokenPtr, tokenDex, tokenBit)
 458
 459 /*
 460  * Macros for accessing lookahead array elements
 461  */
 462
 463 #if             QUEUE_LOOKAHEAD_BIT
 464 /*
 465  * This way saves memory
 466  */
 467 #define markInQueue(cbuf, codeWord, val)                        \
 468         MARK_BIT_ARRAY(cbuf->lookAhead, codeWord, val)
 469
 470 #define inQueue(cbuf, codeWord)                                         \
 471         GET_BIT_ARRAY(cbuf->lookAhead, codeWord)
 472
 473 #else   /* QUEUE_LOOKAHEAD_BIT */
 474
 475 /*
 476  * This way saves time
 477  */
 478 #define markInQueue(cbuf, codeWord, val) {              \
 479         cbuf->lookAhead[codeWord] = val;                        \
 480 }
 481 #define inQueue(cbuf, codeWord)         (cbuf->lookAhead[codeWord])
 482
 483 #endif  /* QUEUE_LOOKAHEAD_BIT */
 484
 485 void *ascMalloc(unsigned size);
 486 void ascFree(void *data);
 487
 488 #ifdef __cplusplus
 489 }
 490 #endif
 491
 492 #endif  /*_COMCRYPT_PRIV_H_*/