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