1 /*
2 * FreeSec: libcrypt for NetBSD
3 *
4 * Copyright (c) 1994 David Burren
5 * All rights reserved.
6 *
7 * Adapted for FreeBSD-2.0 by Geoffrey M. Rehmet
8 * this file should now *only* export crypt(), in order to make
9 * binaries of libcrypt exportable from the USA
10 *
11 * Adapted for FreeBSD-4.0 by Mark R V Murray
12 * this file should now *only* export crypt_des(), in order to make
13 * a module that can be optionally included in libcrypt.
14 *
15 * Redistribution and use in source and binary forms, with or without
16 * modification, are permitted provided that the following conditions
17 * are met:
18 * 1. Redistributions of source code must retain the above copyright
19 * notice, this list of conditions and the following disclaimer.
20 * 2. Redistributions in binary form must reproduce the above copyright
21 * notice, this list of conditions and the following disclaimer in the
22 * documentation and/or other materials provided with the distribution.
23 * 3. Neither the name of the author nor the names of other contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ''AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 *
39 * This is an original implementation of the DES and the crypt(3) interfaces
40 * by David Burren <davidb@werj.com.au>.
41 *
42 * An excellent reference on the underlying algorithm (and related
43 * algorithms) is:
44 *
45 * B. Schneier, Applied Cryptography: protocols, algorithms,
46 * and source code in C, John Wiley & Sons, 1994.
47 *
48 * Note that in that book's description of DES the lookups for the initial,
49 * pbox, and final permutations are inverted (this has been brought to the
50 * attention of the author). A list of errata for this book has been
51 * posted to the sci.crypt newsgroup by the author and is available for FTP.
52 *
53 * ARCHITECTURE ASSUMPTIONS:
54 * It is assumed that the 8-byte arrays passed by reference can be
55 * addressed as arrays of uint32_t's (ie. the CPU is not picky about
56 * alignment).
57 */
58
59
60 /* Parts busybox doesn't need or had optimized */
61 #define USE_PRECOMPUTED_u_sbox 1
62 #define USE_REPETITIVE_SPEEDUP 0
63 #define USE_ip_mask 0
64 #define USE_de_keys 0
65
66
67 /* A pile of data */
68 static const uint8_t IP[64] ALIGN1 = {
69 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
70 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
71 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
72 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
73 };
74
75 static const uint8_t key_perm[56] ALIGN1 = {
76 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
77 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
78 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
79 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
80 };
81
82 static const uint8_t key_shifts[16] ALIGN1 = {
83 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
84 };
85
86 static const uint8_t comp_perm[48] ALIGN1 = {
87 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
88 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
89 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
90 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
91 };
92
93 /*
94 * No E box is used, as it's replaced by some ANDs, shifts, and ORs.
95 */
96 #if !USE_PRECOMPUTED_u_sbox
97 static const uint8_t sbox[8][64] = {
98 { 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
99 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
100 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
101 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
102 },
103 { 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
104 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
105 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
106 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
107 },
108 { 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
109 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
110 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
111 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
112 },
113 { 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
114 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
115 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
116 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
117 },
118 { 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
119 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
120 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
121 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
122 },
123 { 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
124 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
125 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
126 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
127 },
128 { 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
129 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
130 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
131 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
132 },
133 { 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
134 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
135 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
136 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
137 }
138 };
139 #else /* precomputed, with half-bytes packed into one byte */
140 static const uint8_t u_sbox[8][32] = {
141 { 0x0e, 0xf4, 0x7d, 0x41, 0xe2, 0x2f, 0xdb, 0x18,
142 0xa3, 0x6a, 0xc6, 0xbc, 0x95, 0x59, 0x30, 0x87,
143 0xf4, 0xc1, 0x8e, 0x28, 0x4d, 0x96, 0x12, 0x7b,
144 0x5f, 0xbc, 0x39, 0xe7, 0xa3, 0x0a, 0x65, 0xd0,
145 },
146 { 0x3f, 0xd1, 0x48, 0x7e, 0xf6, 0x2b, 0x83, 0xe4,
147 0xc9, 0x07, 0x12, 0xad, 0x6c, 0x90, 0xb5, 0x5a,
148 0xd0, 0x8e, 0xa7, 0x1b, 0x3a, 0xf4, 0x4d, 0x21,
149 0xb5, 0x68, 0x7c, 0xc6, 0x09, 0x53, 0xe2, 0x9f,
150 },
151 { 0xda, 0x70, 0x09, 0x9e, 0x36, 0x43, 0x6f, 0xa5,
152 0x21, 0x8d, 0x5c, 0xe7, 0xcb, 0xb4, 0xf2, 0x18,
153 0x1d, 0xa6, 0xd4, 0x09, 0x68, 0x9f, 0x83, 0x70,
154 0x4b, 0xf1, 0xe2, 0x3c, 0xb5, 0x5a, 0x2e, 0xc7,
155 },
156 { 0xd7, 0x8d, 0xbe, 0x53, 0x60, 0xf6, 0x09, 0x3a,
157 0x41, 0x72, 0x28, 0xc5, 0x1b, 0xac, 0xe4, 0x9f,
158 0x3a, 0xf6, 0x09, 0x60, 0xac, 0x1b, 0xd7, 0x8d,
159 0x9f, 0x41, 0x53, 0xbe, 0xc5, 0x72, 0x28, 0xe4,
160 },
161 { 0xe2, 0xbc, 0x24, 0xc1, 0x47, 0x7a, 0xdb, 0x16,
162 0x58, 0x05, 0xf3, 0xaf, 0x3d, 0x90, 0x8e, 0x69,
163 0xb4, 0x82, 0xc1, 0x7b, 0x1a, 0xed, 0x27, 0xd8,
164 0x6f, 0xf9, 0x0c, 0x95, 0xa6, 0x43, 0x50, 0x3e,
165 },
166 { 0xac, 0xf1, 0x4a, 0x2f, 0x79, 0xc2, 0x96, 0x58,
167 0x60, 0x1d, 0xd3, 0xe4, 0x0e, 0xb7, 0x35, 0x8b,
168 0x49, 0x3e, 0x2f, 0xc5, 0x92, 0x58, 0xfc, 0xa3,
169 0xb7, 0xe0, 0x14, 0x7a, 0x61, 0x0d, 0x8b, 0xd6,
170 },
171 { 0xd4, 0x0b, 0xb2, 0x7e, 0x4f, 0x90, 0x18, 0xad,
172 0xe3, 0x3c, 0x59, 0xc7, 0x25, 0xfa, 0x86, 0x61,
173 0x61, 0xb4, 0xdb, 0x8d, 0x1c, 0x43, 0xa7, 0x7e,
174 0x9a, 0x5f, 0x06, 0xf8, 0xe0, 0x25, 0x39, 0xc2,
175 },
176 { 0x1d, 0xf2, 0xd8, 0x84, 0xa6, 0x3f, 0x7b, 0x41,
177 0xca, 0x59, 0x63, 0xbe, 0x05, 0xe0, 0x9c, 0x27,
178 0x27, 0x1b, 0xe4, 0x71, 0x49, 0xac, 0x8e, 0xd2,
179 0xf0, 0xc6, 0x9a, 0x0d, 0x3f, 0x53, 0x65, 0xb8,
180 },
181 };
182 #endif
183
184 static const uint8_t pbox[32] ALIGN1 = {
185 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
186 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
187 };
188
189 static const uint32_t bits32[32] ALIGN4 = {
190 0x80000000, 0x40000000, 0x20000000, 0x10000000,
191 0x08000000, 0x04000000, 0x02000000, 0x01000000,
192 0x00800000, 0x00400000, 0x00200000, 0x00100000,
193 0x00080000, 0x00040000, 0x00020000, 0x00010000,
194 0x00008000, 0x00004000, 0x00002000, 0x00001000,
195 0x00000800, 0x00000400, 0x00000200, 0x00000100,
196 0x00000080, 0x00000040, 0x00000020, 0x00000010,
197 0x00000008, 0x00000004, 0x00000002, 0x00000001
198 };
199
200 static const uint8_t bits8[8] ALIGN1 = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
201
202
203 static int
ascii_to_bin(char ch)204 ascii_to_bin(char ch)
205 {
206 if (ch > 'z')
207 return 0;
208 if (ch >= 'a')
209 return (ch - 'a' + 38);
210 if (ch > 'Z')
211 return 0;
212 if (ch >= 'A')
213 return (ch - 'A' + 12);
214 if (ch > '9')
215 return 0;
216 if (ch >= '.')
217 return (ch - '.');
218 return 0;
219 }
220
221
222 /* Static stuff that stays resident and doesn't change after
223 * being initialized, and therefore doesn't need to be made
224 * reentrant. */
225 struct const_des_ctx {
226 #if USE_ip_mask
227 uint8_t init_perm[64]; /* referenced 2 times */
228 #endif
229 uint8_t final_perm[64]; /* 2 times */
230 uint8_t m_sbox[4][4096]; /* 5 times */
231 };
232 #define C (*cctx)
233 #define init_perm (C.init_perm )
234 #define final_perm (C.final_perm)
235 #define m_sbox (C.m_sbox )
236
237 static struct const_des_ctx*
const_des_init(void)238 const_des_init(void)
239 {
240 unsigned i, j, b;
241 struct const_des_ctx *cctx;
242
243 #if !USE_PRECOMPUTED_u_sbox
244 uint8_t u_sbox[8][64];
245
246 cctx = xmalloc(sizeof(*cctx));
247
248 /* Invert the S-boxes, reordering the input bits. */
249 for (i = 0; i < 8; i++) {
250 for (j = 0; j < 64; j++) {
251 b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
252 u_sbox[i][j] = sbox[i][b];
253 }
254 }
255 for (i = 0; i < 8; i++) {
256 fprintf(stderr, "\t{\t");
257 for (j = 0; j < 64; j+=2)
258 fprintf(stderr, " 0x%02x,", u_sbox[i][j] + u_sbox[i][j+1]*16);
259 fprintf(stderr, "\n\t},\n");
260 }
261 /*
262 * Convert the inverted S-boxes into 4 arrays of 8 bits.
263 * Each will handle 12 bits of the S-box input.
264 */
265 for (b = 0; b < 4; b++)
266 for (i = 0; i < 64; i++)
267 for (j = 0; j < 64; j++)
268 m_sbox[b][(i << 6) | j] =
269 (uint8_t)((u_sbox[(b << 1)][i] << 4) |
270 u_sbox[(b << 1) + 1][j]);
271 #else
272 cctx = xmalloc(sizeof(*cctx));
273
274 /*
275 * Convert the inverted S-boxes into 4 arrays of 8 bits.
276 * Each will handle 12 bits of the S-box input.
277 */
278 for (b = 0; b < 4; b++)
279 for (i = 0; i < 64; i++)
280 for (j = 0; j < 64; j++) {
281 uint8_t lo, hi;
282 hi = u_sbox[(b << 1)][i / 2];
283 if (!(i & 1))
284 hi <<= 4;
285 lo = u_sbox[(b << 1) + 1][j / 2];
286 if (j & 1)
287 lo >>= 4;
288 m_sbox[b][(i << 6) | j] = (hi & 0xf0) | (lo & 0x0f);
289 }
290 #endif
291
292 /*
293 * Set up the initial & final permutations into a useful form.
294 */
295 for (i = 0; i < 64; i++) {
296 final_perm[i] = IP[i] - 1;
297 #if USE_ip_mask
298 init_perm[final_perm[i]] = (uint8_t)i;
299 #endif
300 }
301
302 return cctx;
303 }
304
305
306 struct des_ctx {
307 const struct const_des_ctx *const_ctx;
308 uint32_t saltbits; /* referenced 5 times */
309 #if USE_REPETITIVE_SPEEDUP
310 uint32_t old_salt; /* 3 times */
311 uint32_t old_rawkey0, old_rawkey1; /* 3 times each */
312 #endif
313 uint8_t un_pbox[32]; /* 2 times */
314 uint8_t inv_comp_perm[56]; /* 3 times */
315 uint8_t inv_key_perm[64]; /* 3 times */
316 uint32_t en_keysl[16], en_keysr[16]; /* 2 times each */
317 #if USE_de_keys
318 uint32_t de_keysl[16], de_keysr[16]; /* 2 times each */
319 #endif
320 #if USE_ip_mask
321 uint32_t ip_maskl[8][256], ip_maskr[8][256]; /* 9 times each */
322 #endif
323 uint32_t fp_maskl[8][256], fp_maskr[8][256]; /* 9 times each */
324 uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128]; /* 9 times */
325 uint32_t comp_maskl[8][128], comp_maskr[8][128]; /* 9 times each */
326 uint32_t psbox[4][256]; /* 5 times */
327 };
328 #define D (*ctx)
329 #define const_ctx (D.const_ctx )
330 #define saltbits (D.saltbits )
331 #define old_salt (D.old_salt )
332 #define old_rawkey0 (D.old_rawkey0 )
333 #define old_rawkey1 (D.old_rawkey1 )
334 #define un_pbox (D.un_pbox )
335 #define inv_comp_perm (D.inv_comp_perm )
336 #define inv_key_perm (D.inv_key_perm )
337 #define en_keysl (D.en_keysl )
338 #define en_keysr (D.en_keysr )
339 #define de_keysl (D.de_keysl )
340 #define de_keysr (D.de_keysr )
341 #define ip_maskl (D.ip_maskl )
342 #define ip_maskr (D.ip_maskr )
343 #define fp_maskl (D.fp_maskl )
344 #define fp_maskr (D.fp_maskr )
345 #define key_perm_maskl (D.key_perm_maskl )
346 #define key_perm_maskr (D.key_perm_maskr )
347 #define comp_maskl (D.comp_maskl )
348 #define comp_maskr (D.comp_maskr )
349 #define psbox (D.psbox )
350
351 static struct des_ctx*
des_init(struct des_ctx * ctx,const struct const_des_ctx * cctx)352 des_init(struct des_ctx *ctx, const struct const_des_ctx *cctx)
353 {
354 int i, j, b, k, inbit, obit;
355 uint32_t p;
356 const uint32_t *bits28, *bits24;
357
358 if (!ctx)
359 ctx = xmalloc(sizeof(*ctx));
360 const_ctx = cctx;
361
362 #if USE_REPETITIVE_SPEEDUP
363 old_rawkey0 = old_rawkey1 = 0;
364 old_salt = 0;
365 #endif
366 //saltbits = 0; /* not needed: we call setup_salt() before do_des() */
367 bits28 = bits32 + 4;
368 bits24 = bits28 + 4;
369
370 /* Initialise the inverted key permutation. */
371 for (i = 0; i < 64; i++) {
372 inv_key_perm[i] = 255;
373 }
374
375 /*
376 * Invert the key permutation and initialise the inverted key
377 * compression permutation.
378 */
379 for (i = 0; i < 56; i++) {
380 inv_key_perm[key_perm[i] - 1] = (uint8_t)i;
381 inv_comp_perm[i] = 255;
382 }
383
384 /* Invert the key compression permutation. */
385 for (i = 0; i < 48; i++) {
386 inv_comp_perm[comp_perm[i] - 1] = (uint8_t)i;
387 }
388
389 /*
390 * Set up the OR-mask arrays for the initial and final permutations,
391 * and for the key initial and compression permutations.
392 */
393 for (k = 0; k < 8; k++) {
394 uint32_t il, ir;
395 uint32_t fl, fr;
396 for (i = 0; i < 256; i++) {
397 #if USE_ip_mask
398 il = 0;
399 ir = 0;
400 #endif
401 fl = 0;
402 fr = 0;
403 for (j = 0; j < 8; j++) {
404 inbit = 8 * k + j;
405 if (i & bits8[j]) {
406 #if USE_ip_mask
407 obit = init_perm[inbit];
408 if (obit < 32)
409 il |= bits32[obit];
410 else
411 ir |= bits32[obit - 32];
412 #endif
413 obit = final_perm[inbit];
414 if (obit < 32)
415 fl |= bits32[obit];
416 else
417 fr |= bits32[obit - 32];
418 }
419 }
420 #if USE_ip_mask
421 ip_maskl[k][i] = il;
422 ip_maskr[k][i] = ir;
423 #endif
424 fp_maskl[k][i] = fl;
425 fp_maskr[k][i] = fr;
426 }
427 for (i = 0; i < 128; i++) {
428 il = 0;
429 ir = 0;
430 for (j = 0; j < 7; j++) {
431 inbit = 8 * k + j;
432 if (i & bits8[j + 1]) {
433 obit = inv_key_perm[inbit];
434 if (obit == 255)
435 continue;
436 if (obit < 28)
437 il |= bits28[obit];
438 else
439 ir |= bits28[obit - 28];
440 }
441 }
442 key_perm_maskl[k][i] = il;
443 key_perm_maskr[k][i] = ir;
444 il = 0;
445 ir = 0;
446 for (j = 0; j < 7; j++) {
447 inbit = 7 * k + j;
448 if (i & bits8[j + 1]) {
449 obit = inv_comp_perm[inbit];
450 if (obit == 255)
451 continue;
452 if (obit < 24)
453 il |= bits24[obit];
454 else
455 ir |= bits24[obit - 24];
456 }
457 }
458 comp_maskl[k][i] = il;
459 comp_maskr[k][i] = ir;
460 }
461 }
462
463 /*
464 * Invert the P-box permutation, and convert into OR-masks for
465 * handling the output of the S-box arrays setup above.
466 */
467 for (i = 0; i < 32; i++)
468 un_pbox[pbox[i] - 1] = (uint8_t)i;
469
470 for (b = 0; b < 4; b++) {
471 for (i = 0; i < 256; i++) {
472 p = 0;
473 for (j = 0; j < 8; j++) {
474 if (i & bits8[j])
475 p |= bits32[un_pbox[8 * b + j]];
476 }
477 psbox[b][i] = p;
478 }
479 }
480
481 return ctx;
482 }
483
484 /* Accepts 24-bit salt at max */
485 static void
setup_salt(struct des_ctx * ctx,uint32_t salt)486 setup_salt(struct des_ctx *ctx, uint32_t salt)
487 {
488 uint32_t invbits;
489
490 #if USE_REPETITIVE_SPEEDUP
491 if (salt == old_salt)
492 return;
493 old_salt = salt;
494 #endif
495
496 invbits = 0;
497
498 salt |= (1 << 24);
499 do {
500 invbits = (invbits << 1) + (salt & 1);
501 salt >>= 1;
502 } while (salt != 1);
503
504 saltbits = invbits;
505 }
506
507 static void
des_setkey(struct des_ctx * ctx,const char * key)508 des_setkey(struct des_ctx *ctx, const char *key)
509 {
510 uint32_t k0, k1, rawkey0, rawkey1;
511 int shifts, round;
512
513 rawkey0 = ntohl(*(const uint32_t *) key);
514 rawkey1 = ntohl(*(const uint32_t *) (key + 4));
515
516 #if USE_REPETITIVE_SPEEDUP
517 if ((rawkey0 | rawkey1)
518 && rawkey0 == old_rawkey0
519 && rawkey1 == old_rawkey1
520 ) {
521 /*
522 * Already setup for this key.
523 * This optimisation fails on a zero key (which is weak and
524 * has bad parity anyway) in order to simplify the starting
525 * conditions.
526 */
527 return;
528 }
529 old_rawkey0 = rawkey0;
530 old_rawkey1 = rawkey1;
531 #endif
532
533 /*
534 * Do key permutation and split into two 28-bit subkeys.
535 */
536 k0 = key_perm_maskl[0][rawkey0 >> 25]
537 | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
538 | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
539 | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
540 | key_perm_maskl[4][rawkey1 >> 25]
541 | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
542 | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
543 | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
544 k1 = key_perm_maskr[0][rawkey0 >> 25]
545 | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
546 | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
547 | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
548 | key_perm_maskr[4][rawkey1 >> 25]
549 | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
550 | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
551 | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
552 /*
553 * Rotate subkeys and do compression permutation.
554 */
555 shifts = 0;
556 for (round = 0; round < 16; round++) {
557 uint32_t t0, t1;
558
559 shifts += key_shifts[round];
560
561 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
562 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
563
564 #if USE_de_keys
565 de_keysl[15 - round] =
566 #endif
567 en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
568 | comp_maskl[1][(t0 >> 14) & 0x7f]
569 | comp_maskl[2][(t0 >> 7) & 0x7f]
570 | comp_maskl[3][t0 & 0x7f]
571 | comp_maskl[4][(t1 >> 21) & 0x7f]
572 | comp_maskl[5][(t1 >> 14) & 0x7f]
573 | comp_maskl[6][(t1 >> 7) & 0x7f]
574 | comp_maskl[7][t1 & 0x7f];
575
576 #if USE_de_keys
577 de_keysr[15 - round] =
578 #endif
579 en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
580 | comp_maskr[1][(t0 >> 14) & 0x7f]
581 | comp_maskr[2][(t0 >> 7) & 0x7f]
582 | comp_maskr[3][t0 & 0x7f]
583 | comp_maskr[4][(t1 >> 21) & 0x7f]
584 | comp_maskr[5][(t1 >> 14) & 0x7f]
585 | comp_maskr[6][(t1 >> 7) & 0x7f]
586 | comp_maskr[7][t1 & 0x7f];
587 }
588 }
589
590
591 static void
do_des(struct des_ctx * ctx,uint32_t * l_out,uint32_t * r_out,int count)592 do_des(struct des_ctx *ctx, /*uint32_t l_in, uint32_t r_in,*/ uint32_t *l_out, uint32_t *r_out, int count)
593 {
594 const struct const_des_ctx *cctx = const_ctx;
595 /*
596 * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
597 */
598 uint32_t l, r, *kl, *kr;
599 uint32_t f = f; /* silence gcc */
600 uint32_t r48l, r48r;
601 int round;
602
603 /* Do initial permutation (IP). */
604 #if USE_ip_mask
605 uint32_t l_in = 0;
606 uint32_t r_in = 0;
607 l = ip_maskl[0][l_in >> 24]
608 | ip_maskl[1][(l_in >> 16) & 0xff]
609 | ip_maskl[2][(l_in >> 8) & 0xff]
610 | ip_maskl[3][l_in & 0xff]
611 | ip_maskl[4][r_in >> 24]
612 | ip_maskl[5][(r_in >> 16) & 0xff]
613 | ip_maskl[6][(r_in >> 8) & 0xff]
614 | ip_maskl[7][r_in & 0xff];
615 r = ip_maskr[0][l_in >> 24]
616 | ip_maskr[1][(l_in >> 16) & 0xff]
617 | ip_maskr[2][(l_in >> 8) & 0xff]
618 | ip_maskr[3][l_in & 0xff]
619 | ip_maskr[4][r_in >> 24]
620 | ip_maskr[5][(r_in >> 16) & 0xff]
621 | ip_maskr[6][(r_in >> 8) & 0xff]
622 | ip_maskr[7][r_in & 0xff];
623 #elif 0 /* -65 bytes (using the fact that l_in == r_in == 0) */
624 l = r = 0;
625 for (round = 0; round < 8; round++) {
626 l |= ip_maskl[round][0];
627 r |= ip_maskr[round][0];
628 }
629 bb_error_msg("l:%x r:%x", l, r); /* reports 0, 0 always! */
630 #else /* using the fact that ip_maskX[] is constant (written to by des_init) */
631 l = r = 0;
632 #endif
633
634 do {
635 /* Do each round. */
636 kl = en_keysl;
637 kr = en_keysr;
638 round = 16;
639 do {
640 /* Expand R to 48 bits (simulate the E-box). */
641 r48l = ((r & 0x00000001) << 23)
642 | ((r & 0xf8000000) >> 9)
643 | ((r & 0x1f800000) >> 11)
644 | ((r & 0x01f80000) >> 13)
645 | ((r & 0x001f8000) >> 15);
646
647 r48r = ((r & 0x0001f800) << 7)
648 | ((r & 0x00001f80) << 5)
649 | ((r & 0x000001f8) << 3)
650 | ((r & 0x0000001f) << 1)
651 | ((r & 0x80000000) >> 31);
652 /*
653 * Do salting for crypt() and friends, and
654 * XOR with the permuted key.
655 */
656 f = (r48l ^ r48r) & saltbits;
657 r48l ^= f ^ *kl++;
658 r48r ^= f ^ *kr++;
659 /*
660 * Do sbox lookups (which shrink it back to 32 bits)
661 * and do the pbox permutation at the same time.
662 */
663 f = psbox[0][m_sbox[0][r48l >> 12]]
664 | psbox[1][m_sbox[1][r48l & 0xfff]]
665 | psbox[2][m_sbox[2][r48r >> 12]]
666 | psbox[3][m_sbox[3][r48r & 0xfff]];
667 /* Now that we've permuted things, complete f(). */
668 f ^= l;
669 l = r;
670 r = f;
671 } while (--round);
672 r = l;
673 l = f;
674 } while (--count);
675
676 /* Do final permutation (inverse of IP). */
677 *l_out = fp_maskl[0][l >> 24]
678 | fp_maskl[1][(l >> 16) & 0xff]
679 | fp_maskl[2][(l >> 8) & 0xff]
680 | fp_maskl[3][l & 0xff]
681 | fp_maskl[4][r >> 24]
682 | fp_maskl[5][(r >> 16) & 0xff]
683 | fp_maskl[6][(r >> 8) & 0xff]
684 | fp_maskl[7][r & 0xff];
685 *r_out = fp_maskr[0][l >> 24]
686 | fp_maskr[1][(l >> 16) & 0xff]
687 | fp_maskr[2][(l >> 8) & 0xff]
688 | fp_maskr[3][l & 0xff]
689 | fp_maskr[4][r >> 24]
690 | fp_maskr[5][(r >> 16) & 0xff]
691 | fp_maskr[6][(r >> 8) & 0xff]
692 | fp_maskr[7][r & 0xff];
693 }
694
695 #define DES_OUT_BUFSIZE 21
696
697 static void
to64_msb_first(char * s,unsigned v)698 to64_msb_first(char *s, unsigned v)
699 {
700 #if 0
701 *s++ = ascii64[(v >> 18) & 0x3f]; /* bits 23..18 */
702 *s++ = ascii64[(v >> 12) & 0x3f]; /* bits 17..12 */
703 *s++ = ascii64[(v >> 6) & 0x3f]; /* bits 11..6 */
704 *s = ascii64[v & 0x3f]; /* bits 5..0 */
705 #endif
706 *s++ = i64c(v >> 18); /* bits 23..18 */
707 *s++ = i64c(v >> 12); /* bits 17..12 */
708 *s++ = i64c(v >> 6); /* bits 11..6 */
709 *s = i64c(v); /* bits 5..0 */
710 }
711
712 static char *
713 NOINLINE
des_crypt(struct des_ctx * ctx,char output[DES_OUT_BUFSIZE],const unsigned char * key,const unsigned char * salt_str)714 des_crypt(struct des_ctx *ctx, char output[DES_OUT_BUFSIZE],
715 const unsigned char *key, const unsigned char *salt_str)
716 {
717 uint32_t salt, r0, r1, keybuf[2];
718 uint8_t *q;
719
720 /* Bad salt? Mimic crypt() API - return NULL */
721 if (!salt_str[0] || !salt_str[1])
722 return NULL;
723
724 /*
725 * Copy the key, shifting each character up by one bit
726 * and padding with zeros.
727 */
728 q = (uint8_t *)keybuf;
729 while (q - (uint8_t *)keybuf != 8) {
730 *q = *key << 1;
731 if (*q)
732 key++;
733 q++;
734 }
735 des_setkey(ctx, (char *)keybuf);
736
737 /*
738 * salt_str - 2 chars of salt (converted to 12 bits)
739 * key - up to 8 characters
740 */
741 output[0] = salt_str[0];
742 output[1] = salt_str[1];
743 salt = (ascii_to_bin(salt_str[1]) << 6)
744 | ascii_to_bin(salt_str[0]);
745 setup_salt(ctx, salt); /* set ctx->saltbits for do_des() */
746
747 /* Do it. */
748 do_des(ctx, /*0, 0,*/ &r0, &r1, 25 /* count */);
749
750 /* Now encode the result. */
751 #if 0
752 {
753 uint32_t l = (r0 >> 8);
754 q = (uint8_t *)output + 2;
755 *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 31..26 of r0 */
756 *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 25..20 of r0 */
757 *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 19..14 of r0 */
758 *q++ = ascii64[l & 0x3f]; /* bits 13..8 of r0 */
759 l = ((r0 << 16) | (r1 >> 16));
760 *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 7..2 of r0 */
761 *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 1..2 of r0 and 31..28 of r1 */
762 *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 27..22 of r1 */
763 *q++ = ascii64[l & 0x3f]; /* bits 21..16 of r1 */
764 l = r1 << 2;
765 *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 15..10 of r1 */
766 *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 9..4 of r1 */
767 *q++ = ascii64[l & 0x3f]; /* bits 3..0 of r1 + 00 */
768 *q = 0;
769 }
770 #else
771 /* Each call takes low-order 24 bits and stores 4 chars */
772 /* bits 31..8 of r0 */
773 to64_msb_first(output + 2, (r0 >> 8));
774 /* bits 7..0 of r0 and 31..16 of r1 */
775 to64_msb_first(output + 6, (r0 << 16) | (r1 >> 16));
776 /* bits 15..0 of r1 and two zero bits (plus extra zero byte) */
777 to64_msb_first(output + 10, (r1 << 8));
778 /* extra zero byte is encoded as '.', fixing it */
779 output[13] = '\0';
780 #endif
781
782 return output;
783 }
784
785 #undef USE_PRECOMPUTED_u_sbox
786 #undef USE_REPETITIVE_SPEEDUP
787 #undef USE_ip_mask
788 #undef USE_de_keys
789
790 #undef C
791 #undef init_perm
792 #undef final_perm
793 #undef m_sbox
794 #undef D
795 #undef const_ctx
796 #undef saltbits
797 #undef old_salt
798 #undef old_rawkey0
799 #undef old_rawkey1
800 #undef un_pbox
801 #undef inv_comp_perm
802 #undef inv_key_perm
803 #undef en_keysl
804 #undef en_keysr
805 #undef de_keysl
806 #undef de_keysr
807 #undef ip_maskl
808 #undef ip_maskr
809 #undef fp_maskl
810 #undef fp_maskr
811 #undef key_perm_maskl
812 #undef key_perm_maskr
813 #undef comp_maskl
814 #undef comp_maskr
815 #undef psbox
816