xref: /netbsd-src/lib/libcrypt/crypt.c (revision d48f14661dda8638fee055ba15d35bdfb29b9fa8)
1 /*	$NetBSD: crypt.c,v 1.23 2006/04/08 23:24:44 christos Exp $	*/
2 
3 /*
4  * Copyright (c) 1989, 1993
5  *	The Regents of the University of California.  All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * Tom Truscott.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  */
34 
35 #include <sys/cdefs.h>
36 #if !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.23 2006/04/08 23:24:44 christos Exp $");
41 #endif
42 #endif /* not lint */
43 
44 #include <limits.h>
45 #include <pwd.h>
46 #include <stdlib.h>
47 #include <unistd.h>
48 #ifdef DEBUG
49 #include <stdio.h>
50 #endif
51 
52 #include "crypt.h"
53 
54 /*
55  * UNIX password, and DES, encryption.
56  * By Tom Truscott, trt@rti.rti.org,
57  * from algorithms by Robert W. Baldwin and James Gillogly.
58  *
59  * References:
60  * "Mathematical Cryptology for Computer Scientists and Mathematicians,"
61  * by Wayne Patterson, 1987, ISBN 0-8476-7438-X.
62  *
63  * "Password Security: A Case History," R. Morris and Ken Thompson,
64  * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979.
65  *
66  * "DES will be Totally Insecure within Ten Years," M.E. Hellman,
67  * IEEE Spectrum, vol. 16, pp. 32-39, July 1979.
68  */
69 
70 /* =====  Configuration ==================== */
71 
72 /*
73  * define "MUST_ALIGN" if your compiler cannot load/store
74  * long integers at arbitrary (e.g. odd) memory locations.
75  * (Either that or never pass unaligned addresses to des_cipher!)
76  */
77 #if !defined(__vax__) && !defined(__i386__)
78 #define	MUST_ALIGN
79 #endif
80 
81 #ifdef CHAR_BITS
82 #if CHAR_BITS != 8
83 	#error C_block structure assumes 8 bit characters
84 #endif
85 #endif
86 
87 /*
88  * define "B64" to be the declaration for a 64 bit integer.
89  * XXX this feature is currently unused, see "endian" comment below.
90  */
91 #if defined(cray)
92 #define	B64	long
93 #endif
94 #if defined(convex)
95 #define	B64	long long
96 #endif
97 
98 /*
99  * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes
100  * of lookup tables.  This speeds up des_setkey() and des_cipher(), but has
101  * little effect on crypt().
102  */
103 #if defined(notdef)
104 #define	LARGEDATA
105 #endif
106 
107 /* compile with "-DSTATIC=void" when profiling */
108 #ifndef STATIC
109 #define	STATIC	static void
110 #endif
111 
112 /* ==================================== */
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 	unsigned char b[8];
230 	struct {
231 		int32_t	i0;
232 		int32_t	i1;
233 	} b32;
234 #if defined(B64)
235 	B64	b64;
236 #endif
237 } C_block;
238 
239 /*
240  * Convert twenty-four-bit long in host-order
241  * to six bits (and 2 low-order zeroes) per char little-endian format.
242  */
243 #define	TO_SIX_BIT(rslt, src) {				\
244 		C_block cvt;				\
245 		cvt.b[0] = src; src >>= 6;		\
246 		cvt.b[1] = src; src >>= 6;		\
247 		cvt.b[2] = src; src >>= 6;		\
248 		cvt.b[3] = src;				\
249 		rslt = (cvt.b32.i0 & 0x3f3f3f3fL) << 2;	\
250 	}
251 
252 /*
253  * These macros may someday permit efficient use of 64-bit integers.
254  */
255 #define	ZERO(d,d0,d1)			d0 = 0, d1 = 0
256 #define	LOAD(d,d0,d1,bl)		d0 = (bl).b32.i0, d1 = (bl).b32.i1
257 #define	LOADREG(d,d0,d1,s,s0,s1)	d0 = s0, d1 = s1
258 #define	OR(d,d0,d1,bl)			d0 |= (bl).b32.i0, d1 |= (bl).b32.i1
259 #define	STORE(s,s0,s1,bl)		(bl).b32.i0 = s0, (bl).b32.i1 = s1
260 #define	DCL_BLOCK(d,d0,d1)		int32_t d0, d1
261 
262 #if defined(LARGEDATA)
263 	/* Waste memory like crazy.  Also, do permutations in line */
264 #define	LGCHUNKBITS	3
265 #define	CHUNKBITS	(1<<LGCHUNKBITS)
266 #define	PERM6464(d,d0,d1,cpp,p)				\
267 	LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]);		\
268 	OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]);		\
269 	OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]);		\
270 	OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]);		\
271 	OR (d,d0,d1,(p)[(4<<CHUNKBITS)+(cpp)[4]]);		\
272 	OR (d,d0,d1,(p)[(5<<CHUNKBITS)+(cpp)[5]]);		\
273 	OR (d,d0,d1,(p)[(6<<CHUNKBITS)+(cpp)[6]]);		\
274 	OR (d,d0,d1,(p)[(7<<CHUNKBITS)+(cpp)[7]]);
275 #define	PERM3264(d,d0,d1,cpp,p)				\
276 	LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]);		\
277 	OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]);		\
278 	OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]);		\
279 	OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]);
280 #else
281 	/* "small data" */
282 #define	LGCHUNKBITS	2
283 #define	CHUNKBITS	(1<<LGCHUNKBITS)
284 #define	PERM6464(d,d0,d1,cpp,p)				\
285 	{ C_block tblk; permute(cpp,&tblk,p,8); LOAD (d,d0,d1,tblk); }
286 #define	PERM3264(d,d0,d1,cpp,p)				\
287 	{ C_block tblk; permute(cpp,&tblk,p,4); LOAD (d,d0,d1,tblk); }
288 #endif /* LARGEDATA */
289 
290 STATIC	init_des __P((void));
291 STATIC	init_perm __P((C_block [64/CHUNKBITS][1<<CHUNKBITS], unsigned char [64], int, int));
292 #ifndef LARGEDATA
293 STATIC	permute __P((unsigned char *, C_block *, C_block *, int));
294 #endif
295 #ifdef DEBUG
296 STATIC	prtab __P((char *, unsigned char *, int));
297 #endif
298 
299 
300 #ifndef LARGEDATA
301 STATIC
302 permute(cp, out, p, chars_in)
303 	unsigned char *cp;
304 	C_block *out;
305 	C_block *p;
306 	int chars_in;
307 {
308 	DCL_BLOCK(D,D0,D1);
309 	C_block *tp;
310 	int t;
311 
312 	ZERO(D,D0,D1);
313 	do {
314 		t = *cp++;
315 		tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
316 		tp = &p[t>>4];  OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
317 	} while (--chars_in > 0);
318 	STORE(D,D0,D1,*out);
319 }
320 #endif /* LARGEDATA */
321 
322 
323 /* =====  (mostly) Standard DES Tables ==================== */
324 
325 static const unsigned char IP[] = {	/* initial permutation */
326 	58, 50, 42, 34, 26, 18, 10,  2,
327 	60, 52, 44, 36, 28, 20, 12,  4,
328 	62, 54, 46, 38, 30, 22, 14,  6,
329 	64, 56, 48, 40, 32, 24, 16,  8,
330 	57, 49, 41, 33, 25, 17,  9,  1,
331 	59, 51, 43, 35, 27, 19, 11,  3,
332 	61, 53, 45, 37, 29, 21, 13,  5,
333 	63, 55, 47, 39, 31, 23, 15,  7,
334 };
335 
336 /* The final permutation is the inverse of IP - no table is necessary */
337 
338 static const unsigned char ExpandTr[] = {	/* expansion operation */
339 	32,  1,  2,  3,  4,  5,
340 	 4,  5,  6,  7,  8,  9,
341 	 8,  9, 10, 11, 12, 13,
342 	12, 13, 14, 15, 16, 17,
343 	16, 17, 18, 19, 20, 21,
344 	20, 21, 22, 23, 24, 25,
345 	24, 25, 26, 27, 28, 29,
346 	28, 29, 30, 31, 32,  1,
347 };
348 
349 static const unsigned char PC1[] = {	/* permuted choice table 1 */
350 	57, 49, 41, 33, 25, 17,  9,
351 	 1, 58, 50, 42, 34, 26, 18,
352 	10,  2, 59, 51, 43, 35, 27,
353 	19, 11,  3, 60, 52, 44, 36,
354 
355 	63, 55, 47, 39, 31, 23, 15,
356 	 7, 62, 54, 46, 38, 30, 22,
357 	14,  6, 61, 53, 45, 37, 29,
358 	21, 13,  5, 28, 20, 12,  4,
359 };
360 
361 static const unsigned char Rotates[] = {/* PC1 rotation schedule */
362 	1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
363 };
364 
365 /* note: each "row" of PC2 is left-padded with bits that make it invertible */
366 static const unsigned char PC2[] = {	/* permuted choice table 2 */
367 	 9, 18,    14, 17, 11, 24,  1,  5,
368 	22, 25,     3, 28, 15,  6, 21, 10,
369 	35, 38,    23, 19, 12,  4, 26,  8,
370 	43, 54,    16,  7, 27, 20, 13,  2,
371 
372 	 0,  0,    41, 52, 31, 37, 47, 55,
373 	 0,  0,    30, 40, 51, 45, 33, 48,
374 	 0,  0,    44, 49, 39, 56, 34, 53,
375 	 0,  0,    46, 42, 50, 36, 29, 32,
376 };
377 
378 static const unsigned char S[8][64] = {	/* 48->32 bit substitution tables */
379 					/* S[1]			*/
380 	{ 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
381 	   0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
382 	   4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
383 	  15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13 },
384 					/* S[2]			*/
385 	{ 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
386 	   3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
387 	   0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
388 	  13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9 },
389 					/* S[3]			*/
390 	{ 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
391 	  13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
392 	  13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
393 	   1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12 },
394 					/* S[4]			*/
395 	{  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
396 	  13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
397 	  10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
398 	   3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14 },
399 					/* S[5]			*/
400 	{  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
401 	  14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
402 	   4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
403 	  11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3 },
404 					/* S[6]			*/
405 	{ 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
406 	  10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
407 	   9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
408 	   4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13 },
409 					/* S[7]			*/
410 	{  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
411 	  13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
412 	   1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
413 	   6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12 },
414 					/* S[8]			*/
415 	{ 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
416 	   1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
417 	   7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
418 	   2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11 }
419 };
420 
421 static const unsigned char P32Tr[] = {	/* 32-bit permutation function */
422 	16,  7, 20, 21,
423 	29, 12, 28, 17,
424 	 1, 15, 23, 26,
425 	 5, 18, 31, 10,
426 	 2,  8, 24, 14,
427 	32, 27,  3,  9,
428 	19, 13, 30,  6,
429 	22, 11,  4, 25,
430 };
431 
432 static const unsigned char CIFP[] = {	/* compressed/interleaved permutation */
433 	 1,  2,  3,  4,   17, 18, 19, 20,
434 	 5,  6,  7,  8,   21, 22, 23, 24,
435 	 9, 10, 11, 12,   25, 26, 27, 28,
436 	13, 14, 15, 16,   29, 30, 31, 32,
437 
438 	33, 34, 35, 36,   49, 50, 51, 52,
439 	37, 38, 39, 40,   53, 54, 55, 56,
440 	41, 42, 43, 44,   57, 58, 59, 60,
441 	45, 46, 47, 48,   61, 62, 63, 64,
442 };
443 
444 static const unsigned char itoa64[] =		/* 0..63 => ascii-64 */
445 	"./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
446 
447 
448 /* =====  Tables that are initialized at run time  ==================== */
449 
450 
451 static unsigned char a64toi[128];	/* ascii-64 => 0..63 */
452 
453 /* Initial key schedule permutation */
454 static C_block	PC1ROT[64/CHUNKBITS][1<<CHUNKBITS];
455 
456 /* Subsequent key schedule rotation permutations */
457 static C_block	PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS];
458 
459 /* Initial permutation/expansion table */
460 static C_block	IE3264[32/CHUNKBITS][1<<CHUNKBITS];
461 
462 /* Table that combines the S, P, and E operations.  */
463 static int32_t SPE[2][8][64];
464 
465 /* compressed/interleaved => final permutation table */
466 static C_block	CF6464[64/CHUNKBITS][1<<CHUNKBITS];
467 
468 
469 /* ==================================== */
470 
471 
472 static C_block	constdatablock;			/* encryption constant */
473 static char	cryptresult[1+4+4+11+1];	/* encrypted result */
474 
475 
476 /*
477  * Return a pointer to static data consisting of the "setting"
478  * followed by an encryption produced by the "key" and "setting".
479  */
480 char *
481 crypt(key, setting)
482 	const char *key;
483 	const char *setting;
484 {
485 	char *encp;
486 	int32_t i;
487 	int t;
488 	int32_t salt;
489 	int num_iter, salt_size;
490 	C_block keyblock, rsltblock;
491 
492 	/* Non-DES encryption schemes hook in here. */
493 	if (setting[0] == _PASSWORD_NONDES) {
494 		switch (setting[1]) {
495 		case '2':
496 			return (__bcrypt(key, setting));
497 		case 's':
498 			return (__crypt_sha1(key, setting));
499 		case '1':
500 		default:
501 			return (__md5crypt(key, setting));
502 		}
503 	}
504 
505 	for (i = 0; i < 8; i++) {
506 		if ((t = 2*(unsigned char)(*key)) != 0)
507 			key++;
508 		keyblock.b[i] = t;
509 	}
510 	if (des_setkey((char *)keyblock.b))	/* also initializes "a64toi" */
511 		return (NULL);
512 
513 	encp = &cryptresult[0];
514 	switch (*setting) {
515 	case _PASSWORD_EFMT1:
516 		/*
517 		 * Involve the rest of the password 8 characters at a time.
518 		 */
519 		while (*key) {
520 			if (des_cipher((char *)(void *)&keyblock,
521 			    (char *)(void *)&keyblock, 0L, 1))
522 				return (NULL);
523 			for (i = 0; i < 8; i++) {
524 				if ((t = 2*(unsigned char)(*key)) != 0)
525 					key++;
526 				keyblock.b[i] ^= t;
527 			}
528 			if (des_setkey((char *)keyblock.b))
529 				return (NULL);
530 		}
531 
532 		*encp++ = *setting++;
533 
534 		/* get iteration count */
535 		num_iter = 0;
536 		for (i = 4; --i >= 0; ) {
537 			if ((t = (unsigned char)setting[i]) == '\0')
538 				t = '.';
539 			encp[i] = t;
540 			num_iter = (num_iter<<6) | a64toi[t];
541 		}
542 		setting += 4;
543 		encp += 4;
544 		salt_size = 4;
545 		break;
546 	default:
547 		num_iter = 25;
548 		salt_size = 2;
549 	}
550 
551 	salt = 0;
552 	for (i = salt_size; --i >= 0; ) {
553 		if ((t = (unsigned char)setting[i]) == '\0')
554 			t = '.';
555 		encp[i] = t;
556 		salt = (salt<<6) | a64toi[t];
557 	}
558 	encp += salt_size;
559 	if (des_cipher((char *)(void *)&constdatablock,
560 	    (char *)(void *)&rsltblock, salt, num_iter))
561 		return (NULL);
562 
563 	/*
564 	 * Encode the 64 cipher bits as 11 ascii characters.
565 	 */
566 	i = ((int32_t)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) |
567 	    rsltblock.b[2];
568 	encp[3] = itoa64[i&0x3f];	i >>= 6;
569 	encp[2] = itoa64[i&0x3f];	i >>= 6;
570 	encp[1] = itoa64[i&0x3f];	i >>= 6;
571 	encp[0] = itoa64[i];		encp += 4;
572 	i = ((int32_t)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) |
573 	    rsltblock.b[5];
574 	encp[3] = itoa64[i&0x3f];	i >>= 6;
575 	encp[2] = itoa64[i&0x3f];	i >>= 6;
576 	encp[1] = itoa64[i&0x3f];	i >>= 6;
577 	encp[0] = itoa64[i];		encp += 4;
578 	i = ((int32_t)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2;
579 	encp[2] = itoa64[i&0x3f];	i >>= 6;
580 	encp[1] = itoa64[i&0x3f];	i >>= 6;
581 	encp[0] = itoa64[i];
582 
583 	encp[3] = 0;
584 
585 	return (cryptresult);
586 }
587 
588 
589 /*
590  * The Key Schedule, filled in by des_setkey() or setkey().
591  */
592 #define	KS_SIZE	16
593 static C_block	KS[KS_SIZE];
594 
595 /*
596  * Set up the key schedule from the key.
597  */
598 int
599 des_setkey(key)
600 	const char *key;
601 {
602 	DCL_BLOCK(K, K0, K1);
603 	C_block *ptabp;
604 	int i;
605 	static int des_ready = 0;
606 
607 	if (!des_ready) {
608 		init_des();
609 		des_ready = 1;
610 	}
611 
612 	PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT);
613 	key = (char *)&KS[0];
614 	STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key);
615 	for (i = 1; i < 16; i++) {
616 		key += sizeof(C_block);
617 		STORE(K,K0,K1,*(C_block *)key);
618 		ptabp = (C_block *)PC2ROT[Rotates[i]-1];
619 		PERM6464(K,K0,K1,(unsigned char *)key,ptabp);
620 		STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key);
621 	}
622 	return (0);
623 }
624 
625 /*
626  * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter)
627  * iterations of DES, using the given 24-bit salt and the pre-computed key
628  * schedule, and store the resulting 8 chars at "out" (in == out is permitted).
629  *
630  * NOTE: the performance of this routine is critically dependent on your
631  * compiler and machine architecture.
632  */
633 int
634 des_cipher(in, out, salt, num_iter)
635 	const char *in;
636 	char *out;
637 	long salt;
638 	int num_iter;
639 {
640 	/* variables that we want in registers, most important first */
641 #if defined(pdp11)
642 	int j;
643 #endif
644 	int32_t L0, L1, R0, R1, k;
645 	C_block *kp;
646 	int ks_inc, loop_count;
647 	C_block B;
648 
649 	L0 = salt;
650 	TO_SIX_BIT(salt, L0);	/* convert to 4*(6+2) format */
651 
652 #if defined(__vax__) || defined(pdp11)
653 	salt = ~salt;	/* "x &~ y" is faster than "x & y". */
654 #define	SALT (~salt)
655 #else
656 #define	SALT salt
657 #endif
658 
659 #if defined(MUST_ALIGN)
660 	B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3];
661 	B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7];
662 	LOAD(L,L0,L1,B);
663 #else
664 	LOAD(L,L0,L1,*(C_block *)in);
665 #endif
666 	LOADREG(R,R0,R1,L,L0,L1);
667 	L0 &= 0x55555555L;
668 	L1 &= 0x55555555L;
669 	L0 = (L0 << 1) | L1;	/* L0 is the even-numbered input bits */
670 	R0 &= 0xaaaaaaaaL;
671 	R1 = (R1 >> 1) & 0x55555555L;
672 	L1 = R0 | R1;		/* L1 is the odd-numbered input bits */
673 	STORE(L,L0,L1,B);
674 	PERM3264(L,L0,L1,B.b,  (C_block *)IE3264);	/* even bits */
675 	PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264);	/* odd bits */
676 
677 	if (num_iter >= 0)
678 	{		/* encryption */
679 		kp = &KS[0];
680 		ks_inc  = sizeof(*kp);
681 	}
682 	else
683 	{		/* decryption */
684 		num_iter = -num_iter;
685 		kp = &KS[KS_SIZE-1];
686 		ks_inc  = -(long)sizeof(*kp);
687 	}
688 
689 	while (--num_iter >= 0) {
690 		loop_count = 8;
691 		do {
692 
693 #define	SPTAB(t, i) \
694 	    (*(int32_t *)((unsigned char *)t + i*(sizeof(int32_t)/4)))
695 #if defined(gould)
696 			/* use this if B.b[i] is evaluated just once ... */
697 #define	DOXOR(x,y,i)	x^=SPTAB(SPE[0][i],B.b[i]); y^=SPTAB(SPE[1][i],B.b[i]);
698 #else
699 #if defined(pdp11)
700 			/* use this if your "long" int indexing is slow */
701 #define	DOXOR(x,y,i)	j=B.b[i]; x^=SPTAB(SPE[0][i],j); y^=SPTAB(SPE[1][i],j);
702 #else
703 			/* use this if "k" is allocated to a register ... */
704 #define	DOXOR(x,y,i)	k=B.b[i]; x^=SPTAB(SPE[0][i],k); y^=SPTAB(SPE[1][i],k);
705 #endif
706 #endif
707 
708 #define	CRUNCH(p0, p1, q0, q1)	\
709 			k = (q0 ^ q1) & SALT;	\
710 			B.b32.i0 = k ^ q0 ^ kp->b32.i0;		\
711 			B.b32.i1 = k ^ q1 ^ kp->b32.i1;		\
712 			kp = (C_block *)((char *)kp+ks_inc);	\
713 							\
714 			DOXOR(p0, p1, 0);		\
715 			DOXOR(p0, p1, 1);		\
716 			DOXOR(p0, p1, 2);		\
717 			DOXOR(p0, p1, 3);		\
718 			DOXOR(p0, p1, 4);		\
719 			DOXOR(p0, p1, 5);		\
720 			DOXOR(p0, p1, 6);		\
721 			DOXOR(p0, p1, 7);
722 
723 			CRUNCH(L0, L1, R0, R1);
724 			CRUNCH(R0, R1, L0, L1);
725 		} while (--loop_count != 0);
726 		kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE));
727 
728 
729 		/* swap L and R */
730 		L0 ^= R0;  L1 ^= R1;
731 		R0 ^= L0;  R1 ^= L1;
732 		L0 ^= R0;  L1 ^= R1;
733 	}
734 
735 	/* store the encrypted (or decrypted) result */
736 	L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L);
737 	L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L);
738 	STORE(L,L0,L1,B);
739 	PERM6464(L,L0,L1,B.b, (C_block *)CF6464);
740 #if defined(MUST_ALIGN)
741 	STORE(L,L0,L1,B);
742 	out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3];
743 	out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7];
744 #else
745 	STORE(L,L0,L1,*(C_block *)out);
746 #endif
747 	return (0);
748 }
749 
750 
751 /*
752  * Initialize various tables.  This need only be done once.  It could even be
753  * done at compile time, if the compiler were capable of that sort of thing.
754  */
755 STATIC
756 init_des()
757 {
758 	int i, j;
759 	int32_t k;
760 	int tableno;
761 	static unsigned char perm[64], tmp32[32];	/* "static" for speed */
762 
763 	/*
764 	 * table that converts chars "./0-9A-Za-z"to integers 0-63.
765 	 */
766 	for (i = 0; i < 64; i++)
767 		a64toi[itoa64[i]] = i;
768 
769 	/*
770 	 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2.
771 	 */
772 	for (i = 0; i < 64; i++)
773 		perm[i] = 0;
774 	for (i = 0; i < 64; i++) {
775 		if ((k = PC2[i]) == 0)
776 			continue;
777 		k += Rotates[0]-1;
778 		if ((k%28) < Rotates[0]) k -= 28;
779 		k = PC1[k];
780 		if (k > 0) {
781 			k--;
782 			k = (k|07) - (k&07);
783 			k++;
784 		}
785 		perm[i] = k;
786 	}
787 #ifdef DEBUG
788 	prtab("pc1tab", perm, 8);
789 #endif
790 	init_perm(PC1ROT, perm, 8, 8);
791 
792 	/*
793 	 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2.
794 	 */
795 	for (j = 0; j < 2; j++) {
796 		unsigned char pc2inv[64];
797 		for (i = 0; i < 64; i++)
798 			perm[i] = pc2inv[i] = 0;
799 		for (i = 0; i < 64; i++) {
800 			if ((k = PC2[i]) == 0)
801 				continue;
802 			pc2inv[k-1] = i+1;
803 		}
804 		for (i = 0; i < 64; i++) {
805 			if ((k = PC2[i]) == 0)
806 				continue;
807 			k += j;
808 			if ((k%28) <= j) k -= 28;
809 			perm[i] = pc2inv[k];
810 		}
811 #ifdef DEBUG
812 		prtab("pc2tab", perm, 8);
813 #endif
814 		init_perm(PC2ROT[j], perm, 8, 8);
815 	}
816 
817 	/*
818 	 * Bit reverse, then initial permutation, then expansion.
819 	 */
820 	for (i = 0; i < 8; i++) {
821 		for (j = 0; j < 8; j++) {
822 			k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1];
823 			if (k > 32)
824 				k -= 32;
825 			else if (k > 0)
826 				k--;
827 			if (k > 0) {
828 				k--;
829 				k = (k|07) - (k&07);
830 				k++;
831 			}
832 			perm[i*8+j] = k;
833 		}
834 	}
835 #ifdef DEBUG
836 	prtab("ietab", perm, 8);
837 #endif
838 	init_perm(IE3264, perm, 4, 8);
839 
840 	/*
841 	 * Compression, then final permutation, then bit reverse.
842 	 */
843 	for (i = 0; i < 64; i++) {
844 		k = IP[CIFP[i]-1];
845 		if (k > 0) {
846 			k--;
847 			k = (k|07) - (k&07);
848 			k++;
849 		}
850 		perm[k-1] = i+1;
851 	}
852 #ifdef DEBUG
853 	prtab("cftab", perm, 8);
854 #endif
855 	init_perm(CF6464, perm, 8, 8);
856 
857 	/*
858 	 * SPE table
859 	 */
860 	for (i = 0; i < 48; i++)
861 		perm[i] = P32Tr[ExpandTr[i]-1];
862 	for (tableno = 0; tableno < 8; tableno++) {
863 		for (j = 0; j < 64; j++)  {
864 			k = (((j >> 0) &01) << 5)|
865 			    (((j >> 1) &01) << 3)|
866 			    (((j >> 2) &01) << 2)|
867 			    (((j >> 3) &01) << 1)|
868 			    (((j >> 4) &01) << 0)|
869 			    (((j >> 5) &01) << 4);
870 			k = S[tableno][k];
871 			k = (((k >> 3)&01) << 0)|
872 			    (((k >> 2)&01) << 1)|
873 			    (((k >> 1)&01) << 2)|
874 			    (((k >> 0)&01) << 3);
875 			for (i = 0; i < 32; i++)
876 				tmp32[i] = 0;
877 			for (i = 0; i < 4; i++)
878 				tmp32[4 * tableno + i] = (k >> i) & 01;
879 			k = 0;
880 			for (i = 24; --i >= 0; )
881 				k = (k<<1) | tmp32[perm[i]-1];
882 			TO_SIX_BIT(SPE[0][tableno][j], k);
883 			k = 0;
884 			for (i = 24; --i >= 0; )
885 				k = (k<<1) | tmp32[perm[i+24]-1];
886 			TO_SIX_BIT(SPE[1][tableno][j], k);
887 		}
888 	}
889 }
890 
891 /*
892  * Initialize "perm" to represent transformation "p", which rearranges
893  * (perhaps with expansion and/or contraction) one packed array of bits
894  * (of size "chars_in" characters) into another array (of size "chars_out"
895  * characters).
896  *
897  * "perm" must be all-zeroes on entry to this routine.
898  */
899 STATIC
900 init_perm(perm, p, chars_in, chars_out)
901 	C_block perm[64/CHUNKBITS][1<<CHUNKBITS];
902 	unsigned char p[64];
903 	int chars_in, chars_out;
904 {
905 	int i, j, k, l;
906 
907 	for (k = 0; k < chars_out*8; k++) {	/* each output bit position */
908 		l = p[k] - 1;		/* where this bit comes from */
909 		if (l < 0)
910 			continue;	/* output bit is always 0 */
911 		i = l>>LGCHUNKBITS;	/* which chunk this bit comes from */
912 		l = 1<<(l&(CHUNKBITS-1));	/* mask for this bit */
913 		for (j = 0; j < (1<<CHUNKBITS); j++) {	/* each chunk value */
914 			if ((j & l) != 0)
915 				perm[i][j].b[k>>3] |= 1<<(k&07);
916 		}
917 	}
918 }
919 
920 /*
921  * "setkey" routine (for backwards compatibility)
922  */
923 int
924 setkey(key)
925 	const char *key;
926 {
927 	int i, j, k;
928 	C_block keyblock;
929 
930 	for (i = 0; i < 8; i++) {
931 		k = 0;
932 		for (j = 0; j < 8; j++) {
933 			k <<= 1;
934 			k |= (unsigned char)*key++;
935 		}
936 		keyblock.b[i] = k;
937 	}
938 	return (des_setkey((char *)keyblock.b));
939 }
940 
941 /*
942  * "encrypt" routine (for backwards compatibility)
943  */
944 int
945 encrypt(block, flag)
946 	char *block;
947 	int flag;
948 {
949 	int i, j, k;
950 	C_block cblock;
951 
952 	for (i = 0; i < 8; i++) {
953 		k = 0;
954 		for (j = 0; j < 8; j++) {
955 			k <<= 1;
956 			k |= (unsigned char)*block++;
957 		}
958 		cblock.b[i] = k;
959 	}
960 	if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1)))
961 		return (1);
962 	for (i = 7; i >= 0; i--) {
963 		k = cblock.b[i];
964 		for (j = 7; j >= 0; j--) {
965 			*--block = k&01;
966 			k >>= 1;
967 		}
968 	}
969 	return (0);
970 }
971 
972 #ifdef DEBUG
973 STATIC
974 prtab(s, t, num_rows)
975 	char *s;
976 	unsigned char *t;
977 	int num_rows;
978 {
979 	int i, j;
980 
981 	(void)printf("%s:\n", s);
982 	for (i = 0; i < num_rows; i++) {
983 		for (j = 0; j < 8; j++) {
984 			 (void)printf("%3d", t[i*8+j]);
985 		}
986 		(void)printf("\n");
987 	}
988 	(void)printf("\n");
989 }
990 #endif
991 
992 #if defined(MAIN) || defined(UNIT_TEST)
993 #include <stdio.h>
994 #include <err.h>
995 
996 int
997 main (int argc, char *argv[])
998 {
999     if (argc < 2)
1000 	errx(1, "Usage: %s password [salt]\n", argv[0]);
1001 
1002     printf("%s\n", crypt(argv[1], (argc > 2) ? argv[2] : argv[1]));
1003     exit(0);
1004 }
1005 #endif
1006