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