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

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