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 {
233 int32_t i0;
234 int32_t i1;
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
permute(cp,out,p,chars_in)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 *
crypt(key,setting)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
626 static C_block KS[KS_SIZE];
627
628 static volatile int des_ready = 0;
629
630 /*
631 * Set up the key schedule from the key.
632 */
633 static int
des_setkey(key)634 des_setkey(key)
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
des_cipher(in,out,salt,num_iter)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
init_des()811 init_des()
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
init_perm(perm,p,chars_in,chars_out)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
setkey(key)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
encrypt(block,flag)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
prtab(s,t,num_rows)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
1089