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