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