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