ccc816d9008d9d271c87812191d5562c3b0ea678
[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)
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 /* Hide these functions for Transarc use; only export crypt() */
124 STATIC int des_setkey(const char *key);
125 STATIC int des_cipher(const char *in, char *out, long salt, int num_iter);
126
127 #ifdef CRYPT_DEBUG
128 STATIC prtab();
129 #endif
130
131 /* ==================================== */
132
133 /*
134  * Cipher-block representation (Bob Baldwin):
135  *
136  * DES operates on groups of 64 bits, numbered 1..64 (sigh).  One
137  * representation is to store one bit per byte in an array of bytes.  Bit N of
138  * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array.
139  * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the
140  * first byte, 9..16 in the second, and so on.  The DES spec apparently has
141  * bit 1 in the MSB of the first byte, but that is particularly noxious so we
142  * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is
143  * the MSB of the first byte.  Specifically, the 64-bit input data and key are
144  * converted to LSB format, and the output 64-bit block is converted back into
145  * MSB format.
146  *
147  * DES operates internally on groups of 32 bits which are expanded to 48 bits
148  * by permutation E and shrunk back to 32 bits by the S boxes.  To speed up
149  * the computation, the expansion is applied only once, the expanded
150  * representation is maintained during the encryption, and a compression
151  * permutation is applied only at the end.  To speed up the S-box lookups,
152  * the 48 bits are maintained as eight 6 bit groups, one per byte, which
153  * directly feed the eight S-boxes.  Within each byte, the 6 bits are the
154  * most significant ones.  The low two bits of each byte are zero.  (Thus,
155  * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the
156  * first byte in the eight byte representation, bit 2 of the 48 bit value is
157  * the "8"-valued bit, and so on.)  In fact, a combined "SPE"-box lookup is
158  * used, in which the output is the 64 bit result of an S-box lookup which
159  * has been permuted by P and expanded by E, and is ready for use in the next
160  * iteration.  Two 32-bit wide tables, SPE[0] and SPE[1], are used for this
161  * lookup.  Since each byte in the 48 bit path is a multiple of four, indexed
162  * lookup of SPE[0] and SPE[1] is simple and fast.  The key schedule and
163  * "salt" are also converted to this 8*(6+2) format.  The SPE table size is
164  * 8*64*8 = 4K bytes.
165  *
166  * To speed up bit-parallel operations (such as XOR), the 8 byte
167  * representation is "union"ed with 32 bit values "i0" and "i1", and, on
168  * machines which support it, a 64 bit value "b64".  This data structure,
169  * "C_block", has two problems.  First, alignment restrictions must be
170  * honored.  Second, the byte-order (e.g. little-endian or big-endian) of
171  * the architecture becomes visible.
172  *
173  * The byte-order problem is unfortunate, since on the one hand it is good
174  * to have a machine-independent C_block representation (bits 1..8 in the
175  * first byte, etc.), and on the other hand it is good for the LSB of the
176  * first byte to be the LSB of i0.  We cannot have both these things, so we
177  * currently use the "little-endian" representation and avoid any multi-byte
178  * operations that depend on byte order.  This largely precludes use of the
179  * 64-bit datatype since the relative order of i0 and i1 are unknown.  It
180  * also inhibits grouping the SPE table to look up 12 bits at a time.  (The
181  * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1
182  * high-order zero, providing fast indexing into a 64-bit wide SPE.)  On the
183  * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup
184  * requires a 128 kilobyte table, so perhaps this is not a big loss.
185  *
186  * Permutation representation (Jim Gillogly):
187  *
188  * A transformation is defined by its effect on each of the 8 bytes of the
189  * 64-bit input.  For each byte we give a 64-bit output that has the bits in
190  * the input distributed appropriately.  The transformation is then the OR
191  * of the 8 sets of 64-bits.  This uses 8*256*8 = 16K bytes of storage for
192  * each transformation.  Unless LARGEDATA is defined, however, a more compact
193  * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks.
194  * The smaller table uses 16*16*8 = 2K bytes for each transformation.  This
195  * is slower but tolerable, particularly for password encryption in which
196  * the SPE transformation is iterated many times.  The small tables total 9K
197  * bytes, the large tables total 72K bytes.
198  *
199  * The transformations used are:
200  * IE3264: MSB->LSB conversion, initial permutation, and expansion.
201  *      This is done by collecting the 32 even-numbered bits and applying
202  *      a 32->64 bit transformation, and then collecting the 32 odd-numbered
203  *      bits and applying the same transformation.  Since there are only
204  *      32 input bits, the IE3264 transformation table is half the size of
205  *      the usual table.
206  * CF6464: Compression, final permutation, and LSB->MSB conversion.
207  *      This is done by two trivial 48->32 bit compressions to obtain
208  *      a 64-bit block (the bit numbering is given in the "CIFP" table)
209  *      followed by a 64->64 bit "cleanup" transformation.  (It would
210  *      be possible to group the bits in the 64-bit block so that 2
211  *      identical 32->32 bit transformations could be used instead,
212  *      saving a factor of 4 in space and possibly 2 in time, but
213  *      byte-ordering and other complications rear their ugly head.
214  *      Similar opportunities/problems arise in the key schedule
215  *      transforms.)
216  * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation.
217  *      This admittedly baroque 64->64 bit transformation is used to
218  *      produce the first code (in 8*(6+2) format) of the key schedule.
219  * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation.
220  *      It would be possible to define 15 more transformations, each
221  *      with a different rotation, to generate the entire key schedule.
222  *      To save space, however, we instead permute each code into the
223  *      next by using a transformation that "undoes" the PC2 permutation,
224  *      rotates the code, and then applies PC2.  Unfortunately, PC2
225  *      transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not
226  *      invertible.  We get around that problem by using a modified PC2
227  *      which retains the 8 otherwise-lost bits in the unused low-order
228  *      bits of each byte.  The low-order bits are cleared when the
229  *      codes are stored into the key schedule.
230  * PC2ROT[1]: Same as PC2ROT[0], but with two rotations.
231  *      This is faster than applying PC2ROT[0] twice,
232  *
233  * The Bell Labs "salt" (Bob Baldwin):
234  *
235  * The salting is a simple permutation applied to the 48-bit result of E.
236  * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and
237  * i+24 of the result are swapped.  The salt is thus a 24 bit number, with
238  * 16777216 possible values.  (The original salt was 12 bits and could not
239  * swap bits 13..24 with 36..48.)
240  *
241  * It is possible, but ugly, to warp the SPE table to account for the salt
242  * permutation.  Fortunately, the conditional bit swapping requires only
243  * about four machine instructions and can be done on-the-fly with about an
244  * 8% performance penalty.
245  */
246
247 typedef union {
248         unsigned char b[8];
249         struct {
250 #if defined(LONG_IS_32_BITS)
251                 /* long is often faster than a 32-bit bit field */
252                 long    i0;
253                 long    i1;
254 #else
255                 long    i0: 32;
256                 long    i1: 32;
257 #endif
258         } b32;
259 #if defined(B64)
260         B64     b64;
261 #endif
262 } C_block;
263
264 /*
265  * Convert twenty-four-bit long in host-order
266  * to six bits (and 2 low-order zeroes) per char little-endian format.
267  */
268 #define TO_SIX_BIT(rslt, src) {                                         \
269                 C_block cvt;                                            \
270                 cvt.b[0] = (unsigned char) src; src >>= 6;              \
271                 cvt.b[1] = (unsigned char) src; src >>= 6;              \
272                 cvt.b[2] = (unsigned char) src; src >>= 6;              \
273                 cvt.b[3] = (unsigned char) src;                         \
274                 rslt = (cvt.b32.i0 & 0x3f3f3f3fL) << 2;                 \
275         }
276
277 /*
278  * These macros may someday permit efficient use of 64-bit integers.
279  */
280 #define ZERO(d,d0,d1)                   d0 = 0, d1 = 0
281 #define LOAD(d,d0,d1,bl)                d0 = (bl).b32.i0, d1 = (bl).b32.i1
282 #define LOADREG(d,d0,d1,s,s0,s1)        d0 = s0, d1 = s1
283 #define OR(d,d0,d1,bl)                  d0 |= (bl).b32.i0, d1 |= (bl).b32.i1
284 #define STORE(s,s0,s1,bl)               (bl).b32.i0 = s0, (bl).b32.i1 = s1
285 #define DCL_BLOCK(d,d0,d1)              long d0, d1
286
287 #if defined(LARGEDATA)
288         /* Waste memory like crazy.  Also, do permutations in line */
289 #define LGCHUNKBITS     3
290 #define CHUNKBITS       (1<<LGCHUNKBITS)
291 #define PERM6464(d,d0,d1,cpp,p)                         \
292         LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]);             \
293         OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]);              \
294         OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]);              \
295         OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]);              \
296         OR (d,d0,d1,(p)[(4<<CHUNKBITS)+(cpp)[4]]);              \
297         OR (d,d0,d1,(p)[(5<<CHUNKBITS)+(cpp)[5]]);              \
298         OR (d,d0,d1,(p)[(6<<CHUNKBITS)+(cpp)[6]]);              \
299         OR (d,d0,d1,(p)[(7<<CHUNKBITS)+(cpp)[7]]);
300 #define PERM3264(d,d0,d1,cpp,p)                         \
301         LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]);             \
302         OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]);              \
303         OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]);              \
304         OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]);
305 #else
306         /* "small data" */
307 #define LGCHUNKBITS     2
308 #define CHUNKBITS       (1<<LGCHUNKBITS)
309 #define PERM6464(d,d0,d1,cpp,p)                         \
310         { C_block tblk; permute(cpp,&tblk,p,8); LOAD (d,d0,d1,tblk); }
311 #define PERM3264(d,d0,d1,cpp,p)                         \
312         { C_block tblk; permute(cpp,&tblk,p,4); LOAD (d,d0,d1,tblk); }
313
314 STATIC
315 void permute(cp, out, p, chars_in)
316         unsigned char *cp;
317         C_block *out;
318         register C_block *p;
319         int chars_in;
320 {
321         register DCL_BLOCK(D,D0,D1);
322         register C_block *tp;
323         register int t;
324
325         ZERO(D,D0,D1);
326         do {
327                 t = *cp++;
328                 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
329                 tp = &p[t>>4];  OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
330         } while (--chars_in > 0);
331         STORE(D,D0,D1,*out);
332 }
333 #endif /* LARGEDATA */
334
335
336 /* =====  (mostly) Standard DES Tables ==================== */
337
338 static unsigned char IP[] = {           /* initial permutation */
339         58, 50, 42, 34, 26, 18, 10,  2,
340         60, 52, 44, 36, 28, 20, 12,  4,
341         62, 54, 46, 38, 30, 22, 14,  6,
342         64, 56, 48, 40, 32, 24, 16,  8,
343         57, 49, 41, 33, 25, 17,  9,  1,
344         59, 51, 43, 35, 27, 19, 11,  3,
345         61, 53, 45, 37, 29, 21, 13,  5,
346         63, 55, 47, 39, 31, 23, 15,  7,
347 };
348
349 /* The final permutation is the inverse of IP - no table is necessary */
350
351 static unsigned char ExpandTr[] = {     /* expansion operation */
352         32,  1,  2,  3,  4,  5,
353          4,  5,  6,  7,  8,  9,
354          8,  9, 10, 11, 12, 13,
355         12, 13, 14, 15, 16, 17,
356         16, 17, 18, 19, 20, 21,
357         20, 21, 22, 23, 24, 25,
358         24, 25, 26, 27, 28, 29,
359         28, 29, 30, 31, 32,  1,
360 };
361
362 static unsigned char PC1[] = {          /* permuted choice table 1 */
363         57, 49, 41, 33, 25, 17,  9,
364          1, 58, 50, 42, 34, 26, 18,
365         10,  2, 59, 51, 43, 35, 27,
366         19, 11,  3, 60, 52, 44, 36,
367
368         63, 55, 47, 39, 31, 23, 15,
369          7, 62, 54, 46, 38, 30, 22,
370         14,  6, 61, 53, 45, 37, 29,
371         21, 13,  5, 28, 20, 12,  4,
372 };
373
374 static unsigned char Rotates[] = {      /* PC1 rotation schedule */
375         1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
376 };
377
378 /* note: each "row" of PC2 is left-padded with bits that make it invertible */
379 static unsigned char PC2[] = {          /* permuted choice table 2 */
380          9, 18,    14, 17, 11, 24,  1,  5,
381         22, 25,     3, 28, 15,  6, 21, 10,
382         35, 38,    23, 19, 12,  4, 26,  8,
383         43, 54,    16,  7, 27, 20, 13,  2,
384
385          0,  0,    41, 52, 31, 37, 47, 55,
386          0,  0,    30, 40, 51, 45, 33, 48,
387          0,  0,    44, 49, 39, 56, 34, 53,
388          0,  0,    46, 42, 50, 36, 29, 32,
389 };
390
391 static unsigned char S[8][64] = {       /* 48->32 bit substitution tables */
392                                         /* S[1]                 */
393 {       14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
394          0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
395          4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
396         15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13, },
397                                         /* S[2]                 */
398 {       15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
399          3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
400          0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
401         13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9, },
402                                         /* S[3]                 */
403 {       10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
404         13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
405         13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
406          1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12, },
407                                         /* S[4]                 */
408 {        7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
409         13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
410         10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
411          3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14, },
412                                         /* S[5]                 */
413 {        2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
414         14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
415          4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
416         11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3, },
417                                         /* S[6]                 */
418 {       12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
419         10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
420          9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
421          4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13, },
422                                         /* S[7]                 */
423 {        4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
424         13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
425          1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
426          6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12, },
427                                         /* S[8]                 */
428 {       13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
429          1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
430          7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
431          2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11, }
432 };
433
434 static unsigned char P32Tr[] = {        /* 32-bit permutation function */
435         16,  7, 20, 21,
436         29, 12, 28, 17,
437          1, 15, 23, 26,
438          5, 18, 31, 10,
439          2,  8, 24, 14,
440         32, 27,  3,  9,
441         19, 13, 30,  6,
442         22, 11,  4, 25,
443 };
444
445 static unsigned char CIFP[] = {         /* compressed/interleaved permutation */
446          1,  2,  3,  4,   17, 18, 19, 20,
447          5,  6,  7,  8,   21, 22, 23, 24,
448          9, 10, 11, 12,   25, 26, 27, 28,
449         13, 14, 15, 16,   29, 30, 31, 32,
450
451         33, 34, 35, 36,   49, 50, 51, 52,
452         37, 38, 39, 40,   53, 54, 55, 56,
453         41, 42, 43, 44,   57, 58, 59, 60,
454         45, 46, 47, 48,   61, 62, 63, 64,
455 };
456
457 static unsigned char itoa64[] =         /* 0..63 => ascii-64 */
458         "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
459
460
461 /* =====  Tables that are initialized at run time  ==================== */
462
463
464 static unsigned char a64toi[128];       /* ascii-64 => 0..63 */
465
466 /* Initial key schedule permutation */
467 static C_block  PC1ROT[64/CHUNKBITS][1<<CHUNKBITS];
468
469 /* Subsequent key schedule rotation permutations */
470 static C_block  PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS];
471
472 /* Initial permutation/expansion table */
473 static C_block  IE3264[32/CHUNKBITS][1<<CHUNKBITS];
474
475 /* Table that combines the S, P, and E operations.  */
476 static long SPE[2][8][64];
477
478 /* compressed/interleaved => final permutation table */
479 static C_block  CF6464[64/CHUNKBITS][1<<CHUNKBITS];
480
481
482 /* ==================================== */
483
484
485 static C_block  constdatablock;                 /* encryption constant */
486 static char     cryptresult[1+4+4+11+1];        /* encrypted result */
487
488 /*
489  * Return a pointer to static data consisting of the "setting"
490  * followed by an encryption produced by the "key" and "setting".
491  */
492 char *
493 crypt(key, setting)
494         register const char *key;
495         register const char *setting;
496 {
497         register char *encp;
498         register long i;
499         register int t;
500         long salt;
501         int num_iter, salt_size;
502         C_block keyblock, rsltblock;
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