PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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  DCL_BLOCK(D, D0, D1);
312  C_block *tp;
313  int t;
314 
315  ZERO(D, D0, D1);
316  do
317  {
318  t = *cp++;
319  tp = &p[t & 0xf];
320  OR(D, D0, D1, *tp);
321  p += (1 << CHUNKBITS);
322  tp = &p[t >> 4];
323  OR(D, D0, D1, *tp);
324  p += (1 << CHUNKBITS);
325  } while (--chars_in > 0);
326  STORE(D, D0, D1, *out);
327 }
328 #endif /* LARGEDATA */
329 
330 
331 /* ===== (mostly) Standard DES Tables ==================== */
332 
333 static const unsigned char IP[] = { /* initial permutation */
334  58, 50, 42, 34, 26, 18, 10, 2,
335  60, 52, 44, 36, 28, 20, 12, 4,
336  62, 54, 46, 38, 30, 22, 14, 6,
337  64, 56, 48, 40, 32, 24, 16, 8,
338  57, 49, 41, 33, 25, 17, 9, 1,
339  59, 51, 43, 35, 27, 19, 11, 3,
340  61, 53, 45, 37, 29, 21, 13, 5,
341  63, 55, 47, 39, 31, 23, 15, 7,
342 };
343 
344 /* The final permutation is the inverse of IP - no table is necessary */
345 
346 static const unsigned char ExpandTr[] = { /* expansion operation */
347  32, 1, 2, 3, 4, 5,
348  4, 5, 6, 7, 8, 9,
349  8, 9, 10, 11, 12, 13,
350  12, 13, 14, 15, 16, 17,
351  16, 17, 18, 19, 20, 21,
352  20, 21, 22, 23, 24, 25,
353  24, 25, 26, 27, 28, 29,
354  28, 29, 30, 31, 32, 1,
355 };
356 
357 static const unsigned char PC1[] = { /* permuted choice table 1 */
358  57, 49, 41, 33, 25, 17, 9,
359  1, 58, 50, 42, 34, 26, 18,
360  10, 2, 59, 51, 43, 35, 27,
361  19, 11, 3, 60, 52, 44, 36,
362 
363  63, 55, 47, 39, 31, 23, 15,
364  7, 62, 54, 46, 38, 30, 22,
365  14, 6, 61, 53, 45, 37, 29,
366  21, 13, 5, 28, 20, 12, 4,
367 };
368 
369 static const unsigned char Rotates[] = { /* PC1 rotation schedule */
370  1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
371 };
372 
373 /* note: each "row" of PC2 is left-padded with bits that make it invertible */
374 static const unsigned char PC2[] = { /* permuted choice table 2 */
375  9, 18, 14, 17, 11, 24, 1, 5,
376  22, 25, 3, 28, 15, 6, 21, 10,
377  35, 38, 23, 19, 12, 4, 26, 8,
378  43, 54, 16, 7, 27, 20, 13, 2,
379 
380  0, 0, 41, 52, 31, 37, 47, 55,
381  0, 0, 30, 40, 51, 45, 33, 48,
382  0, 0, 44, 49, 39, 56, 34, 53,
383  0, 0, 46, 42, 50, 36, 29, 32,
384 };
385 
386 static const unsigned char S[8][64] = { /* 48->32 bit substitution tables */
387  /* S[1] */
388  {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
389  0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
390  4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
391  15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13},
392  /* S[2] */
393  {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
394  3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
395  0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
396  13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9},
397  /* S[3] */
398  {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
399  13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
400  13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
401  1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12},
402  /* S[4] */
403  {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
404  13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
405  10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
406  3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14},
407  /* S[5] */
408  {2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
409  14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
410  4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
411  11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3},
412  /* S[6] */
413  {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
414  10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
415  9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
416  4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13},
417  /* S[7] */
418  {4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
419  13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
420  1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
421  6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12},
422  /* S[8] */
423  {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
424  1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
425  7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
426  2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}
427 };
428 
429 static const unsigned char P32Tr[] = { /* 32-bit permutation function */
430  16, 7, 20, 21,
431  29, 12, 28, 17,
432  1, 15, 23, 26,
433  5, 18, 31, 10,
434  2, 8, 24, 14,
435  32, 27, 3, 9,
436  19, 13, 30, 6,
437  22, 11, 4, 25,
438 };
439 
440 static const unsigned char CIFP[] = { /* compressed/interleaved permutation */
441  1, 2, 3, 4, 17, 18, 19, 20,
442  5, 6, 7, 8, 21, 22, 23, 24,
443  9, 10, 11, 12, 25, 26, 27, 28,
444  13, 14, 15, 16, 29, 30, 31, 32,
445 
446  33, 34, 35, 36, 49, 50, 51, 52,
447  37, 38, 39, 40, 53, 54, 55, 56,
448  41, 42, 43, 44, 57, 58, 59, 60,
449  45, 46, 47, 48, 61, 62, 63, 64,
450 };
451 
452 static const unsigned char itoa64[] = /* 0..63 => ascii-64 */
453 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
454 
455 
456 /* ===== Tables that are initialized at run time ==================== */
457 
458 
459 static unsigned char a64toi[128]; /* ascii-64 => 0..63 */
460 
461 /* Initial key schedule permutation */
462 static C_block PC1ROT[64 / CHUNKBITS][1 << CHUNKBITS];
463 
464 /* Subsequent key schedule rotation permutations */
465 static C_block PC2ROT[2][64 / CHUNKBITS][1 << CHUNKBITS];
466 
467 /* Initial permutation/expansion table */
468 static C_block IE3264[32 / CHUNKBITS][1 << CHUNKBITS];
469 
470 /* Table that combines the S, P, and E operations. */
471 static int32_t SPE[2][8][64];
472 
473 /* compressed/interleaved => final permutation table */
474 static C_block CF6464[64 / CHUNKBITS][1 << CHUNKBITS];
475 
476 
477 /* ==================================== */
478 
479 
480 static C_block constdatablock; /* encryption constant */
481 static char cryptresult[1 + 4 + 4 + 11 + 1]; /* encrypted result */
482 
483 extern char *__md5crypt(const char *, const char *); /* XXX */
484 extern char *__bcrypt(const char *, const char *); /* XXX */
485 
486 
487 /*
488  * Return a pointer to static data consisting of the "setting"
489  * followed by an encryption produced by the "key" and "setting".
490  */
491 char *
492 crypt(key, setting)
493 const char *key;
494 const char *setting;
495 {
496  char *encp;
497  int32_t i;
498  int t;
499  int32_t salt;
500  int num_iter,
501  salt_size;
502  C_block keyblock,
503  rsltblock;
504 
505 #if 0
506  /* Non-DES encryption schemes hook in here. */
507  if (setting[0] == _PASSWORD_NONDES)
508  {
509  switch (setting[1])
510  {
511  case '2':
512  return (__bcrypt(key, setting));
513  case '1':
514  default:
515  return (__md5crypt(key, setting));
516  }
517  }
518 #endif
519 
520  for (i = 0; i < 8; i++)
521  {
522  if ((t = 2 * (unsigned char) (*key)) != 0)
523  key++;
524  keyblock.b[i] = t;
525  }
526  if (des_setkey((char *) keyblock.b)) /* also initializes "a64toi" */
527  return (NULL);
528 
529  encp = &cryptresult[0];
530  switch (*setting)
531  {
532  case _PASSWORD_EFMT1:
533 
534  /*
535  * Involve the rest of the password 8 characters at a time.
536  */
537  while (*key)
538  {
539  if (des_cipher((char *) (void *) &keyblock,
540  (char *) (void *) &keyblock, 0L, 1))
541  return (NULL);
542  for (i = 0; i < 8; i++)
543  {
544  if ((t = 2 * (unsigned char) (*key)) != 0)
545  key++;
546  keyblock.b[i] ^= t;
547  }
548  if (des_setkey((char *) keyblock.b))
549  return (NULL);
550  }
551 
552  *encp++ = *setting++;
553 
554  /* get iteration count */
555  num_iter = 0;
556  for (i = 4; --i >= 0;)
557  {
558  if ((t = (unsigned char) setting[i]) == '\0')
559  t = '.';
560  encp[i] = t;
561  num_iter = (num_iter << 6) | a64toi[t];
562  }
563  setting += 4;
564  encp += 4;
565  salt_size = 4;
566  break;
567  default:
568  num_iter = 25;
569  salt_size = 2;
570  }
571 
572  salt = 0;
573  for (i = salt_size; --i >= 0;)
574  {
575  if ((t = (unsigned char) setting[i]) == '\0')
576  t = '.';
577  encp[i] = t;
578  salt = (salt << 6) | a64toi[t];
579  }
580  encp += salt_size;
581  if (des_cipher((char *) (void *) &constdatablock,
582  (char *) (void *) &rsltblock, salt, num_iter))
583  return (NULL);
584 
585  /*
586  * Encode the 64 cipher bits as 11 ascii characters.
587  */
588  i = ((int32_t) ((rsltblock.b[0] << 8) | rsltblock.b[1]) << 8) |
589  rsltblock.b[2];
590  encp[3] = itoa64[i & 0x3f];
591  i >>= 6;
592  encp[2] = itoa64[i & 0x3f];
593  i >>= 6;
594  encp[1] = itoa64[i & 0x3f];
595  i >>= 6;
596  encp[0] = itoa64[i];
597  encp += 4;
598  i = ((int32_t) ((rsltblock.b[3] << 8) | rsltblock.b[4]) << 8) |
599  rsltblock.b[5];
600  encp[3] = itoa64[i & 0x3f];
601  i >>= 6;
602  encp[2] = itoa64[i & 0x3f];
603  i >>= 6;
604  encp[1] = itoa64[i & 0x3f];
605  i >>= 6;
606  encp[0] = itoa64[i];
607  encp += 4;
608  i = ((int32_t) ((rsltblock.b[6]) << 8) | rsltblock.b[7]) << 2;
609  encp[2] = itoa64[i & 0x3f];
610  i >>= 6;
611  encp[1] = itoa64[i & 0x3f];
612  i >>= 6;
613  encp[0] = itoa64[i];
614 
615  encp[3] = 0;
616 
617  return (cryptresult);
618 }
619 
620 
621 /*
622  * The Key Schedule, filled in by des_setkey() or setkey().
623  */
624 #define KS_SIZE 16
626 
627 static volatile int des_ready = 0;
628 
629 /*
630  * Set up the key schedule from the key.
631  */
632 static int
634 const char *key;
635 {
636  DCL_BLOCK(K, K0, K1);
637  C_block *ptabp;
638  int i;
639 
640  if (!des_ready)
641  init_des();
642 
643  PERM6464(K, K0, K1, (unsigned char *) key, (C_block *) PC1ROT);
644  key = (char *) &KS[0];
645  STORE(K & ~0x03030303L, K0 & ~0x03030303L, K1, *(C_block *) key);
646  for (i = 1; i < 16; i++)
647  {
648  key += sizeof(C_block);
649  STORE(K, K0, K1, *(C_block *) key);
650  ptabp = (C_block *) PC2ROT[Rotates[i] - 1];
651  PERM6464(K, K0, K1, (unsigned char *) key, ptabp);
652  STORE(K & ~0x03030303L, K0 & ~0x03030303L, K1, *(C_block *) key);
653  }
654  return (0);
655 }
656 
657 /*
658  * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter)
659  * iterations of DES, using the given 24-bit salt and the pre-computed key
660  * schedule, and store the resulting 8 chars at "out" (in == out is permitted).
661  *
662  * NOTE: the performance of this routine is critically dependent on your
663  * compiler and machine architecture.
664  */
665 static int
666 des_cipher(in, out, salt, num_iter)
667 const char *in;
668 char *out;
669 long salt;
670 int num_iter;
671 {
672  /* variables that we want in registers, most important first */
673 #if defined(pdp11)
674  int j;
675 #endif
676  int32_t L0,
677  L1,
678  R0,
679  R1,
680  k;
681  C_block *kp;
682  int ks_inc,
683  loop_count;
684  C_block B;
685 
686  L0 = salt;
687  TO_SIX_BIT(salt, L0); /* convert to 4*(6+2) format */
688 
689 #if defined(__vax__) || defined(pdp11)
690  salt = ~salt; /* "x &~ y" is faster than "x & y". */
691 #define SALT (~salt)
692 #else
693 #define SALT salt
694 #endif
695 
696 #if defined(MUST_ALIGN)
697  B.b[0] = in[0];
698  B.b[1] = in[1];
699  B.b[2] = in[2];
700  B.b[3] = in[3];
701  B.b[4] = in[4];
702  B.b[5] = in[5];
703  B.b[6] = in[6];
704  B.b[7] = in[7];
705  LOAD(L, L0, L1, B);
706 #else
707  LOAD(L, L0, L1, *(C_block *) in);
708 #endif
709  LOADREG(R, R0, R1, L, L0, L1);
710  L0 &= 0x55555555L;
711  L1 &= 0x55555555L;
712  L0 = (L0 << 1) | L1; /* L0 is the even-numbered input bits */
713  R0 &= 0xaaaaaaaaL;
714  R1 = (R1 >> 1) & 0x55555555L;
715  L1 = R0 | R1; /* L1 is the odd-numbered input bits */
716  STORE(L, L0, L1, B);
717  PERM3264(L, L0, L1, B.b, (C_block *) IE3264); /* even bits */
718  PERM3264(R, R0, R1, B.b + 4, (C_block *) IE3264); /* odd bits */
719 
720  if (num_iter >= 0)
721  { /* encryption */
722  kp = &KS[0];
723  ks_inc = sizeof(*kp);
724  }
725  else
726  { /* decryption */
727  num_iter = -num_iter;
728  kp = &KS[KS_SIZE - 1];
729  ks_inc = -(long) sizeof(*kp);
730  }
731 
732  while (--num_iter >= 0)
733  {
734  loop_count = 8;
735  do
736  {
737 
738 #define SPTAB(t, i) \
739  (*(int32_t *)((unsigned char *)(t) + (i)*(sizeof(int32_t)/4)))
740 #if defined(gould)
741  /* use this if B.b[i] is evaluated just once ... */
742 #define DOXOR(x,y,i) x^=SPTAB(SPE[0][i],B.b[i]); y^=SPTAB(SPE[1][i],B.b[i]);
743 #else
744 #if defined(pdp11)
745  /* use this if your "long" int indexing is slow */
746 #define DOXOR(x,y,i) j=B.b[i]; x^=SPTAB(SPE[0][i],j); y^=SPTAB(SPE[1][i],j);
747 #else
748  /* use this if "k" is allocated to a register ... */
749 #define DOXOR(x,y,i) k=B.b[i]; x^=SPTAB(SPE[0][i],k); y^=SPTAB(SPE[1][i],k);
750 #endif
751 #endif
752 
753 #define CRUNCH(p0, p1, q0, q1) \
754  k = ((q0) ^ (q1)) & SALT; \
755  B.b32.i0 = k ^ (q0) ^ kp->b32.i0; \
756  B.b32.i1 = k ^ (q1) ^ kp->b32.i1; \
757  kp = (C_block *)((char *)kp+ks_inc); \
758  \
759  DOXOR(p0, p1, 0); \
760  DOXOR(p0, p1, 1); \
761  DOXOR(p0, p1, 2); \
762  DOXOR(p0, p1, 3); \
763  DOXOR(p0, p1, 4); \
764  DOXOR(p0, p1, 5); \
765  DOXOR(p0, p1, 6); \
766  DOXOR(p0, p1, 7);
767 
768  CRUNCH(L0, L1, R0, R1);
769  CRUNCH(R0, R1, L0, L1);
770  } while (--loop_count != 0);
771  kp = (C_block *) ((char *) kp - (ks_inc * KS_SIZE));
772 
773 
774  /* swap L and R */
775  L0 ^= R0;
776  L1 ^= R1;
777  R0 ^= L0;
778  R1 ^= L1;
779  L0 ^= R0;
780  L1 ^= R1;
781  }
782 
783  /* store the encrypted (or decrypted) result */
784  L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L);
785  L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L);
786  STORE(L, L0, L1, B);
787  PERM6464(L, L0, L1, B.b, (C_block *) CF6464);
788 #if defined(MUST_ALIGN)
789  STORE(L, L0, L1, B);
790  out[0] = B.b[0];
791  out[1] = B.b[1];
792  out[2] = B.b[2];
793  out[3] = B.b[3];
794  out[4] = B.b[4];
795  out[5] = B.b[5];
796  out[6] = B.b[6];
797  out[7] = B.b[7];
798 #else
799  STORE(L, L0, L1, *(C_block *) out);
800 #endif
801  return (0);
802 }
803 
804 
805 /*
806  * Initialize various tables. This need only be done once. It could even be
807  * done at compile time, if the compiler were capable of that sort of thing.
808  */
809 STATIC
811 {
812  int i,
813  j;
814  int32_t k;
815  int tableno;
816  static unsigned char perm[64],
817  tmp32[32]; /* "static" for speed */
818 
819 /* static volatile long init_start = 0; not used */
820 
821  /*
822  * table that converts chars "./0-9A-Za-z"to integers 0-63.
823  */
824  for (i = 0; i < 64; i++)
825  a64toi[itoa64[i]] = i;
826 
827  /*
828  * PC1ROT - bit reverse, then PC1, then Rotate, then PC2.
829  */
830  for (i = 0; i < 64; i++)
831  perm[i] = 0;
832  for (i = 0; i < 64; i++)
833  {
834  if ((k = PC2[i]) == 0)
835  continue;
836  k += Rotates[0] - 1;
837  if ((k % 28) < Rotates[0])
838  k -= 28;
839  k = PC1[k];
840  if (k > 0)
841  {
842  k--;
843  k = (k | 07) - (k & 07);
844  k++;
845  }
846  perm[i] = k;
847  }
848 #ifdef DEBUG
849  prtab("pc1tab", perm, 8);
850 #endif
851  init_perm(PC1ROT, perm, 8, 8);
852 
853  /*
854  * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2.
855  */
856  for (j = 0; j < 2; j++)
857  {
858  unsigned char pc2inv[64];
859 
860  for (i = 0; i < 64; i++)
861  perm[i] = pc2inv[i] = 0;
862  for (i = 0; i < 64; i++)
863  {
864  if ((k = PC2[i]) == 0)
865  continue;
866  pc2inv[k - 1] = i + 1;
867  }
868  for (i = 0; i < 64; i++)
869  {
870  if ((k = PC2[i]) == 0)
871  continue;
872  k += j;
873  if ((k % 28) <= j)
874  k -= 28;
875  perm[i] = pc2inv[k];
876  }
877 #ifdef DEBUG
878  prtab("pc2tab", perm, 8);
879 #endif
880  init_perm(PC2ROT[j], perm, 8, 8);
881  }
882 
883  /*
884  * Bit reverse, then initial permutation, then expansion.
885  */
886  for (i = 0; i < 8; i++)
887  {
888  for (j = 0; j < 8; j++)
889  {
890  k = (j < 2) ? 0 : IP[ExpandTr[i * 6 + j - 2] - 1];
891  if (k > 32)
892  k -= 32;
893  else if (k > 0)
894  k--;
895  if (k > 0)
896  {
897  k--;
898  k = (k | 07) - (k & 07);
899  k++;
900  }
901  perm[i * 8 + j] = k;
902  }
903  }
904 #ifdef DEBUG
905  prtab("ietab", perm, 8);
906 #endif
907  init_perm(IE3264, perm, 4, 8);
908 
909  /*
910  * Compression, then final permutation, then bit reverse.
911  */
912  for (i = 0; i < 64; i++)
913  {
914  k = IP[CIFP[i] - 1];
915  if (k > 0)
916  {
917  k--;
918  k = (k | 07) - (k & 07);
919  k++;
920  }
921  perm[k - 1] = i + 1;
922  }
923 #ifdef DEBUG
924  prtab("cftab", perm, 8);
925 #endif
926  init_perm(CF6464, perm, 8, 8);
927 
928  /*
929  * SPE table
930  */
931  for (i = 0; i < 48; i++)
932  perm[i] = P32Tr[ExpandTr[i] - 1];
933  for (tableno = 0; tableno < 8; tableno++)
934  {
935  for (j = 0; j < 64; j++)
936  {
937  k = (((j >> 0) & 01) << 5) |
938  (((j >> 1) & 01) << 3) |
939  (((j >> 2) & 01) << 2) |
940  (((j >> 3) & 01) << 1) |
941  (((j >> 4) & 01) << 0) |
942  (((j >> 5) & 01) << 4);
943  k = S[tableno][k];
944  k = (((k >> 3) & 01) << 0) |
945  (((k >> 2) & 01) << 1) |
946  (((k >> 1) & 01) << 2) |
947  (((k >> 0) & 01) << 3);
948  for (i = 0; i < 32; i++)
949  tmp32[i] = 0;
950  for (i = 0; i < 4; i++)
951  tmp32[4 * tableno + i] = (k >> i) & 01;
952  k = 0;
953  for (i = 24; --i >= 0;)
954  k = (k << 1) | tmp32[perm[i] - 1];
955  TO_SIX_BIT(SPE[0][tableno][j], k);
956  k = 0;
957  for (i = 24; --i >= 0;)
958  k = (k << 1) | tmp32[perm[i + 24] - 1];
959  TO_SIX_BIT(SPE[1][tableno][j], k);
960  }
961  }
962 
963  des_ready = 1;
964 }
965 
966 /*
967  * Initialize "perm" to represent transformation "p", which rearranges
968  * (perhaps with expansion and/or contraction) one packed array of bits
969  * (of size "chars_in" characters) into another array (of size "chars_out"
970  * characters).
971  *
972  * "perm" must be all-zeroes on entry to this routine.
973  */
974 STATIC
975 init_perm(perm, p, chars_in, chars_out)
976 C_block perm[64 / CHUNKBITS][1 << CHUNKBITS];
977 unsigned char p[64];
978 int chars_in,
979  chars_out;
980 {
981  int i,
982  j,
983  k,
984  l;
985 
986  for (k = 0; k < chars_out * 8; k++)
987  { /* each output bit position */
988  l = p[k] - 1; /* where this bit comes from */
989  if (l < 0)
990  continue; /* output bit is always 0 */
991  i = l >> LGCHUNKBITS; /* which chunk this bit comes from */
992  l = 1 << (l & (CHUNKBITS - 1)); /* mask for this bit */
993  for (j = 0; j < (1 << CHUNKBITS); j++)
994  { /* each chunk value */
995  if ((j & l) != 0)
996  perm[i][j].b[k >> 3] |= 1 << (k & 07);
997  }
998  }
999 }
1000 
1001 /*
1002  * "setkey" routine (for backwards compatibility)
1003  */
1004 #ifdef NOT_USED
1005 int
1006 setkey(key)
1007 const char *key;
1008 {
1009  int i,
1010  j,
1011  k;
1012  C_block keyblock;
1013 
1014  for (i = 0; i < 8; i++)
1015  {
1016  k = 0;
1017  for (j = 0; j < 8; j++)
1018  {
1019  k <<= 1;
1020  k |= (unsigned char) *key++;
1021  }
1022  keyblock.b[i] = k;
1023  }
1024  return (des_setkey((char *) keyblock.b));
1025 }
1026 
1027 /*
1028  * "encrypt" routine (for backwards compatibility)
1029  */
1030 static int
1031 encrypt(block, flag)
1032 char *block;
1033 int flag;
1034 {
1035  int i,
1036  j,
1037  k;
1038  C_block cblock;
1039 
1040  for (i = 0; i < 8; i++)
1041  {
1042  k = 0;
1043  for (j = 0; j < 8; j++)
1044  {
1045  k <<= 1;
1046  k |= (unsigned char) *block++;
1047  }
1048  cblock.b[i] = k;
1049  }
1050  if (des_cipher((char *) &cblock, (char *) &cblock, 0L, (flag ? -1 : 1)))
1051  return (1);
1052  for (i = 7; i >= 0; i--)
1053  {
1054  k = cblock.b[i];
1055  for (j = 7; j >= 0; j--)
1056  {
1057  *--block = k & 01;
1058  k >>= 1;
1059  }
1060  }
1061  return (0);
1062 }
1063 #endif
1064 
1065 #ifdef DEBUG
1066 STATIC
1067 prtab(s, t, num_rows)
1068 char *s;
1069 unsigned char *t;
1070 int num_rows;
1071 {
1072  int i,
1073  j;
1074 
1075  (void) printf("%s:\n", s);
1076  for (i = 0; i < num_rows; i++)
1077  {
1078  for (j = 0; j < 8; j++)
1079  (void) printf("%3d", t[i * 8 + j]);
1080  (void) printf("\n");
1081  }
1082  (void) printf("\n");
1083 }
1084 
1085 #endif
STATIC init_des(void)
Definition: crypt.c:810
#define R(b, x)
Definition: sha2.c:106
#define STATIC
Definition: crypt.c:101
static const unsigned char S[8][64]
Definition: crypt.c:386
#define CRUNCH(p0, p1, q0, q1)
static const unsigned char CIFP[]
Definition: crypt.c:440
#define CHUNKBITS
Definition: crypt.c:285
static unsigned char a64toi[128]
Definition: crypt.c:459
static int des_setkey(const char *key)
#define KS_SIZE
Definition: crypt.c:624
#define PERM3264(d, d0, d1, cpp, p)
Definition: crypt.c:288
static C_block KS[KS_SIZE]
Definition: crypt.c:625
static C_block constdatablock
Definition: crypt.c:480
#define LOADREG(d, d0, d1, s, s0, s1)
Definition: crypt.c:259
static C_block CF6464[64/CHUNKBITS][1<< CHUNKBITS]
Definition: crypt.c:474
char * crypt(char *key, const char *setting) const
Definition: crypt.c:492
#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:333
#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:627
static const unsigned char PC2[]
Definition: crypt.c:374
static const unsigned char ExpandTr[]
Definition: crypt.c:346
#define LGCHUNKBITS
Definition: crypt.c:284
static const unsigned char itoa64[]
Definition: crypt.c:452
#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 NULL
Definition: c.h:226
#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:465
static int32_t SPE[2][8][64]
Definition: crypt.c:471
static const unsigned char PC1[]
Definition: crypt.c:357
static const unsigned char P32Tr[]
Definition: crypt.c:429
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:481
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:468
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:462
static const unsigned char Rotates[]
Definition: crypt.c:369