Meg's Mirrors

zig

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	*/
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	*/
670	static inline int ascii_is_unsafe(unsigned char ch)
671	{
672	return !ch || ch == '\n' || ch == ':';
673	}
674
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
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	*/
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
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
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
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	}