src/des/crypt.c

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