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