1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Tom Truscott. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)crypt.c 5.9 (Berkeley) 05/18/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <unistd.h> 16 #include <pwd.h> 17 18 /* 19 * UNIX password, and DES, encryption. 20 * By Tom Truscott, trt@rti.rti.org, 21 * from algorithms by Robert W. Baldwin and James Gillogly. 22 * 23 * References: 24 * "Mathematical Cryptology for Computer Scientists and Mathematicians," 25 * by Wayne Patterson, 1987, ISBN 0-8476-7438-X. 26 * 27 * "Password Security: A Case History," R. Morris and Ken Thompson, 28 * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979. 29 * 30 * "DES will be Totally Insecure within Ten Years," M.E. Hellman, 31 * IEEE Spectrum, vol. 16, pp. 32-39, July 1979. 32 */ 33 34 /* ===== Configuration ==================== */ 35 36 /* 37 * define "MUST_ALIGN" if your compiler cannot load/store 38 * long integers at arbitrary (e.g. odd) memory locations. 39 * (Either that or never pass unaligned addresses to des_cipher!) 40 */ 41 #if !defined(vax) 42 #define MUST_ALIGN 43 #endif 44 45 /* 46 * define "LONG_IS_32_BITS" only if sizeof(long)==4. 47 * This avoids use of bit fields (your compiler may be sloppy with them). 48 */ 49 #if !defined(cray) 50 #define LONG_IS_32_BITS 51 #endif 52 53 /* 54 * define "B64" to be the declaration for a 64 bit integer. 55 * XXX this feature is currently unused, see "endian" comment below. 56 */ 57 #if defined(cray) 58 #define B64 long 59 #endif 60 #if defined(convex) 61 #define B64 long long 62 #endif 63 64 /* 65 * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes 66 * of lookup tables. This speeds up des_setkey() and des_cipher(), but has 67 * little effect on crypt(). 68 */ 69 #if defined(notdef) 70 #define LARGEDATA 71 #endif 72 73 /* compile with "-DSTATIC=int" when profiling */ 74 #ifndef STATIC 75 #define STATIC static 76 #endif 77 STATIC init_des(), init_perm(), permute(); 78 #ifdef DEBUG 79 STATIC prtab(); 80 #endif 81 82 /* ==================================== */ 83 84 /* 85 * Cipher-block representation (Bob Baldwin): 86 * 87 * DES operates on groups of 64 bits, numbered 1..64 (sigh). One 88 * representation is to store one bit per byte in an array of bytes. Bit N of 89 * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array. 90 * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the 91 * first byte, 9..16 in the second, and so on. The DES spec apparently has 92 * bit 1 in the MSB of the first byte, but that is particularly noxious so we 93 * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is 94 * the MSB of the first byte. Specifically, the 64-bit input data and key are 95 * converted to LSB format, and the output 64-bit block is converted back into 96 * MSB format. 97 * 98 * DES operates internally on groups of 32 bits which are expanded to 48 bits 99 * by permutation E and shrunk back to 32 bits by the S boxes. To speed up 100 * the computation, the expansion is applied only once, the expanded 101 * representation is maintained during the encryption, and a compression 102 * permutation is applied only at the end. To speed up the S-box lookups, 103 * the 48 bits are maintained as eight 6 bit groups, one per byte, which 104 * directly feed the eight S-boxes. Within each byte, the 6 bits are the 105 * most significant ones. The low two bits of each byte are zero. (Thus, 106 * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the 107 * first byte in the eight byte representation, bit 2 of the 48 bit value is 108 * the "8"-valued bit, and so on.) In fact, a combined "SPE"-box lookup is 109 * used, in which the output is the 64 bit result of an S-box lookup which 110 * has been permuted by P and expanded by E, and is ready for use in the next 111 * iteration. Two 32-bit wide tables, SPE[0] and SPE[1], are used for this 112 * lookup. Since each byte in the 48 bit path is a multiple of four, indexed 113 * lookup of SPE[0] and SPE[1] is simple and fast. The key schedule and 114 * "salt" are also converted to this 8*(6+2) format. The SPE table size is 115 * 8*64*8 = 4K bytes. 116 * 117 * To speed up bit-parallel operations (such as XOR), the 8 byte 118 * representation is "union"ed with 32 bit values "i0" and "i1", and, on 119 * machines which support it, a 64 bit value "b64". This data structure, 120 * "C_block", has two problems. First, alignment restrictions must be 121 * honored. Second, the byte-order (e.g. little-endian or big-endian) of 122 * the architecture becomes visible. 123 * 124 * The byte-order problem is unfortunate, since on the one hand it is good 125 * to have a machine-independent C_block representation (bits 1..8 in the 126 * first byte, etc.), and on the other hand it is good for the LSB of the 127 * first byte to be the LSB of i0. We cannot have both these things, so we 128 * currently use the "little-endian" representation and avoid any multi-byte 129 * operations that depend on byte order. This largely precludes use of the 130 * 64-bit datatype since the relative order of i0 and i1 are unknown. It 131 * also inhibits grouping the SPE table to look up 12 bits at a time. (The 132 * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1 133 * high-order zero, providing fast indexing into a 64-bit wide SPE.) On the 134 * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup 135 * requires a 128 kilobyte table, so perhaps this is not a big loss. 136 * 137 * Permutation representation (Jim Gillogly): 138 * 139 * A transformation is defined by its effect on each of the 8 bytes of the 140 * 64-bit input. For each byte we give a 64-bit output that has the bits in 141 * the input distributed appropriately. The transformation is then the OR 142 * of the 8 sets of 64-bits. This uses 8*256*8 = 16K bytes of storage for 143 * each transformation. Unless LARGEDATA is defined, however, a more compact 144 * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks. 145 * The smaller table uses 16*16*8 = 2K bytes for each transformation. This 146 * is slower but tolerable, particularly for password encryption in which 147 * the SPE transformation is iterated many times. The small tables total 9K 148 * bytes, the large tables total 72K bytes. 149 * 150 * The transformations used are: 151 * IE3264: MSB->LSB conversion, initial permutation, and expansion. 152 * This is done by collecting the 32 even-numbered bits and applying 153 * a 32->64 bit transformation, and then collecting the 32 odd-numbered 154 * bits and applying the same transformation. Since there are only 155 * 32 input bits, the IE3264 transformation table is half the size of 156 * the usual table. 157 * CF6464: Compression, final permutation, and LSB->MSB conversion. 158 * This is done by two trivial 48->32 bit compressions to obtain 159 * a 64-bit block (the bit numbering is given in the "CIFP" table) 160 * followed by a 64->64 bit "cleanup" transformation. (It would 161 * be possible to group the bits in the 64-bit block so that 2 162 * identical 32->32 bit transformations could be used instead, 163 * saving a factor of 4 in space and possibly 2 in time, but 164 * byte-ordering and other complications rear their ugly head. 165 * Similar opportunities/problems arise in the key schedule 166 * transforms.) 167 * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation. 168 * This admittedly baroque 64->64 bit transformation is used to 169 * produce the first code (in 8*(6+2) format) of the key schedule. 170 * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation. 171 * It would be possible to define 15 more transformations, each 172 * with a different rotation, to generate the entire key schedule. 173 * To save space, however, we instead permute each code into the 174 * next by using a transformation that "undoes" the PC2 permutation, 175 * rotates the code, and then applies PC2. Unfortunately, PC2 176 * transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not 177 * invertible. We get around that problem by using a modified PC2 178 * which retains the 8 otherwise-lost bits in the unused low-order 179 * bits of each byte. The low-order bits are cleared when the 180 * codes are stored into the key schedule. 181 * PC2ROT[1]: Same as PC2ROT[0], but with two rotations. 182 * This is faster than applying PC2ROT[0] twice, 183 * 184 * The Bell Labs "salt" (Bob Baldwin): 185 * 186 * The salting is a simple permutation applied to the 48-bit result of E. 187 * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and 188 * i+24 of the result are swapped. The salt is thus a 24 bit number, with 189 * 16777216 possible values. (The original salt was 12 bits and could not 190 * swap bits 13..24 with 36..48.) 191 * 192 * It is possible, but ugly, to warp the SPE table to account for the salt 193 * permutation. Fortunately, the conditional bit swapping requires only 194 * about four machine instructions and can be done on-the-fly with about an 195 * 8% performance penalty. 196 */ 197 198 typedef union { 199 unsigned char b[8]; 200 struct { 201 #if defined(LONG_IS_32_BITS) 202 /* long is often faster than a 32-bit bit field */ 203 long i0; 204 long i1; 205 #else 206 long i0: 32; 207 long i1: 32; 208 #endif 209 } b32; 210 #if defined(B64) 211 B64 b64; 212 #endif 213 } C_block; 214 215 /* 216 * Convert twenty-four-bit long in host-order 217 * to six bits (and 2 low-order zeroes) per char little-endian format. 218 */ 219 #define TO_SIX_BIT(rslt, src) { \ 220 C_block cvt; \ 221 cvt.b[0] = src; src >>= 6; \ 222 cvt.b[1] = src; src >>= 6; \ 223 cvt.b[2] = src; src >>= 6; \ 224 cvt.b[3] = src; \ 225 rslt = (cvt.b32.i0 & 0x3f3f3f3fL) << 2; \ 226 } 227 228 /* 229 * These macros may someday permit efficient use of 64-bit integers. 230 */ 231 #define ZERO(d,d0,d1) d0 = 0, d1 = 0 232 #define LOAD(d,d0,d1,bl) d0 = (bl).b32.i0, d1 = (bl).b32.i1 233 #define LOADREG(d,d0,d1,s,s0,s1) d0 = s0, d1 = s1 234 #define OR(d,d0,d1,bl) d0 |= (bl).b32.i0, d1 |= (bl).b32.i1 235 #define STORE(s,s0,s1,bl) (bl).b32.i0 = s0, (bl).b32.i1 = s1 236 #define DCL_BLOCK(d,d0,d1) long d0, d1 237 238 #if defined(LARGEDATA) 239 /* Waste memory like crazy. Also, do permutations in line */ 240 #define LGCHUNKBITS 3 241 #define CHUNKBITS (1<<LGCHUNKBITS) 242 #define PERM6464(d,d0,d1,cpp,p) \ 243 LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]); \ 244 OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]); \ 245 OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]); \ 246 OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]); \ 247 OR (d,d0,d1,(p)[(4<<CHUNKBITS)+(cpp)[4]]); \ 248 OR (d,d0,d1,(p)[(5<<CHUNKBITS)+(cpp)[5]]); \ 249 OR (d,d0,d1,(p)[(6<<CHUNKBITS)+(cpp)[6]]); \ 250 OR (d,d0,d1,(p)[(7<<CHUNKBITS)+(cpp)[7]]); 251 #define PERM3264(d,d0,d1,cpp,p) \ 252 LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]); \ 253 OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]); \ 254 OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]); \ 255 OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]); 256 #else 257 /* "small data" */ 258 #define LGCHUNKBITS 2 259 #define CHUNKBITS (1<<LGCHUNKBITS) 260 #define PERM6464(d,d0,d1,cpp,p) \ 261 { C_block tblk; permute(cpp,&tblk,p,8); LOAD (d,d0,d1,tblk); } 262 #define PERM3264(d,d0,d1,cpp,p) \ 263 { C_block tblk; permute(cpp,&tblk,p,4); LOAD (d,d0,d1,tblk); } 264 265 STATIC 266 permute(cp, out, p, chars_in) 267 unsigned char *cp; 268 C_block *out; 269 register C_block *p; 270 int chars_in; 271 { 272 register DCL_BLOCK(D,D0,D1); 273 register C_block *tp; 274 register int t; 275 276 ZERO(D,D0,D1); 277 do { 278 t = *cp++; 279 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 280 tp = &p[t>>4]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 281 } while (--chars_in > 0); 282 STORE(D,D0,D1,*out); 283 } 284 #endif /* LARGEDATA */ 285 286 287 /* ===== (mostly) Standard DES Tables ==================== */ 288 289 static unsigned char IP[] = { /* initial permutation */ 290 58, 50, 42, 34, 26, 18, 10, 2, 291 60, 52, 44, 36, 28, 20, 12, 4, 292 62, 54, 46, 38, 30, 22, 14, 6, 293 64, 56, 48, 40, 32, 24, 16, 8, 294 57, 49, 41, 33, 25, 17, 9, 1, 295 59, 51, 43, 35, 27, 19, 11, 3, 296 61, 53, 45, 37, 29, 21, 13, 5, 297 63, 55, 47, 39, 31, 23, 15, 7, 298 }; 299 300 /* The final permutation is the inverse of IP - no table is necessary */ 301 302 static unsigned char ExpandTr[] = { /* expansion operation */ 303 32, 1, 2, 3, 4, 5, 304 4, 5, 6, 7, 8, 9, 305 8, 9, 10, 11, 12, 13, 306 12, 13, 14, 15, 16, 17, 307 16, 17, 18, 19, 20, 21, 308 20, 21, 22, 23, 24, 25, 309 24, 25, 26, 27, 28, 29, 310 28, 29, 30, 31, 32, 1, 311 }; 312 313 static unsigned char PC1[] = { /* permuted choice table (key) */ 314 57, 49, 41, 33, 25, 17, 9, 315 1, 58, 50, 42, 34, 26, 18, 316 10, 2, 59, 51, 43, 35, 27, 317 19, 11, 3, 60, 52, 44, 36, 318 319 63, 55, 47, 39, 31, 23, 15, 320 7, 62, 54, 46, 38, 30, 22, 321 14, 6, 61, 53, 45, 37, 29, 322 21, 13, 5, 28, 20, 12, 4, 323 }; 324 325 static unsigned char Rotates[] = { /* number of rotations of PC1 */ 326 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 327 }; 328 329 /* note: each "row" of PC2 is left-padded with bits that make it invertible */ 330 static unsigned char PC2[] = { /* permuted choice key (table) */ 331 9, 18, 14, 17, 11, 24, 1, 5, 332 22, 25, 3, 28, 15, 6, 21, 10, 333 35, 38, 23, 19, 12, 4, 26, 8, 334 43, 54, 16, 7, 27, 20, 13, 2, 335 336 0, 0, 41, 52, 31, 37, 47, 55, 337 0, 0, 30, 40, 51, 45, 33, 48, 338 0, 0, 44, 49, 39, 56, 34, 53, 339 0, 0, 46, 42, 50, 36, 29, 32, 340 }; 341 342 static unsigned char S[8][64] = { /* 48->32 bit substitution tables */ 343 /* S[1] */ 344 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 345 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 346 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 347 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13, 348 /* S[2] */ 349 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 350 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 351 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 352 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9, 353 /* S[3] */ 354 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 355 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 356 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 357 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12, 358 /* S[4] */ 359 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 360 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 361 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 362 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14, 363 /* S[5] */ 364 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 365 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 366 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 367 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, 368 /* S[6] */ 369 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 370 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 371 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 372 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13, 373 /* S[7] */ 374 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 375 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 376 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 377 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12, 378 /* S[8] */ 379 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 380 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 381 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 382 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11, 383 }; 384 385 static unsigned char P32Tr[] = { /* 32-bit permutation function */ 386 16, 7, 20, 21, 387 29, 12, 28, 17, 388 1, 15, 23, 26, 389 5, 18, 31, 10, 390 2, 8, 24, 14, 391 32, 27, 3, 9, 392 19, 13, 30, 6, 393 22, 11, 4, 25, 394 }; 395 396 static unsigned char CIFP[] = { /* compressed/interleaved permutation */ 397 1, 2, 3, 4, 17, 18, 19, 20, 398 5, 6, 7, 8, 21, 22, 23, 24, 399 9, 10, 11, 12, 25, 26, 27, 28, 400 13, 14, 15, 16, 29, 30, 31, 32, 401 402 33, 34, 35, 36, 49, 50, 51, 52, 403 37, 38, 39, 40, 53, 54, 55, 56, 404 41, 42, 43, 44, 57, 58, 59, 60, 405 45, 46, 47, 48, 61, 62, 63, 64, 406 }; 407 408 static unsigned char itoa64[] = /* 0..63 => ascii-64 */ 409 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 410 411 412 /* ===== Tables that are initialized at run time ==================== */ 413 414 415 static unsigned char a64toi[128]; /* ascii-64 => 0..63 */ 416 417 /* Initial key schedule permutation */ 418 static C_block PC1ROT[64/CHUNKBITS][1<<CHUNKBITS]; 419 420 /* Subsequent key schedule rotation permutations */ 421 static C_block PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS]; 422 423 /* Initial permutation/expansion table */ 424 static C_block IE3264[32/CHUNKBITS][1<<CHUNKBITS]; 425 426 /* Table that combines the S, P, and E operations. */ 427 static long SPE[2][8][64]; 428 429 /* compressed/interleaved => final permutation table */ 430 static C_block CF6464[64/CHUNKBITS][1<<CHUNKBITS]; 431 432 433 /* ==================================== */ 434 435 436 static C_block constdatablock; /* encryption constant */ 437 static char cryptresult[1+4+4+11+1]; /* encrypted result */ 438 439 /* 440 * Return a pointer to static data consisting of the "setting" 441 * followed by an encryption produced by the "key" and "setting". 442 */ 443 char * 444 crypt(key, setting) 445 register const char *key; 446 register const char *setting; 447 { 448 register char *encp; 449 register long i; 450 register int t; 451 long salt; 452 int num_iter, salt_size, key_size; 453 C_block keyblock, rsltblock; 454 455 for (i = 0; i < 8; i++) { 456 if ((t = 2*(unsigned char)(*key)) != 0) 457 key++; 458 keyblock.b[i] = t; 459 } 460 if (des_setkey((char *)keyblock.b)) /* also initializes "a64toi" */ 461 return(NULL); 462 463 encp = &cryptresult[0]; 464 switch (*setting) { 465 case _PASSWORD_EFMT1: 466 *encp++ = *setting++; 467 468 /* get iteration count */ 469 num_iter = 0; 470 for (i = 4; --i >= 0; ) { 471 if ((t = (unsigned char)setting[i]) == '\0') 472 t = '.'; 473 encp[i] = t; 474 num_iter = (num_iter<<6) | a64toi[t]; 475 } 476 setting += 4; 477 encp += 4; 478 salt_size = 4; 479 key_size = 128; 480 break; 481 default: 482 num_iter = 25; 483 salt_size = 2; 484 key_size = 8; 485 } 486 487 salt = 0; 488 for (i = salt_size; --i >= 0; ) { 489 if ((t = (unsigned char)setting[i]) == '\0') 490 t = '.'; 491 encp[i] = t; 492 salt = (salt<<6) | a64toi[t]; 493 } 494 encp += salt_size; 495 if (des_cipher((char *)&constdatablock, (char *)&rsltblock, 496 salt, num_iter)) 497 return(NULL); 498 499 /* 500 * encrypt the remainder of the password 8 characters at a time. 501 */ 502 while ((key_size -= 8) > 0 && *key) { 503 C_block xdatablock; 504 505 for (i = 0; i < 8; i++) { 506 if ((t = 2*(unsigned char)(*key)) != 0) 507 key++; 508 keyblock.b[i] = t; 509 if (t == 0) 510 break; /* pad out with previous key */ 511 } 512 if (des_setkey((char *)keyblock.b)) 513 return(NULL); 514 if (des_cipher((char *)&constdatablock, 515 (char *)&xdatablock, 0L, 1)) 516 return(NULL); 517 rsltblock.b32.i0 ^= xdatablock.b32.i0; 518 rsltblock.b32.i1 ^= xdatablock.b32.i1; 519 } 520 521 /* 522 * Encode the 64 cipher bits as 11 ascii characters. 523 */ 524 i = ((long)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | rsltblock.b[2]; 525 encp[3] = itoa64[i&0x3f]; i >>= 6; 526 encp[2] = itoa64[i&0x3f]; i >>= 6; 527 encp[1] = itoa64[i&0x3f]; i >>= 6; 528 encp[0] = itoa64[i]; encp += 4; 529 i = ((long)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | rsltblock.b[5]; 530 encp[3] = itoa64[i&0x3f]; i >>= 6; 531 encp[2] = itoa64[i&0x3f]; i >>= 6; 532 encp[1] = itoa64[i&0x3f]; i >>= 6; 533 encp[0] = itoa64[i]; encp += 4; 534 i = ((long)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2; 535 encp[2] = itoa64[i&0x3f]; i >>= 6; 536 encp[1] = itoa64[i&0x3f]; i >>= 6; 537 encp[0] = itoa64[i]; 538 539 encp[3] = 0; 540 541 return(cryptresult); 542 } 543 544 545 /* 546 * The Key Schedule, filled in by des_setkey() or setkey(). 547 */ 548 #define KS_SIZE 16 549 static C_block KS[KS_SIZE]; 550 551 /* 552 * Set up the key schedule from the key. 553 */ 554 des_setkey(key) 555 register const char *key; 556 { 557 register DCL_BLOCK(K, K0, K1); 558 register C_block *ptabp; 559 register int i; 560 static int des_ready = 0; 561 562 if (!des_ready) { 563 init_des(); 564 des_ready = 1; 565 } 566 567 PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT); 568 key = (char *)&KS[0]; 569 STORE(K&0xfcfcfcfcL, K0&0xfcfcfcfcL, K1, *(C_block *)key); 570 for (i = 1; i < 16; i++) { 571 key += sizeof(C_block); 572 STORE(K,K0,K1,*(C_block *)key); 573 ptabp = (C_block *)PC2ROT[Rotates[i]-1]; 574 PERM6464(K,K0,K1,(unsigned char *)key,ptabp); 575 STORE(K&0xfcfcfcfcL, K0&0xfcfcfcfcL, K1, *(C_block *)key); 576 } 577 return(0); 578 } 579 580 /* 581 * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter) 582 * iterations of DES, using the the given 24-bit salt and the pre-computed key 583 * schedule, and store the resulting 8 chars at "out" (in == out is permitted). 584 * 585 * NOTE: the performance of this routine is critically dependent on your 586 * compiler and machine architecture. 587 */ 588 des_cipher(in, out, salt, num_iter) 589 const char *in; 590 char *out; 591 long salt; 592 int num_iter; 593 { 594 /* variables that we want in registers, most important first */ 595 #if defined(pdp11) 596 register int j; 597 #endif 598 register long L0, L1, R0, R1, k; 599 register C_block *kp; 600 register int ks_inc, loop_count; 601 C_block B; 602 603 L0 = salt; 604 TO_SIX_BIT(salt, L0); /* convert to 8*(6+2) format */ 605 606 #if defined(vax) || defined(pdp11) 607 salt = ~salt; /* "x &~ y" is faster than "x & y". */ 608 #define SALT (~salt) 609 #else 610 #define SALT salt 611 #endif 612 613 #if defined(MUST_ALIGN) 614 B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3]; 615 B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7]; 616 LOAD(L,L0,L1,B); 617 #else 618 LOAD(L,L0,L1,*(C_block *)in); 619 #endif 620 LOADREG(R,R0,R1,L,L0,L1); 621 L0 &= 0x55555555L; 622 L1 &= 0x55555555L; 623 L0 = (L0 << 1) | L1; /* L0 is the even-numbered input bits */ 624 R0 &= 0xaaaaaaaaL; 625 R1 = (R1 >> 1) & 0x55555555L; 626 L1 = R0 | R1; /* L1 is the odd-numbered input bits */ 627 STORE(L,L0,L1,B); 628 PERM3264(L,L0,L1,B.b, (C_block *)IE3264); /* even bits */ 629 PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264); /* odd bits */ 630 631 if (num_iter >= 0) 632 { /* encryption */ 633 kp = &KS[0]; 634 ks_inc = sizeof(*kp); 635 } 636 else 637 { /* decryption */ 638 num_iter = -num_iter; 639 kp = &KS[KS_SIZE-1]; 640 ks_inc = -sizeof(*kp); 641 } 642 643 while (--num_iter >= 0) { 644 loop_count = 8; 645 do { 646 647 #define BTAB(i) (((unsigned char *)&B.b[0])[i]) 648 #define SPTAB(t, i) (*(long *)((unsigned char *)t \ 649 + i*(sizeof(long)/4))) 650 #if defined(gould) 651 /* use this if BTAB(i) is evaluated just once ... */ 652 #define DOXOR(a,b,i) a^=SPTAB(SPE[0][i],BTAB(i));b^=SPTAB(SPE[1][i],BTAB(i)); 653 #else 654 #if defined(pdp11) 655 /* use this if your "long" int indexing is slow */ 656 #define DOXOR(a,b,i) j=BTAB(i); a^=SPTAB(SPE[0][i],j); b^=SPTAB(SPE[1][i],j); 657 #else 658 /* use this if "k" is allocated to a register ... */ 659 #define DOXOR(a,b,i) k=BTAB(i); a^=SPTAB(SPE[0][i],k); b^=SPTAB(SPE[1][i],k); 660 #endif 661 #endif 662 663 #define CRUNCH(L0, L1, R0, R1) \ 664 k = (R0 ^ R1) & SALT; \ 665 B.b32.i0 = k ^ R0 ^ kp->b32.i0; \ 666 B.b32.i1 = k ^ R1 ^ kp->b32.i1; \ 667 kp = (C_block *)((char *)kp+ks_inc); \ 668 \ 669 DOXOR(L0, L1, 0); \ 670 DOXOR(L0, L1, 1); \ 671 DOXOR(L0, L1, 2); \ 672 DOXOR(L0, L1, 3); \ 673 DOXOR(L0, L1, 4); \ 674 DOXOR(L0, L1, 5); \ 675 DOXOR(L0, L1, 6); \ 676 DOXOR(L0, L1, 7); 677 678 CRUNCH(L0, L1, R0, R1); 679 CRUNCH(R0, R1, L0, L1); 680 } while (--loop_count != 0); 681 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE)); 682 683 684 /* swap L and R */ 685 L0 ^= R0; L1 ^= R1; 686 R0 ^= L0; R1 ^= L1; 687 L0 ^= R0; L1 ^= R1; 688 } 689 690 /* store the encrypted (or decrypted) result */ 691 L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L); 692 L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L); 693 STORE(L,L0,L1,B); 694 PERM6464(L,L0,L1,B.b, (C_block *)CF6464); 695 #if defined(MUST_ALIGN) 696 STORE(L,L0,L1,B); 697 out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3]; 698 out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7]; 699 #else 700 STORE(L,L0,L1,*(C_block *)out); 701 #endif 702 return(0); 703 } 704 705 706 /* 707 * Initialize various tables. This need only be done once. It could even be 708 * done at compile time, if the compiler were capable of that sort of thing. 709 */ 710 STATIC 711 init_des() 712 { 713 register int i, j; 714 register long k; 715 register int tableno; 716 static unsigned char perm[64], tmp32[32]; /* "static" for speed */ 717 718 /* 719 * table that converts chars "./0-9A-Za-z"to integers 0-63. 720 */ 721 for (i = 0; i < 64; i++) 722 a64toi[itoa64[i]] = i; 723 724 /* 725 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2. 726 */ 727 for (i = 0; i < 64; i++) 728 perm[i] = 0; 729 for (i = 0; i < 64; i++) { 730 if ((k = PC2[i]) == 0) 731 continue; 732 k += Rotates[0]-1; 733 if ((k%28) < Rotates[0]) k -= 28; 734 k = PC1[k]; 735 if (k > 0) { 736 k--; 737 k = (k|07) - (k&07); 738 k++; 739 } 740 perm[i] = k; 741 } 742 #ifdef DEBUG 743 prtab("pc1tab", perm, 8); 744 #endif 745 init_perm(PC1ROT, perm, 8, 8); 746 747 /* 748 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2. 749 */ 750 for (j = 0; j < 2; j++) { 751 unsigned char pc2inv[64]; 752 for (i = 0; i < 64; i++) 753 perm[i] = pc2inv[i] = 0; 754 for (i = 0; i < 64; i++) { 755 if ((k = PC2[i]) == 0) 756 continue; 757 pc2inv[k-1] = i+1; 758 } 759 for (i = 0; i < 64; i++) { 760 if ((k = PC2[i]) == 0) 761 continue; 762 k += j; 763 if ((k%28) <= j) k -= 28; 764 perm[i] = pc2inv[k]; 765 } 766 #ifdef DEBUG 767 prtab("pc2tab", perm, 8); 768 #endif 769 init_perm(PC2ROT[j], perm, 8, 8); 770 } 771 772 /* 773 * Bit reverse, then initial permutation, then expansion. 774 */ 775 for (i = 0; i < 8; i++) { 776 for (j = 0; j < 8; j++) { 777 k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1]; 778 if (k > 32) 779 k -= 32; 780 else if (k > 0) 781 k--; 782 if (k > 0) { 783 k--; 784 k = (k|07) - (k&07); 785 k++; 786 } 787 perm[i*8+j] = k; 788 } 789 } 790 #ifdef DEBUG 791 prtab("ietab", perm, 8); 792 #endif 793 init_perm(IE3264, perm, 4, 8); 794 795 /* 796 * Compression, then final permutation, then bit reverse. 797 */ 798 for (i = 0; i < 64; i++) { 799 k = IP[CIFP[i]-1]; 800 if (k > 0) { 801 k--; 802 k = (k|07) - (k&07); 803 k++; 804 } 805 perm[k-1] = i+1; 806 } 807 #ifdef DEBUG 808 prtab("cftab", perm, 8); 809 #endif 810 init_perm(CF6464, perm, 8, 8); 811 812 /* 813 * SPE table 814 */ 815 for (i = 0; i < 48; i++) 816 perm[i] = P32Tr[ExpandTr[i]-1]; 817 for (tableno = 0; tableno < 8; tableno++) { 818 for (j = 0; j < 64; j++) { 819 k = (((j >> 0) &01) << 5)| 820 (((j >> 1) &01) << 3)| 821 (((j >> 2) &01) << 2)| 822 (((j >> 3) &01) << 1)| 823 (((j >> 4) &01) << 0)| 824 (((j >> 5) &01) << 4); 825 k = S[tableno][k]; 826 k = (((k >> 3)&01) << 0)| 827 (((k >> 2)&01) << 1)| 828 (((k >> 1)&01) << 2)| 829 (((k >> 0)&01) << 3); 830 for (i = 0; i < 32; i++) 831 tmp32[i] = 0; 832 for (i = 0; i < 4; i++) 833 tmp32[4 * tableno + i] = (k >> i) & 01; 834 k = 0; 835 for (i = 24; --i >= 0; ) 836 k = (k<<1) | tmp32[perm[i]-1]; 837 TO_SIX_BIT(SPE[0][tableno][j], k); 838 k = 0; 839 for (i = 24; --i >= 0; ) 840 k = (k<<1) | tmp32[perm[i+24]-1]; 841 TO_SIX_BIT(SPE[1][tableno][j], k); 842 } 843 } 844 } 845 846 /* 847 * Initialize "perm" to represent transformation "p", which rearranges 848 * (perhaps with expansion and/or contraction) one packed array of bits 849 * (of size "chars_in" characters) into another array (of size "chars_out" 850 * characters). 851 * 852 * "perm" must be all-zeroes on entry to this routine. 853 */ 854 STATIC 855 init_perm(perm, p, chars_in, chars_out) 856 C_block perm[64/CHUNKBITS][1<<CHUNKBITS]; 857 unsigned char p[64]; 858 int chars_in, chars_out; 859 { 860 register int i, j, k, l; 861 862 for (k = 0; k < chars_out*8; k++) { /* each output bit position */ 863 l = p[k] - 1; /* where this bit comes from */ 864 if (l < 0) 865 continue; /* output bit is always 0 */ 866 i = l>>LGCHUNKBITS; /* which chunk this bit comes from */ 867 l = 1<<(l&(CHUNKBITS-1)); /* mask for this bit */ 868 for (j = 0; j < (1<<CHUNKBITS); j++) { /* each chunk value */ 869 if ((j & l) != 0) 870 perm[i][j].b[k>>3] |= 1<<(k&07); 871 } 872 } 873 } 874 875 /* 876 * "setkey" routine (for backwards compatibility) 877 */ 878 setkey(key) 879 register const char *key; 880 { 881 register int i, j, k; 882 C_block keyblock; 883 884 for (i = 0; i < 8; i++) { 885 k = 0; 886 for (j = 0; j < 8; j++) { 887 k <<= 1; 888 k |= (unsigned char)*key++; 889 } 890 keyblock.b[i] = k; 891 } 892 return(des_setkey((char *)keyblock.b)); 893 } 894 895 /* 896 * "encrypt" routine (for backwards compatibility) 897 */ 898 encrypt(block, flag) 899 register char *block; 900 int flag; 901 { 902 register int i, j, k; 903 C_block cblock; 904 905 for (i = 0; i < 8; i++) { 906 k = 0; 907 for (j = 0; j < 8; j++) { 908 k <<= 1; 909 k |= (unsigned char)*block++; 910 } 911 cblock.b[i] = k; 912 } 913 if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1))) 914 return(1); 915 for (i = 7; i >= 0; i--) { 916 k = cblock.b[i]; 917 for (j = 7; j >= 0; j--) { 918 *--block = k&01; 919 k >>= 1; 920 } 921 } 922 return(0); 923 } 924 925 #ifdef DEBUG 926 STATIC 927 prtab(s, t, num_rows) 928 char *s; 929 unsigned char *t; 930 int num_rows; 931 { 932 register int i, j; 933 934 (void)printf("%s:\n", s); 935 for (i = 0; i < num_rows; i++) { 936 for (j = 0; j < 8; j++) { 937 (void)printf("%3d", t[i*8+j]); 938 } 939 (void)printf("\n"); 940 } 941 (void)printf("\n"); 942 } 943 #endif 944