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