1 /*
2 * This version has been further modified by Rich Felker, primary author
3 * and maintainer of musl libc, to remove table generation code and
4 * replaced all runtime-generated constant tables with static-initialized
5 * tables in the binary, in the interest of minimizing non-shareable
6 * memory usage and stack size requirements.
7 */
8 /*
9 * This version is derived from the original implementation of FreeSec
10 * (release 1.1) by David Burren. I've made it reentrant, reduced its memory
11 * usage from about 70 KB to about 7 KB (with only minimal performance impact
12 * and keeping code size about the same), made the handling of invalid salts
13 * mostly UFC-crypt compatible, added a quick runtime self-test (which also
14 * serves to zeroize the stack from sensitive data), and added optional tests.
15 * - Solar Designer <solar at openwall.com>
16 */
17
18 /*
19 * FreeSec: libcrypt for NetBSD
20 *
21 * Copyright (c) 1994 David Burren
22 * Copyright (c) 2000,2002,2010,2012 Solar Designer
23 * All rights reserved.
24 *
25 * Redistribution and use in source and binary forms, with or without
26 * modification, are permitted provided that the following conditions
27 * are met:
28 * 1. Redistributions of source code must retain the above copyright
29 * notice, this list of conditions and the following disclaimer.
30 * 2. Redistributions in binary form must reproduce the above copyright
31 * notice, this list of conditions and the following disclaimer in the
32 * documentation and/or other materials provided with the distribution.
33 * 3. Neither the name of the author nor the names of other contributors
34 * may be used to endorse or promote products derived from this software
35 * without specific prior written permission.
36 *
37 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
38 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
40 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
41 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
42 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
43 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
45 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
46 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
47 * SUCH DAMAGE.
48 *
49 * $Owl: Owl/packages/glibc/crypt_freesec.c,v 1.6 2010/02/20 14:45:06 solar Exp $
50 * $Id: crypt.c,v 1.15 1994/09/13 04:58:49 davidb Exp $
51 *
52 * This is an original implementation of the DES and the crypt(3) interfaces
53 * by David Burren. It has been heavily re-worked by Solar Designer.
54 */
55
56 #include <stdint.h>
57 #include <string.h>
58
59 #include "crypt_des.h"
60
61 #define _PASSWORD_EFMT1 '_'
62
63 static const unsigned char key_shifts[16] = {
64 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
65 };
66
67 static const uint32_t psbox[8][64] = {
68 {
69 0x00808200,0x00000000,0x00008000,0x00808202,
70 0x00808002,0x00008202,0x00000002,0x00008000,
71 0x00000200,0x00808200,0x00808202,0x00000200,
72 0x00800202,0x00808002,0x00800000,0x00000002,
73 0x00000202,0x00800200,0x00800200,0x00008200,
74 0x00008200,0x00808000,0x00808000,0x00800202,
75 0x00008002,0x00800002,0x00800002,0x00008002,
76 0x00000000,0x00000202,0x00008202,0x00800000,
77 0x00008000,0x00808202,0x00000002,0x00808000,
78 0x00808200,0x00800000,0x00800000,0x00000200,
79 0x00808002,0x00008000,0x00008200,0x00800002,
80 0x00000200,0x00000002,0x00800202,0x00008202,
81 0x00808202,0x00008002,0x00808000,0x00800202,
82 0x00800002,0x00000202,0x00008202,0x00808200,
83 0x00000202,0x00800200,0x00800200,0x00000000,
84 0x00008002,0x00008200,0x00000000,0x00808002,
85 },{
86 0x40084010,0x40004000,0x00004000,0x00084010,
87 0x00080000,0x00000010,0x40080010,0x40004010,
88 0x40000010,0x40084010,0x40084000,0x40000000,
89 0x40004000,0x00080000,0x00000010,0x40080010,
90 0x00084000,0x00080010,0x40004010,0x00000000,
91 0x40000000,0x00004000,0x00084010,0x40080000,
92 0x00080010,0x40000010,0x00000000,0x00084000,
93 0x00004010,0x40084000,0x40080000,0x00004010,
94 0x00000000,0x00084010,0x40080010,0x00080000,
95 0x40004010,0x40080000,0x40084000,0x00004000,
96 0x40080000,0x40004000,0x00000010,0x40084010,
97 0x00084010,0x00000010,0x00004000,0x40000000,
98 0x00004010,0x40084000,0x00080000,0x40000010,
99 0x00080010,0x40004010,0x40000010,0x00080010,
100 0x00084000,0x00000000,0x40004000,0x00004010,
101 0x40000000,0x40080010,0x40084010,0x00084000,
102 },{
103 0x00000104,0x04010100,0x00000000,0x04010004,
104 0x04000100,0x00000000,0x00010104,0x04000100,
105 0x00010004,0x04000004,0x04000004,0x00010000,
106 0x04010104,0x00010004,0x04010000,0x00000104,
107 0x04000000,0x00000004,0x04010100,0x00000100,
108 0x00010100,0x04010000,0x04010004,0x00010104,
109 0x04000104,0x00010100,0x00010000,0x04000104,
110 0x00000004,0x04010104,0x00000100,0x04000000,
111 0x04010100,0x04000000,0x00010004,0x00000104,
112 0x00010000,0x04010100,0x04000100,0x00000000,
113 0x00000100,0x00010004,0x04010104,0x04000100,
114 0x04000004,0x00000100,0x00000000,0x04010004,
115 0x04000104,0x00010000,0x04000000,0x04010104,
116 0x00000004,0x00010104,0x00010100,0x04000004,
117 0x04010000,0x04000104,0x00000104,0x04010000,
118 0x00010104,0x00000004,0x04010004,0x00010100,
119 },{
120 0x80401000,0x80001040,0x80001040,0x00000040,
121 0x00401040,0x80400040,0x80400000,0x80001000,
122 0x00000000,0x00401000,0x00401000,0x80401040,
123 0x80000040,0x00000000,0x00400040,0x80400000,
124 0x80000000,0x00001000,0x00400000,0x80401000,
125 0x00000040,0x00400000,0x80001000,0x00001040,
126 0x80400040,0x80000000,0x00001040,0x00400040,
127 0x00001000,0x00401040,0x80401040,0x80000040,
128 0x00400040,0x80400000,0x00401000,0x80401040,
129 0x80000040,0x00000000,0x00000000,0x00401000,
130 0x00001040,0x00400040,0x80400040,0x80000000,
131 0x80401000,0x80001040,0x80001040,0x00000040,
132 0x80401040,0x80000040,0x80000000,0x00001000,
133 0x80400000,0x80001000,0x00401040,0x80400040,
134 0x80001000,0x00001040,0x00400000,0x80401000,
135 0x00000040,0x00400000,0x00001000,0x00401040,
136 },{
137 0x00000080,0x01040080,0x01040000,0x21000080,
138 0x00040000,0x00000080,0x20000000,0x01040000,
139 0x20040080,0x00040000,0x01000080,0x20040080,
140 0x21000080,0x21040000,0x00040080,0x20000000,
141 0x01000000,0x20040000,0x20040000,0x00000000,
142 0x20000080,0x21040080,0x21040080,0x01000080,
143 0x21040000,0x20000080,0x00000000,0x21000000,
144 0x01040080,0x01000000,0x21000000,0x00040080,
145 0x00040000,0x21000080,0x00000080,0x01000000,
146 0x20000000,0x01040000,0x21000080,0x20040080,
147 0x01000080,0x20000000,0x21040000,0x01040080,
148 0x20040080,0x00000080,0x01000000,0x21040000,
149 0x21040080,0x00040080,0x21000000,0x21040080,
150 0x01040000,0x00000000,0x20040000,0x21000000,
151 0x00040080,0x01000080,0x20000080,0x00040000,
152 0x00000000,0x20040000,0x01040080,0x20000080,
153 },{
154 0x10000008,0x10200000,0x00002000,0x10202008,
155 0x10200000,0x00000008,0x10202008,0x00200000,
156 0x10002000,0x00202008,0x00200000,0x10000008,
157 0x00200008,0x10002000,0x10000000,0x00002008,
158 0x00000000,0x00200008,0x10002008,0x00002000,
159 0x00202000,0x10002008,0x00000008,0x10200008,
160 0x10200008,0x00000000,0x00202008,0x10202000,
161 0x00002008,0x00202000,0x10202000,0x10000000,
162 0x10002000,0x00000008,0x10200008,0x00202000,
163 0x10202008,0x00200000,0x00002008,0x10000008,
164 0x00200000,0x10002000,0x10000000,0x00002008,
165 0x10000008,0x10202008,0x00202000,0x10200000,
166 0x00202008,0x10202000,0x00000000,0x10200008,
167 0x00000008,0x00002000,0x10200000,0x00202008,
168 0x00002000,0x00200008,0x10002008,0x00000000,
169 0x10202000,0x10000000,0x00200008,0x10002008,
170 },{
171 0x00100000,0x02100001,0x02000401,0x00000000,
172 0x00000400,0x02000401,0x00100401,0x02100400,
173 0x02100401,0x00100000,0x00000000,0x02000001,
174 0x00000001,0x02000000,0x02100001,0x00000401,
175 0x02000400,0x00100401,0x00100001,0x02000400,
176 0x02000001,0x02100000,0x02100400,0x00100001,
177 0x02100000,0x00000400,0x00000401,0x02100401,
178 0x00100400,0x00000001,0x02000000,0x00100400,
179 0x02000000,0x00100400,0x00100000,0x02000401,
180 0x02000401,0x02100001,0x02100001,0x00000001,
181 0x00100001,0x02000000,0x02000400,0x00100000,
182 0x02100400,0x00000401,0x00100401,0x02100400,
183 0x00000401,0x02000001,0x02100401,0x02100000,
184 0x00100400,0x00000000,0x00000001,0x02100401,
185 0x00000000,0x00100401,0x02100000,0x00000400,
186 0x02000001,0x02000400,0x00000400,0x00100001,
187 },{
188 0x08000820,0x00000800,0x00020000,0x08020820,
189 0x08000000,0x08000820,0x00000020,0x08000000,
190 0x00020020,0x08020000,0x08020820,0x00020800,
191 0x08020800,0x00020820,0x00000800,0x00000020,
192 0x08020000,0x08000020,0x08000800,0x00000820,
193 0x00020800,0x00020020,0x08020020,0x08020800,
194 0x00000820,0x00000000,0x00000000,0x08020020,
195 0x08000020,0x08000800,0x00020820,0x00020000,
196 0x00020820,0x00020000,0x08020800,0x00000800,
197 0x00000020,0x08020020,0x00000800,0x00020820,
198 0x08000800,0x00000020,0x08000020,0x08020000,
199 0x08020020,0x08000000,0x00020000,0x08000820,
200 0x00000000,0x08020820,0x00020020,0x08000020,
201 0x08020000,0x08000800,0x08000820,0x00000000,
202 0x08020820,0x00020800,0x00020800,0x00000820,
203 0x00000820,0x00020020,0x08000000,0x08020800,
204 },
205 };
206 static const uint32_t ip_maskl[16][16] = {
207 {
208 0x00000000,0x00010000,0x00000000,0x00010000,
209 0x01000000,0x01010000,0x01000000,0x01010000,
210 0x00000000,0x00010000,0x00000000,0x00010000,
211 0x01000000,0x01010000,0x01000000,0x01010000,
212 },{
213 0x00000000,0x00000001,0x00000000,0x00000001,
214 0x00000100,0x00000101,0x00000100,0x00000101,
215 0x00000000,0x00000001,0x00000000,0x00000001,
216 0x00000100,0x00000101,0x00000100,0x00000101,
217 },{
218 0x00000000,0x00020000,0x00000000,0x00020000,
219 0x02000000,0x02020000,0x02000000,0x02020000,
220 0x00000000,0x00020000,0x00000000,0x00020000,
221 0x02000000,0x02020000,0x02000000,0x02020000,
222 },{
223 0x00000000,0x00000002,0x00000000,0x00000002,
224 0x00000200,0x00000202,0x00000200,0x00000202,
225 0x00000000,0x00000002,0x00000000,0x00000002,
226 0x00000200,0x00000202,0x00000200,0x00000202,
227 },{
228 0x00000000,0x00040000,0x00000000,0x00040000,
229 0x04000000,0x04040000,0x04000000,0x04040000,
230 0x00000000,0x00040000,0x00000000,0x00040000,
231 0x04000000,0x04040000,0x04000000,0x04040000,
232 },{
233 0x00000000,0x00000004,0x00000000,0x00000004,
234 0x00000400,0x00000404,0x00000400,0x00000404,
235 0x00000000,0x00000004,0x00000000,0x00000004,
236 0x00000400,0x00000404,0x00000400,0x00000404,
237 },{
238 0x00000000,0x00080000,0x00000000,0x00080000,
239 0x08000000,0x08080000,0x08000000,0x08080000,
240 0x00000000,0x00080000,0x00000000,0x00080000,
241 0x08000000,0x08080000,0x08000000,0x08080000,
242 },{
243 0x00000000,0x00000008,0x00000000,0x00000008,
244 0x00000800,0x00000808,0x00000800,0x00000808,
245 0x00000000,0x00000008,0x00000000,0x00000008,
246 0x00000800,0x00000808,0x00000800,0x00000808,
247 },{
248 0x00000000,0x00100000,0x00000000,0x00100000,
249 0x10000000,0x10100000,0x10000000,0x10100000,
250 0x00000000,0x00100000,0x00000000,0x00100000,
251 0x10000000,0x10100000,0x10000000,0x10100000,
252 },{
253 0x00000000,0x00000010,0x00000000,0x00000010,
254 0x00001000,0x00001010,0x00001000,0x00001010,
255 0x00000000,0x00000010,0x00000000,0x00000010,
256 0x00001000,0x00001010,0x00001000,0x00001010,
257 },{
258 0x00000000,0x00200000,0x00000000,0x00200000,
259 0x20000000,0x20200000,0x20000000,0x20200000,
260 0x00000000,0x00200000,0x00000000,0x00200000,
261 0x20000000,0x20200000,0x20000000,0x20200000,
262 },{
263 0x00000000,0x00000020,0x00000000,0x00000020,
264 0x00002000,0x00002020,0x00002000,0x00002020,
265 0x00000000,0x00000020,0x00000000,0x00000020,
266 0x00002000,0x00002020,0x00002000,0x00002020,
267 },{
268 0x00000000,0x00400000,0x00000000,0x00400000,
269 0x40000000,0x40400000,0x40000000,0x40400000,
270 0x00000000,0x00400000,0x00000000,0x00400000,
271 0x40000000,0x40400000,0x40000000,0x40400000,
272 },{
273 0x00000000,0x00000040,0x00000000,0x00000040,
274 0x00004000,0x00004040,0x00004000,0x00004040,
275 0x00000000,0x00000040,0x00000000,0x00000040,
276 0x00004000,0x00004040,0x00004000,0x00004040,
277 },{
278 0x00000000,0x00800000,0x00000000,0x00800000,
279 0x80000000,0x80800000,0x80000000,0x80800000,
280 0x00000000,0x00800000,0x00000000,0x00800000,
281 0x80000000,0x80800000,0x80000000,0x80800000,
282 },{
283 0x00000000,0x00000080,0x00000000,0x00000080,
284 0x00008000,0x00008080,0x00008000,0x00008080,
285 0x00000000,0x00000080,0x00000000,0x00000080,
286 0x00008000,0x00008080,0x00008000,0x00008080,
287 },
288 };
289 static const uint32_t ip_maskr[16][16] = {
290 {
291 0x00000000,0x00000000,0x00010000,0x00010000,
292 0x00000000,0x00000000,0x00010000,0x00010000,
293 0x01000000,0x01000000,0x01010000,0x01010000,
294 0x01000000,0x01000000,0x01010000,0x01010000,
295 },{
296 0x00000000,0x00000000,0x00000001,0x00000001,
297 0x00000000,0x00000000,0x00000001,0x00000001,
298 0x00000100,0x00000100,0x00000101,0x00000101,
299 0x00000100,0x00000100,0x00000101,0x00000101,
300 },{
301 0x00000000,0x00000000,0x00020000,0x00020000,
302 0x00000000,0x00000000,0x00020000,0x00020000,
303 0x02000000,0x02000000,0x02020000,0x02020000,
304 0x02000000,0x02000000,0x02020000,0x02020000,
305 },{
306 0x00000000,0x00000000,0x00000002,0x00000002,
307 0x00000000,0x00000000,0x00000002,0x00000002,
308 0x00000200,0x00000200,0x00000202,0x00000202,
309 0x00000200,0x00000200,0x00000202,0x00000202,
310 },{
311 0x00000000,0x00000000,0x00040000,0x00040000,
312 0x00000000,0x00000000,0x00040000,0x00040000,
313 0x04000000,0x04000000,0x04040000,0x04040000,
314 0x04000000,0x04000000,0x04040000,0x04040000,
315 },{
316 0x00000000,0x00000000,0x00000004,0x00000004,
317 0x00000000,0x00000000,0x00000004,0x00000004,
318 0x00000400,0x00000400,0x00000404,0x00000404,
319 0x00000400,0x00000400,0x00000404,0x00000404,
320 },{
321 0x00000000,0x00000000,0x00080000,0x00080000,
322 0x00000000,0x00000000,0x00080000,0x00080000,
323 0x08000000,0x08000000,0x08080000,0x08080000,
324 0x08000000,0x08000000,0x08080000,0x08080000,
325 },{
326 0x00000000,0x00000000,0x00000008,0x00000008,
327 0x00000000,0x00000000,0x00000008,0x00000008,
328 0x00000800,0x00000800,0x00000808,0x00000808,
329 0x00000800,0x00000800,0x00000808,0x00000808,
330 },{
331 0x00000000,0x00000000,0x00100000,0x00100000,
332 0x00000000,0x00000000,0x00100000,0x00100000,
333 0x10000000,0x10000000,0x10100000,0x10100000,
334 0x10000000,0x10000000,0x10100000,0x10100000,
335 },{
336 0x00000000,0x00000000,0x00000010,0x00000010,
337 0x00000000,0x00000000,0x00000010,0x00000010,
338 0x00001000,0x00001000,0x00001010,0x00001010,
339 0x00001000,0x00001000,0x00001010,0x00001010,
340 },{
341 0x00000000,0x00000000,0x00200000,0x00200000,
342 0x00000000,0x00000000,0x00200000,0x00200000,
343 0x20000000,0x20000000,0x20200000,0x20200000,
344 0x20000000,0x20000000,0x20200000,0x20200000,
345 },{
346 0x00000000,0x00000000,0x00000020,0x00000020,
347 0x00000000,0x00000000,0x00000020,0x00000020,
348 0x00002000,0x00002000,0x00002020,0x00002020,
349 0x00002000,0x00002000,0x00002020,0x00002020,
350 },{
351 0x00000000,0x00000000,0x00400000,0x00400000,
352 0x00000000,0x00000000,0x00400000,0x00400000,
353 0x40000000,0x40000000,0x40400000,0x40400000,
354 0x40000000,0x40000000,0x40400000,0x40400000,
355 },{
356 0x00000000,0x00000000,0x00000040,0x00000040,
357 0x00000000,0x00000000,0x00000040,0x00000040,
358 0x00004000,0x00004000,0x00004040,0x00004040,
359 0x00004000,0x00004000,0x00004040,0x00004040,
360 },{
361 0x00000000,0x00000000,0x00800000,0x00800000,
362 0x00000000,0x00000000,0x00800000,0x00800000,
363 0x80000000,0x80000000,0x80800000,0x80800000,
364 0x80000000,0x80000000,0x80800000,0x80800000,
365 },{
366 0x00000000,0x00000000,0x00000080,0x00000080,
367 0x00000000,0x00000000,0x00000080,0x00000080,
368 0x00008000,0x00008000,0x00008080,0x00008080,
369 0x00008000,0x00008000,0x00008080,0x00008080,
370 },
371 };
372 static const uint32_t fp_maskl[8][16] = {
373 {
374 0x00000000,0x40000000,0x00400000,0x40400000,
375 0x00004000,0x40004000,0x00404000,0x40404000,
376 0x00000040,0x40000040,0x00400040,0x40400040,
377 0x00004040,0x40004040,0x00404040,0x40404040,
378 },{
379 0x00000000,0x10000000,0x00100000,0x10100000,
380 0x00001000,0x10001000,0x00101000,0x10101000,
381 0x00000010,0x10000010,0x00100010,0x10100010,
382 0x00001010,0x10001010,0x00101010,0x10101010,
383 },{
384 0x00000000,0x04000000,0x00040000,0x04040000,
385 0x00000400,0x04000400,0x00040400,0x04040400,
386 0x00000004,0x04000004,0x00040004,0x04040004,
387 0x00000404,0x04000404,0x00040404,0x04040404,
388 },{
389 0x00000000,0x01000000,0x00010000,0x01010000,
390 0x00000100,0x01000100,0x00010100,0x01010100,
391 0x00000001,0x01000001,0x00010001,0x01010001,
392 0x00000101,0x01000101,0x00010101,0x01010101,
393 },{
394 0x00000000,0x80000000,0x00800000,0x80800000,
395 0x00008000,0x80008000,0x00808000,0x80808000,
396 0x00000080,0x80000080,0x00800080,0x80800080,
397 0x00008080,0x80008080,0x00808080,0x80808080,
398 },{
399 0x00000000,0x20000000,0x00200000,0x20200000,
400 0x00002000,0x20002000,0x00202000,0x20202000,
401 0x00000020,0x20000020,0x00200020,0x20200020,
402 0x00002020,0x20002020,0x00202020,0x20202020,
403 },{
404 0x00000000,0x08000000,0x00080000,0x08080000,
405 0x00000800,0x08000800,0x00080800,0x08080800,
406 0x00000008,0x08000008,0x00080008,0x08080008,
407 0x00000808,0x08000808,0x00080808,0x08080808,
408 },{
409 0x00000000,0x02000000,0x00020000,0x02020000,
410 0x00000200,0x02000200,0x00020200,0x02020200,
411 0x00000002,0x02000002,0x00020002,0x02020002,
412 0x00000202,0x02000202,0x00020202,0x02020202,
413 },
414 };
415 static const uint32_t fp_maskr[8][16] = {
416 {
417 0x00000000,0x40000000,0x00400000,0x40400000,
418 0x00004000,0x40004000,0x00404000,0x40404000,
419 0x00000040,0x40000040,0x00400040,0x40400040,
420 0x00004040,0x40004040,0x00404040,0x40404040,
421 },{
422 0x00000000,0x10000000,0x00100000,0x10100000,
423 0x00001000,0x10001000,0x00101000,0x10101000,
424 0x00000010,0x10000010,0x00100010,0x10100010,
425 0x00001010,0x10001010,0x00101010,0x10101010,
426 },{
427 0x00000000,0x04000000,0x00040000,0x04040000,
428 0x00000400,0x04000400,0x00040400,0x04040400,
429 0x00000004,0x04000004,0x00040004,0x04040004,
430 0x00000404,0x04000404,0x00040404,0x04040404,
431 },{
432 0x00000000,0x01000000,0x00010000,0x01010000,
433 0x00000100,0x01000100,0x00010100,0x01010100,
434 0x00000001,0x01000001,0x00010001,0x01010001,
435 0x00000101,0x01000101,0x00010101,0x01010101,
436 },{
437 0x00000000,0x80000000,0x00800000,0x80800000,
438 0x00008000,0x80008000,0x00808000,0x80808000,
439 0x00000080,0x80000080,0x00800080,0x80800080,
440 0x00008080,0x80008080,0x00808080,0x80808080,
441 },{
442 0x00000000,0x20000000,0x00200000,0x20200000,
443 0x00002000,0x20002000,0x00202000,0x20202000,
444 0x00000020,0x20000020,0x00200020,0x20200020,
445 0x00002020,0x20002020,0x00202020,0x20202020,
446 },{
447 0x00000000,0x08000000,0x00080000,0x08080000,
448 0x00000800,0x08000800,0x00080800,0x08080800,
449 0x00000008,0x08000008,0x00080008,0x08080008,
450 0x00000808,0x08000808,0x00080808,0x08080808,
451 },{
452 0x00000000,0x02000000,0x00020000,0x02020000,
453 0x00000200,0x02000200,0x00020200,0x02020200,
454 0x00000002,0x02000002,0x00020002,0x02020002,
455 0x00000202,0x02000202,0x00020202,0x02020202,
456 },
457 };
458 static const uint32_t key_perm_maskl[8][16] = {
459 {
460 0x00000000,0x00000000,0x00000010,0x00000010,
461 0x00001000,0x00001000,0x00001010,0x00001010,
462 0x00100000,0x00100000,0x00100010,0x00100010,
463 0x00101000,0x00101000,0x00101010,0x00101010,
464 },{
465 0x00000000,0x00000000,0x00000020,0x00000020,
466 0x00002000,0x00002000,0x00002020,0x00002020,
467 0x00200000,0x00200000,0x00200020,0x00200020,
468 0x00202000,0x00202000,0x00202020,0x00202020,
469 },{
470 0x00000000,0x00000000,0x00000040,0x00000040,
471 0x00004000,0x00004000,0x00004040,0x00004040,
472 0x00400000,0x00400000,0x00400040,0x00400040,
473 0x00404000,0x00404000,0x00404040,0x00404040,
474 },{
475 0x00000000,0x00000000,0x00000080,0x00000080,
476 0x00008000,0x00008000,0x00008080,0x00008080,
477 0x00800000,0x00800000,0x00800080,0x00800080,
478 0x00808000,0x00808000,0x00808080,0x00808080,
479 },{
480 0x00000000,0x00000001,0x00000100,0x00000101,
481 0x00010000,0x00010001,0x00010100,0x00010101,
482 0x01000000,0x01000001,0x01000100,0x01000101,
483 0x01010000,0x01010001,0x01010100,0x01010101,
484 },{
485 0x00000000,0x00000002,0x00000200,0x00000202,
486 0x00020000,0x00020002,0x00020200,0x00020202,
487 0x02000000,0x02000002,0x02000200,0x02000202,
488 0x02020000,0x02020002,0x02020200,0x02020202,
489 },{
490 0x00000000,0x00000004,0x00000400,0x00000404,
491 0x00040000,0x00040004,0x00040400,0x00040404,
492 0x04000000,0x04000004,0x04000400,0x04000404,
493 0x04040000,0x04040004,0x04040400,0x04040404,
494 },{
495 0x00000000,0x00000008,0x00000800,0x00000808,
496 0x00080000,0x00080008,0x00080800,0x00080808,
497 0x08000000,0x08000008,0x08000800,0x08000808,
498 0x08080000,0x08080008,0x08080800,0x08080808,
499 },
500 };
501 static const uint32_t key_perm_maskr[12][16] = {
502 {
503 0x00000000,0x00000001,0x00000000,0x00000001,
504 0x00000000,0x00000001,0x00000000,0x00000001,
505 0x00000000,0x00000001,0x00000000,0x00000001,
506 0x00000000,0x00000001,0x00000000,0x00000001,
507 },{
508 0x00000000,0x00000000,0x00100000,0x00100000,
509 0x00001000,0x00001000,0x00101000,0x00101000,
510 0x00000010,0x00000010,0x00100010,0x00100010,
511 0x00001010,0x00001010,0x00101010,0x00101010,
512 },{
513 0x00000000,0x00000002,0x00000000,0x00000002,
514 0x00000000,0x00000002,0x00000000,0x00000002,
515 0x00000000,0x00000002,0x00000000,0x00000002,
516 0x00000000,0x00000002,0x00000000,0x00000002,
517 },{
518 0x00000000,0x00000000,0x00200000,0x00200000,
519 0x00002000,0x00002000,0x00202000,0x00202000,
520 0x00000020,0x00000020,0x00200020,0x00200020,
521 0x00002020,0x00002020,0x00202020,0x00202020,
522 },{
523 0x00000000,0x00000004,0x00000000,0x00000004,
524 0x00000000,0x00000004,0x00000000,0x00000004,
525 0x00000000,0x00000004,0x00000000,0x00000004,
526 0x00000000,0x00000004,0x00000000,0x00000004,
527 },{
528 0x00000000,0x00000000,0x00400000,0x00400000,
529 0x00004000,0x00004000,0x00404000,0x00404000,
530 0x00000040,0x00000040,0x00400040,0x00400040,
531 0x00004040,0x00004040,0x00404040,0x00404040,
532 },{
533 0x00000000,0x00000008,0x00000000,0x00000008,
534 0x00000000,0x00000008,0x00000000,0x00000008,
535 0x00000000,0x00000008,0x00000000,0x00000008,
536 0x00000000,0x00000008,0x00000000,0x00000008,
537 },{
538 0x00000000,0x00000000,0x00800000,0x00800000,
539 0x00008000,0x00008000,0x00808000,0x00808000,
540 0x00000080,0x00000080,0x00800080,0x00800080,
541 0x00008080,0x00008080,0x00808080,0x00808080,
542 },{
543 0x00000000,0x00000000,0x01000000,0x01000000,
544 0x00010000,0x00010000,0x01010000,0x01010000,
545 0x00000100,0x00000100,0x01000100,0x01000100,
546 0x00010100,0x00010100,0x01010100,0x01010100,
547 },{
548 0x00000000,0x00000000,0x02000000,0x02000000,
549 0x00020000,0x00020000,0x02020000,0x02020000,
550 0x00000200,0x00000200,0x02000200,0x02000200,
551 0x00020200,0x00020200,0x02020200,0x02020200,
552 },{
553 0x00000000,0x00000000,0x04000000,0x04000000,
554 0x00040000,0x00040000,0x04040000,0x04040000,
555 0x00000400,0x00000400,0x04000400,0x04000400,
556 0x00040400,0x00040400,0x04040400,0x04040400,
557 },{
558 0x00000000,0x00000000,0x08000000,0x08000000,
559 0x00080000,0x00080000,0x08080000,0x08080000,
560 0x00000800,0x00000800,0x08000800,0x08000800,
561 0x00080800,0x00080800,0x08080800,0x08080800,
562 },
563 };
564 static const uint32_t comp_maskl0[4][8] = {
565 {
566 0x00000000,0x00020000,0x00000001,0x00020001,
567 0x00080000,0x000a0000,0x00080001,0x000a0001,
568 },{
569 0x00000000,0x00001000,0x00000000,0x00001000,
570 0x00000040,0x00001040,0x00000040,0x00001040,
571 },{
572 0x00000000,0x00400000,0x00000020,0x00400020,
573 0x00008000,0x00408000,0x00008020,0x00408020,
574 },{
575 0x00000000,0x00100000,0x00000800,0x00100800,
576 0x00000000,0x00100000,0x00000800,0x00100800,
577 },
578 };
579 static const uint32_t comp_maskr0[4][8] = {
580 {
581 0x00000000,0x00200000,0x00020000,0x00220000,
582 0x00000002,0x00200002,0x00020002,0x00220002,
583 },{
584 0x00000000,0x00000000,0x00100000,0x00100000,
585 0x00000004,0x00000004,0x00100004,0x00100004,
586 },{
587 0x00000000,0x00004000,0x00000800,0x00004800,
588 0x00000000,0x00004000,0x00000800,0x00004800,
589 },{
590 0x00000000,0x00400000,0x00008000,0x00408000,
591 0x00000008,0x00400008,0x00008008,0x00408008,
592 },
593 };
594 static const uint32_t comp_maskl1[4][16] = {
595 {
596 0x00000000,0x00000010,0x00004000,0x00004010,
597 0x00040000,0x00040010,0x00044000,0x00044010,
598 0x00000100,0x00000110,0x00004100,0x00004110,
599 0x00040100,0x00040110,0x00044100,0x00044110,
600 },{
601 0x00000000,0x00800000,0x00000002,0x00800002,
602 0x00000200,0x00800200,0x00000202,0x00800202,
603 0x00200000,0x00a00000,0x00200002,0x00a00002,
604 0x00200200,0x00a00200,0x00200202,0x00a00202,
605 },{
606 0x00000000,0x00002000,0x00000004,0x00002004,
607 0x00000400,0x00002400,0x00000404,0x00002404,
608 0x00000000,0x00002000,0x00000004,0x00002004,
609 0x00000400,0x00002400,0x00000404,0x00002404,
610 },{
611 0x00000000,0x00010000,0x00000008,0x00010008,
612 0x00000080,0x00010080,0x00000088,0x00010088,
613 0x00000000,0x00010000,0x00000008,0x00010008,
614 0x00000080,0x00010080,0x00000088,0x00010088,
615 },
616 };
617 static const uint32_t comp_maskr1[4][16] = {
618 {
619 0x00000000,0x00000000,0x00000080,0x00000080,
620 0x00002000,0x00002000,0x00002080,0x00002080,
621 0x00000001,0x00000001,0x00000081,0x00000081,
622 0x00002001,0x00002001,0x00002081,0x00002081,
623 },{
624 0x00000000,0x00000010,0x00800000,0x00800010,
625 0x00010000,0x00010010,0x00810000,0x00810010,
626 0x00000200,0x00000210,0x00800200,0x00800210,
627 0x00010200,0x00010210,0x00810200,0x00810210,
628 },{
629 0x00000000,0x00000400,0x00001000,0x00001400,
630 0x00080000,0x00080400,0x00081000,0x00081400,
631 0x00000020,0x00000420,0x00001020,0x00001420,
632 0x00080020,0x00080420,0x00081020,0x00081420,
633 },{
634 0x00000000,0x00000100,0x00040000,0x00040100,
635 0x00000000,0x00000100,0x00040000,0x00040100,
636 0x00000040,0x00000140,0x00040040,0x00040140,
637 0x00000040,0x00000140,0x00040040,0x00040140,
638 },
639 };
640
641 static const unsigned char ascii64[] =
642 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
643 /* 0000000000111111111122222222223333333333444444444455555555556666 */
644 /* 0123456789012345678901234567890123456789012345678901234567890123 */
645
646 /*
647 * We match the behavior of UFC-crypt on systems where "char" is signed by
648 * default (the majority), regardless of char's signedness on our system.
649 */
ascii_to_bin(int ch)650 static uint32_t ascii_to_bin(int ch)
651 {
652 int sch = (ch < 0x80) ? ch : -(0x100 - ch);
653 int retval;
654
655 retval = sch - '.';
656 if (sch >= 'A') {
657 retval = sch - ('A' - 12);
658 if (sch >= 'a')
659 retval = sch - ('a' - 38);
660 }
661 retval &= 0x3f;
662
663 return retval;
664 }
665
666 /*
667 * When we choose to "support" invalid salts, nevertheless disallow those
668 * containing characters that would violate the passwd file format.
669 */
ascii_is_unsafe(unsigned char ch)670 static inline int ascii_is_unsafe(unsigned char ch)
671 {
672 return !ch || ch == '\n' || ch == ':';
673 }
674
setup_salt(uint32_t salt)675 static uint32_t setup_salt(uint32_t salt)
676 {
677 uint32_t obit, saltbit, saltbits;
678 unsigned int i;
679
680 saltbits = 0;
681 saltbit = 1;
682 obit = 0x800000;
683 for (i = 0; i < 24; i++) {
684 if (salt & saltbit)
685 saltbits |= obit;
686 saltbit <<= 1;
687 obit >>= 1;
688 }
689
690 return saltbits;
691 }
692
__des_setkey(const unsigned char * key,struct expanded_key * ekey)693 void __des_setkey(const unsigned char *key, struct expanded_key *ekey)
694 {
695 uint32_t k0, k1, rawkey0, rawkey1;
696 unsigned int shifts, round, i, ibit;
697
698 rawkey0 =
699 (uint32_t)key[3] |
700 ((uint32_t)key[2] << 8) |
701 ((uint32_t)key[1] << 16) |
702 ((uint32_t)key[0] << 24);
703 rawkey1 =
704 (uint32_t)key[7] |
705 ((uint32_t)key[6] << 8) |
706 ((uint32_t)key[5] << 16) |
707 ((uint32_t)key[4] << 24);
708
709 /*
710 * Do key permutation and split into two 28-bit subkeys.
711 */
712 k0 = k1 = 0;
713 for (i = 0, ibit = 28; i < 4; i++, ibit -= 4) {
714 unsigned int j = i << 1;
715 k0 |= key_perm_maskl[i][(rawkey0 >> ibit) & 0xf] |
716 key_perm_maskl[i + 4][(rawkey1 >> ibit) & 0xf];
717 k1 |= key_perm_maskr[j][(rawkey0 >> ibit) & 0xf];
718 ibit -= 4;
719 k1 |= key_perm_maskr[j + 1][(rawkey0 >> ibit) & 0xf] |
720 key_perm_maskr[i + 8][(rawkey1 >> ibit) & 0xf];
721 }
722
723 /*
724 * Rotate subkeys and do compression permutation.
725 */
726 shifts = 0;
727 for (round = 0; round < 16; round++) {
728 uint32_t t0, t1;
729 uint32_t kl, kr;
730
731 shifts += key_shifts[round];
732
733 t0 = (k0 << shifts) | (k0 >> (28 - shifts));
734 t1 = (k1 << shifts) | (k1 >> (28 - shifts));
735
736 kl = kr = 0;
737 ibit = 25;
738 for (i = 0; i < 4; i++) {
739 kl |= comp_maskl0[i][(t0 >> ibit) & 7];
740 kr |= comp_maskr0[i][(t1 >> ibit) & 7];
741 ibit -= 4;
742 kl |= comp_maskl1[i][(t0 >> ibit) & 0xf];
743 kr |= comp_maskr1[i][(t1 >> ibit) & 0xf];
744 ibit -= 3;
745 }
746 ekey->l[round] = kl;
747 ekey->r[round] = kr;
748 }
749 }
750
751 /*
752 * l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
753 */
__do_des(uint32_t l_in,uint32_t r_in,uint32_t * l_out,uint32_t * r_out,uint32_t count,uint32_t saltbits,const struct expanded_key * ekey)754 void __do_des(uint32_t l_in, uint32_t r_in,
755 uint32_t *l_out, uint32_t *r_out,
756 uint32_t count, uint32_t saltbits, const struct expanded_key *ekey)
757 {
758 uint32_t l, r;
759
760 /*
761 * Do initial permutation (IP).
762 */
763 l = r = 0;
764 if (l_in | r_in) {
765 unsigned int i, ibit;
766 for (i = 0, ibit = 28; i < 8; i++, ibit -= 4) {
767 l |= ip_maskl[i][(l_in >> ibit) & 0xf] |
768 ip_maskl[i + 8][(r_in >> ibit) & 0xf];
769 r |= ip_maskr[i][(l_in >> ibit) & 0xf] |
770 ip_maskr[i + 8][(r_in >> ibit) & 0xf];
771 }
772 }
773
774 while (count--) {
775 /*
776 * Do each round.
777 */
778 unsigned int round = 16;
779 const uint32_t *kl = ekey->l;
780 const uint32_t *kr = ekey->r;
781 uint32_t f;
782 while (round--) {
783 uint32_t r48l, r48r;
784 /*
785 * Expand R to 48 bits (simulate the E-box).
786 */
787 r48l = ((r & 0x00000001) << 23)
788 | ((r & 0xf8000000) >> 9)
789 | ((r & 0x1f800000) >> 11)
790 | ((r & 0x01f80000) >> 13)
791 | ((r & 0x001f8000) >> 15);
792
793 r48r = ((r & 0x0001f800) << 7)
794 | ((r & 0x00001f80) << 5)
795 | ((r & 0x000001f8) << 3)
796 | ((r & 0x0000001f) << 1)
797 | ((r & 0x80000000) >> 31);
798 /*
799 * Do salting for crypt() and friends, and
800 * XOR with the permuted key.
801 */
802 f = (r48l ^ r48r) & saltbits;
803 r48l ^= f ^ *kl++;
804 r48r ^= f ^ *kr++;
805 /*
806 * Do S-box lookups (which shrink it back to 32 bits)
807 * and do the P-box permutation at the same time.
808 */
809 f = psbox[0][r48l >> 18]
810 | psbox[1][(r48l >> 12) & 0x3f]
811 | psbox[2][(r48l >> 6) & 0x3f]
812 | psbox[3][r48l & 0x3f]
813 | psbox[4][r48r >> 18]
814 | psbox[5][(r48r >> 12) & 0x3f]
815 | psbox[6][(r48r >> 6) & 0x3f]
816 | psbox[7][r48r & 0x3f];
817 /*
818 * Now that we've permuted things, complete f().
819 */
820 f ^= l;
821 l = r;
822 r = f;
823 }
824 r = l;
825 l = f;
826 }
827
828 /*
829 * Do final permutation (inverse of IP).
830 */
831 {
832 unsigned int i, ibit;
833 uint32_t lo, ro;
834 lo = ro = 0;
835 for (i = 0, ibit = 28; i < 4; i++, ibit -= 4) {
836 ro |= fp_maskr[i][(l >> ibit) & 0xf] |
837 fp_maskr[i + 4][(r >> ibit) & 0xf];
838 ibit -= 4;
839 lo |= fp_maskl[i][(l >> ibit) & 0xf] |
840 fp_maskl[i + 4][(r >> ibit) & 0xf];
841 }
842 *l_out = lo;
843 *r_out = ro;
844 }
845 }
846
des_cipher(const unsigned char * in,unsigned char * out,uint32_t count,uint32_t saltbits,const struct expanded_key * ekey)847 static void des_cipher(const unsigned char *in, unsigned char *out,
848 uint32_t count, uint32_t saltbits, const struct expanded_key *ekey)
849 {
850 uint32_t l_out, r_out, rawl, rawr;
851
852 rawl =
853 (uint32_t)in[3] |
854 ((uint32_t)in[2] << 8) |
855 ((uint32_t)in[1] << 16) |
856 ((uint32_t)in[0] << 24);
857 rawr =
858 (uint32_t)in[7] |
859 ((uint32_t)in[6] << 8) |
860 ((uint32_t)in[5] << 16) |
861 ((uint32_t)in[4] << 24);
862
863 __do_des(rawl, rawr, &l_out, &r_out, count, saltbits, ekey);
864
865 out[0] = l_out >> 24;
866 out[1] = l_out >> 16;
867 out[2] = l_out >> 8;
868 out[3] = l_out;
869 out[4] = r_out >> 24;
870 out[5] = r_out >> 16;
871 out[6] = r_out >> 8;
872 out[7] = r_out;
873 }
874
_crypt_extended_r_uut(const char * _key,const char * _setting,char * output)875 static char *_crypt_extended_r_uut(const char *_key, const char *_setting, char *output)
876 {
877 const unsigned char *key = (const unsigned char *)_key;
878 const unsigned char *setting = (const unsigned char *)_setting;
879 struct expanded_key ekey;
880 unsigned char keybuf[8];
881 unsigned char *p, *q;
882 uint32_t count, salt, l, r0, r1;
883 unsigned int i;
884
885 /*
886 * Copy the key, shifting each character left by one bit and padding
887 * with zeroes.
888 */
889 q = keybuf;
890 while (q <= &keybuf[sizeof(keybuf) - 1]) {
891 *q++ = *key << 1;
892 if (*key)
893 key++;
894 }
895 __des_setkey(keybuf, &ekey);
896
897 if (*setting == _PASSWORD_EFMT1) {
898 /*
899 * "new"-style:
900 * setting - underscore, 4 chars of count, 4 chars of salt
901 * key - unlimited characters
902 */
903 for (i = 1, count = 0; i < 5; i++) {
904 uint32_t value = ascii_to_bin(setting[i]);
905 if (ascii64[value] != setting[i])
906 return NULL;
907 count |= value << (i - 1) * 6;
908 }
909 if (!count)
910 return NULL;
911
912 for (i = 5, salt = 0; i < 9; i++) {
913 uint32_t value = ascii_to_bin(setting[i]);
914 if (ascii64[value] != setting[i])
915 return NULL;
916 salt |= value << (i - 5) * 6;
917 }
918
919 while (*key) {
920 /*
921 * Encrypt the key with itself.
922 */
923 des_cipher(keybuf, keybuf, 1, 0, &ekey);
924 /*
925 * And XOR with the next 8 characters of the key.
926 */
927 q = keybuf;
928 while (q <= &keybuf[sizeof(keybuf) - 1] && *key)
929 *q++ ^= *key++ << 1;
930 __des_setkey(keybuf, &ekey);
931 }
932
933 memcpy(output, setting, 9);
934 output[9] = '\0';
935 p = (unsigned char *)output + 9;
936 } else {
937 /*
938 * "old"-style:
939 * setting - 2 chars of salt
940 * key - up to 8 characters
941 */
942 count = 25;
943
944 if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
945 return NULL;
946
947 salt = (ascii_to_bin(setting[1]) << 6)
948 | ascii_to_bin(setting[0]);
949
950 output[0] = setting[0];
951 output[1] = setting[1];
952 p = (unsigned char *)output + 2;
953 }
954
955 /*
956 * Do it.
957 */
958 __do_des(0, 0, &r0, &r1, count, setup_salt(salt), &ekey);
959
960 /*
961 * Now encode the result...
962 */
963 l = (r0 >> 8);
964 *p++ = ascii64[(l >> 18) & 0x3f];
965 *p++ = ascii64[(l >> 12) & 0x3f];
966 *p++ = ascii64[(l >> 6) & 0x3f];
967 *p++ = ascii64[l & 0x3f];
968
969 l = (r0 << 16) | ((r1 >> 16) & 0xffff);
970 *p++ = ascii64[(l >> 18) & 0x3f];
971 *p++ = ascii64[(l >> 12) & 0x3f];
972 *p++ = ascii64[(l >> 6) & 0x3f];
973 *p++ = ascii64[l & 0x3f];
974
975 l = r1 << 2;
976 *p++ = ascii64[(l >> 12) & 0x3f];
977 *p++ = ascii64[(l >> 6) & 0x3f];
978 *p++ = ascii64[l & 0x3f];
979 *p = 0;
980
981 return output;
982 }
983
__crypt_des(const char * key,const char * setting,char * output)984 char *__crypt_des(const char *key, const char *setting, char *output)
985 {
986 const char *test_key = "\x80\xff\x80\x01 "
987 "\x7f\x81\x80\x80\x0d\x0a\xff\x7f \x81 test";
988 const char *test_setting = "_0.../9Zz";
989 const char *test_hash = "_0.../9ZzX7iSJNd21sU";
990 char test_buf[21];
991 char *retval;
992 const char *p;
993
994 if (*setting != _PASSWORD_EFMT1) {
995 test_setting = "\x80x";
996 test_hash = "\x80x22/wK52ZKGA";
997 }
998
999 /*
1000 * Hash the supplied password.
1001 */
1002 retval = _crypt_extended_r_uut(key, setting, output);
1003
1004 /*
1005 * Perform a quick self-test. It is important that we make both calls
1006 * to _crypt_extended_r_uut() from the same scope such that they likely
1007 * use the same stack locations, which makes the second call overwrite
1008 * the first call's sensitive data on the stack and makes it more
1009 * likely that any alignment related issues would be detected.
1010 */
1011 p = _crypt_extended_r_uut(test_key, test_setting, test_buf);
1012 if (p && !strcmp(p, test_hash) && retval)
1013 return retval;
1014
1015 return (setting[0]=='*') ? "x" : "*";
1016 }
1017