OSX/libsecurity_cryptkit/lib/ckDES.c

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