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