1 /* $NetBSD: crypt.c,v 1.6 1997/07/02 04:55:41 mikel 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 #if defined(LIBC_SCCS) && !defined(lint) 40 #if 0 41 static char sccsid[] = "@(#)crypt.c 8.1.1.1 (Berkeley) 8/18/93"; 42 #endif 43 static char rcsid[] = "$NetBSD: crypt.c,v 1.6 1997/07/02 04:55:41 mikel Exp $"; 44 #endif /* LIBC_SCCS and not lint */ 45 46 #include <limits.h> 47 #include <pwd.h> 48 #include <unistd.h> 49 50 /* 51 * UNIX password, and DES, encryption. 52 * By Tom Truscott, trt@rti.rti.org, 53 * from algorithms by Robert W. Baldwin and James Gillogly. 54 * 55 * References: 56 * "Mathematical Cryptology for Computer Scientists and Mathematicians," 57 * by Wayne Patterson, 1987, ISBN 0-8476-7438-X. 58 * 59 * "Password Security: A Case History," R. Morris and Ken Thompson, 60 * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979. 61 * 62 * "DES will be Totally Insecure within Ten Years," M.E. Hellman, 63 * IEEE Spectrum, vol. 16, pp. 32-39, July 1979. 64 */ 65 66 /* ===== Configuration ==================== */ 67 68 /* 69 * define "MUST_ALIGN" if your compiler cannot load/store 70 * long integers at arbitrary (e.g. odd) memory locations. 71 * (Either that or never pass unaligned addresses to des_cipher!) 72 */ 73 #if !defined(vax) 74 #define MUST_ALIGN 75 #endif 76 77 #ifdef CHAR_BITS 78 #if CHAR_BITS != 8 79 #error C_block structure assumes 8 bit characters 80 #endif 81 #endif 82 83 /* 84 * define "B64" to be the declaration for a 64 bit integer. 85 * XXX this feature is currently unused, see "endian" comment below. 86 */ 87 #if defined(cray) 88 #define B64 long 89 #endif 90 #if defined(convex) 91 #define B64 long long 92 #endif 93 94 /* 95 * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes 96 * of lookup tables. This speeds up des_setkey() and des_cipher(), but has 97 * little effect on crypt(). 98 */ 99 #if defined(notdef) 100 #define LARGEDATA 101 #endif 102 103 /* compile with "-DSTATIC=void" when profiling */ 104 #ifndef STATIC 105 #define STATIC static void 106 #endif 107 STATIC init_des(), init_perm(), permute(); 108 #ifdef DEBUG 109 STATIC prtab(); 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 289 STATIC 290 permute(cp, out, p, chars_in) 291 unsigned char *cp; 292 C_block *out; 293 register C_block *p; 294 int chars_in; 295 { 296 register DCL_BLOCK(D,D0,D1); 297 register C_block *tp; 298 register int t; 299 300 ZERO(D,D0,D1); 301 do { 302 t = *cp++; 303 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 304 tp = &p[t>>4]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 305 } while (--chars_in > 0); 306 STORE(D,D0,D1,*out); 307 } 308 #endif /* LARGEDATA */ 309 310 311 /* ===== (mostly) Standard DES Tables ==================== */ 312 313 static unsigned char IP[] = { /* initial permutation */ 314 58, 50, 42, 34, 26, 18, 10, 2, 315 60, 52, 44, 36, 28, 20, 12, 4, 316 62, 54, 46, 38, 30, 22, 14, 6, 317 64, 56, 48, 40, 32, 24, 16, 8, 318 57, 49, 41, 33, 25, 17, 9, 1, 319 59, 51, 43, 35, 27, 19, 11, 3, 320 61, 53, 45, 37, 29, 21, 13, 5, 321 63, 55, 47, 39, 31, 23, 15, 7, 322 }; 323 324 /* The final permutation is the inverse of IP - no table is necessary */ 325 326 static unsigned char ExpandTr[] = { /* expansion operation */ 327 32, 1, 2, 3, 4, 5, 328 4, 5, 6, 7, 8, 9, 329 8, 9, 10, 11, 12, 13, 330 12, 13, 14, 15, 16, 17, 331 16, 17, 18, 19, 20, 21, 332 20, 21, 22, 23, 24, 25, 333 24, 25, 26, 27, 28, 29, 334 28, 29, 30, 31, 32, 1, 335 }; 336 337 static unsigned char PC1[] = { /* permuted choice table 1 */ 338 57, 49, 41, 33, 25, 17, 9, 339 1, 58, 50, 42, 34, 26, 18, 340 10, 2, 59, 51, 43, 35, 27, 341 19, 11, 3, 60, 52, 44, 36, 342 343 63, 55, 47, 39, 31, 23, 15, 344 7, 62, 54, 46, 38, 30, 22, 345 14, 6, 61, 53, 45, 37, 29, 346 21, 13, 5, 28, 20, 12, 4, 347 }; 348 349 static unsigned char Rotates[] = { /* PC1 rotation schedule */ 350 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 351 }; 352 353 /* note: each "row" of PC2 is left-padded with bits that make it invertible */ 354 static unsigned char PC2[] = { /* permuted choice table 2 */ 355 9, 18, 14, 17, 11, 24, 1, 5, 356 22, 25, 3, 28, 15, 6, 21, 10, 357 35, 38, 23, 19, 12, 4, 26, 8, 358 43, 54, 16, 7, 27, 20, 13, 2, 359 360 0, 0, 41, 52, 31, 37, 47, 55, 361 0, 0, 30, 40, 51, 45, 33, 48, 362 0, 0, 44, 49, 39, 56, 34, 53, 363 0, 0, 46, 42, 50, 36, 29, 32, 364 }; 365 366 static unsigned char S[8][64] = { /* 48->32 bit substitution tables */ 367 /* S[1] */ 368 { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 369 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 370 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 371 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13 }, 372 /* S[2] */ 373 { 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 374 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 375 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 376 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9 }, 377 /* S[3] */ 378 { 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 379 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 380 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 381 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12 }, 382 /* S[4] */ 383 { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 384 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 385 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 386 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14 }, 387 /* S[5] */ 388 { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 389 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 390 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 391 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3 }, 392 /* S[6] */ 393 { 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 394 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 395 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 396 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13 }, 397 /* S[7] */ 398 { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 399 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 400 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 401 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12 }, 402 /* S[8] */ 403 { 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 404 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 405 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 406 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11 } 407 }; 408 409 static unsigned char P32Tr[] = { /* 32-bit permutation function */ 410 16, 7, 20, 21, 411 29, 12, 28, 17, 412 1, 15, 23, 26, 413 5, 18, 31, 10, 414 2, 8, 24, 14, 415 32, 27, 3, 9, 416 19, 13, 30, 6, 417 22, 11, 4, 25, 418 }; 419 420 static unsigned char CIFP[] = { /* compressed/interleaved permutation */ 421 1, 2, 3, 4, 17, 18, 19, 20, 422 5, 6, 7, 8, 21, 22, 23, 24, 423 9, 10, 11, 12, 25, 26, 27, 28, 424 13, 14, 15, 16, 29, 30, 31, 32, 425 426 33, 34, 35, 36, 49, 50, 51, 52, 427 37, 38, 39, 40, 53, 54, 55, 56, 428 41, 42, 43, 44, 57, 58, 59, 60, 429 45, 46, 47, 48, 61, 62, 63, 64, 430 }; 431 432 static unsigned char itoa64[] = /* 0..63 => ascii-64 */ 433 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 434 435 436 /* ===== Tables that are initialized at run time ==================== */ 437 438 439 static unsigned char a64toi[128]; /* ascii-64 => 0..63 */ 440 441 /* Initial key schedule permutation */ 442 static C_block PC1ROT[64/CHUNKBITS][1<<CHUNKBITS]; 443 444 /* Subsequent key schedule rotation permutations */ 445 static C_block PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS]; 446 447 /* Initial permutation/expansion table */ 448 static C_block IE3264[32/CHUNKBITS][1<<CHUNKBITS]; 449 450 /* Table that combines the S, P, and E operations. */ 451 static int32_t SPE[2][8][64]; 452 453 /* compressed/interleaved => final permutation table */ 454 static C_block CF6464[64/CHUNKBITS][1<<CHUNKBITS]; 455 456 457 /* ==================================== */ 458 459 460 static C_block constdatablock; /* encryption constant */ 461 static char cryptresult[1+4+4+11+1]; /* encrypted result */ 462 463 /* 464 * Return a pointer to static data consisting of the "setting" 465 * followed by an encryption produced by the "key" and "setting". 466 */ 467 char * 468 crypt(key, setting) 469 register const char *key; 470 register const char *setting; 471 { 472 register char *encp; 473 register int32_t i; 474 register int t; 475 int32_t salt; 476 int num_iter, salt_size; 477 C_block keyblock, rsltblock; 478 479 for (i = 0; i < 8; i++) { 480 if ((t = 2*(unsigned char)(*key)) != 0) 481 key++; 482 keyblock.b[i] = t; 483 } 484 if (des_setkey((char *)keyblock.b)) /* also initializes "a64toi" */ 485 return (NULL); 486 487 encp = &cryptresult[0]; 488 switch (*setting) { 489 case _PASSWORD_EFMT1: 490 /* 491 * Involve the rest of the password 8 characters at a time. 492 */ 493 while (*key) { 494 if (des_cipher((char *)&keyblock, 495 (char *)&keyblock, 0L, 1)) 496 return (NULL); 497 for (i = 0; i < 8; i++) { 498 if ((t = 2*(unsigned char)(*key)) != 0) 499 key++; 500 keyblock.b[i] ^= t; 501 } 502 if (des_setkey((char *)keyblock.b)) 503 return (NULL); 504 } 505 506 *encp++ = *setting++; 507 508 /* get iteration count */ 509 num_iter = 0; 510 for (i = 4; --i >= 0; ) { 511 if ((t = (unsigned char)setting[i]) == '\0') 512 t = '.'; 513 encp[i] = t; 514 num_iter = (num_iter<<6) | a64toi[t]; 515 } 516 setting += 4; 517 encp += 4; 518 salt_size = 4; 519 break; 520 default: 521 num_iter = 25; 522 salt_size = 2; 523 } 524 525 salt = 0; 526 for (i = salt_size; --i >= 0; ) { 527 if ((t = (unsigned char)setting[i]) == '\0') 528 t = '.'; 529 encp[i] = t; 530 salt = (salt<<6) | a64toi[t]; 531 } 532 encp += salt_size; 533 if (des_cipher((char *)&constdatablock, (char *)&rsltblock, 534 salt, num_iter)) 535 return (NULL); 536 537 /* 538 * Encode the 64 cipher bits as 11 ascii characters. 539 */ 540 i = ((int32_t)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | 541 rsltblock.b[2]; 542 encp[3] = itoa64[i&0x3f]; i >>= 6; 543 encp[2] = itoa64[i&0x3f]; i >>= 6; 544 encp[1] = itoa64[i&0x3f]; i >>= 6; 545 encp[0] = itoa64[i]; encp += 4; 546 i = ((int32_t)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | 547 rsltblock.b[5]; 548 encp[3] = itoa64[i&0x3f]; i >>= 6; 549 encp[2] = itoa64[i&0x3f]; i >>= 6; 550 encp[1] = itoa64[i&0x3f]; i >>= 6; 551 encp[0] = itoa64[i]; encp += 4; 552 i = ((int32_t)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2; 553 encp[2] = itoa64[i&0x3f]; i >>= 6; 554 encp[1] = itoa64[i&0x3f]; i >>= 6; 555 encp[0] = itoa64[i]; 556 557 encp[3] = 0; 558 559 return (cryptresult); 560 } 561 562 563 /* 564 * The Key Schedule, filled in by des_setkey() or setkey(). 565 */ 566 #define KS_SIZE 16 567 static C_block KS[KS_SIZE]; 568 569 /* 570 * Set up the key schedule from the key. 571 */ 572 int 573 des_setkey(key) 574 register const char *key; 575 { 576 register DCL_BLOCK(K, K0, K1); 577 register C_block *ptabp; 578 register int i; 579 static int des_ready = 0; 580 581 if (!des_ready) { 582 init_des(); 583 des_ready = 1; 584 } 585 586 PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT); 587 key = (char *)&KS[0]; 588 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key); 589 for (i = 1; i < 16; i++) { 590 key += sizeof(C_block); 591 STORE(K,K0,K1,*(C_block *)key); 592 ptabp = (C_block *)PC2ROT[Rotates[i]-1]; 593 PERM6464(K,K0,K1,(unsigned char *)key,ptabp); 594 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key); 595 } 596 return (0); 597 } 598 599 /* 600 * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter) 601 * iterations of DES, using the the given 24-bit salt and the pre-computed key 602 * schedule, and store the resulting 8 chars at "out" (in == out is permitted). 603 * 604 * NOTE: the performance of this routine is critically dependent on your 605 * compiler and machine architecture. 606 */ 607 int 608 des_cipher(in, out, salt, num_iter) 609 const char *in; 610 char *out; 611 long salt; 612 int num_iter; 613 { 614 /* variables that we want in registers, most important first */ 615 #if defined(pdp11) 616 register int j; 617 #endif 618 register int32_t L0, L1, R0, R1, k; 619 register C_block *kp; 620 register int ks_inc, loop_count; 621 C_block B; 622 623 L0 = salt; 624 TO_SIX_BIT(salt, L0); /* convert to 4*(6+2) format */ 625 626 #if defined(vax) || defined(pdp11) 627 salt = ~salt; /* "x &~ y" is faster than "x & y". */ 628 #define SALT (~salt) 629 #else 630 #define SALT salt 631 #endif 632 633 #if defined(MUST_ALIGN) 634 B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3]; 635 B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7]; 636 LOAD(L,L0,L1,B); 637 #else 638 LOAD(L,L0,L1,*(C_block *)in); 639 #endif 640 LOADREG(R,R0,R1,L,L0,L1); 641 L0 &= 0x55555555L; 642 L1 &= 0x55555555L; 643 L0 = (L0 << 1) | L1; /* L0 is the even-numbered input bits */ 644 R0 &= 0xaaaaaaaaL; 645 R1 = (R1 >> 1) & 0x55555555L; 646 L1 = R0 | R1; /* L1 is the odd-numbered input bits */ 647 STORE(L,L0,L1,B); 648 PERM3264(L,L0,L1,B.b, (C_block *)IE3264); /* even bits */ 649 PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264); /* odd bits */ 650 651 if (num_iter >= 0) 652 { /* encryption */ 653 kp = &KS[0]; 654 ks_inc = sizeof(*kp); 655 } 656 else 657 { /* decryption */ 658 return (1); /* always fail */ 659 } 660 661 while (--num_iter >= 0) { 662 loop_count = 8; 663 do { 664 665 #define SPTAB(t, i) \ 666 (*(int32_t *)((unsigned char *)t + i*(sizeof(int32_t)/4))) 667 #if defined(gould) 668 /* use this if B.b[i] is evaluated just once ... */ 669 #define DOXOR(x,y,i) x^=SPTAB(SPE[0][i],B.b[i]); y^=SPTAB(SPE[1][i],B.b[i]); 670 #else 671 #if defined(pdp11) 672 /* use this if your "long" int indexing is slow */ 673 #define DOXOR(x,y,i) j=B.b[i]; x^=SPTAB(SPE[0][i],j); y^=SPTAB(SPE[1][i],j); 674 #else 675 /* use this if "k" is allocated to a register ... */ 676 #define DOXOR(x,y,i) k=B.b[i]; x^=SPTAB(SPE[0][i],k); y^=SPTAB(SPE[1][i],k); 677 #endif 678 #endif 679 680 #define CRUNCH(p0, p1, q0, q1) \ 681 k = (q0 ^ q1) & SALT; \ 682 B.b32.i0 = k ^ q0 ^ kp->b32.i0; \ 683 B.b32.i1 = k ^ q1 ^ kp->b32.i1; \ 684 kp = (C_block *)((char *)kp+ks_inc); \ 685 \ 686 DOXOR(p0, p1, 0); \ 687 DOXOR(p0, p1, 1); \ 688 DOXOR(p0, p1, 2); \ 689 DOXOR(p0, p1, 3); \ 690 DOXOR(p0, p1, 4); \ 691 DOXOR(p0, p1, 5); \ 692 DOXOR(p0, p1, 6); \ 693 DOXOR(p0, p1, 7); 694 695 CRUNCH(L0, L1, R0, R1); 696 CRUNCH(R0, R1, L0, L1); 697 } while (--loop_count != 0); 698 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE)); 699 700 701 /* swap L and R */ 702 L0 ^= R0; L1 ^= R1; 703 R0 ^= L0; R1 ^= L1; 704 L0 ^= R0; L1 ^= R1; 705 } 706 707 /* store the encrypted (or decrypted) result */ 708 L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L); 709 L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L); 710 STORE(L,L0,L1,B); 711 PERM6464(L,L0,L1,B.b, (C_block *)CF6464); 712 #if defined(MUST_ALIGN) 713 STORE(L,L0,L1,B); 714 out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3]; 715 out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7]; 716 #else 717 STORE(L,L0,L1,*(C_block *)out); 718 #endif 719 return (0); 720 } 721 722 723 /* 724 * Initialize various tables. This need only be done once. It could even be 725 * done at compile time, if the compiler were capable of that sort of thing. 726 */ 727 STATIC 728 init_des() 729 { 730 register int i, j; 731 register int32_t k; 732 register int tableno; 733 static unsigned char perm[64], tmp32[32]; /* "static" for speed */ 734 735 /* 736 * table that converts chars "./0-9A-Za-z"to integers 0-63. 737 */ 738 for (i = 0; i < 64; i++) 739 a64toi[itoa64[i]] = i; 740 741 /* 742 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2. 743 */ 744 for (i = 0; i < 64; i++) 745 perm[i] = 0; 746 for (i = 0; i < 64; i++) { 747 if ((k = PC2[i]) == 0) 748 continue; 749 k += Rotates[0]-1; 750 if ((k%28) < Rotates[0]) k -= 28; 751 k = PC1[k]; 752 if (k > 0) { 753 k--; 754 k = (k|07) - (k&07); 755 k++; 756 } 757 perm[i] = k; 758 } 759 #ifdef DEBUG 760 prtab("pc1tab", perm, 8); 761 #endif 762 init_perm(PC1ROT, perm, 8, 8); 763 764 /* 765 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2. 766 */ 767 for (j = 0; j < 2; j++) { 768 unsigned char pc2inv[64]; 769 for (i = 0; i < 64; i++) 770 perm[i] = pc2inv[i] = 0; 771 for (i = 0; i < 64; i++) { 772 if ((k = PC2[i]) == 0) 773 continue; 774 pc2inv[k-1] = i+1; 775 } 776 for (i = 0; i < 64; i++) { 777 if ((k = PC2[i]) == 0) 778 continue; 779 k += j; 780 if ((k%28) <= j) k -= 28; 781 perm[i] = pc2inv[k]; 782 } 783 #ifdef DEBUG 784 prtab("pc2tab", perm, 8); 785 #endif 786 init_perm(PC2ROT[j], perm, 8, 8); 787 } 788 789 /* 790 * Bit reverse, then initial permutation, then expansion. 791 */ 792 for (i = 0; i < 8; i++) { 793 for (j = 0; j < 8; j++) { 794 k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1]; 795 if (k > 32) 796 k -= 32; 797 else if (k > 0) 798 k--; 799 if (k > 0) { 800 k--; 801 k = (k|07) - (k&07); 802 k++; 803 } 804 perm[i*8+j] = k; 805 } 806 } 807 #ifdef DEBUG 808 prtab("ietab", perm, 8); 809 #endif 810 init_perm(IE3264, perm, 4, 8); 811 812 /* 813 * Compression, then final permutation, then bit reverse. 814 */ 815 for (i = 0; i < 64; i++) { 816 k = IP[CIFP[i]-1]; 817 if (k > 0) { 818 k--; 819 k = (k|07) - (k&07); 820 k++; 821 } 822 perm[k-1] = i+1; 823 } 824 #ifdef DEBUG 825 prtab("cftab", perm, 8); 826 #endif 827 init_perm(CF6464, perm, 8, 8); 828 829 /* 830 * SPE table 831 */ 832 for (i = 0; i < 48; i++) 833 perm[i] = P32Tr[ExpandTr[i]-1]; 834 for (tableno = 0; tableno < 8; tableno++) { 835 for (j = 0; j < 64; j++) { 836 k = (((j >> 0) &01) << 5)| 837 (((j >> 1) &01) << 3)| 838 (((j >> 2) &01) << 2)| 839 (((j >> 3) &01) << 1)| 840 (((j >> 4) &01) << 0)| 841 (((j >> 5) &01) << 4); 842 k = S[tableno][k]; 843 k = (((k >> 3)&01) << 0)| 844 (((k >> 2)&01) << 1)| 845 (((k >> 1)&01) << 2)| 846 (((k >> 0)&01) << 3); 847 for (i = 0; i < 32; i++) 848 tmp32[i] = 0; 849 for (i = 0; i < 4; i++) 850 tmp32[4 * tableno + i] = (k >> i) & 01; 851 k = 0; 852 for (i = 24; --i >= 0; ) 853 k = (k<<1) | tmp32[perm[i]-1]; 854 TO_SIX_BIT(SPE[0][tableno][j], k); 855 k = 0; 856 for (i = 24; --i >= 0; ) 857 k = (k<<1) | tmp32[perm[i+24]-1]; 858 TO_SIX_BIT(SPE[1][tableno][j], k); 859 } 860 } 861 } 862 863 /* 864 * Initialize "perm" to represent transformation "p", which rearranges 865 * (perhaps with expansion and/or contraction) one packed array of bits 866 * (of size "chars_in" characters) into another array (of size "chars_out" 867 * characters). 868 * 869 * "perm" must be all-zeroes on entry to this routine. 870 */ 871 STATIC 872 init_perm(perm, p, chars_in, chars_out) 873 C_block perm[64/CHUNKBITS][1<<CHUNKBITS]; 874 unsigned char p[64]; 875 int chars_in, chars_out; 876 { 877 register int i, j, k, l; 878 879 for (k = 0; k < chars_out*8; k++) { /* each output bit position */ 880 l = p[k] - 1; /* where this bit comes from */ 881 if (l < 0) 882 continue; /* output bit is always 0 */ 883 i = l>>LGCHUNKBITS; /* which chunk this bit comes from */ 884 l = 1<<(l&(CHUNKBITS-1)); /* mask for this bit */ 885 for (j = 0; j < (1<<CHUNKBITS); j++) { /* each chunk value */ 886 if ((j & l) != 0) 887 perm[i][j].b[k>>3] |= 1<<(k&07); 888 } 889 } 890 } 891 892 /* 893 * "setkey" routine (for backwards compatibility) 894 */ 895 int 896 setkey(key) 897 register const char *key; 898 { 899 register int i, j, k; 900 C_block keyblock; 901 902 for (i = 0; i < 8; i++) { 903 k = 0; 904 for (j = 0; j < 8; j++) { 905 k <<= 1; 906 k |= (unsigned char)*key++; 907 } 908 keyblock.b[i] = k; 909 } 910 return (des_setkey((char *)keyblock.b)); 911 } 912 913 /* 914 * "encrypt" routine (for backwards compatibility) 915 */ 916 int 917 encrypt(block, flag) 918 register char *block; 919 int flag; 920 { 921 register int i, j, k; 922 C_block cblock; 923 924 for (i = 0; i < 8; i++) { 925 k = 0; 926 for (j = 0; j < 8; j++) { 927 k <<= 1; 928 k |= (unsigned char)*block++; 929 } 930 cblock.b[i] = k; 931 } 932 if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1))) 933 return (1); 934 for (i = 7; i >= 0; i--) { 935 k = cblock.b[i]; 936 for (j = 7; j >= 0; j--) { 937 *--block = k&01; 938 k >>= 1; 939 } 940 } 941 return (0); 942 } 943 944 #ifdef DEBUG 945 STATIC 946 prtab(s, t, num_rows) 947 char *s; 948 unsigned char *t; 949 int num_rows; 950 { 951 register int i, j; 952 953 (void)printf("%s:\n", s); 954 for (i = 0; i < num_rows; i++) { 955 for (j = 0; j < 8; j++) { 956 (void)printf("%3d", t[i*8+j]); 957 } 958 (void)printf("\n"); 959 } 960 (void)printf("\n"); 961 } 962 #endif 963