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
43 /*
44 * This program can regenerate the tables in alg-des-tables.c.
45 * It is preserved as documentation, but it should no longer be
46 * necessary to run it.
47 */
48
49 #include "crypt-port.h"
50
51 #include <inttypes.h>
52 #include <stdio.h>
53
54 static const uint8_t IP[64] =
55 {
56 58, 50, 42, 34, 26, 18, 10, 2, 60, 52, 44, 36, 28, 20, 12, 4,
57 62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,
58 57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, 11, 3,
59 61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7
60 };
61
62 static uint8_t inv_key_perm[64];
63 static const uint8_t key_perm[56] =
64 {
65 57, 49, 41, 33, 25, 17, 9, 1, 58, 50, 42, 34, 26, 18,
66 10, 2, 59, 51, 43, 35, 27, 19, 11, 3, 60, 52, 44, 36,
67 63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,
68 14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4
69 };
70
71 static uint8_t inv_comp_perm[56];
72 static const uint8_t comp_perm[48] =
73 {
74 14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10,
75 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2,
76 41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
77 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
78 };
79
80 /*
81 * No E box is used, as it's replaced by some ANDs, shifts, and ORs.
82 */
83
84 static uint8_t u_sbox[8][64];
85 static const uint8_t sbox[8][64] =
86 {
87 {
88 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
89 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
90 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
91 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13
92 },
93 {
94 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
95 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
96 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
97 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9
98 },
99 {
100 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
101 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
102 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
103 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12
104 },
105 {
106 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
107 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
108 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
109 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14
110 },
111 {
112 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
113 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
114 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
115 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3
116 },
117 {
118 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
119 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
120 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
121 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13
122 },
123 {
124 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
125 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
126 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
127 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12
128 },
129 {
130 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
131 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
132 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
133 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
134 }
135 };
136
137 static uint8_t un_pbox[32];
138 static const uint8_t pbox[32] =
139 {
140 16, 7, 20, 21, 29, 12, 28, 17, 1, 15, 23, 26, 5, 18, 31, 10,
141 2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, 11, 4, 25
142 };
143
144 static const uint32_t *bits28, *bits24;
145 static uint8_t init_perm[64], final_perm[64];
146
147 static const uint32_t bits32[32] =
148 {
149 0x80000000, 0x40000000, 0x20000000, 0x10000000,
150 0x08000000, 0x04000000, 0x02000000, 0x01000000,
151 0x00800000, 0x00400000, 0x00200000, 0x00100000,
152 0x00080000, 0x00040000, 0x00020000, 0x00010000,
153 0x00008000, 0x00004000, 0x00002000, 0x00001000,
154 0x00000800, 0x00000400, 0x00000200, 0x00000100,
155 0x00000080, 0x00000040, 0x00000020, 0x00000010,
156 0x00000008, 0x00000004, 0x00000002, 0x00000001
157 };
158
159 static const uint8_t bits8[8] =
160 { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
161
162 static uint8_t m_sbox_[4][4096];
163 static uint32_t ip_maskl_[8][256], ip_maskr_[8][256];
164 static uint32_t fp_maskl_[8][256], fp_maskr_[8][256];
165 static uint32_t key_perm_maskl_[8][128], key_perm_maskr_[8][128];
166 static uint32_t comp_maskl_[8][128], comp_maskr_[8][128];
167 static uint32_t psbox_[4][256];
168
169 static void
170 des_init(void)
171 {
172 int i, j, b, k, inbit, obit;
173 uint32_t *p, *il, *ir, *fl, *fr;
174
175 bits24 = (bits28 = bits32 + 4) + 4;
176
177 /*
178 * Invert the S-boxes, reordering the input bits.
179 */
180 for (i = 0; i < 8; i++)
181 for (j = 0; j < 64; j++)
182 {
183 b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
184 u_sbox[i][j] = sbox[i][b];
185 }
186
187 /*
188 * Convert the inverted S-boxes into 4 arrays of 8 bits.
189 * Each will handle 12 bits of the S-box input.
190 */
191 for (b = 0; b < 4; b++)
192 for (i = 0; i < 64; i++)
193 for (j = 0; j < 64; j++)
194 m_sbox_[b][(i << 6) | j] =
195 (uint8_t)((u_sbox[(b << 1)][i] << 4) |
196 u_sbox[(b << 1) + 1][j]);
197
198 /*
199 * Set up the initial & final permutations into a useful form, and
200 * initialise the inverted key permutation.
201 */
202 for (i = 0; i < 64; i++)
203 {
204 final_perm[i] = (uint8_t)(IP[i] - 1);
205 init_perm[final_perm[i]] = (uint8_t)i;
206 inv_key_perm[i] = 255;
207 }
208
209 /*
210 * Invert the key permutation and initialise the inverted key
211 * compression permutation.
212 */
213 for (i = 0; i < 56; i++)
214 {
215 inv_key_perm[key_perm[i] - 1] = (uint8_t)i;
216 inv_comp_perm[i] = 255;
217 }
218
219 /*
220 * Invert the key compression permutation.
221 */
222 for (i = 0; i < 48; i++)
223 {
224 inv_comp_perm[comp_perm[i] - 1] = (uint8_t)i;
225 }
226
227 /*
228 * Set up the OR-mask arrays for the initial and final permutations,
229 * and for the key initial and compression permutations.
230 */
231 for (k = 0; k < 8; k++)
232 {
233 for (i = 0; i < 256; i++)
234 {
235 *(il = &ip_maskl_[k][i]) = 0L;
236 *(ir = &ip_maskr_[k][i]) = 0L;
237 *(fl = &fp_maskl_[k][i]) = 0L;
238 *(fr = &fp_maskr_[k][i]) = 0L;
239 for (j = 0; j < 8; j++)
240 {
241 inbit = 8 * k + j;
242 if (i & bits8[j])
243 {
244 if ((obit = init_perm[inbit]) < 32)
245 *il |= bits32[obit];
246 else
247 *ir |= bits32[obit-32];
248 if ((obit = final_perm[inbit]) < 32)
249 *fl |= bits32[obit];
250 else
251 *fr |= bits32[obit - 32];
252 }
253 }
254 }
255 for (i = 0; i < 128; i++)
256 {
257 *(il = &key_perm_maskl_[k][i]) = 0L;
258 *(ir = &key_perm_maskr_[k][i]) = 0L;
259 for (j = 0; j < 7; j++)
260 {
261 inbit = 8 * k + j;
262 if (i & bits8[j + 1])
263 {
264 if ((obit = inv_key_perm[inbit]) == 255)
265 continue;
266 if (obit < 28)
267 *il |= bits28[obit];
268 else
269 *ir |= bits28[obit - 28];
270 }
271 }
272 *(il = &comp_maskl_[k][i]) = 0L;
273 *(ir = &comp_maskr_[k][i]) = 0L;
274 for (j = 0; j < 7; j++)
275 {
276 inbit = 7 * k + j;
277 if (i & bits8[j + 1])
278 {
279 if ((obit=inv_comp_perm[inbit]) == 255)
280 continue;
281 if (obit < 24)
282 *il |= bits24[obit];
283 else
284 *ir |= bits24[obit - 24];
285 }
286 }
287 }
288 }
289
290 /*
291 * Invert the P-box permutation, and convert into OR-masks for
292 * handling the output of the S-box arrays setup above.
293 */
294 for (i = 0; i < 32; i++)
295 un_pbox[pbox[i] - 1] = (uint8_t)i;
296
297 for (b = 0; b < 4; b++)
298 for (i = 0; i < 256; i++)
299 {
300 *(p = &psbox_[b][i]) = 0L;
301 for (j = 0; j < 8; j++)
302 {
303 if (i & bits8[j])
304 *p |= bits32[un_pbox[8 * b + j]];
305 }
306 }
307 }
308
309 static void
310 write_table_u8(size_t m, size_t n, const uint8_t *tbl, const char *name)
311 {
312 printf("\nconst uint8_t %s[%zu][%zu] = {\n", name, m, n);
313 for (size_t i = 0; i < m; i++)
314 {
315 fputs(" {", stdout);
316 for (size_t j = 0; j < n; j++)
317 {
318 if (j % 12 == 0)
319 fputs("\n ", stdout);
320 printf(" 0x%02x,", (unsigned int)tbl[i*n + j]);
321 }
322 puts("\n },");
323 }
324 puts("};");
325 }
326
327 static void
328 write_table_u32(size_t m, size_t n, const uint32_t *tbl, const char *name)
329 {
330 printf("\nconst uint32_t %s[%zu][%zu] = {\n", name, m, n);
331 for (size_t i = 0; i < m; i++)
332 {
333 fputs(" {", stdout);
334 for (size_t j = 0; j < n; j++)
335 {
336 if (j % 6 == 0)
337 fputs("\n ", stdout);
338 printf(" 0x%08"PRIx32",", tbl[i*n + j]);
339 }
340 puts("\n },");
341 }
342 puts("};");
343 }
344
345 int
346 main(void)
347 {
348 des_init();
349
350 write_table_u8(4, 4096, &m_sbox_[0][0], "m_sbox");
351
352 write_table_u32(8, 256, &ip_maskl_[0][0], "ip_maskl");
353 write_table_u32(8, 256, &ip_maskr_[0][0], "ip_maskr");
354 write_table_u32(8, 256, &fp_maskl_[0][0], "fp_maskl");
355 write_table_u32(8, 256, &fp_maskr_[0][0], "fp_maskr");
356
357 write_table_u32(8, 128, &key_perm_maskl_[0][0], "key_perm_maskl");
358 write_table_u32(8, 128, &key_perm_maskr_[0][0], "key_perm_maskr");
359 write_table_u32(8, 128, &comp_maskl_[0][0], "comp_maskl");
360 write_table_u32(8, 128, &comp_maskr_[0][0], "comp_maskr");
361
362 write_table_u32(4, 256, &psbox_[0][0], "psbox");
363 }