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.5 (Berkeley) 03/06/91"; 23 #endif /* LIBC_SCCS and not lint */ 24 25 #include <sys/cdefs.h> 26 #include <unistd.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 /* comment out "static" when profiling */ 84 #define STATIC static 85 STATIC init_des(), perminit(), permute(); 86 #ifdef DEBUG 87 STATIC prtab(); 88 #endif 89 90 /* ==================================== */ 91 92 /* 93 * Cipher-block representation (Bob Baldwin): 94 * 95 * DES operates on groups of 64 bits, numbered 1..64 (sigh). One 96 * representation is to store one bit per byte in an array of bytes. Bit N of 97 * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array. 98 * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the 99 * first byte, 9..16 in the second, and so on. The DES spec apparently has 100 * bit 1 in the MSB of the first byte, but that is particularly noxious so we 101 * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is 102 * the MSB of the first byte. Specifically, the 64-bit input data and key are 103 * converted to LSB format, and the output 64-bit block is converted back into 104 * MSB format. 105 * 106 * DES operates internally on groups of 32 bits which are expanded to 48 bits 107 * by permutation E and shrunk back to 32 bits by the S boxes. To speed up 108 * the computation, the expansion is applied only once, the expanded 109 * representation is maintained during the encryption, and a compression 110 * permutation is applied only at the end. To speed up the S-box lookups, 111 * the 48 bits are maintained as eight 6 bit groups, one per byte, which 112 * directly feed the eight S-boxes. Within each byte, the 6 bits are the 113 * most significant ones. The low two bits of each byte are zero. (Thus, 114 * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the 115 * first byte in the eight byte representation, bit 2 of the 48 bit value is 116 * the "8"-valued bit, and so on.) In fact, a combined "SPE"-box lookup is 117 * used, in which the output is the 64 bit result of an S-box lookup which 118 * has been permuted by P and expanded by E, and is ready for use in the next 119 * iteration. Two 32-bit wide tables, SPE[0] and SPE[1], are used for this 120 * lookup. Since each byte in the 48 bit path is a multiple of four, indexed 121 * lookup of SPE[0] and SPE[1] is simple and fast. The key schedule and 122 * "salt" are also converted to this 8*(6+2) format. The SPE table size is 123 * 8*64*8 = 4K bytes. 124 * 125 * To speed up bit-parallel operations (such as XOR), the 8 byte 126 * representation is "union"ed with 32 bit values "i0" and "i1", and, on 127 * machines which support it, a 64 bit value "b64". This data structure, 128 * "C_block", has two problems. First, alignment restrictions must be 129 * honored. Second, the byte-order (e.g. little-endian or big-endian) of 130 * the architecture becomes visible. 131 * 132 * The byte-order problem is unfortunate, since on the one hand it is good 133 * to have a machine-independent C_block representation (bits 1..8 in the 134 * first byte, etc.), and on the other hand it is good for the LSB of the 135 * first byte to be the LSB of i0. We cannot have both these things, so we 136 * currently use the "little-endian" representation and avoid any multi-byte 137 * operations that depend on byte order. This largely precludes use of the 138 * 64-bit datatype since the relative order of i0 and i1 are unknown. It 139 * also inhibits grouping the SPE table to look up 12 bits at a time. (The 140 * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1 141 * high-order zero, providing fast indexing into a 64-bit wide SPE.) On the 142 * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup 143 * requires a 128 kilobyte table, so perhaps this is not a big loss. 144 * 145 * Permutation representation (Jim Gillogly): 146 * 147 * A transformation is defined by its effect on each of the 8 bytes of the 148 * 64-bit input. For each byte we give a 64-bit output that has the bits in 149 * the input distributed appropriately. The transformation is then the OR 150 * of the 8 sets of 64-bits. This uses 8*256*8 = 16K bytes of storage for 151 * each transformation. Unless LARGEDATA is defined, however, a more compact 152 * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks. 153 * The smaller table uses 16*16*8 = 2K bytes for each transformation. This 154 * is slower but tolerable, particularly for password encryption in which 155 * the SPE transformation is iterated many times. The small tables total 9K 156 * bytes, the large tables total 72K bytes. 157 * 158 * The transformations used are: 159 * IE3264: MSB->LSB conversion, initial permutation, and expansion. 160 * This is done by collecting the 32 even-numbered bits and applying 161 * a 32->64 bit transformation, and then collecting the 32 odd-numbered 162 * bits and applying the same transformation. Since there are only 163 * 32 input bits, the IE3264 transformation table is half the size of 164 * the usual table. 165 * CF6464: Compression, final permutation, and LSB->MSB conversion. 166 * This is done by two trivial 48->32 bit compressions to obtain 167 * a 64-bit block (the bit numbering is given in the "CIFP" table) 168 * followed by a 64->64 bit "cleanup" transformation. (It would 169 * be possible to group the bits in the 64-bit block so that 2 170 * identical 32->32 bit transformations could be used instead, 171 * saving a factor of 4 in space and possibly 2 in time, but 172 * byte-ordering and other complications rear their ugly head. 173 * Similar opportunities/problems arise in the key schedule 174 * transforms.) 175 * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation. 176 * This admittedly baroque 64->64 bit transformation is used to 177 * produce the first code (in 8*(6+2) format) of the key schedule. 178 * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation. 179 * It would be possible to define 15 more transformations, each 180 * with a different rotation, to generate the entire key schedule. 181 * To save space, however, we instead permute each code into the 182 * next by using a transformation that "undoes" the PC2 permutation, 183 * rotates the code, and then applies PC2. Unfortunately, PC2 184 * transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not 185 * invertible. We get around that problem by using a modified PC2 186 * which retains the 8 otherwise-lost bits in the unused low-order 187 * bits of each byte. The low-order bits are cleared when the 188 * codes are stored into the key schedule. 189 * PC2ROT[1]: Same as PC2ROT[0], but with two rotations. 190 * This is faster than applying PC2ROT[0] twice, 191 * 192 * The Bell Labs "salt" (Bob Baldwin): 193 * 194 * The salting is a simple permutation applied to the 48-bit result of E. 195 * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and 196 * i+24 of the result are swapped. The salt is thus a 24 bit number, with 197 * 16777216 possible values. (The original salt was 12 bits and could not 198 * swap bits 13..24 with 36..48.) 199 * 200 * It is possible, but expensive and ugly, to warp the SPE table account for 201 * the salt permutation. Fortunately, the conditional bit swapping requires 202 * only about four machine instructions and can be done on-the-fly with only 203 * a 2% performance penalty. 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 (key) */ 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[] = { /* number of rotations of PC1 */ 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 key (table) */ 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 * XXX need comment 448 */ 449 char * 450 crypt(key, setting) 451 register const char *key; 452 register const char *setting; 453 { 454 register char *encp; 455 register long i; 456 long salt; 457 int num_iter, salt_size, key_size; 458 C_block keyblock, rsltblock; 459 460 for (i = 0; i < 8; i++) 461 if ((keyblock.b[i] = 2*(unsigned char)(*key)) != 0) 462 key++; 463 des_setkey((char *)keyblock.b); /* also initializes "a64toi" */ 464 465 encp = &cryptresult[0]; 466 if (*setting != '_') { /* old style */ 467 num_iter = 25; 468 salt_size = 2; 469 key_size = 8; 470 } 471 else { /* new style */ 472 *encp++ = *setting++; 473 474 /* get iteration count */ 475 num_iter = 0; 476 for (i = 4; --i >= 0; ) { 477 num_iter = (num_iter<<6) | 478 a64toi[(unsigned char) 479 (encp[i] = (unsigned char)setting[i])]; 480 } 481 setting += 4; 482 encp += 4; 483 salt_size = 4; 484 key_size = 128; 485 } 486 487 salt = 0; 488 for (i = salt_size; --i >= 0; ) { 489 salt = (salt<<6) | 490 a64toi[(unsigned char) 491 (encp[i] = (unsigned char)setting[i])]; 492 } 493 encp += salt_size; 494 des_cipher((char *)&constdatablock, (char *)&rsltblock, salt, num_iter); 495 496 /* 497 * encrypt the remainder of the password 8 characters at a time. 498 */ 499 while ((key_size -= 8) > 0 && *key) { 500 C_block xdatablock; 501 502 for (i = 0; i < 8; i++) 503 if ((keyblock.b[i] = 2*(unsigned char)(*key)) != 0) 504 key++; 505 else 506 break; /* pad out with previous key */ 507 des_setkey((char *)keyblock.b); 508 des_cipher((char *)&constdatablock, (char *)&xdatablock, 0L, 1); 509 rsltblock.b32.i0 ^= xdatablock.b32.i0; 510 rsltblock.b32.i1 ^= xdatablock.b32.i1; 511 } 512 513 /* 514 * Encode the 64 cipher bits as 11 ascii characters. 515 */ 516 i = ((long)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | rsltblock.b[2]; 517 encp[3] = itoa64[i&0x3f]; i >>= 6; 518 encp[2] = itoa64[i&0x3f]; i >>= 6; 519 encp[1] = itoa64[i&0x3f]; i >>= 6; 520 encp[0] = itoa64[i]; encp += 4; 521 i = ((long)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | rsltblock.b[5]; 522 encp[3] = itoa64[i&0x3f]; i >>= 6; 523 encp[2] = itoa64[i&0x3f]; i >>= 6; 524 encp[1] = itoa64[i&0x3f]; i >>= 6; 525 encp[0] = itoa64[i]; encp += 4; 526 i = ((long)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2; 527 encp[2] = itoa64[i&0x3f]; i >>= 6; 528 encp[1] = itoa64[i&0x3f]; i >>= 6; 529 encp[0] = itoa64[i]; 530 531 encp[3] = 0; 532 return(cryptresult); 533 } 534 535 536 /* 537 * The Key Schedule, filled in by des_setkey() or setkey(). 538 */ 539 #define KS_SIZE 16 540 static C_block KS[KS_SIZE]; 541 542 /* 543 * Set up the key schedule from the key. 544 */ 545 void 546 des_setkey(key) 547 register const char *key; 548 { 549 register DCL_BLOCK(K, K0, K1); 550 register C_block *ptabp; 551 register int i; 552 static int des_ready = 0; 553 554 if (!des_ready) { 555 init_des(); 556 des_ready = 1; 557 } 558 559 PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT); 560 key = (char *)&KS[0]; 561 STORE(K&0xfcfcfcfcL, K0&0xfcfcfcfcL, K1, *(C_block *)key); 562 for (i = 1; i < 16; i++) { 563 key += sizeof(C_block); 564 STORE(K,K0,K1,*(C_block *)key); 565 ptabp = (C_block *)PC2ROT[Rotates[i]-1]; 566 PERM6464(K,K0,K1,(unsigned char *)key,ptabp); 567 STORE(K&0xfcfcfcfcL, K0&0xfcfcfcfcL, K1, *(C_block *)key); 568 } 569 } 570 571 /* 572 * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter) 573 * iterations of DES, using the the given 24-bit salt and the pre-computed key 574 * schedule, and store the resulting 8 chars at "out" (in == out is permitted). 575 * 576 * NOTE: the performance of this routine is critically dependent on your 577 * compiler and machine architecture. 578 */ 579 void 580 des_cipher(in, out, salt, num_iter) 581 const char *in; 582 char *out; 583 u_long salt; 584 int num_iter; 585 { 586 /* variables that we want in registers, most important first */ 587 #if defined(pdp11) 588 register int j; 589 #endif 590 register long L0, L1, R0, R1, k; 591 register C_block *kp; 592 register int ks_inc, loop_count; 593 C_block B; 594 595 L0 = salt; 596 TO_SIX_BIT(salt, L0); /* convert to 8*(6+2) format */ 597 598 #if defined(vax) || defined(pdp11) 599 salt = ~salt; /* "x &~ y" is faster than "x & y". */ 600 #define SALT (~salt) 601 #else 602 #define SALT salt 603 #endif 604 605 #if defined(MUST_ALIGN) 606 B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3]; 607 B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7]; 608 LOAD(L,L0,L1,B); 609 #else 610 LOAD(L,L0,L1,*(C_block *)in); 611 #endif 612 LOADREG(R,R0,R1,L,L0,L1); 613 L0 &= 0x55555555L; 614 L1 &= 0x55555555L; 615 L0 = (L0 << 1) | L1; /* L0 is the even-numbered input bits */ 616 R0 &= 0xaaaaaaaaL; 617 R1 = (R1 >> 1) & 0x55555555L; 618 L1 = R0 | R1; /* L1 is the odd-numbered input bits */ 619 STORE(L,L0,L1,B); 620 PERM3264(L,L0,L1,B.b, (C_block *)IE3264); /* even bits */ 621 PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264); /* odd bits */ 622 623 if (num_iter >= 0) 624 { /* encryption */ 625 kp = &KS[0]; 626 ks_inc = sizeof(*kp); 627 } 628 else 629 { /* decryption */ 630 num_iter = -num_iter; 631 kp = &KS[KS_SIZE-1]; 632 ks_inc = -sizeof(*kp); 633 } 634 635 while (--num_iter >= 0) { 636 loop_count = 8; 637 do { 638 639 #define BTAB(i) (((unsigned char *)&B.b[0])[i]) 640 #define SPTAB(t, i) (*(long *)((unsigned char *)t \ 641 + i*(sizeof(long)/4))) 642 #if defined(gould) 643 /* use this if BTAB(i) is evaluated just once ... */ 644 #define DOXOR(a,b,i) a^=SPTAB(SPE[0][i],BTAB(i));b^=SPTAB(SPE[1][i],BTAB(i)); 645 #else 646 #if defined(pdp11) 647 /* use this if your "long" int indexing is slow */ 648 #define DOXOR(a,b,i) j=BTAB(i); a^=SPTAB(SPE[0][i],j); b^=SPTAB(SPE[1][i],j); 649 #else 650 /* use this if "k" is allocated to a register ... */ 651 #define DOXOR(a,b,i) k=BTAB(i); a^=SPTAB(SPE[0][i],k); b^=SPTAB(SPE[1][i],k); 652 #endif 653 #endif 654 655 #define CRUNCH(L0, L1, R0, R1) \ 656 k = (R0 ^ R1) & SALT; \ 657 B.b32.i0 = k ^ R0 ^ kp->b32.i0; \ 658 B.b32.i1 = k ^ R1 ^ kp->b32.i1; \ 659 kp = (C_block *)((char *)kp+ks_inc); \ 660 \ 661 DOXOR(L0, L1, 0); \ 662 DOXOR(L0, L1, 1); \ 663 DOXOR(L0, L1, 2); \ 664 DOXOR(L0, L1, 3); \ 665 DOXOR(L0, L1, 4); \ 666 DOXOR(L0, L1, 5); \ 667 DOXOR(L0, L1, 6); \ 668 DOXOR(L0, L1, 7); 669 670 CRUNCH(L0, L1, R0, R1); 671 CRUNCH(R0, R1, L0, L1); 672 } while (--loop_count != 0); 673 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE)); 674 675 676 /* swap L and R */ 677 L0 ^= R0; L1 ^= R1; 678 R0 ^= L0; R1 ^= L1; 679 L0 ^= R0; L1 ^= R1; 680 } 681 682 /* store the encrypted (or decrypted) result */ 683 L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L); 684 L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L); 685 STORE(L,L0,L1,B); 686 PERM6464(L,L0,L1,B.b, (C_block *)CF6464); 687 #if defined(MUST_ALIGN) 688 STORE(L,L0,L1,B); 689 out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3]; 690 out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7]; 691 #else 692 STORE(L,L0,L1,*(C_block *)out); 693 #endif 694 } 695 696 697 /* 698 * Initialize various tables. This need only be done once. It could even be 699 * done at compile time, if the compiler were capable of that sort of thing. 700 */ 701 STATIC 702 init_des() 703 { 704 register int i, j; 705 register long k; 706 register int tableno; 707 static unsigned char perm[64], tmp32[32]; /* "static" for speed */ 708 709 /* 710 * table that converts chars "./0-9A-Za-z"to integers 0-63. 711 */ 712 for (i = 0; i < 64; i++) 713 a64toi[itoa64[i]] = i; 714 715 /* 716 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2. 717 */ 718 for (i = 0; i < 64; i++) 719 perm[i] = 0; 720 for (i = 0; i < 64; i++) { 721 if ((k = PC2[i]) == 0) 722 continue; 723 k += Rotates[0]-1; 724 if ((k%28) < Rotates[0]) k -= 28; 725 k = PC1[k]; 726 if (k > 0) { 727 k--; 728 k = (k|07) - (k&07); 729 k++; 730 } 731 perm[i] = k; 732 } 733 #ifdef DEBUG 734 prtab("pc1tab", perm, 8); 735 #endif 736 perminit(PC1ROT, perm, 8, 8); 737 738 /* 739 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2. 740 */ 741 for (j = 0; j < 2; j++) { 742 unsigned char pc2inv[64]; 743 for (i = 0; i < 64; i++) 744 perm[i] = pc2inv[i] = 0; 745 for (i = 0; i < 64; i++) { 746 if ((k = PC2[i]) == 0) 747 continue; 748 pc2inv[k-1] = i+1; 749 } 750 for (i = 0; i < 64; i++) { 751 if ((k = PC2[i]) == 0) 752 continue; 753 k += j; 754 if ((k%28) <= j) k -= 28; 755 perm[i] = pc2inv[k]; 756 } 757 #ifdef DEBUG 758 prtab("pc2tab", perm, 8); 759 #endif 760 perminit(PC2ROT[j], perm, 8, 8); 761 } 762 763 /* 764 * Bit reverse, then initial permutation, then expansion. 765 */ 766 for (i = 0; i < 8; i++) { 767 for (j = 0; j < 8; j++) { 768 k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1]; 769 if (k > 32) 770 k -= 32; 771 else if (k > 0) 772 k--; 773 if (k > 0) { 774 k--; 775 k = (k|07) - (k&07); 776 k++; 777 } 778 perm[i*8+j] = k; 779 } 780 } 781 #ifdef DEBUG 782 prtab("ietab", perm, 8); 783 #endif 784 perminit(IE3264, perm, 4, 8); 785 786 /* 787 * Compression, then final permutation, then bit reverse. 788 */ 789 for (i = 0; i < 64; i++) { 790 k = IP[CIFP[i]-1]; 791 if (k > 0) { 792 k--; 793 k = (k|07) - (k&07); 794 k++; 795 } 796 perm[k-1] = i+1; 797 } 798 #ifdef DEBUG 799 prtab("cftab", perm, 8); 800 #endif 801 perminit(CF6464, perm, 8, 8); 802 803 /* 804 * SPE table 805 */ 806 for (i = 0; i < 48; i++) 807 perm[i] = P32Tr[ExpandTr[i]-1]; 808 for (tableno = 0; tableno < 8; tableno++) { 809 for (j = 0; j < 64; j++) { 810 k = (((j >> 0) &01) << 5)| 811 (((j >> 1) &01) << 3)| 812 (((j >> 2) &01) << 2)| 813 (((j >> 3) &01) << 1)| 814 (((j >> 4) &01) << 0)| 815 (((j >> 5) &01) << 4); 816 k = S[tableno][k]; 817 k = (((k >> 3)&01) << 0)| 818 (((k >> 2)&01) << 1)| 819 (((k >> 1)&01) << 2)| 820 (((k >> 0)&01) << 3); 821 for (i = 0; i < 32; i++) 822 tmp32[i] = 0; 823 for (i = 0; i < 4; i++) 824 tmp32[4 * tableno + i] = (k >> i) & 01; 825 k = 0; 826 for (i = 24; --i >= 0; ) 827 k = (k<<1) | tmp32[perm[i]-1]; 828 TO_SIX_BIT(SPE[0][tableno][j], k); 829 k = 0; 830 for (i = 24; --i >= 0; ) 831 k = (k<<1) | tmp32[perm[i+24]-1]; 832 TO_SIX_BIT(SPE[1][tableno][j], k); 833 } 834 } 835 } 836 837 838 /* 839 * XXX need comment 840 * "perm" must be all-zeroes on entry to this routine. 841 */ 842 STATIC 843 perminit(perm, p, chars_in, chars_out) 844 C_block perm[64/CHUNKBITS][1<<CHUNKBITS]; 845 unsigned char p[64]; 846 int chars_in, chars_out; 847 { 848 register int i, j, k, l; 849 850 for (k = 0; k < chars_out*8; k++) { /* each output bit position */ 851 l = p[k] - 1; /* where this bit comes from */ 852 if (l < 0) 853 continue; /* output bit is always 0 */ 854 i = l>>LGCHUNKBITS; /* which chunk this bit comes from */ 855 l = 1<<(l&(CHUNKBITS-1)); /* mask for this bit */ 856 for (j = 0; j < (1<<CHUNKBITS); j++) { /* each chunk value */ 857 if ((j & l) != 0) 858 perm[i][j].b[k>>3] |= 1<<(k&07); 859 } 860 } 861 } 862 863 /* 864 * "setkey" routine (for backwards compatibility) 865 */ 866 void 867 setkey(key) 868 register const char *key; 869 { 870 register int i, j, k; 871 C_block keyblock; 872 873 for (i = 0; i < 8; i++) { 874 k = 0; 875 for (j = 0; j < 8; j++) { 876 k <<= 1; 877 k |= (unsigned char)*key++; 878 } 879 keyblock.b[i] = k; 880 } 881 des_setkey((char *)keyblock.b); 882 } 883 884 /* 885 * "encrypt" routine (for backwards compatibility) 886 */ 887 void 888 encrypt(block, flag) 889 register char *block; 890 int flag; 891 { 892 register int i, j, k; 893 C_block cblock; 894 895 for (i = 0; i < 8; i++) { 896 k = 0; 897 for (j = 0; j < 8; j++) { 898 k <<= 1; 899 k |= (unsigned char)*block++; 900 } 901 cblock.b[i] = k; 902 } 903 des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag? -1: 1)); 904 for (i = 7; i >= 0; i--) { 905 k = cblock.b[i]; 906 for (j = 7; j >= 0; j--) { 907 *--block = k&01; 908 k >>= 1; 909 } 910 } 911 } 912 913 #ifdef DEBUG 914 STATIC 915 prtab(s, t, num_rows) 916 char *s; 917 unsigned char *t; 918 int num_rows; 919 { 920 register int i, j; 921 922 printf("%s:\n", s); 923 for (i = 0; i < num_rows; i++) { 924 for (j = 0; j < 8; j++) { 925 printf("%3d", t[i*8+j]); 926 } 927 printf("\n"); 928 } 929 printf("\n"); 930 } 931 #endif 932