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