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