granicus.if.org Git - postgresql/blob - src/port/crypt.c

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