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