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