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