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