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
63static 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
67static 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};
206static 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};
289static 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};
372static 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};
415static 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};
458static 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};
501static 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};
564static 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};
579static 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};
594static 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};
617static 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
641static 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 */
650static 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 */
670static inline int ascii_is_unsafe(unsigned char ch)
671{
672	return !ch || ch == '\n' || ch == ':';
673}
674
675static 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
693void __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 */
754void __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
847static 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
875static 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
984char *_crypt_des_r(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