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