1 /* $NetBSD: crypt.c,v 1.16 2000/07/06 11:13:49 ad 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.16 2000/07/06 11:13:49 ad 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 /* 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 extern char *__md5crypt(const char *, const char *); /* XXX */ 484 char *encp; 485 int32_t i; 486 int t; 487 int32_t salt; 488 int num_iter, salt_size; 489 C_block keyblock, rsltblock; 490 491 /* Non-DES encryption schemes hook in here. */ 492 if (setting[0] == _PASSWORD_NONDES) { 493 switch (setting[1]) { 494 #ifdef notyet 495 case '2': 496 return (__bcrypt(key, setting)); 497 #endif 498 case '1': 499 default: 500 return (__md5crypt(key, setting)); 501 } 502 } 503 504 for (i = 0; i < 8; i++) { 505 if ((t = 2*(unsigned char)(*key)) != 0) 506 key++; 507 keyblock.b[i] = t; 508 } 509 if (des_setkey((char *)keyblock.b)) /* also initializes "a64toi" */ 510 return (NULL); 511 512 encp = &cryptresult[0]; 513 switch (*setting) { 514 case _PASSWORD_EFMT1: 515 /* 516 * Involve the rest of the password 8 characters at a time. 517 */ 518 while (*key) { 519 if (des_cipher((char *)&keyblock, 520 (char *)&keyblock, 0L, 1)) 521 return (NULL); 522 for (i = 0; i < 8; i++) { 523 if ((t = 2*(unsigned char)(*key)) != 0) 524 key++; 525 keyblock.b[i] ^= t; 526 } 527 if (des_setkey((char *)keyblock.b)) 528 return (NULL); 529 } 530 531 *encp++ = *setting++; 532 533 /* get iteration count */ 534 num_iter = 0; 535 for (i = 4; --i >= 0; ) { 536 if ((t = (unsigned char)setting[i]) == '\0') 537 t = '.'; 538 encp[i] = t; 539 num_iter = (num_iter<<6) | a64toi[t]; 540 } 541 setting += 4; 542 encp += 4; 543 salt_size = 4; 544 break; 545 default: 546 num_iter = 25; 547 salt_size = 2; 548 } 549 550 salt = 0; 551 for (i = salt_size; --i >= 0; ) { 552 if ((t = (unsigned char)setting[i]) == '\0') 553 t = '.'; 554 encp[i] = t; 555 salt = (salt<<6) | a64toi[t]; 556 } 557 encp += salt_size; 558 if (des_cipher((char *)&constdatablock, (char *)&rsltblock, 559 salt, num_iter)) 560 return (NULL); 561 562 /* 563 * Encode the 64 cipher bits as 11 ascii characters. 564 */ 565 i = ((int32_t)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | 566 rsltblock.b[2]; 567 encp[3] = itoa64[i&0x3f]; i >>= 6; 568 encp[2] = itoa64[i&0x3f]; i >>= 6; 569 encp[1] = itoa64[i&0x3f]; i >>= 6; 570 encp[0] = itoa64[i]; encp += 4; 571 i = ((int32_t)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | 572 rsltblock.b[5]; 573 encp[3] = itoa64[i&0x3f]; i >>= 6; 574 encp[2] = itoa64[i&0x3f]; i >>= 6; 575 encp[1] = itoa64[i&0x3f]; i >>= 6; 576 encp[0] = itoa64[i]; encp += 4; 577 i = ((int32_t)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2; 578 encp[2] = itoa64[i&0x3f]; i >>= 6; 579 encp[1] = itoa64[i&0x3f]; i >>= 6; 580 encp[0] = itoa64[i]; 581 582 encp[3] = 0; 583 584 return (cryptresult); 585 } 586 587 588 /* 589 * The Key Schedule, filled in by des_setkey() or setkey(). 590 */ 591 #define KS_SIZE 16 592 static C_block KS[KS_SIZE]; 593 594 /* 595 * Set up the key schedule from the key. 596 */ 597 int 598 des_setkey(key) 599 const char *key; 600 { 601 DCL_BLOCK(K, K0, K1); 602 C_block *ptabp; 603 int i; 604 static int des_ready = 0; 605 606 if (!des_ready) { 607 init_des(); 608 des_ready = 1; 609 } 610 611 PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT); 612 key = (char *)&KS[0]; 613 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key); 614 for (i = 1; i < 16; i++) { 615 key += sizeof(C_block); 616 STORE(K,K0,K1,*(C_block *)key); 617 ptabp = (C_block *)PC2ROT[Rotates[i]-1]; 618 PERM6464(K,K0,K1,(unsigned char *)key,ptabp); 619 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key); 620 } 621 return (0); 622 } 623 624 /* 625 * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter) 626 * iterations of DES, using the given 24-bit salt and the pre-computed key 627 * schedule, and store the resulting 8 chars at "out" (in == out is permitted). 628 * 629 * NOTE: the performance of this routine is critically dependent on your 630 * compiler and machine architecture. 631 */ 632 int 633 des_cipher(in, out, salt, num_iter) 634 const char *in; 635 char *out; 636 long salt; 637 int num_iter; 638 { 639 /* variables that we want in registers, most important first */ 640 #if defined(pdp11) 641 int j; 642 #endif 643 int32_t L0, L1, R0, R1, k; 644 C_block *kp; 645 int ks_inc, loop_count; 646 C_block B; 647 648 L0 = salt; 649 TO_SIX_BIT(salt, L0); /* convert to 4*(6+2) format */ 650 651 #if defined(__vax__) || defined(pdp11) 652 salt = ~salt; /* "x &~ y" is faster than "x & y". */ 653 #define SALT (~salt) 654 #else 655 #define SALT salt 656 #endif 657 658 #if defined(MUST_ALIGN) 659 B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3]; 660 B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7]; 661 LOAD(L,L0,L1,B); 662 #else 663 LOAD(L,L0,L1,*(C_block *)in); 664 #endif 665 LOADREG(R,R0,R1,L,L0,L1); 666 L0 &= 0x55555555L; 667 L1 &= 0x55555555L; 668 L0 = (L0 << 1) | L1; /* L0 is the even-numbered input bits */ 669 R0 &= 0xaaaaaaaaL; 670 R1 = (R1 >> 1) & 0x55555555L; 671 L1 = R0 | R1; /* L1 is the odd-numbered input bits */ 672 STORE(L,L0,L1,B); 673 PERM3264(L,L0,L1,B.b, (C_block *)IE3264); /* even bits */ 674 PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264); /* odd bits */ 675 676 if (num_iter >= 0) 677 { /* encryption */ 678 kp = &KS[0]; 679 ks_inc = sizeof(*kp); 680 } 681 else 682 { /* decryption */ 683 num_iter = -num_iter; 684 kp = &KS[KS_SIZE-1]; 685 ks_inc = -(long)sizeof(*kp); 686 } 687 688 while (--num_iter >= 0) { 689 loop_count = 8; 690 do { 691 692 #define SPTAB(t, i) \ 693 (*(int32_t *)((unsigned char *)t + i*(sizeof(int32_t)/4))) 694 #if defined(gould) 695 /* use this if B.b[i] is evaluated just once ... */ 696 #define DOXOR(x,y,i) x^=SPTAB(SPE[0][i],B.b[i]); y^=SPTAB(SPE[1][i],B.b[i]); 697 #else 698 #if defined(pdp11) 699 /* use this if your "long" int indexing is slow */ 700 #define DOXOR(x,y,i) j=B.b[i]; x^=SPTAB(SPE[0][i],j); y^=SPTAB(SPE[1][i],j); 701 #else 702 /* use this if "k" is allocated to a register ... */ 703 #define DOXOR(x,y,i) k=B.b[i]; x^=SPTAB(SPE[0][i],k); y^=SPTAB(SPE[1][i],k); 704 #endif 705 #endif 706 707 #define CRUNCH(p0, p1, q0, q1) \ 708 k = (q0 ^ q1) & SALT; \ 709 B.b32.i0 = k ^ q0 ^ kp->b32.i0; \ 710 B.b32.i1 = k ^ q1 ^ kp->b32.i1; \ 711 kp = (C_block *)((char *)kp+ks_inc); \ 712 \ 713 DOXOR(p0, p1, 0); \ 714 DOXOR(p0, p1, 1); \ 715 DOXOR(p0, p1, 2); \ 716 DOXOR(p0, p1, 3); \ 717 DOXOR(p0, p1, 4); \ 718 DOXOR(p0, p1, 5); \ 719 DOXOR(p0, p1, 6); \ 720 DOXOR(p0, p1, 7); 721 722 CRUNCH(L0, L1, R0, R1); 723 CRUNCH(R0, R1, L0, L1); 724 } while (--loop_count != 0); 725 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE)); 726 727 728 /* swap L and R */ 729 L0 ^= R0; L1 ^= R1; 730 R0 ^= L0; R1 ^= L1; 731 L0 ^= R0; L1 ^= R1; 732 } 733 734 /* store the encrypted (or decrypted) result */ 735 L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L); 736 L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L); 737 STORE(L,L0,L1,B); 738 PERM6464(L,L0,L1,B.b, (C_block *)CF6464); 739 #if defined(MUST_ALIGN) 740 STORE(L,L0,L1,B); 741 out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3]; 742 out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7]; 743 #else 744 STORE(L,L0,L1,*(C_block *)out); 745 #endif 746 return (0); 747 } 748 749 750 /* 751 * Initialize various tables. This need only be done once. It could even be 752 * done at compile time, if the compiler were capable of that sort of thing. 753 */ 754 STATIC 755 init_des() 756 { 757 int i, j; 758 int32_t k; 759 int tableno; 760 static unsigned char perm[64], tmp32[32]; /* "static" for speed */ 761 762 /* 763 * table that converts chars "./0-9A-Za-z"to integers 0-63. 764 */ 765 for (i = 0; i < 64; i++) 766 a64toi[itoa64[i]] = i; 767 768 /* 769 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2. 770 */ 771 for (i = 0; i < 64; i++) 772 perm[i] = 0; 773 for (i = 0; i < 64; i++) { 774 if ((k = PC2[i]) == 0) 775 continue; 776 k += Rotates[0]-1; 777 if ((k%28) < Rotates[0]) k -= 28; 778 k = PC1[k]; 779 if (k > 0) { 780 k--; 781 k = (k|07) - (k&07); 782 k++; 783 } 784 perm[i] = k; 785 } 786 #ifdef DEBUG 787 prtab("pc1tab", perm, 8); 788 #endif 789 init_perm(PC1ROT, perm, 8, 8); 790 791 /* 792 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2. 793 */ 794 for (j = 0; j < 2; j++) { 795 unsigned char pc2inv[64]; 796 for (i = 0; i < 64; i++) 797 perm[i] = pc2inv[i] = 0; 798 for (i = 0; i < 64; i++) { 799 if ((k = PC2[i]) == 0) 800 continue; 801 pc2inv[k-1] = i+1; 802 } 803 for (i = 0; i < 64; i++) { 804 if ((k = PC2[i]) == 0) 805 continue; 806 k += j; 807 if ((k%28) <= j) k -= 28; 808 perm[i] = pc2inv[k]; 809 } 810 #ifdef DEBUG 811 prtab("pc2tab", perm, 8); 812 #endif 813 init_perm(PC2ROT[j], perm, 8, 8); 814 } 815 816 /* 817 * Bit reverse, then initial permutation, then expansion. 818 */ 819 for (i = 0; i < 8; i++) { 820 for (j = 0; j < 8; j++) { 821 k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1]; 822 if (k > 32) 823 k -= 32; 824 else if (k > 0) 825 k--; 826 if (k > 0) { 827 k--; 828 k = (k|07) - (k&07); 829 k++; 830 } 831 perm[i*8+j] = k; 832 } 833 } 834 #ifdef DEBUG 835 prtab("ietab", perm, 8); 836 #endif 837 init_perm(IE3264, perm, 4, 8); 838 839 /* 840 * Compression, then final permutation, then bit reverse. 841 */ 842 for (i = 0; i < 64; i++) { 843 k = IP[CIFP[i]-1]; 844 if (k > 0) { 845 k--; 846 k = (k|07) - (k&07); 847 k++; 848 } 849 perm[k-1] = i+1; 850 } 851 #ifdef DEBUG 852 prtab("cftab", perm, 8); 853 #endif 854 init_perm(CF6464, perm, 8, 8); 855 856 /* 857 * SPE table 858 */ 859 for (i = 0; i < 48; i++) 860 perm[i] = P32Tr[ExpandTr[i]-1]; 861 for (tableno = 0; tableno < 8; tableno++) { 862 for (j = 0; j < 64; j++) { 863 k = (((j >> 0) &01) << 5)| 864 (((j >> 1) &01) << 3)| 865 (((j >> 2) &01) << 2)| 866 (((j >> 3) &01) << 1)| 867 (((j >> 4) &01) << 0)| 868 (((j >> 5) &01) << 4); 869 k = S[tableno][k]; 870 k = (((k >> 3)&01) << 0)| 871 (((k >> 2)&01) << 1)| 872 (((k >> 1)&01) << 2)| 873 (((k >> 0)&01) << 3); 874 for (i = 0; i < 32; i++) 875 tmp32[i] = 0; 876 for (i = 0; i < 4; i++) 877 tmp32[4 * tableno + i] = (k >> i) & 01; 878 k = 0; 879 for (i = 24; --i >= 0; ) 880 k = (k<<1) | tmp32[perm[i]-1]; 881 TO_SIX_BIT(SPE[0][tableno][j], k); 882 k = 0; 883 for (i = 24; --i >= 0; ) 884 k = (k<<1) | tmp32[perm[i+24]-1]; 885 TO_SIX_BIT(SPE[1][tableno][j], k); 886 } 887 } 888 } 889 890 /* 891 * Initialize "perm" to represent transformation "p", which rearranges 892 * (perhaps with expansion and/or contraction) one packed array of bits 893 * (of size "chars_in" characters) into another array (of size "chars_out" 894 * characters). 895 * 896 * "perm" must be all-zeroes on entry to this routine. 897 */ 898 STATIC 899 init_perm(perm, p, chars_in, chars_out) 900 C_block perm[64/CHUNKBITS][1<<CHUNKBITS]; 901 unsigned char p[64]; 902 int chars_in, chars_out; 903 { 904 int i, j, k, l; 905 906 for (k = 0; k < chars_out*8; k++) { /* each output bit position */ 907 l = p[k] - 1; /* where this bit comes from */ 908 if (l < 0) 909 continue; /* output bit is always 0 */ 910 i = l>>LGCHUNKBITS; /* which chunk this bit comes from */ 911 l = 1<<(l&(CHUNKBITS-1)); /* mask for this bit */ 912 for (j = 0; j < (1<<CHUNKBITS); j++) { /* each chunk value */ 913 if ((j & l) != 0) 914 perm[i][j].b[k>>3] |= 1<<(k&07); 915 } 916 } 917 } 918 919 /* 920 * "setkey" routine (for backwards compatibility) 921 */ 922 int 923 setkey(key) 924 const char *key; 925 { 926 int i, j, k; 927 C_block keyblock; 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)*key++; 934 } 935 keyblock.b[i] = k; 936 } 937 return (des_setkey((char *)keyblock.b)); 938 } 939 940 /* 941 * "encrypt" routine (for backwards compatibility) 942 */ 943 int 944 encrypt(block, flag) 945 char *block; 946 int flag; 947 { 948 int i, j, k; 949 C_block cblock; 950 951 for (i = 0; i < 8; i++) { 952 k = 0; 953 for (j = 0; j < 8; j++) { 954 k <<= 1; 955 k |= (unsigned char)*block++; 956 } 957 cblock.b[i] = k; 958 } 959 if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1))) 960 return (1); 961 for (i = 7; i >= 0; i--) { 962 k = cblock.b[i]; 963 for (j = 7; j >= 0; j--) { 964 *--block = k&01; 965 k >>= 1; 966 } 967 } 968 return (0); 969 } 970 971 #ifdef DEBUG 972 STATIC 973 prtab(s, t, num_rows) 974 char *s; 975 unsigned char *t; 976 int num_rows; 977 { 978 int i, j; 979 980 (void)printf("%s:\n", s); 981 for (i = 0; i < num_rows; i++) { 982 for (j = 0; j < 8; j++) { 983 (void)printf("%3d", t[i*8+j]); 984 } 985 (void)printf("\n"); 986 } 987 (void)printf("\n"); 988 } 989 #endif 990