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