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