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