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