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