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