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