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 */ 50static 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 */ 69static 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 */ 81static 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 97static 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) */ 110static 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 */ 123static 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) */ 128static 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 */ 140static 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 */ 200static 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() */ 213static long (*sp)[64]; /* Combined S and P boxes */ 214 215static char (*iperm)[16][8]; /* Initial and final permutations */ 216static char (*fperm)[16][8]; 217 218 219/* bit 0 is left-most in byte */ 220static const int bytebit[] = { 221 0200,0100,040,020,010,04,02,01 222}; 223 224static 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 */ 235static 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 */ 273static 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 296int 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 */ 331void 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) */ 354void 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 */ 412static 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 */ 446static 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 */ 461static 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 */ 489void 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 */ 516void 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 */ 546