hush: get rid of charmap[]
[oweals/busybox.git] / libbb / pw_encrypt_des.c
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] = {
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] = {
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] = {
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] = {
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] = {
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] =
190 {
191         0x80000000, 0x40000000, 0x20000000, 0x10000000,
192         0x08000000, 0x04000000, 0x02000000, 0x01000000,
193         0x00800000, 0x00400000, 0x00200000, 0x00100000,
194         0x00080000, 0x00040000, 0x00020000, 0x00010000,
195         0x00008000, 0x00004000, 0x00002000, 0x00001000,
196         0x00000800, 0x00000400, 0x00000200, 0x00000100,
197         0x00000080, 0x00000040, 0x00000020, 0x00000010,
198         0x00000008, 0x00000004, 0x00000002, 0x00000001
199 };
200
201 static const uint8_t bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
202
203
204 static int
205 ascii_to_bin(char ch)
206 {
207         if (ch > 'z')
208                 return 0;
209         if (ch >= 'a')
210                 return (ch - 'a' + 38);
211         if (ch > 'Z')
212                 return 0;
213         if (ch >= 'A')
214                 return (ch - 'A' + 12);
215         if (ch > '9')
216                 return 0;
217         if (ch >= '.')
218                 return (ch - '.');
219         return 0;
220 }
221
222
223 /* Static stuff that stays resident and doesn't change after
224  * being initialized, and therefore doesn't need to be made
225  * reentrant. */
226 struct const_des_ctx {
227 #if USE_ip_mask
228         uint8_t init_perm[64]; /* referenced 2 times */
229 #endif
230         uint8_t final_perm[64]; /* 2 times */
231         uint8_t m_sbox[4][4096]; /* 5 times */
232 };
233 #define C (*cctx)
234 #define init_perm  (C.init_perm )
235 #define final_perm (C.final_perm)
236 #define m_sbox     (C.m_sbox    )
237
238 static struct const_des_ctx*
239 const_des_init(void)
240 {
241         unsigned i, j, b;
242         struct const_des_ctx *cctx;
243
244 #if !USE_PRECOMPUTED_u_sbox
245         uint8_t u_sbox[8][64];
246
247         cctx = xmalloc(sizeof(*cctx));
248
249         /* Invert the S-boxes, reordering the input bits. */
250         for (i = 0; i < 8; i++) {
251                 for (j = 0; j < 64; j++) {
252                         b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
253                         u_sbox[i][j] = sbox[i][b];
254                 }
255         }
256         for (i = 0; i < 8; i++) {
257                 fprintf(stderr, "\t{\t");
258                 for (j = 0; j < 64; j+=2)
259                         fprintf(stderr, " 0x%02x,", u_sbox[i][j] + u_sbox[i][j+1]*16);
260                 fprintf(stderr, "\n\t},\n");
261         }
262         /*
263          * Convert the inverted S-boxes into 4 arrays of 8 bits.
264          * Each will handle 12 bits of the S-box input.
265          */
266         for (b = 0; b < 4; b++)
267                 for (i = 0; i < 64; i++)
268                         for (j = 0; j < 64; j++)
269                                 m_sbox[b][(i << 6) | j] =
270                                         (uint8_t)((u_sbox[(b << 1)][i] << 4) |
271                                                 u_sbox[(b << 1) + 1][j]);
272 #else
273         cctx = xmalloc(sizeof(*cctx));
274
275         /*
276          * Convert the inverted S-boxes into 4 arrays of 8 bits.
277          * Each will handle 12 bits of the S-box input.
278          */
279         for (b = 0; b < 4; b++)
280          for (i = 0; i < 64; i++)
281           for (j = 0; j < 64; j++) {
282                 uint8_t lo, hi;
283                 hi = u_sbox[(b << 1)][i / 2];
284                 if (!(i & 1))
285                         hi <<= 4;
286                 lo = u_sbox[(b << 1) + 1][j / 2];
287                 if (j & 1)
288                         lo >>= 4;
289                 m_sbox[b][(i << 6) | j] = (hi & 0xf0) | (lo & 0x0f);
290         }
291 #endif
292
293         /*
294          * Set up the initial & final permutations into a useful form.
295          */
296         for (i = 0; i < 64; i++) {
297                 final_perm[i] = IP[i] - 1;
298 #if USE_ip_mask
299                 init_perm[final_perm[i]] = (uint8_t)i;
300 #endif
301         }
302
303         return cctx;
304 }
305
306
307 struct des_ctx {
308         const struct const_des_ctx *const_ctx;
309         uint32_t saltbits; /* referenced 5 times */
310 #if USE_REPETITIVE_SPEEDUP
311         uint32_t old_salt; /* 3 times */
312         uint32_t old_rawkey0, old_rawkey1; /* 3 times each */
313 #endif
314         uint8_t un_pbox[32]; /* 2 times */
315         uint8_t inv_comp_perm[56]; /* 3 times */
316         uint8_t inv_key_perm[64]; /* 3 times */
317         uint32_t en_keysl[16], en_keysr[16]; /* 2 times each */
318 #if USE_de_keys
319         uint32_t de_keysl[16], de_keysr[16]; /* 2 times each */
320 #endif
321 #if USE_ip_mask
322         uint32_t ip_maskl[8][256], ip_maskr[8][256]; /* 9 times each */
323 #endif
324         uint32_t fp_maskl[8][256], fp_maskr[8][256]; /* 9 times each */
325         uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128]; /* 9 times */
326         uint32_t comp_maskl[8][128], comp_maskr[8][128]; /* 9 times each */
327         uint32_t psbox[4][256]; /* 5 times */
328 };
329 #define D (*ctx)
330 #define const_ctx       (D.const_ctx      )
331 #define saltbits        (D.saltbits       )
332 #define old_salt        (D.old_salt       )
333 #define old_rawkey0     (D.old_rawkey0    )
334 #define old_rawkey1     (D.old_rawkey1    )
335 #define un_pbox         (D.un_pbox        )
336 #define inv_comp_perm   (D.inv_comp_perm  )
337 #define inv_key_perm    (D.inv_key_perm   )
338 #define en_keysl        (D.en_keysl       )
339 #define en_keysr        (D.en_keysr       )
340 #define de_keysl        (D.de_keysl       )
341 #define de_keysr        (D.de_keysr       )
342 #define ip_maskl        (D.ip_maskl       )
343 #define ip_maskr        (D.ip_maskr       )
344 #define fp_maskl        (D.fp_maskl       )
345 #define fp_maskr        (D.fp_maskr       )
346 #define key_perm_maskl  (D.key_perm_maskl )
347 #define key_perm_maskr  (D.key_perm_maskr )
348 #define comp_maskl      (D.comp_maskl     )
349 #define comp_maskr      (D.comp_maskr     )
350 #define psbox           (D.psbox          )
351
352 static struct des_ctx*
353 des_init(struct des_ctx *ctx, const struct const_des_ctx *cctx)
354 {
355         int i, j, b, k, inbit, obit;
356         uint32_t p;
357         const uint32_t *bits28, *bits24;
358
359         if (!ctx)
360                 ctx = xmalloc(sizeof(*ctx));
361         const_ctx = cctx;
362
363 #if USE_REPETITIVE_SPEEDUP
364         old_rawkey0 = old_rawkey1 = 0;
365         old_salt = 0;
366 #endif
367         saltbits = 0;
368         bits28 = bits32 + 4;
369         bits24 = bits28 + 4;
370
371         /* Initialise the inverted key permutation. */
372         for (i = 0; i < 64; i++) {
373                 inv_key_perm[i] = 255;
374         }
375
376         /*
377          * Invert the key permutation and initialise the inverted key
378          * compression permutation.
379          */
380         for (i = 0; i < 56; i++) {
381                 inv_key_perm[key_perm[i] - 1] = (uint8_t)i;
382                 inv_comp_perm[i] = 255;
383         }
384
385         /* Invert the key compression permutation. */
386         for (i = 0; i < 48; i++) {
387                 inv_comp_perm[comp_perm[i] - 1] = (uint8_t)i;
388         }
389
390         /*
391          * Set up the OR-mask arrays for the initial and final permutations,
392          * and for the key initial and compression permutations.
393          */
394         for (k = 0; k < 8; k++) {
395                 uint32_t il, ir;
396                 uint32_t fl, fr;
397                 for (i = 0; i < 256; i++) {
398 #if USE_ip_mask
399                         il = 0;
400                         ir = 0;
401 #endif
402                         fl = 0;
403                         fr = 0;
404                         for (j = 0; j < 8; j++) {
405                                 inbit = 8 * k + j;
406                                 if (i & bits8[j]) {
407 #if USE_ip_mask
408                                         obit = init_perm[inbit];
409                                         if (obit < 32)
410                                                 il |= bits32[obit];
411                                         else
412                                                 ir |= bits32[obit - 32];
413 #endif
414                                         obit = final_perm[inbit];
415                                         if (obit < 32)
416                                                 fl |= bits32[obit];
417                                         else
418                                                 fr |= bits32[obit - 32];
419                                 }
420                         }
421 #if USE_ip_mask
422                         ip_maskl[k][i] = il;
423                         ip_maskr[k][i] = ir;
424 #endif
425                         fp_maskl[k][i] = fl;
426                         fp_maskr[k][i] = fr;
427                 }
428                 for (i = 0; i < 128; i++) {
429                         il = 0;
430                         ir = 0;
431                         for (j = 0; j < 7; j++) {
432                                 inbit = 8 * k + j;
433                                 if (i & bits8[j + 1]) {
434                                         obit = inv_key_perm[inbit];
435                                         if (obit == 255)
436                                                 continue;
437                                         if (obit < 28)
438                                                 il |= bits28[obit];
439                                         else
440                                                 ir |= bits28[obit - 28];
441                                 }
442                         }
443                         key_perm_maskl[k][i] = il;
444                         key_perm_maskr[k][i] = ir;
445                         il = 0;
446                         ir = 0;
447                         for (j = 0; j < 7; j++) {
448                                 inbit = 7 * k + j;
449                                 if (i & bits8[j + 1]) {
450                                         obit = inv_comp_perm[inbit];
451                                         if (obit == 255)
452                                                 continue;
453                                         if (obit < 24)
454                                                 il |= bits24[obit];
455                                         else
456                                                 ir |= bits24[obit - 24];
457                                 }
458                         }
459                         comp_maskl[k][i] = il;
460                         comp_maskr[k][i] = ir;
461                 }
462         }
463
464         /*
465          * Invert the P-box permutation, and convert into OR-masks for
466          * handling the output of the S-box arrays setup above.
467          */
468         for (i = 0; i < 32; i++)
469                 un_pbox[pbox[i] - 1] = (uint8_t)i;
470
471         for (b = 0; b < 4; b++) {
472                 for (i = 0; i < 256; i++) {
473                         p = 0;
474                         for (j = 0; j < 8; j++) {
475                                 if (i & bits8[j])
476                                         p |= bits32[un_pbox[8 * b + j]];
477                         }
478                         psbox[b][i] = p;
479                 }
480         }
481
482         return ctx;
483 }
484
485
486 static void
487 setup_salt(struct des_ctx *ctx, uint32_t salt)
488 {
489         uint32_t obit, saltbit;
490         int i;
491
492 #if USE_REPETITIVE_SPEEDUP
493         if (salt == old_salt)
494                 return;
495         old_salt = salt;
496 #endif
497
498         saltbits = 0;
499         saltbit = 1;
500         obit = 0x800000;
501         for (i = 0; i < 24; i++) {
502                 if (salt & saltbit)
503                         saltbits |= obit;
504                 saltbit <<= 1;
505                 obit >>= 1;
506         }
507 }
508
509 static void
510 des_setkey(struct des_ctx *ctx, const char *key)
511 {
512         uint32_t k0, k1, rawkey0, rawkey1;
513         int shifts, round;
514
515         rawkey0 = ntohl(*(const uint32_t *) key);
516         rawkey1 = ntohl(*(const uint32_t *) (key + 4));
517
518 #if USE_REPETITIVE_SPEEDUP
519         if ((rawkey0 | rawkey1)
520          && rawkey0 == old_rawkey0
521          && rawkey1 == old_rawkey1
522         ) {
523                 /*
524                  * Already setup for this key.
525                  * This optimisation fails on a zero key (which is weak and
526                  * has bad parity anyway) in order to simplify the starting
527                  * conditions.
528                  */
529                 return;
530         }
531         old_rawkey0 = rawkey0;
532         old_rawkey1 = rawkey1;
533 #endif
534
535         /*
536          * Do key permutation and split into two 28-bit subkeys.
537          */
538         k0 = key_perm_maskl[0][rawkey0 >> 25]
539            | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
540            | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
541            | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
542            | key_perm_maskl[4][rawkey1 >> 25]
543            | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
544            | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
545            | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
546         k1 = key_perm_maskr[0][rawkey0 >> 25]
547            | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
548            | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
549            | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
550            | key_perm_maskr[4][rawkey1 >> 25]
551            | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
552            | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
553            | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
554         /*
555          * Rotate subkeys and do compression permutation.
556          */
557         shifts = 0;
558         for (round = 0; round < 16; round++) {
559                 uint32_t t0, t1;
560
561                 shifts += key_shifts[round];
562
563                 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
564                 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
565
566 #if USE_de_keys
567                 de_keysl[15 - round] =
568 #endif
569                 en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
570                                 | comp_maskl[1][(t0 >> 14) & 0x7f]
571                                 | comp_maskl[2][(t0 >> 7) & 0x7f]
572                                 | comp_maskl[3][t0 & 0x7f]
573                                 | comp_maskl[4][(t1 >> 21) & 0x7f]
574                                 | comp_maskl[5][(t1 >> 14) & 0x7f]
575                                 | comp_maskl[6][(t1 >> 7) & 0x7f]
576                                 | comp_maskl[7][t1 & 0x7f];
577
578 #if USE_de_keys
579                 de_keysr[15 - round] =
580 #endif
581                 en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
582                                 | comp_maskr[1][(t0 >> 14) & 0x7f]
583                                 | comp_maskr[2][(t0 >> 7) & 0x7f]
584                                 | comp_maskr[3][t0 & 0x7f]
585                                 | comp_maskr[4][(t1 >> 21) & 0x7f]
586                                 | comp_maskr[5][(t1 >> 14) & 0x7f]
587                                 | comp_maskr[6][(t1 >> 7) & 0x7f]
588                                 | comp_maskr[7][t1 & 0x7f];
589         }
590 }
591
592
593 static void
594 do_des(struct des_ctx *ctx, /*uint32_t l_in, uint32_t r_in,*/ uint32_t *l_out, uint32_t *r_out, int count)
595 {
596         const struct const_des_ctx *cctx = const_ctx;
597         /*
598          * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
599          */
600         uint32_t l, r, *kl, *kr;
601         uint32_t f = f; /* silence gcc */
602         uint32_t r48l, r48r;
603         int round;
604
605         /* Do initial permutation (IP). */
606 #if USE_ip_mask
607         uint32_t l_in = 0;
608         uint32_t r_in = 0;
609         l = ip_maskl[0][l_in >> 24]
610           | ip_maskl[1][(l_in >> 16) & 0xff]
611           | ip_maskl[2][(l_in >> 8) & 0xff]
612           | ip_maskl[3][l_in & 0xff]
613           | ip_maskl[4][r_in >> 24]
614           | ip_maskl[5][(r_in >> 16) & 0xff]
615           | ip_maskl[6][(r_in >> 8) & 0xff]
616           | ip_maskl[7][r_in & 0xff];
617         r = ip_maskr[0][l_in >> 24]
618           | ip_maskr[1][(l_in >> 16) & 0xff]
619           | ip_maskr[2][(l_in >> 8) & 0xff]
620           | ip_maskr[3][l_in & 0xff]
621           | ip_maskr[4][r_in >> 24]
622           | ip_maskr[5][(r_in >> 16) & 0xff]
623           | ip_maskr[6][(r_in >> 8) & 0xff]
624           | ip_maskr[7][r_in & 0xff];
625 #elif 0 /* -65 bytes (using the fact that l_in == r_in == 0) */
626         l = r = 0;
627         for (round = 0; round < 8; round++) {
628                 l |= ip_maskl[round][0];
629                 r |= ip_maskr[round][0];
630         }
631         bb_error_msg("l:%x r:%x", l, r); /* reports 0, 0 always! */
632 #else /* using the fact that ip_maskX[] is constant (written to by des_init) */
633         l = r = 0;
634 #endif
635
636         do {
637                 /* Do each round. */
638                 kl = en_keysl;
639                 kr = en_keysr;
640                 round = 16;
641                 do {
642                         /* Expand R to 48 bits (simulate the E-box). */
643                         r48l    = ((r & 0x00000001) << 23)
644                                 | ((r & 0xf8000000) >> 9)
645                                 | ((r & 0x1f800000) >> 11)
646                                 | ((r & 0x01f80000) >> 13)
647                                 | ((r & 0x001f8000) >> 15);
648
649                         r48r    = ((r & 0x0001f800) << 7)
650                                 | ((r & 0x00001f80) << 5)
651                                 | ((r & 0x000001f8) << 3)
652                                 | ((r & 0x0000001f) << 1)
653                                 | ((r & 0x80000000) >> 31);
654                         /*
655                          * Do salting for crypt() and friends, and
656                          * XOR with the permuted key.
657                          */
658                         f = (r48l ^ r48r) & saltbits;
659                         r48l ^= f ^ *kl++;
660                         r48r ^= f ^ *kr++;
661                         /*
662                          * Do sbox lookups (which shrink it back to 32 bits)
663                          * and do the pbox permutation at the same time.
664                          */
665                         f = psbox[0][m_sbox[0][r48l >> 12]]
666                           | psbox[1][m_sbox[1][r48l & 0xfff]]
667                           | psbox[2][m_sbox[2][r48r >> 12]]
668                           | psbox[3][m_sbox[3][r48r & 0xfff]];
669                         /* Now that we've permuted things, complete f(). */
670                         f ^= l;
671                         l = r;
672                         r = f;
673                 } while (--round);
674                 r = l;
675                 l = f;
676         } while (--count);
677
678         /* Do final permutation (inverse of IP). */
679         *l_out  = fp_maskl[0][l >> 24]
680                 | fp_maskl[1][(l >> 16) & 0xff]
681                 | fp_maskl[2][(l >> 8) & 0xff]
682                 | fp_maskl[3][l & 0xff]
683                 | fp_maskl[4][r >> 24]
684                 | fp_maskl[5][(r >> 16) & 0xff]
685                 | fp_maskl[6][(r >> 8) & 0xff]
686                 | fp_maskl[7][r & 0xff];
687         *r_out  = fp_maskr[0][l >> 24]
688                 | fp_maskr[1][(l >> 16) & 0xff]
689                 | fp_maskr[2][(l >> 8) & 0xff]
690                 | fp_maskr[3][l & 0xff]
691                 | fp_maskr[4][r >> 24]
692                 | fp_maskr[5][(r >> 16) & 0xff]
693                 | fp_maskr[6][(r >> 8) & 0xff]
694                 | fp_maskr[7][r & 0xff];
695 }
696
697 #define DES_OUT_BUFSIZE 21
698
699 static void
700 to64_msb_first(char *s, unsigned v)
701 {
702 #if 0
703         *s++ = ascii64[(v >> 18) & 0x3f]; /* bits 23..18 */
704         *s++ = ascii64[(v >> 12) & 0x3f]; /* bits 17..12 */
705         *s++ = ascii64[(v >> 6) & 0x3f]; /* bits 11..6 */
706         *s   = ascii64[v & 0x3f]; /* bits 5..0 */
707 #endif
708         *s++ = i64c(v >> 18); /* bits 23..18 */
709         *s++ = i64c(v >> 12); /* bits 17..12 */
710         *s++ = i64c(v >> 6); /* bits 11..6 */
711         *s   = i64c(v); /* bits 5..0 */
712 }
713
714 static char *
715 NOINLINE
716 des_crypt(struct des_ctx *ctx, char output[DES_OUT_BUFSIZE],
717                 const unsigned char *key, const unsigned char *setting)
718 {
719         uint32_t salt, r0, r1, keybuf[2];
720         uint8_t *q;
721
722         /*
723          * Copy the key, shifting each character up by one bit
724          * and padding with zeros.
725          */
726         q = (uint8_t *)keybuf;
727         while (q - (uint8_t *)keybuf != 8) {
728                 *q = *key << 1;
729                 if (*q)
730                         key++;
731                 q++;
732         }
733         des_setkey(ctx, (char *)keybuf);
734
735         /*
736          * setting - 2 bytes of salt
737          * key - up to 8 characters
738          */
739         salt = (ascii_to_bin(setting[1]) << 6)
740              |  ascii_to_bin(setting[0]);
741
742         output[0] = setting[0];
743         /*
744          * If the encrypted password that the salt was extracted from
745          * is only 1 character long, the salt will be corrupted.  We
746          * need to ensure that the output string doesn't have an extra
747          * NUL in it!
748          */
749         output[1] = setting[1] ? setting[1] : output[0];
750
751         setup_salt(ctx, salt);
752         /* Do it. */
753         do_des(ctx, /*0, 0,*/ &r0, &r1, 25 /* count */);
754
755         /* Now encode the result. */
756 #if 0
757 {
758         uint32_t l = (r0 >> 8);
759         q = (uint8_t *)output + 2;
760         *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 31..26 of r0 */
761         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 25..20 of r0 */
762         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 19..14 of r0 */
763         *q++ = ascii64[l & 0x3f]; /* bits 13..8 of r0 */
764         l = ((r0 << 16) | (r1 >> 16));
765         *q++ = ascii64[(l >> 18) & 0x3f]; /* bits 7..2 of r0 */
766         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 1..2 of r0 and 31..28 of r1 */
767         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 27..22 of r1 */
768         *q++ = ascii64[l & 0x3f]; /* bits 21..16 of r1 */
769         l = r1 << 2;
770         *q++ = ascii64[(l >> 12) & 0x3f]; /* bits 15..10 of r1 */
771         *q++ = ascii64[(l >> 6) & 0x3f]; /* bits 9..4 of r1 */
772         *q++ = ascii64[l & 0x3f]; /* bits 3..0 of r1 + 00 */
773         *q = 0;
774 }
775 #else
776         /* Each call takes low-order 24 bits and stores 4 chars */
777         /* bits 31..8 of r0 */
778         to64_msb_first(output + 2, (r0 >> 8));
779         /* bits 7..0 of r0 and 31..16 of r1 */
780         to64_msb_first(output + 6, (r0 << 16) | (r1 >> 16));
781         /* (bits 15..0 of r1 + 00) and NUL byte */
782         to64_msb_first(output + 10, (r1 << 8));
783 #endif
784
785         return output;
786 }
787
788 #undef USE_PRECOMPUTED_u_sbox
789 #undef USE_REPETITIVE_SPEEDUP
790 #undef USE_ip_mask
791 #undef USE_de_keys
792
793 #undef C
794 #undef init_perm
795 #undef final_perm
796 #undef m_sbox
797 #undef D
798 #undef const_ctx
799 #undef saltbits
800 #undef old_salt
801 #undef old_rawkey0
802 #undef old_rawkey1
803 #undef un_pbox
804 #undef inv_comp_perm
805 #undef inv_key_perm
806 #undef en_keysl
807 #undef en_keysr
808 #undef de_keysl
809 #undef de_keysr
810 #undef ip_maskl
811 #undef ip_maskr
812 #undef fp_maskl
813 #undef fp_maskr
814 #undef key_perm_maskl
815 #undef key_perm_maskr
816 #undef comp_maskl
817 #undef comp_maskr
818 #undef psbox