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