AppleCSP/MiscCSPAlgs/DES.c

   1 /* Copyright (c) 1998 Apple Computer, 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 COMPUTER, INC. AND THE
   6  * ORIGINAL LICENSEE THAT OBTAINED THESE MATERIALS FROM APPLE COMPUTER,
   7  * INC.  ANY USE OF THESE MATERIALS NOT PERMITTED BY SUCH AGREEMENT WILL
   8  * EXPOSE YOU TO LIABILITY.
   9  ***************************************************************************
  10  *
  11  * DES.c - raw DES encryption engine
  12  *
  13  * Revision History
  14  * ----------------
  15  * 11/03/98     Michael Brouwer at Apple
  16  *      Added braces to static array definition of si[][].
  17  * 10/06/98             ap
  18  *      Changed to compile with C++.
  19  * 28 May 98    Doug Mitchel at Apple
  20  *      Changed to use platform-dependent fmalloc(), ffree()
  21  * 31 Mar 97    Doug Mitchell at Apple
  22  *      Put per-instance data in struct _desInst
  23  *      Changed setkey() to dessetkey() to avoid collision with libc version
  24  * 21 Aug 96    Doug Mitchell at NeXT
  25  *      Broke out from NSDESCryptor.m
  26  * 22 Feb 96    Blaine Garst at NeXT
  27  *      Created.
  28  */
  29
  30 #ifdef  CRYPTKIT_CSP_ENABLE
  31 /* CryptKit compiled in; secure malloc available */
  32 #define STATIC_PERMS    0
  33 #else
  34 /* Statically allocated lookup tables */
  35 #define STATIC_PERMS    1
  36 #endif  /* CRYPTKIT_CSP_ENABLE */
  37
  38 #include "DES.h"
  39 #if     !STATIC_PERMS
  40 #include <CryptKit/falloc.h>
  41 #endif
  42 #include <stdlib.h>
  43
  44 #ifndef NULL
  45 #define NULL    ((void *)0)
  46 #endif  /* NULL */
  47
  48 #define DES_DEBUG       0       /* enables some printfs */
  49
  50 /* Sofware DES functions
  51  * written 12 Dec 1986 by Phil Karn, KA9Q; large sections adapted from
  52  * the 1977 public-domain program by Jim Gillogly
  53  */
  54
  55 #ifdef  __LITTLE_ENDIAN__
  56 /* Byte swap a long */
  57 static unsigned int byteswap(unsigned int x) {
  58         register char *cp,tmp;
  59
  60         cp = (char *)&x;
  61         tmp = cp[3];
  62         cp[3] = cp[0];
  63         cp[0] = tmp;
  64
  65         tmp = cp[2];
  66         cp[2] = cp[1];
  67         cp[1] = tmp;
  68
  69         return x;
  70 }
  71 #endif
  72
  73 /* Tables defined in the Data Encryption Standard documents */
  74
  75 /* initial permutation IP */
  76 static const char ip[] = {
  77         58, 50, 42, 34, 26, 18, 10,  2,
  78         60, 52, 44, 36, 28, 20, 12,  4,
  79         62, 54, 46, 38, 30, 22, 14,  6,
  80         64, 56, 48, 40, 32, 24, 16,  8,
  81         57, 49, 41, 33, 25, 17,  9,  1,
  82         59, 51, 43, 35, 27, 19, 11,  3,
  83         61, 53, 45, 37, 29, 21, 13,  5,
  84         63, 55, 47, 39, 31, 23, 15,  7
  85 };
  86
  87 /* final permutation IP^-1 */
  88 static const char fp[] = {
  89         40,  8, 48, 16, 56, 24, 64, 32,
  90         39,  7, 47, 15, 55, 23, 63, 31,
  91         38,  6, 46, 14, 54, 22, 62, 30,
  92         37,  5, 45, 13, 53, 21, 61, 29,
  93         36,  4, 44, 12, 52, 20, 60, 28,
  94         35,  3, 43, 11, 51, 19, 59, 27,
  95         34,  2, 42, 10, 50, 18, 58, 26,
  96         33,  1, 41,  9, 49, 17, 57, 25
  97 };
  98
  99 /* expansion operation matrix
 100  * This is for reference only; it is unused in the code
 101  * as the f() function performs it implicitly for speed
 102  */
 103 #ifdef notdef
 104 static char ei[] = {
 105         32,  1,  2,  3,  4,  5,
 106          4,  5,  6,  7,  8,  9,
 107          8,  9, 10, 11, 12, 13,
 108         12, 13, 14, 15, 16, 17,
 109         16, 17, 18, 19, 20, 21,
 110         20, 21, 22, 23, 24, 25,
 111         24, 25, 26, 27, 28, 29,
 112         28, 29, 30, 31, 32,  1
 113 };
 114 #endif
 115
 116 /* permuted choice table (key) */
 117 static const char pc1[] = {
 118         57, 49, 41, 33, 25, 17,  9,
 119          1, 58, 50, 42, 34, 26, 18,
 120         10,  2, 59, 51, 43, 35, 27,
 121         19, 11,  3, 60, 52, 44, 36,
 122
 123         63, 55, 47, 39, 31, 23, 15,
 124          7, 62, 54, 46, 38, 30, 22,
 125         14,  6, 61, 53, 45, 37, 29,
 126         21, 13,  5, 28, 20, 12,  4
 127 };
 128
 129 /* number left rotations of pc1 */
 130 static const char totrot[] = {
 131         1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
 132 };
 133
 134 /* permuted choice key (table) */
 135 static const char pc2[] = {
 136         14, 17, 11, 24,  1,  5,
 137          3, 28, 15,  6, 21, 10,
 138         23, 19, 12,  4, 26,  8,
 139         16,  7, 27, 20, 13,  2,
 140         41, 52, 31, 37, 47, 55,
 141         30, 40, 51, 45, 33, 48,
 142         44, 49, 39, 56, 34, 53,
 143         46, 42, 50, 36, 29, 32
 144 };
 145
 146 /* The (in)famous S-boxes */
 147 static const char si[8][64] = {
 148     {
 149         /* S1 */
 150         14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
 151          0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
 152          4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
 153         15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
 154     },
 155     {
 156         /* S2 */
 157         15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
 158          3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
 159          0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
 160         13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
 161     },
 162     {
 163         /* S3 */
 164         10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
 165         13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
 166         13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
 167          1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
 168     },
 169     {
 170         /* S4 */
 171          7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
 172         13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
 173         10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
 174          3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
 175     },
 176     {
 177         /* S5 */
 178          2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
 179         14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
 180          4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
 181         11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
 182     },
 183     {
 184         /* S6 */
 185         12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
 186         10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
 187          9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
 188          4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
 189     },
 190     {
 191         /* S7 */
 192          4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
 193         13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
 194          1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
 195          6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
 196     },
 197     {
 198         /* S8 */
 199         13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
 200          1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
 201          7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
 202          2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
 203     }
 204 };
 205
 206 /* 32-bit permutation function P used on the output of the S-boxes */
 207 static const char p32i[] = {
 208         16,  7, 20, 21,
 209         29, 12, 28, 17,
 210          1, 15, 23, 26,
 211          5, 18, 31, 10,
 212          2,  8, 24, 14,
 213         32, 27,  3,  9,
 214         19, 13, 30,  6,
 215         22, 11,  4, 25
 216 };
 217 /* End of DES-defined tables */
 218
 219 /* Lookup tables initialized once only at startup by desinit() */
 220 #if STATIC_PERMS
 221 static long sp[8][64];                  /* Combined S and P boxes */
 222 static char iperm[16][16][8];   /* Initial and final permutations */
 223 static char fperm[16][16][8];
 224 static char perms_init = 0;
 225 #else
 226 static long (*sp)[64];          /* Combined S and P boxes */
 227 static char (*iperm)[16][8];    /* Initial and final permutations */
 228 static char (*fperm)[16][8];
 229 #endif
 230
 231 /* bit 0 is left-most in byte */
 232 static const int bytebit[] = {
 233         0200,0100,040,020,010,04,02,01
 234 };
 235
 236 static const int nibblebit[] = {
 237          010,04,02,01
 238 };
 239
 240 /* Allocate space and initialize DES lookup arrays
 241  * mode == 0: standard Data Encryption Algorithm
 242  * mode == 1: DEA without initial and final permutations for speed
 243  * mode == 2: DEA without permutations and with 128-byte key (completely
 244  *            independent subkeys for each round)
 245  */
 246 /* Initialize the lookup table for the combined S and P boxes */
 247 static void spinit() {
 248     char pbox[32];
 249     int p,i,s,j,rowcol;
 250     long val;
 251
 252     /* Compute pbox, the inverse of p32i.
 253        * This is easier to work with
 254        */
 255     for(p=0;p<32;p++){
 256         for(i=0;i<32;i++){
 257             if(p32i[i]-1 == p){
 258                 pbox[p] = i;
 259                 break;
 260             }
 261         }
 262     }
 263     for(s = 0; s < 8; s++){                     /* For each S-box */
 264         for(i=0; i<64; i++){            /* For each possible input */
 265             val = 0;
 266             /* The row number is formed from the first and last
 267                * bits; the column number is from the middle 4
 268                */
 269             rowcol = (i & 32) | ((i & 1) ? 16 : 0) | ((i >> 1) & 0xf);
 270             for(j=0;j<4;j++){   /* For each output bit */
 271                 if(si[s][rowcol] & (8 >> j)){
 272                     val |= 1L << (31 - pbox[4*s + j]);
 273                 }
 274             }
 275             sp[s][i] = val;
 276
 277 #if     DES_DEBUG
 278             printf("sp[%d][%2d] = %08lx\n",s,i,sp[s][i]);
 279 #endif
 280         }
 281     }
 282 }
 283
 284 /* initialize a perm array */
 285 static void perminit(char perm[16][16][8], const char p[64]) {
 286         register int l, j, k;
 287         int i,m;
 288
 289         /* Clear the permutation array */
 290         for (i=0; i<16; i++)
 291                 for (j=0; j<16; j++)
 292                         for (k=0; k<8; k++)
 293                                 perm[i][j][k]=0;
 294
 295         for (i=0; i<16; i++)            /* each input nibble position */
 296                 for (j = 0; j < 16; j++)/* each possible input nibble */
 297                 for (k = 0; k < 64; k++)/* each output bit position */
 298                 {   l = p[k] - 1;       /* where does this bit come from*/
 299                         if ((l >> 2) != i)  /* does it come from input posn?*/
 300                         continue;       /* if not, bit k is 0    */
 301                         if (!(j & nibblebit[l & 3]))
 302                         continue;       /* any such bit in input? */
 303                         m = k & 07;     /* which bit is this in the byte*/
 304                         perm[i][j][k>>3] |= bytebit[m];
 305                 }
 306 }
 307
 308 /*
 309  * This is NOT thread-safe. Caler must ensure single-threaded access. */
 310 int desinit(desInst dinst, int mode) {
 311         dinst->desmode = mode;
 312
 313         /*
 314          * Remainder only has to be done once.
 315          */
 316         #if             STATIC_PERMS
 317         /* statically allocated */
 318         if(perms_init) {
 319                 return 0;
 320         }
 321         #else
 322         /* malloc the perm tables */
 323         if(sp != NULL){
 324                 /* Already initialized */
 325                 return 0;
 326         }
 327         if((sp = (long (*)[64])fmalloc(sizeof(long) * 8 * 64)) == NULL){
 328                 return -1;
 329         }
 330         iperm = (char (*)[16][8])fmalloc(sizeof(char) * 16 * 16 * 8);
 331         if(iperm == NULL){
 332                 ffree((char *)sp);
 333                 return -1;
 334         }
 335         fperm = (char (*)[16][8])fmalloc(sizeof(char) * 16 * 16 * 8);
 336         if(fperm == NULL){
 337                 ffree((char *)sp);
 338                 ffree((char *)iperm);
 339                 return -1;
 340         }
 341         #endif  /* STATIC_PERMS */
 342
 343         /* common code to init the perm tables */
 344         spinit();
 345         perminit(iperm,ip);
 346         perminit(fperm,fp);
 347         #if             STATIC_PERMS
 348         perms_init = 1;
 349         #endif
 350         return 0;
 351 }
 352 /* Free up storage used by DES */
 353 void desdone(desInst dinst) {
 354         /*
 355          * no per-instance mallocd data
 356          */
 357 }
 358 /* Set key (initialize key schedule array) */
 359 void dessetkey(desInst dinst, char *key) {
 360         char pc1m[56];          /* place to modify pc1 into */
 361         char pcr[56];           /* place to rotate pc1 into */
 362         register int i,j,l;
 363         int m;
 364
 365         /* In mode 2, the 128 bytes of subkey are set directly from the
 366          * user's key, allowing him to use completely independent
 367          * subkeys for each round. Note that the user MUST specify a
 368          * full 128 bytes.
 369          *
 370          * I would like to think that this technique gives the NSA a real
 371          * headache, but I'm not THAT naive.
 372          */
 373         if(dinst->desmode == 2){
 374                 for(i=0;i<16;i++)
 375                         for(j=0;j<8;j++)
 376                                 dinst->kn[i][j] = *key++;
 377                 return;
 378         }
 379         /* Clear key schedule */
 380         for (i=0; i<16; i++)
 381                 for (j=0; j<8; j++)
 382                         dinst->kn[i][j]=0;
 383
 384         for (j=0; j<56; j++) {          /* convert pc1 to bits of key */
 385                 l=pc1[j]-1;             /* integer bit location  */
 386                 m = l & 07;             /* find bit              */
 387                 pc1m[j]=(key[l>>3] &    /* find which key byte l is in */
 388                         bytebit[m])     /* and which bit of that byte */
 389                         ? 1 : 0;        /* and store 1-bit result */
 390         }
 391         for (i=0; i<16; i++) {          /* key chunk for each iteration */
 392                 for (j=0; j<56; j++)    /* rotate pc1 the right amount */
 393                         pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
 394                         /* rotate left and right halves independently */
 395                 for (j=0; j<48; j++){   /* select bits individually */
 396                         /* check bit that goes to dinst->kn[j] */
 397                         if (pcr[pc2[j]-1]){
 398                                 /* mask it in if it's there */
 399                                 l= j % 6;
 400                                 dinst->kn[i][j/6] |= bytebit[l] >> 2;
 401                         }
 402                 }
 403         }
 404 #if     DES_DEBUG
 405         for(i=0;i<16;i++) {
 406                 printf("dinst->kn[%d] = ", i);
 407                 for(j=0;j<8;j++) {
 408                         printf("%x ", dinst->kn[i][j]);
 409                 }
 410                 printf("\n");
 411         }
 412
 413 #endif  /* 1 */
 414 }
 415
 416 /* The nonlinear function f(r,k), the heart of DES */
 417 static long int f(unsigned long r, unsigned char subkey[8]) {
 418                 /* 32 bits */
 419         /* 48-bit key for this round */
 420         register unsigned long rval,rt;
 421 #if     DES_DEBUG
 422         printf("f(%08lx, %02x %02x %02x %02x %02x %02x %02x %02x) = ",
 423                 r,
 424                 subkey[0], subkey[1], subkey[2],
 425                 subkey[3], subkey[4], subkey[5],
 426                 subkey[6], subkey[7]);
 427 #endif
 428         /* Run E(R) ^ K through the combined S & P boxes
 429          * This code takes advantage of a convenient regularity in
 430          * E, namely that each group of 6 bits in E(R) feeding
 431          * a single S-box is a contiguous segment of R.
 432          */
 433         rt = (r >> 1) | ((r & 1) ? 0x80000000 : 0);
 434         rval = 0;
 435         rval |= sp[0][((rt >> 26) ^ *subkey++) & 0x3f];
 436         rval |= sp[1][((rt >> 22) ^ *subkey++) & 0x3f];
 437         rval |= sp[2][((rt >> 18) ^ *subkey++) & 0x3f];
 438         rval |= sp[3][((rt >> 14) ^ *subkey++) & 0x3f];
 439         rval |= sp[4][((rt >> 10) ^ *subkey++) & 0x3f];
 440         rval |= sp[5][((rt >> 6) ^ *subkey++) & 0x3f];
 441         rval |= sp[6][((rt >> 2) ^ *subkey++) & 0x3f];
 442         rt = (r << 1) | ((r & 0x80000000) ? 1 : 0);
 443         rval |= sp[7][(rt ^ *subkey) & 0x3f];
 444 #if     DES_DEBUG
 445         printf(" %08lx\n",rval);
 446 #endif
 447         return rval;
 448 }
 449
 450 /* Do one DES cipher round */
 451 static void round(desInst dinst, int num, unsigned long int *block) {
 452                                 /* i.e. the num-th one   */
 453
 454     /* The rounds are numbered from 0 to 15. On even rounds
 455        * the right half is fed to f() and the result exclusive-ORs
 456        * the left half; on odd rounds the reverse is done.
 457        */
 458     if(num & 1){
 459         block[1] ^= f(block[0],dinst->kn[num]);
 460     } else {
 461         block[0] ^= f(block[1],dinst->kn[num]);
 462     }
 463 }
 464
 465 /* Permute inblock with perm */
 466 static void permute(char *inblock, char perm[16][16][8], char *outblock) {
 467     /* result into outblock,64 bits */
 468     /* 2K bytes defining perm. */
 469     register int i,j;
 470     register char *ib, *ob;             /* ptr to input or output block */
 471     register char *p, *q;
 472
 473     if(perm == NULL){
 474         /* No permutation, just copy */
 475         for(i=8; i!=0; i--)
 476             *outblock++ = *inblock++;
 477         return;
 478     }
 479     /* Clear output block        */
 480     for (i=8, ob = outblock; i != 0; i--)
 481         *ob++ = 0;
 482
 483     ib = inblock;
 484     for (j = 0; j < 16; j += 2, ib++) { /* for each input nibble */
 485         ob = outblock;
 486         p = perm[j][(*ib >> 4) & 017];
 487         q = perm[j + 1][*ib & 017];
 488         for (i = 8; i != 0; i--){   /* and each output byte */
 489             *ob++ |= *p++ | *q++;       /* OR the masks together*/
 490         }
 491     }
 492 }
 493 /* In-place encryption of 64-bit block */
 494 void endes(desInst dinst, char *block) {
 495         register int i;
 496         unsigned long work[2];          /* Working data storage */
 497         long tmp;
 498
 499         permute(block,iperm,(char *)work);      /* Initial Permutation */
 500 #ifdef __LITTLE_ENDIAN__
 501         work[0] = byteswap(work[0]);
 502         work[1] = byteswap(work[1]);
 503 #endif
 504
 505         /* Do the 16 rounds */
 506         for (i=0; i<16; i++)
 507                 round(dinst,i,work);
 508
 509         /* Left/right half swap */
 510         tmp = work[0];
 511         work[0] = work[1];
 512         work[1] = tmp;
 513
 514 #ifdef __LITTLE_ENDIAN__
 515         work[0] = byteswap(work[0]);
 516         work[1] = byteswap(work[1]);
 517 #endif
 518         permute((char *)work,fperm,block);      /* Inverse initial permutation */
 519 }
 520 /* In-place decryption of 64-bit block */
 521 void dedes(desInst dinst, char *block) {
 522         register int i;
 523         unsigned long work[2];  /* Working data storage */
 524         long tmp;
 525
 526         permute(block,iperm,(char *)work);      /* Initial permutation */
 527
 528 #ifdef __LITTLE_ENDIAN__
 529         work[0] = byteswap(work[0]);
 530         work[1] = byteswap(work[1]);
 531 #endif
 532
 533         /* Left/right half swap */
 534         tmp = work[0];
 535         work[0] = work[1];
 536         work[1] = tmp;
 537
 538         /* Do the 16 rounds in reverse order */
 539         for (i=15; i >= 0; i--)
 540                 round(dinst,i,work);
 541
 542 #ifdef __LITTLE_ENDIAN__
 543         work[0] = byteswap(work[0]);
 544         work[1] = byteswap(work[1]);
 545 #endif
 546
 547         permute((char *)work,fperm,block);      /* Inverse initial permutation */
 548 }