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