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