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