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