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