Ruby  2.0.0p247(2013-06-27revision41674)
missing/crypt.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1989, 1993
00003  *      The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Tom Truscott.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. Neither the name of the University nor the names of its contributors
00017  *    may be used to endorse or promote products derived from this software
00018  *    without specific prior written permission.
00019  *
00020  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00021  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00022  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00023  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00024  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00025  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00026  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00027  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00028  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00029  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00030  * SUCH DAMAGE.
00031  */
00032 
00033 #if defined(LIBC_SCCS) && !defined(lint)
00034 static char sccsid[] = "@(#)crypt.c     8.1 (Berkeley) 6/4/93";
00035 #endif /* LIBC_SCCS and not lint */
00036 
00037 #include "ruby/missing.h"
00038 #ifdef HAVE_UNISTD_H
00039 #include <unistd.h>
00040 #endif
00041 #include <limits.h>
00042 #ifdef HAVE_PWD_H
00043 #include <pwd.h>
00044 #endif
00045 #include <stdio.h>
00046 #ifndef _PASSWORD_EFMT1
00047 #define _PASSWORD_EFMT1 '_'
00048 #endif
00049 
00050 /*
00051  * UNIX password, and DES, encryption.
00052  * By Tom Truscott, trt@rti.rti.org,
00053  * from algorithms by Robert W. Baldwin and James Gillogly.
00054  *
00055  * References:
00056  * "Mathematical Cryptology for Computer Scientists and Mathematicians,"
00057  * by Wayne Patterson, 1987, ISBN 0-8476-7438-X.
00058  *
00059  * "Password Security: A Case History," R. Morris and Ken Thompson,
00060  * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979.
00061  *
00062  * "DES will be Totally Insecure within Ten Years," M.E. Hellman,
00063  * IEEE Spectrum, vol. 16, pp. 32-39, July 1979.
00064  */
00065 
00066 /* =====  Configuration ==================== */
00067 
00068 /*
00069  * define "MUST_ALIGN" if your compiler cannot load/store
00070  * long integers at arbitrary (e.g. odd) memory locations.
00071  * (Either that or never pass unaligned addresses to des_cipher!)
00072  */
00073 #if !defined(vax)
00074 #define MUST_ALIGN
00075 #endif
00076 
00077 #ifdef CHAR_BITS
00078 #if CHAR_BITS != 8
00079         #error C_block structure assumes 8 bit characters
00080 #endif
00081 #endif
00082 
00083 /*
00084  * define "LONG_IS_32_BITS" only if sizeof(long)==4.
00085  * This avoids use of bit fields (your compiler may be sloppy with them).
00086  */
00087 #if !defined(cray)
00088 #define LONG_IS_32_BITS
00089 #endif
00090 
00091 /*
00092  * define "B64" to be the declaration for a 64 bit integer.
00093  * XXX this feature is currently unused, see "endian" comment below.
00094  */
00095 #if defined(cray)
00096 #define B64     long
00097 #endif
00098 #if defined(convex)
00099 #define B64     long long
00100 #endif
00101 
00102 /*
00103  * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes
00104  * of lookup tables.  This speeds up des_setkey() and des_cipher(), but has
00105  * little effect on crypt().
00106  */
00107 #if defined(notdef)
00108 #define LARGEDATA
00109 #endif
00110 
00111 int des_setkey(), des_cipher();
00112 
00113 /* compile with "-DSTATIC=int" when profiling */
00114 #ifndef STATIC
00115 #define STATIC  static
00116 #endif
00117 STATIC void init_des(), init_perm(), permute();
00118 #ifdef DEBUG
00119 STATIC void prtab();
00120 #endif
00121 
00122 /* ==================================== */
00123 
00124 /*
00125  * Cipher-block representation (Bob Baldwin):
00126  *
00127  * DES operates on groups of 64 bits, numbered 1..64 (sigh).  One
00128  * representation is to store one bit per byte in an array of bytes.  Bit N of
00129  * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array.
00130  * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the
00131  * first byte, 9..16 in the second, and so on.  The DES spec apparently has
00132  * bit 1 in the MSB of the first byte, but that is particularly noxious so we
00133  * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is
00134  * the MSB of the first byte.  Specifically, the 64-bit input data and key are
00135  * converted to LSB format, and the output 64-bit block is converted back into
00136  * MSB format.
00137  *
00138  * DES operates internally on groups of 32 bits which are expanded to 48 bits
00139  * by permutation E and shrunk back to 32 bits by the S boxes.  To speed up
00140  * the computation, the expansion is applied only once, the expanded
00141  * representation is maintained during the encryption, and a compression
00142  * permutation is applied only at the end.  To speed up the S-box lookups,
00143  * the 48 bits are maintained as eight 6 bit groups, one per byte, which
00144  * directly feed the eight S-boxes.  Within each byte, the 6 bits are the
00145  * most significant ones.  The low two bits of each byte are zero.  (Thus,
00146  * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the
00147  * first byte in the eight byte representation, bit 2 of the 48 bit value is
00148  * the "8"-valued bit, and so on.)  In fact, a combined "SPE"-box lookup is
00149  * used, in which the output is the 64 bit result of an S-box lookup which
00150  * has been permuted by P and expanded by E, and is ready for use in the next
00151  * iteration.  Two 32-bit wide tables, SPE[0] and SPE[1], are used for this
00152  * lookup.  Since each byte in the 48 bit path is a multiple of four, indexed
00153  * lookup of SPE[0] and SPE[1] is simple and fast.  The key schedule and
00154  * "salt" are also converted to this 8*(6+2) format.  The SPE table size is
00155  * 8*64*8 = 4K bytes.
00156  *
00157  * To speed up bit-parallel operations (such as XOR), the 8 byte
00158  * representation is "union"ed with 32 bit values "i0" and "i1", and, on
00159  * machines which support it, a 64 bit value "b64".  This data structure,
00160  * "C_block", has two problems.  First, alignment restrictions must be
00161  * honored.  Second, the byte-order (e.g. little-endian or big-endian) of
00162  * the architecture becomes visible.
00163  *
00164  * The byte-order problem is unfortunate, since on the one hand it is good
00165  * to have a machine-independent C_block representation (bits 1..8 in the
00166  * first byte, etc.), and on the other hand it is good for the LSB of the
00167  * first byte to be the LSB of i0.  We cannot have both these things, so we
00168  * currently use the "little-endian" representation and avoid any multi-byte
00169  * operations that depend on byte order.  This largely precludes use of the
00170  * 64-bit datatype since the relative order of i0 and i1 are unknown.  It
00171  * also inhibits grouping the SPE table to look up 12 bits at a time.  (The
00172  * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1
00173  * high-order zero, providing fast indexing into a 64-bit wide SPE.)  On the
00174  * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup
00175  * requires a 128 kilobyte table, so perhaps this is not a big loss.
00176  *
00177  * Permutation representation (Jim Gillogly):
00178  *
00179  * A transformation is defined by its effect on each of the 8 bytes of the
00180  * 64-bit input.  For each byte we give a 64-bit output that has the bits in
00181  * the input distributed appropriately.  The transformation is then the OR
00182  * of the 8 sets of 64-bits.  This uses 8*256*8 = 16K bytes of storage for
00183  * each transformation.  Unless LARGEDATA is defined, however, a more compact
00184  * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks.
00185  * The smaller table uses 16*16*8 = 2K bytes for each transformation.  This
00186  * is slower but tolerable, particularly for password encryption in which
00187  * the SPE transformation is iterated many times.  The small tables total 9K
00188  * bytes, the large tables total 72K bytes.
00189  *
00190  * The transformations used are:
00191  * IE3264: MSB->LSB conversion, initial permutation, and expansion.
00192  *      This is done by collecting the 32 even-numbered bits and applying
00193  *      a 32->64 bit transformation, and then collecting the 32 odd-numbered
00194  *      bits and applying the same transformation.  Since there are only
00195  *      32 input bits, the IE3264 transformation table is half the size of
00196  *      the usual table.
00197  * CF6464: Compression, final permutation, and LSB->MSB conversion.
00198  *      This is done by two trivial 48->32 bit compressions to obtain
00199  *      a 64-bit block (the bit numbering is given in the "CIFP" table)
00200  *      followed by a 64->64 bit "cleanup" transformation.  (It would
00201  *      be possible to group the bits in the 64-bit block so that 2
00202  *      identical 32->32 bit transformations could be used instead,
00203  *      saving a factor of 4 in space and possibly 2 in time, but
00204  *      byte-ordering and other complications rear their ugly head.
00205  *      Similar opportunities/problems arise in the key schedule
00206  *      transforms.)
00207  * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation.
00208  *      This admittedly baroque 64->64 bit transformation is used to
00209  *      produce the first code (in 8*(6+2) format) of the key schedule.
00210  * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation.
00211  *      It would be possible to define 15 more transformations, each
00212  *      with a different rotation, to generate the entire key schedule.
00213  *      To save space, however, we instead permute each code into the
00214  *      next by using a transformation that "undoes" the PC2 permutation,
00215  *      rotates the code, and then applies PC2.  Unfortunately, PC2
00216  *      transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not
00217  *      invertible.  We get around that problem by using a modified PC2
00218  *      which retains the 8 otherwise-lost bits in the unused low-order
00219  *      bits of each byte.  The low-order bits are cleared when the
00220  *      codes are stored into the key schedule.
00221  * PC2ROT[1]: Same as PC2ROT[0], but with two rotations.
00222  *      This is faster than applying PC2ROT[0] twice,
00223  *
00224  * The Bell Labs "salt" (Bob Baldwin):
00225  *
00226  * The salting is a simple permutation applied to the 48-bit result of E.
00227  * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and
00228  * i+24 of the result are swapped.  The salt is thus a 24 bit number, with
00229  * 16777216 possible values.  (The original salt was 12 bits and could not
00230  * swap bits 13..24 with 36..48.)
00231  *
00232  * It is possible, but ugly, to warp the SPE table to account for the salt
00233  * permutation.  Fortunately, the conditional bit swapping requires only
00234  * about four machine instructions and can be done on-the-fly with about an
00235  * 8% performance penalty.
00236  */
00237 
00238 typedef union {
00239         unsigned char b[8];
00240         struct {
00241 #if defined(LONG_IS_32_BITS)
00242                 /* long is often faster than a 32-bit bit field */
00243                 long    i0;
00244                 long    i1;
00245 #else
00246                 long    i0: 32;
00247                 long    i1: 32;
00248 #endif
00249         } b32;
00250 #if defined(B64)
00251         B64     b64;
00252 #endif
00253 } C_block;
00254 
00255 /*
00256  * Convert twenty-four-bit long in host-order
00257  * to six bits (and 2 low-order zeroes) per char little-endian format.
00258  */
00259 #define TO_SIX_BIT(rslt, src) {                         \
00260                 C_block cvt;                            \
00261                 cvt.b[0] = (unsigned char)(src); (src) >>= 6; \
00262                 cvt.b[1] = (unsigned char)(src); (src) >>= 6; \
00263                 cvt.b[2] = (unsigned char)(src); (src) >>= 6; \
00264                 cvt.b[3] = (unsigned char)(src);                \
00265                 (rslt) = (cvt.b32.i0 & 0x3f3f3f3fL) << 2;       \
00266         }
00267 
00268 /*
00269  * These macros may someday permit efficient use of 64-bit integers.
00270  */
00271 #define ZERO(d,d0,d1)                   ((d0) = 0, (d1) = 0)
00272 #define LOAD(d,d0,d1,bl)                ((d0) = (bl).b32.i0, (d1) = (bl).b32.i1)
00273 #define LOADREG(d,d0,d1,s,s0,s1)        ((d0) = (s0), (d1) = (s1))
00274 #define OR(d,d0,d1,bl)                  ((d0) |= (bl).b32.i0, (d1) |= (bl).b32.i1)
00275 #define STORE(s,s0,s1,bl)               ((bl).b32.i0 = (s0), (bl).b32.i1 = (s1))
00276 #define DCL_BLOCK(d,d0,d1)              long d0, d1
00277 
00278 #if defined(LARGEDATA)
00279         /* Waste memory like crazy.  Also, do permutations in line */
00280 #define LGCHUNKBITS     3
00281 #define CHUNKBITS       (1<<LGCHUNKBITS)
00282 #define PERM6464(d,d0,d1,cpp,p)                         \
00283         LOAD((d),(d0),(d1),(p)[(0<<CHUNKBITS)+(cpp)[0]]);               \
00284         OR ((d),(d0),(d1),(p)[(1<<CHUNKBITS)+(cpp)[1]]);                \
00285         OR ((d),(d0),(d1),(p)[(2<<CHUNKBITS)+(cpp)[2]]);                \
00286         OR ((d),(d0),(d1),(p)[(3<<CHUNKBITS)+(cpp)[3]]);                \
00287         OR (d),(d0),(d1),(p)[(4<<CHUNKBITS)+(cpp)[4]]);         \
00288         OR (d),(d0),(d1),(p)[(5<<CHUNKBITS)+(cpp)[5]]);         \
00289         OR (d),(d0),(d1),(p)[(6<<CHUNKBITS)+(cpp)[6]]);         \
00290         OR (d),(d0),(d1),(p)[(7<<CHUNKBITS)+(cpp)[7]]);
00291 #define PERM3264(d,d0,d1,cpp,p)                         \
00292         LOAD((d),(d0),(d1),(p)[(0<<CHUNKBITS)+(cpp)[0]]);               \
00293         OR ((d),(d0),(d1),(p)[(1<<CHUNKBITS)+(cpp)[1]]);                \
00294         OR ((d),(d0),(d1),(p)[(2<<CHUNKBITS)+(cpp)[2]]);                \
00295         OR ((d),(d0),(d1),(p)[(3<<CHUNKBITS)+(cpp)[3]]);
00296 #else
00297         /* "small data" */
00298 #define LGCHUNKBITS     2
00299 #define CHUNKBITS       (1<<LGCHUNKBITS)
00300 #define PERM6464(d,d0,d1,cpp,p)                         \
00301         { C_block tblk; permute((cpp),&tblk,(p),8); LOAD ((d),(d0),(d1),tblk); }
00302 #define PERM3264(d,d0,d1,cpp,p)                         \
00303         { C_block tblk; permute((cpp),&tblk,(p),4); LOAD ((d),(d0),(d1),tblk); }
00304 
00305 STATIC void
00306 permute(cp, out, p, chars_in)
00307         unsigned char *cp;
00308         C_block *out;
00309         register C_block *p;
00310         int chars_in;
00311 {
00312         register DCL_BLOCK(D,D0,D1);
00313         register C_block *tp;
00314         register int t;
00315 
00316         ZERO(D,D0,D1);
00317         do {
00318                 t = *cp++;
00319                 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
00320                 tp = &p[t>>4];  OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
00321         } while (--chars_in > 0);
00322         STORE(D,D0,D1,*out);
00323 }
00324 #endif /* LARGEDATA */
00325 
00326 
00327 /* =====  (mostly) Standard DES Tables ==================== */
00328 
00329 static unsigned char IP[] = {           /* initial permutation */
00330         58, 50, 42, 34, 26, 18, 10,  2,
00331         60, 52, 44, 36, 28, 20, 12,  4,
00332         62, 54, 46, 38, 30, 22, 14,  6,
00333         64, 56, 48, 40, 32, 24, 16,  8,
00334         57, 49, 41, 33, 25, 17,  9,  1,
00335         59, 51, 43, 35, 27, 19, 11,  3,
00336         61, 53, 45, 37, 29, 21, 13,  5,
00337         63, 55, 47, 39, 31, 23, 15,  7,
00338 };
00339 
00340 /* The final permutation is the inverse of IP - no table is necessary */
00341 
00342 static unsigned char ExpandTr[] = {     /* expansion operation */
00343         32,  1,  2,  3,  4,  5,
00344          4,  5,  6,  7,  8,  9,
00345          8,  9, 10, 11, 12, 13,
00346         12, 13, 14, 15, 16, 17,
00347         16, 17, 18, 19, 20, 21,
00348         20, 21, 22, 23, 24, 25,
00349         24, 25, 26, 27, 28, 29,
00350         28, 29, 30, 31, 32,  1,
00351 };
00352 
00353 static unsigned char PC1[] = {          /* permuted choice table 1 */
00354         57, 49, 41, 33, 25, 17,  9,
00355          1, 58, 50, 42, 34, 26, 18,
00356         10,  2, 59, 51, 43, 35, 27,
00357         19, 11,  3, 60, 52, 44, 36,
00358 
00359         63, 55, 47, 39, 31, 23, 15,
00360          7, 62, 54, 46, 38, 30, 22,
00361         14,  6, 61, 53, 45, 37, 29,
00362         21, 13,  5, 28, 20, 12,  4,
00363 };
00364 
00365 static unsigned char Rotates[] = {      /* PC1 rotation schedule */
00366         1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
00367 };
00368 
00369 /* note: each "row" of PC2 is left-padded with bits that make it invertible */
00370 static unsigned char PC2[] = {          /* permuted choice table 2 */
00371          9, 18,    14, 17, 11, 24,  1,  5,
00372         22, 25,     3, 28, 15,  6, 21, 10,
00373         35, 38,    23, 19, 12,  4, 26,  8,
00374         43, 54,    16,  7, 27, 20, 13,  2,
00375 
00376          0,  0,    41, 52, 31, 37, 47, 55,
00377          0,  0,    30, 40, 51, 45, 33, 48,
00378          0,  0,    44, 49, 39, 56, 34, 53,
00379          0,  0,    46, 42, 50, 36, 29, 32,
00380 };
00381 
00382 static unsigned char S[8][64] = {       /* 48->32 bit substitution tables */
00383     {
00384                                         /* S[1]                 */
00385         14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
00386          0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
00387          4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
00388         15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,
00389     },
00390     {
00391                                         /* S[2]                 */
00392         15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
00393          3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
00394          0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
00395         13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,
00396     },
00397     {
00398                                         /* S[3]                 */
00399         10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
00400         13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
00401         13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
00402          1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,
00403     },
00404     {
00405                                         /* S[4]                 */
00406          7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
00407         13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
00408         10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
00409          3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,
00410     },
00411     {
00412                                         /* S[5]                 */
00413          2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
00414         14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
00415          4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
00416         11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,
00417     },
00418     {
00419                                         /* S[6]                 */
00420         12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
00421         10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
00422          9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
00423          4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,
00424     },
00425     {
00426                                         /* S[7]                 */
00427          4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
00428         13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
00429          1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
00430          6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,
00431     },
00432     {
00433                                         /* S[8]                 */
00434         13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
00435          1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
00436          7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
00437          2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11,
00438     },
00439 };
00440 
00441 static unsigned char P32Tr[] = {        /* 32-bit permutation function */
00442         16,  7, 20, 21,
00443         29, 12, 28, 17,
00444          1, 15, 23, 26,
00445          5, 18, 31, 10,
00446          2,  8, 24, 14,
00447         32, 27,  3,  9,
00448         19, 13, 30,  6,
00449         22, 11,  4, 25,
00450 };
00451 
00452 static unsigned char CIFP[] = {         /* compressed/interleaved permutation */
00453          1,  2,  3,  4,   17, 18, 19, 20,
00454          5,  6,  7,  8,   21, 22, 23, 24,
00455          9, 10, 11, 12,   25, 26, 27, 28,
00456         13, 14, 15, 16,   29, 30, 31, 32,
00457 
00458         33, 34, 35, 36,   49, 50, 51, 52,
00459         37, 38, 39, 40,   53, 54, 55, 56,
00460         41, 42, 43, 44,   57, 58, 59, 60,
00461         45, 46, 47, 48,   61, 62, 63, 64,
00462 };
00463 
00464 static unsigned char itoa64[] =         /* 0..63 => ascii-64 */
00465         "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
00466 
00467 
00468 /* =====  Tables that are initialized at run time  ==================== */
00469 
00470 
00471 static unsigned char a64toi[128];       /* ascii-64 => 0..63 */
00472 
00473 /* Initial key schedule permutation */
00474 static C_block  PC1ROT[64/CHUNKBITS][1<<CHUNKBITS];
00475 
00476 /* Subsequent key schedule rotation permutations */
00477 static C_block  PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS];
00478 
00479 /* Initial permutation/expansion table */
00480 static C_block  IE3264[32/CHUNKBITS][1<<CHUNKBITS];
00481 
00482 /* Table that combines the S, P, and E operations.  */
00483 static long SPE[2][8][64];
00484 
00485 /* compressed/interleaved => final permutation table */
00486 static C_block  CF6464[64/CHUNKBITS][1<<CHUNKBITS];
00487 
00488 
00489 /* ==================================== */
00490 
00491 
00492 static C_block  constdatablock;                 /* encryption constant */
00493 static char     cryptresult[1+4+4+11+1];        /* encrypted result */
00494 
00495 /*
00496  * Return a pointer to static data consisting of the "setting"
00497  * followed by an encryption produced by the "key" and "setting".
00498  */
00499 char *
00500 crypt(key, setting)
00501         register const char *key;
00502         register const char *setting;
00503 {
00504         register char *encp;
00505         register long i;
00506         register int t;
00507         long salt;
00508         int num_iter, salt_size;
00509         C_block keyblock, rsltblock;
00510 
00511         for (i = 0; i < 8; i++) {
00512                 if ((t = 2*(unsigned char)(*key)) != 0)
00513                         key++;
00514                 keyblock.b[i] = t;
00515         }
00516         if (des_setkey((char *)keyblock.b))     /* also initializes "a64toi" */
00517                 return (NULL);
00518 
00519         encp = &cryptresult[0];
00520         switch (*setting) {
00521         case _PASSWORD_EFMT1:
00522                 /*
00523                  * Involve the rest of the password 8 characters at a time.
00524                  */
00525                 while (*key) {
00526                         if (des_cipher((char *)&keyblock,
00527                             (char *)&keyblock, 0L, 1))
00528                                 return (NULL);
00529                         for (i = 0; i < 8; i++) {
00530                                 if ((t = 2*(unsigned char)(*key)) != 0)
00531                                         key++;
00532                                 keyblock.b[i] ^= t;
00533                         }
00534                         if (des_setkey((char *)keyblock.b))
00535                                 return (NULL);
00536                 }
00537 
00538                 *encp++ = *setting++;
00539 
00540                 /* get iteration count */
00541                 num_iter = 0;
00542                 for (i = 4; --i >= 0; ) {
00543                         if ((t = (unsigned char)setting[i]) == '\0')
00544                                 t = '.';
00545                         encp[i] = t;
00546                         num_iter = (num_iter<<6) | a64toi[t];
00547                 }
00548                 setting += 4;
00549                 encp += 4;
00550                 salt_size = 4;
00551                 break;
00552         default:
00553                 num_iter = 25;
00554                 salt_size = 2;
00555         }
00556 
00557         salt = 0;
00558         for (i = salt_size; --i >= 0; ) {
00559                 if ((t = (unsigned char)setting[i]) == '\0')
00560                         t = '.';
00561                 encp[i] = t;
00562                 salt = (salt<<6) | a64toi[t];
00563         }
00564         encp += salt_size;
00565         if (des_cipher((char *)&constdatablock, (char *)&rsltblock,
00566             salt, num_iter))
00567                 return (NULL);
00568 
00569         /*
00570          * Encode the 64 cipher bits as 11 ascii characters.
00571          */
00572         i = ((long)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | rsltblock.b[2];
00573         encp[3] = itoa64[i&0x3f];       i >>= 6;
00574         encp[2] = itoa64[i&0x3f];       i >>= 6;
00575         encp[1] = itoa64[i&0x3f];       i >>= 6;
00576         encp[0] = itoa64[i];            encp += 4;
00577         i = ((long)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | rsltblock.b[5];
00578         encp[3] = itoa64[i&0x3f];       i >>= 6;
00579         encp[2] = itoa64[i&0x3f];       i >>= 6;
00580         encp[1] = itoa64[i&0x3f];       i >>= 6;
00581         encp[0] = itoa64[i];            encp += 4;
00582         i = ((long)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2;
00583         encp[2] = itoa64[i&0x3f];       i >>= 6;
00584         encp[1] = itoa64[i&0x3f];       i >>= 6;
00585         encp[0] = itoa64[i];
00586 
00587         encp[3] = 0;
00588 
00589         return (cryptresult);
00590 }
00591 
00592 
00593 /*
00594  * The Key Schedule, filled in by des_setkey() or setkey().
00595  */
00596 #define KS_SIZE 16
00597 static C_block  KS[KS_SIZE];
00598 
00599 /*
00600  * Set up the key schedule from the key.
00601  */
00602 int
00603 des_setkey(key)
00604         register const char *key;
00605 {
00606         register DCL_BLOCK(K, K0, K1);
00607         register C_block *ptabp;
00608         register int i;
00609         static int des_ready = 0;
00610 
00611         if (!des_ready) {
00612                 init_des();
00613                 des_ready = 1;
00614         }
00615 
00616         PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT);
00617         key = (char *)&KS[0];
00618         STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key);
00619         for (i = 1; i < 16; i++) {
00620                 key += sizeof(C_block);
00621                 STORE(K,K0,K1,*(C_block *)key);
00622                 ptabp = (C_block *)PC2ROT[Rotates[i]-1];
00623                 PERM6464(K,K0,K1,(unsigned char *)key,ptabp);
00624                 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key);
00625         }
00626         return (0);
00627 }
00628 
00629 /*
00630  * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter)
00631  * iterations of DES, using the the given 24-bit salt and the pre-computed key
00632  * schedule, and store the resulting 8 chars at "out" (in == out is permitted).
00633  *
00634  * NOTE: the performance of this routine is critically dependent on your
00635  * compiler and machine architecture.
00636  */
00637 int
00638 des_cipher(in, out, salt, num_iter)
00639         const char *in;
00640         char *out;
00641         long salt;
00642         int num_iter;
00643 {
00644         /* variables that we want in registers, most important first */
00645 #if defined(pdp11)
00646         register int j;
00647 #endif
00648         register long L0, L1, R0, R1, k;
00649         register C_block *kp;
00650         register int ks_inc, loop_count;
00651         C_block B;
00652 
00653         L0 = salt;
00654         TO_SIX_BIT(salt, L0);   /* convert to 4*(6+2) format */
00655 
00656 #if defined(vax) || defined(pdp11)
00657         salt = ~salt;   /* "x &~ y" is faster than "x & y". */
00658 #define SALT (~salt)
00659 #else
00660 #define SALT salt
00661 #endif
00662 
00663 #if defined(MUST_ALIGN)
00664         B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3];
00665         B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7];
00666         LOAD(L,L0,L1,B);
00667 #else
00668         LOAD(L,L0,L1,*(C_block *)in);
00669 #endif
00670         LOADREG(R,R0,R1,L,L0,L1);
00671         L0 &= 0x55555555L;
00672         L1 &= 0x55555555L;
00673         L0 = (L0 << 1) | L1;    /* L0 is the even-numbered input bits */
00674         R0 &= 0xaaaaaaaaL;
00675         R1 = (R1 >> 1) & 0x55555555L;
00676         L1 = R0 | R1;           /* L1 is the odd-numbered input bits */
00677         STORE(L,L0,L1,B);
00678         PERM3264(L,L0,L1,B.b,  (C_block *)IE3264);      /* even bits */
00679         PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264);      /* odd bits */
00680 
00681         if (num_iter >= 0)
00682         {               /* encryption */
00683                 kp = &KS[0];
00684                 ks_inc  = (int)sizeof(*kp);
00685         }
00686         else
00687         {               /* decryption */
00688                 num_iter = -num_iter;
00689                 kp = &KS[KS_SIZE-1];
00690                 ks_inc  = -(int)sizeof(*kp);
00691         }
00692 
00693         while (--num_iter >= 0) {
00694                 loop_count = 8;
00695                 do {
00696 
00697 #define SPTAB(t, i)     (*(long *)((unsigned char *)(t) + (i)*(sizeof(long)/4)))
00698 #if defined(gould)
00699                         /* use this if B.b[i] is evaluated just once ... */
00700 #define DOXOR(x,y,i)    (x)^=SPTAB(SPE[0][(i)],B.b[(i)]); (y)^=SPTAB(SPE[1][(i)],B.b[(i)]);
00701 #else
00702 #if defined(pdp11)
00703                         /* use this if your "long" int indexing is slow */
00704 #define DOXOR(x,y,i)    j=B.b[(i)]; (x)^=SPTAB(SPE[0][(i)],j); (y)^=SPTAB(SPE[1][(i)],j);
00705 #else
00706                         /* use this if "k" is allocated to a register ... */
00707 #define DOXOR(x,y,i)    k=B.b[(i)]; (x)^=SPTAB(SPE[0][(i)],k); (y)^=SPTAB(SPE[1][(i)],k);
00708 #endif
00709 #endif
00710 
00711 #define CRUNCH(p0, p1, q0, q1)  \
00712                         k = ((q0) ^ (q1)) & SALT;       \
00713                         B.b32.i0 = k ^ (q0) ^ kp->b32.i0;               \
00714                         B.b32.i1 = k ^ (q1) ^ kp->b32.i1;               \
00715                         kp = (C_block *)((char *)kp+ks_inc);    \
00716                                                         \
00717                         DOXOR((p0), (p1), 0);           \
00718                         DOXOR((p0), (p1), 1);           \
00719                         DOXOR((p0), (p1), 2);           \
00720                         DOXOR((p0), (p1), 3);           \
00721                         DOXOR((p0), (p1), 4);           \
00722                         DOXOR((p0), (p1), 5);           \
00723                         DOXOR((p0), (p1), 6);           \
00724                         DOXOR((p0), (p1), 7);
00725 
00726                         CRUNCH(L0, L1, R0, R1);
00727                         CRUNCH(R0, R1, L0, L1);
00728                 } while (--loop_count != 0);
00729                 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE));
00730 
00731 
00732                 /* swap L and R */
00733                 L0 ^= R0;  L1 ^= R1;
00734                 R0 ^= L0;  R1 ^= L1;
00735                 L0 ^= R0;  L1 ^= R1;
00736         }
00737 
00738         /* store the encrypted (or decrypted) result */
00739         L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L);
00740         L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L);
00741         STORE(L,L0,L1,B);
00742         PERM6464(L,L0,L1,B.b, (C_block *)CF6464);
00743 #if defined(MUST_ALIGN)
00744         STORE(L,L0,L1,B);
00745         out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3];
00746         out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7];
00747 #else
00748         STORE(L,L0,L1,*(C_block *)out);
00749 #endif
00750         return (0);
00751 }
00752 
00753 
00754 /*
00755  * Initialize various tables.  This need only be done once.  It could even be
00756  * done at compile time, if the compiler were capable of that sort of thing.
00757  */
00758 STATIC void
00759 init_des()
00760 {
00761         register int i, j;
00762         register long k;
00763         register int tableno;
00764         static unsigned char perm[64], tmp32[32];       /* "static" for speed */
00765 
00766         /*
00767          * table that converts chars "./0-9A-Za-z"to integers 0-63.
00768          */
00769         for (i = 0; i < 64; i++)
00770                 a64toi[itoa64[i]] = i;
00771 
00772         /*
00773          * PC1ROT - bit reverse, then PC1, then Rotate, then PC2.
00774          */
00775         for (i = 0; i < 64; i++)
00776                 perm[i] = 0;
00777         for (i = 0; i < 64; i++) {
00778                 if ((k = PC2[i]) == 0)
00779                         continue;
00780                 k += Rotates[0]-1;
00781                 if ((k%28) < Rotates[0]) k -= 28;
00782                 k = PC1[k];
00783                 if (k > 0) {
00784                         k--;
00785                         k = (k|07) - (k&07);
00786                         k++;
00787                 }
00788                 perm[i] = (unsigned char)k;
00789         }
00790 #ifdef DEBUG
00791         prtab("pc1tab", perm, 8);
00792 #endif
00793         init_perm(PC1ROT, perm, 8, 8);
00794 
00795         /*
00796          * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2.
00797          */
00798         for (j = 0; j < 2; j++) {
00799                 unsigned char pc2inv[64];
00800                 for (i = 0; i < 64; i++)
00801                         perm[i] = pc2inv[i] = 0;
00802                 for (i = 0; i < 64; i++) {
00803                         if ((k = PC2[i]) == 0)
00804                                 continue;
00805                         pc2inv[k-1] = i+1;
00806                 }
00807                 for (i = 0; i < 64; i++) {
00808                         if ((k = PC2[i]) == 0)
00809                                 continue;
00810                         k += j;
00811                         if ((k%28) <= j) k -= 28;
00812                         perm[i] = pc2inv[k];
00813                 }
00814 #ifdef DEBUG
00815                 prtab("pc2tab", perm, 8);
00816 #endif
00817                 init_perm(PC2ROT[j], perm, 8, 8);
00818         }
00819 
00820         /*
00821          * Bit reverse, then initial permutation, then expansion.
00822          */
00823         for (i = 0; i < 8; i++) {
00824                 for (j = 0; j < 8; j++) {
00825                         k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1];
00826                         if (k > 32)
00827                                 k -= 32;
00828                         else if (k > 0)
00829                                 k--;
00830                         if (k > 0) {
00831                                 k--;
00832                                 k = (k|07) - (k&07);
00833                                 k++;
00834                         }
00835                         perm[i*8+j] = (unsigned char)k;
00836                 }
00837         }
00838 #ifdef DEBUG
00839         prtab("ietab", perm, 8);
00840 #endif
00841         init_perm(IE3264, perm, 4, 8);
00842 
00843         /*
00844          * Compression, then final permutation, then bit reverse.
00845          */
00846         for (i = 0; i < 64; i++) {
00847                 k = IP[CIFP[i]-1];
00848                 if (k > 0) {
00849                         k--;
00850                         k = (k|07) - (k&07);
00851                         k++;
00852                 }
00853                 perm[k-1] = i+1;
00854         }
00855 #ifdef DEBUG
00856         prtab("cftab", perm, 8);
00857 #endif
00858         init_perm(CF6464, perm, 8, 8);
00859 
00860         /*
00861          * SPE table
00862          */
00863         for (i = 0; i < 48; i++)
00864                 perm[i] = P32Tr[ExpandTr[i]-1];
00865         for (tableno = 0; tableno < 8; tableno++) {
00866                 for (j = 0; j < 64; j++)  {
00867                         k = (((j >> 0) &01) << 5)|
00868                             (((j >> 1) &01) << 3)|
00869                             (((j >> 2) &01) << 2)|
00870                             (((j >> 3) &01) << 1)|
00871                             (((j >> 4) &01) << 0)|
00872                             (((j >> 5) &01) << 4);
00873                         k = S[tableno][k];
00874                         k = (((k >> 3)&01) << 0)|
00875                             (((k >> 2)&01) << 1)|
00876                             (((k >> 1)&01) << 2)|
00877                             (((k >> 0)&01) << 3);
00878                         for (i = 0; i < 32; i++)
00879                                 tmp32[i] = 0;
00880                         for (i = 0; i < 4; i++)
00881                                 tmp32[4 * tableno + i] = (unsigned char)(k >> i) & 01;
00882                         k = 0;
00883                         for (i = 24; --i >= 0; )
00884                                 k = (k<<1) | tmp32[perm[i]-1];
00885                         TO_SIX_BIT(SPE[0][tableno][j], k);
00886                         k = 0;
00887                         for (i = 24; --i >= 0; )
00888                                 k = (k<<1) | tmp32[perm[i+24]-1];
00889                         TO_SIX_BIT(SPE[1][tableno][j], k);
00890                 }
00891         }
00892 }
00893 
00894 /*
00895  * Initialize "perm" to represent transformation "p", which rearranges
00896  * (perhaps with expansion and/or contraction) one packed array of bits
00897  * (of size "chars_in" characters) into another array (of size "chars_out"
00898  * characters).
00899  *
00900  * "perm" must be all-zeroes on entry to this routine.
00901  */
00902 STATIC void
00903 init_perm(perm, p, chars_in, chars_out)
00904         C_block perm[64/CHUNKBITS][1<<CHUNKBITS];
00905         unsigned char p[64];
00906         int chars_in, chars_out;
00907 {
00908         register int i, j, k, l;
00909 
00910         for (k = 0; k < chars_out*8; k++) {     /* each output bit position */
00911                 l = p[k] - 1;           /* where this bit comes from */
00912                 if (l < 0)
00913                         continue;       /* output bit is always 0 */
00914                 i = l>>LGCHUNKBITS;     /* which chunk this bit comes from */
00915                 l = 1<<(l&(CHUNKBITS-1));       /* mask for this bit */
00916                 for (j = 0; j < (1<<CHUNKBITS); j++) {  /* each chunk value */
00917                         if ((j & l) != 0)
00918                                 perm[i][j].b[k>>3] |= 1<<(k&07);
00919                 }
00920         }
00921 }
00922 
00923 /*
00924  * "setkey" routine (for backwards compatibility)
00925  */
00926 int
00927 setkey(key)
00928         register const char *key;
00929 {
00930         register int i, j, k;
00931         C_block keyblock;
00932 
00933         for (i = 0; i < 8; i++) {
00934                 k = 0;
00935                 for (j = 0; j < 8; j++) {
00936                         k <<= 1;
00937                         k |= (unsigned char)*key++;
00938                 }
00939                 keyblock.b[i] = k;
00940         }
00941         return (des_setkey((char *)keyblock.b));
00942 }
00943 
00944 /*
00945  * "encrypt" routine (for backwards compatibility)
00946  */
00947 int
00948 encrypt(block, flag)
00949         register char *block;
00950         int flag;
00951 {
00952         register int i, j, k;
00953         C_block cblock;
00954 
00955         for (i = 0; i < 8; i++) {
00956                 k = 0;
00957                 for (j = 0; j < 8; j++) {
00958                         k <<= 1;
00959                         k |= (unsigned char)*block++;
00960                 }
00961                 cblock.b[i] = k;
00962         }
00963         if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1)))
00964                 return (1);
00965         for (i = 7; i >= 0; i--) {
00966                 k = cblock.b[i];
00967                 for (j = 7; j >= 0; j--) {
00968                         *--block = k&01;
00969                         k >>= 1;
00970                 }
00971         }
00972         return (0);
00973 }
00974 
00975 #ifdef DEBUG
00976 STATIC void
00977 prtab(s, t, num_rows)
00978         char *s;
00979         unsigned char *t;
00980         int num_rows;
00981 {
00982         register int i, j;
00983 
00984         (void)printf("%s:\n", s);
00985         for (i = 0; i < num_rows; i++) {
00986                 for (j = 0; j < 8; j++) {
00987                          (void)printf("%3d", t[i*8+j]);
00988                 }
00989                 (void)printf("\n");
00990         }
00991         (void)printf("\n");
00992 }
00993 #endif
00994