libsecurity_comcryption/lib/comcryptPriv.h

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