1/*
2  $Id$
3*/
4/*
5 * This version is derived from the original implementation of FreeSec
6 * (release 1.1) by David Burren.  I've reviewed the changes made in
7 * OpenBSD (as of 2.7) and modified the original code in a similar way
8 * where applicable.  I've also made it reentrant and made a number of
9 * other changes.
10 * - Solar Designer <solar at openwall.com>
11 */
12
13/*
14 * FreeSec: libcrypt for NetBSD
15 *
16 * Copyright (c) 1994 David Burren
17 * All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
21 * are met:
22 * 1. Redistributions of source code must retain the above copyright
23 *    notice, this list of conditions and the following disclaimer.
24 * 2. Redistributions in binary form must reproduce the above copyright
25 *    notice, this list of conditions and the following disclaimer in the
26 *    documentation and/or other materials provided with the distribution.
27 * 3. Neither the name of the author nor the names of other contributors
28 *    may be used to endorse or promote products derived from this software
29 *    without specific prior written permission.
30 *
31 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
32 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
33 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
34 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
35 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
36 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
37 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
39 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
40 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
41 * SUCH DAMAGE.
42 *
43 *	$Owl: Owl/packages/glibc/crypt_freesec.c,v 1.4 2005/11/16 13:08:32 solar Exp $
44 *	$Id$
45 *
46 * This is an original implementation of the DES and the crypt(3) interfaces
47 * by David Burren <davidb at werj.com.au>.
48 *
49 * An excellent reference on the underlying algorithm (and related
50 * algorithms) is:
51 *
52 *	B. Schneier, Applied Cryptography: protocols, algorithms,
53 *	and source code in C, John Wiley & Sons, 1994.
54 *
55 * Note that in that book's description of DES the lookups for the initial,
56 * pbox, and final permutations are inverted (this has been brought to the
57 * attention of the author).  A list of errata for this book has been
58 * posted to the sci.crypt newsgroup by the author and is available for FTP.
59 *
60 * ARCHITECTURE ASSUMPTIONS:
61 *	This code used to have some nasty ones, but these have been removed
62 *	by now.  The code requires a 32-bit integer type, though.
63 */
64
65#include <sys/types.h>
66#include <string.h>
67
68#ifdef TEST
69#include <stdio.h>
70#endif
71
72#include "crypt_freesec.h"
73
74#define _PASSWORD_EFMT1 '_'
75
76static u_char	IP[64] = {
77	58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12,  4,
78	62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16,  8,
79	57, 49, 41, 33, 25, 17,  9,  1, 59, 51, 43, 35, 27, 19, 11,  3,
80	61, 53, 45, 37, 29, 21, 13,  5, 63, 55, 47, 39, 31, 23, 15,  7
81};
82
83static u_char	key_perm[56] = {
84	57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
85	10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
86	63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
87	14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
88};
89
90static u_char	key_shifts[16] = {
91	1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
92};
93
94static u_char	comp_perm[48] = {
95	14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
96	23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
97	41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
98	44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
99};
100
101/*
102 *	No E box is used, as it's replaced by some ANDs, shifts, and ORs.
103 */
104
105static u_char	sbox[8][64] = {
106	{
107		14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
108		 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
109		 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
110		15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
111	},
112	{
113		15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
114		 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
115		 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
116		13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
117	},
118	{
119		10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
120		13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
121		13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
122		 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
123	},
124	{
125		 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
126		13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
127		10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
128		 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
129	},
130	{
131		 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
132		14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
133		 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
134		11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
135	},
136	{
137		12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
138		10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
139		 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
140		 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
141	},
142	{
143		 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
144		13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
145		 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
146		 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
147	},
148	{
149		13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
150		 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
151		 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
152		 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
153	}
154};
155
156static u_char	pbox[32] = {
157	16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
158	 2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
159};
160
161static uint32_t bits32[32] =
162{
163	0x80000000, 0x40000000, 0x20000000, 0x10000000,
164	0x08000000, 0x04000000, 0x02000000, 0x01000000,
165	0x00800000, 0x00400000, 0x00200000, 0x00100000,
166	0x00080000, 0x00040000, 0x00020000, 0x00010000,
167	0x00008000, 0x00004000, 0x00002000, 0x00001000,
168	0x00000800, 0x00000400, 0x00000200, 0x00000100,
169	0x00000080, 0x00000040, 0x00000020, 0x00000010,
170	0x00000008, 0x00000004, 0x00000002, 0x00000001
171};
172
173static u_char	bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
174
175static unsigned char	ascii64[] =
176	 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
177/*	  0000000000111111111122222222223333333333444444444455555555556666 */
178/*	  0123456789012345678901234567890123456789012345678901234567890123 */
179
180static u_char m_sbox[4][4096];
181static uint32_t psbox[4][256];
182static uint32_t ip_maskl[8][256], ip_maskr[8][256];
183static uint32_t fp_maskl[8][256], fp_maskr[8][256];
184static uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128];
185static uint32_t comp_maskl[8][128], comp_maskr[8][128];
186
187static inline int
188ascii_to_bin(char ch)
189{
190	signed char sch = ch;
191	int retval;
192
193	retval = sch - '.';
194	if (sch >= 'A') {
195		retval = sch - ('A' - 12);
196		if (sch >= 'a')
197			retval = sch - ('a' - 38);
198	}
199	retval &= 0x3f;
200
201	return(retval);
202}
203
204/*
205 * When we choose to "support" invalid salts, nevertheless disallow those
206 * containing characters that would violate the passwd file format.
207 */
208static inline int
209ascii_is_unsafe(char ch)
210{
211	return !ch || ch == '\n' || ch == ':';
212}
213
214void
215_crypt_extended_init(void)
216{
217	int i, j, b, k, inbit, obit;
218	uint32_t *p, *il, *ir, *fl, *fr;
219	uint32_t *bits28, *bits24;
220	u_char inv_key_perm[64];
221	u_char inv_comp_perm[56];
222	u_char init_perm[64], final_perm[64];
223	u_char u_sbox[8][64];
224	u_char un_pbox[32];
225
226	bits24 = (bits28 = bits32 + 4) + 4;
227
228	/*
229	 * Invert the S-boxes, reordering the input bits.
230	 */
231	for (i = 0; i < 8; i++)
232		for (j = 0; j < 64; j++) {
233			b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
234			u_sbox[i][j] = sbox[i][b];
235		}
236
237	/*
238	 * Convert the inverted S-boxes into 4 arrays of 8 bits.
239	 * Each will handle 12 bits of the S-box input.
240	 */
241	for (b = 0; b < 4; b++)
242		for (i = 0; i < 64; i++)
243			for (j = 0; j < 64; j++)
244				m_sbox[b][(i << 6) | j] =
245					(u_sbox[(b << 1)][i] << 4) |
246					u_sbox[(b << 1) + 1][j];
247
248	/*
249	 * Set up the initial & final permutations into a useful form, and
250	 * initialise the inverted key permutation.
251	 */
252	for (i = 0; i < 64; i++) {
253		init_perm[final_perm[i] = IP[i] - 1] = i;
254		inv_key_perm[i] = 255;
255	}
256
257	/*
258	 * Invert the key permutation and initialise the inverted key
259	 * compression permutation.
260	 */
261	for (i = 0; i < 56; i++) {
262		inv_key_perm[key_perm[i] - 1] = i;
263		inv_comp_perm[i] = 255;
264	}
265
266	/*
267	 * Invert the key compression permutation.
268	 */
269	for (i = 0; i < 48; i++) {
270		inv_comp_perm[comp_perm[i] - 1] = i;
271	}
272
273	/*
274	 * Set up the OR-mask arrays for the initial and final permutations,
275	 * and for the key initial and compression permutations.
276	 */
277	for (k = 0; k < 8; k++) {
278		for (i = 0; i < 256; i++) {
279			*(il = &ip_maskl[k][i]) = 0;
280			*(ir = &ip_maskr[k][i]) = 0;
281			*(fl = &fp_maskl[k][i]) = 0;
282			*(fr = &fp_maskr[k][i]) = 0;
283			for (j = 0; j < 8; j++) {
284				inbit = 8 * k + j;
285				if (i & bits8[j]) {
286					if ((obit = init_perm[inbit]) < 32)
287						*il |= bits32[obit];
288					else
289						*ir |= bits32[obit-32];
290					if ((obit = final_perm[inbit]) < 32)
291						*fl |= bits32[obit];
292					else
293						*fr |= bits32[obit - 32];
294				}
295			}
296		}
297		for (i = 0; i < 128; i++) {
298			*(il = &key_perm_maskl[k][i]) = 0;
299			*(ir = &key_perm_maskr[k][i]) = 0;
300			for (j = 0; j < 7; j++) {
301				inbit = 8 * k + j;
302				if (i & bits8[j + 1]) {
303					if ((obit = inv_key_perm[inbit]) == 255)
304						continue;
305					if (obit < 28)
306						*il |= bits28[obit];
307					else
308						*ir |= bits28[obit - 28];
309				}
310			}
311			*(il = &comp_maskl[k][i]) = 0;
312			*(ir = &comp_maskr[k][i]) = 0;
313			for (j = 0; j < 7; j++) {
314				inbit = 7 * k + j;
315				if (i & bits8[j + 1]) {
316					if ((obit=inv_comp_perm[inbit]) == 255)
317						continue;
318					if (obit < 24)
319						*il |= bits24[obit];
320					else
321						*ir |= bits24[obit - 24];
322				}
323			}
324		}
325	}
326
327	/*
328	 * Invert the P-box permutation, and convert into OR-masks for
329	 * handling the output of the S-box arrays setup above.
330	 */
331	for (i = 0; i < 32; i++)
332		un_pbox[pbox[i] - 1] = i;
333
334	for (b = 0; b < 4; b++)
335		for (i = 0; i < 256; i++) {
336			*(p = &psbox[b][i]) = 0;
337			for (j = 0; j < 8; j++) {
338				if (i & bits8[j])
339					*p |= bits32[un_pbox[8 * b + j]];
340			}
341		}
342}
343
344static void
345des_init_local(struct php_crypt_extended_data *data)
346{
347	data->old_rawkey0 = data->old_rawkey1 = 0;
348	data->saltbits = 0;
349	data->old_salt = 0;
350
351	data->initialized = 1;
352}
353
354static void
355setup_salt(uint32_t salt, struct php_crypt_extended_data *data)
356{
357	uint32_t	obit, saltbit, saltbits;
358	int	i;
359
360	if (salt == data->old_salt)
361		return;
362	data->old_salt = salt;
363
364	saltbits = 0;
365	saltbit = 1;
366	obit = 0x800000;
367	for (i = 0; i < 24; i++) {
368		if (salt & saltbit)
369			saltbits |= obit;
370		saltbit <<= 1;
371		obit >>= 1;
372	}
373	data->saltbits = saltbits;
374}
375
376static int
377des_setkey(const char *key, struct php_crypt_extended_data *data)
378{
379	uint32_t	k0, k1, rawkey0, rawkey1;
380	int	shifts, round;
381
382	rawkey0 =
383		(uint32_t)(u_char)key[3] |
384		((uint32_t)(u_char)key[2] << 8) |
385		((uint32_t)(u_char)key[1] << 16) |
386		((uint32_t)(u_char)key[0] << 24);
387	rawkey1 =
388		(uint32_t)(u_char)key[7] |
389		((uint32_t)(u_char)key[6] << 8) |
390		((uint32_t)(u_char)key[5] << 16) |
391		((uint32_t)(u_char)key[4] << 24);
392
393	if ((rawkey0 | rawkey1)
394	    && rawkey0 == data->old_rawkey0
395	    && rawkey1 == data->old_rawkey1) {
396		/*
397		 * Already setup for this key.
398		 * This optimisation fails on a zero key (which is weak and
399		 * has bad parity anyway) in order to simplify the starting
400		 * conditions.
401		 */
402		return(0);
403	}
404	data->old_rawkey0 = rawkey0;
405	data->old_rawkey1 = rawkey1;
406
407	/*
408	 *	Do key permutation and split into two 28-bit subkeys.
409	 */
410	k0 = key_perm_maskl[0][rawkey0 >> 25]
411	   | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
412	   | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
413	   | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
414	   | key_perm_maskl[4][rawkey1 >> 25]
415	   | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
416	   | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
417	   | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
418	k1 = key_perm_maskr[0][rawkey0 >> 25]
419	   | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
420	   | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
421	   | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
422	   | key_perm_maskr[4][rawkey1 >> 25]
423	   | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
424	   | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
425	   | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
426	/*
427	 *	Rotate subkeys and do compression permutation.
428	 */
429	shifts = 0;
430	for (round = 0; round < 16; round++) {
431		uint32_t	t0, t1;
432
433		shifts += key_shifts[round];
434
435		t0 = (k0 << shifts) | (k0 >> (28 - shifts));
436		t1 = (k1 << shifts) | (k1 >> (28 - shifts));
437
438		data->de_keysl[15 - round] =
439		data->en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
440				| comp_maskl[1][(t0 >> 14) & 0x7f]
441				| comp_maskl[2][(t0 >> 7) & 0x7f]
442				| comp_maskl[3][t0 & 0x7f]
443				| comp_maskl[4][(t1 >> 21) & 0x7f]
444				| comp_maskl[5][(t1 >> 14) & 0x7f]
445				| comp_maskl[6][(t1 >> 7) & 0x7f]
446				| comp_maskl[7][t1 & 0x7f];
447
448		data->de_keysr[15 - round] =
449		data->en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
450				| comp_maskr[1][(t0 >> 14) & 0x7f]
451				| comp_maskr[2][(t0 >> 7) & 0x7f]
452				| comp_maskr[3][t0 & 0x7f]
453				| comp_maskr[4][(t1 >> 21) & 0x7f]
454				| comp_maskr[5][(t1 >> 14) & 0x7f]
455				| comp_maskr[6][(t1 >> 7) & 0x7f]
456				| comp_maskr[7][t1 & 0x7f];
457	}
458	return(0);
459}
460
461static int
462do_des(uint32_t l_in, uint32_t r_in, uint32_t *l_out, uint32_t *r_out,
463	int count, struct php_crypt_extended_data *data)
464{
465	/*
466	 *	l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
467	 */
468	uint32_t	l, r, *kl, *kr, *kl1, *kr1;
469	uint32_t	f, r48l, r48r, saltbits;
470	int	round;
471
472	if (count == 0) {
473		return(1);
474	} else if (count > 0) {
475		/*
476		 * Encrypting
477		 */
478		kl1 = data->en_keysl;
479		kr1 = data->en_keysr;
480	} else {
481		/*
482		 * Decrypting
483		 */
484		count = -count;
485		kl1 = data->de_keysl;
486		kr1 = data->de_keysr;
487	}
488
489	/*
490	 *	Do initial permutation (IP).
491	 */
492	l = ip_maskl[0][l_in >> 24]
493	  | ip_maskl[1][(l_in >> 16) & 0xff]
494	  | ip_maskl[2][(l_in >> 8) & 0xff]
495	  | ip_maskl[3][l_in & 0xff]
496	  | ip_maskl[4][r_in >> 24]
497	  | ip_maskl[5][(r_in >> 16) & 0xff]
498	  | ip_maskl[6][(r_in >> 8) & 0xff]
499	  | ip_maskl[7][r_in & 0xff];
500	r = ip_maskr[0][l_in >> 24]
501	  | ip_maskr[1][(l_in >> 16) & 0xff]
502	  | ip_maskr[2][(l_in >> 8) & 0xff]
503	  | ip_maskr[3][l_in & 0xff]
504	  | ip_maskr[4][r_in >> 24]
505	  | ip_maskr[5][(r_in >> 16) & 0xff]
506	  | ip_maskr[6][(r_in >> 8) & 0xff]
507	  | ip_maskr[7][r_in & 0xff];
508
509	saltbits = data->saltbits;
510	while (count--) {
511		/*
512		 * Do each round.
513		 */
514		kl = kl1;
515		kr = kr1;
516		round = 16;
517		while (round--) {
518			/*
519			 * Expand R to 48 bits (simulate the E-box).
520			 */
521			r48l	= ((r & 0x00000001) << 23)
522				| ((r & 0xf8000000) >> 9)
523				| ((r & 0x1f800000) >> 11)
524				| ((r & 0x01f80000) >> 13)
525				| ((r & 0x001f8000) >> 15);
526
527			r48r	= ((r & 0x0001f800) << 7)
528				| ((r & 0x00001f80) << 5)
529				| ((r & 0x000001f8) << 3)
530				| ((r & 0x0000001f) << 1)
531				| ((r & 0x80000000) >> 31);
532			/*
533			 * Do salting for crypt() and friends, and
534			 * XOR with the permuted key.
535			 */
536			f = (r48l ^ r48r) & saltbits;
537			r48l ^= f ^ *kl++;
538			r48r ^= f ^ *kr++;
539			/*
540			 * Do sbox lookups (which shrink it back to 32 bits)
541			 * and do the pbox permutation at the same time.
542			 */
543			f = psbox[0][m_sbox[0][r48l >> 12]]
544			  | psbox[1][m_sbox[1][r48l & 0xfff]]
545			  | psbox[2][m_sbox[2][r48r >> 12]]
546			  | psbox[3][m_sbox[3][r48r & 0xfff]];
547			/*
548			 * Now that we've permuted things, complete f().
549			 */
550			f ^= l;
551			l = r;
552			r = f;
553		}
554		r = l;
555		l = f;
556	}
557	/*
558	 * Do final permutation (inverse of IP).
559	 */
560	*l_out	= fp_maskl[0][l >> 24]
561		| fp_maskl[1][(l >> 16) & 0xff]
562		| fp_maskl[2][(l >> 8) & 0xff]
563		| fp_maskl[3][l & 0xff]
564		| fp_maskl[4][r >> 24]
565		| fp_maskl[5][(r >> 16) & 0xff]
566		| fp_maskl[6][(r >> 8) & 0xff]
567		| fp_maskl[7][r & 0xff];
568	*r_out	= fp_maskr[0][l >> 24]
569		| fp_maskr[1][(l >> 16) & 0xff]
570		| fp_maskr[2][(l >> 8) & 0xff]
571		| fp_maskr[3][l & 0xff]
572		| fp_maskr[4][r >> 24]
573		| fp_maskr[5][(r >> 16) & 0xff]
574		| fp_maskr[6][(r >> 8) & 0xff]
575		| fp_maskr[7][r & 0xff];
576	return(0);
577}
578
579static int
580des_cipher(const char *in, char *out, uint32_t salt, int count,
581	struct php_crypt_extended_data *data)
582{
583	uint32_t	l_out = 0, r_out = 0, rawl, rawr;
584	int	retval;
585
586	setup_salt(salt, data);
587
588	rawl =
589		(uint32_t)(u_char)in[3] |
590		((uint32_t)(u_char)in[2] << 8) |
591		((uint32_t)(u_char)in[1] << 16) |
592		((uint32_t)(u_char)in[0] << 24);
593	rawr =
594		(uint32_t)(u_char)in[7] |
595		((uint32_t)(u_char)in[6] << 8) |
596		((uint32_t)(u_char)in[5] << 16) |
597		((uint32_t)(u_char)in[4] << 24);
598
599	retval = do_des(rawl, rawr, &l_out, &r_out, count, data);
600
601	out[0] = l_out >> 24;
602	out[1] = l_out >> 16;
603	out[2] = l_out >> 8;
604	out[3] = l_out;
605	out[4] = r_out >> 24;
606	out[5] = r_out >> 16;
607	out[6] = r_out >> 8;
608	out[7] = r_out;
609
610	return(retval);
611}
612
613char *
614_crypt_extended_r(const char *key, const char *setting,
615	struct php_crypt_extended_data *data)
616{
617	int		i;
618	uint32_t	count, salt, l, r0, r1, keybuf[2];
619	u_char		*p, *q;
620
621	if (!data->initialized)
622		des_init_local(data);
623
624	/*
625	 * Copy the key, shifting each character up by one bit
626	 * and padding with zeros.
627	 */
628	q = (u_char *) keybuf;
629	while (q - (u_char *) keybuf < sizeof(keybuf)) {
630		*q++ = *key << 1;
631		if (*key)
632			key++;
633	}
634	if (des_setkey((char *) keybuf, data))
635		return(NULL);
636
637	if (*setting == _PASSWORD_EFMT1) {
638		/*
639		 * "new"-style:
640		 *	setting - underscore, 4 chars of count, 4 chars of salt
641		 *	key - unlimited characters
642		 */
643		for (i = 1, count = 0; i < 5; i++) {
644			int value = ascii_to_bin(setting[i]);
645			if (ascii64[value] != setting[i])
646				return(NULL);
647			count |= value << (i - 1) * 6;
648		}
649		if (!count)
650			return(NULL);
651
652		for (i = 5, salt = 0; i < 9; i++) {
653			int value = ascii_to_bin(setting[i]);
654			if (ascii64[value] != setting[i])
655				return(NULL);
656			salt |= value << (i - 5) * 6;
657		}
658
659		while (*key) {
660			/*
661			 * Encrypt the key with itself.
662			 */
663			if (des_cipher((char *) keybuf, (char *) keybuf,
664			    0, 1, data))
665				return(NULL);
666			/*
667			 * And XOR with the next 8 characters of the key.
668			 */
669			q = (u_char *) keybuf;
670			while (q - (u_char *) keybuf < sizeof(keybuf) && *key)
671				*q++ ^= *key++ << 1;
672
673			if (des_setkey((char *) keybuf, data))
674				return(NULL);
675		}
676		memcpy(data->output, setting, 9);
677		data->output[9] = '\0';
678		p = (u_char *) data->output + 9;
679	} else {
680		/*
681		 * "old"-style:
682		 *	setting - 2 chars of salt
683		 *	key - up to 8 characters
684		 */
685		count = 25;
686
687		if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
688			return(NULL);
689
690		salt = (ascii_to_bin(setting[1]) << 6)
691		     |  ascii_to_bin(setting[0]);
692
693		data->output[0] = setting[0];
694		data->output[1] = setting[1];
695		p = (u_char *) data->output + 2;
696	}
697	setup_salt(salt, data);
698	/*
699	 * Do it.
700	 */
701	if (do_des(0, 0, &r0, &r1, count, data))
702		return(NULL);
703	/*
704	 * Now encode the result...
705	 */
706	l = (r0 >> 8);
707	*p++ = ascii64[(l >> 18) & 0x3f];
708	*p++ = ascii64[(l >> 12) & 0x3f];
709	*p++ = ascii64[(l >> 6) & 0x3f];
710	*p++ = ascii64[l & 0x3f];
711
712	l = (r0 << 16) | ((r1 >> 16) & 0xffff);
713	*p++ = ascii64[(l >> 18) & 0x3f];
714	*p++ = ascii64[(l >> 12) & 0x3f];
715	*p++ = ascii64[(l >> 6) & 0x3f];
716	*p++ = ascii64[l & 0x3f];
717
718	l = r1 << 2;
719	*p++ = ascii64[(l >> 12) & 0x3f];
720	*p++ = ascii64[(l >> 6) & 0x3f];
721	*p++ = ascii64[l & 0x3f];
722	*p = 0;
723
724	return(data->output);
725}
726
727#ifdef TEST
728static char *
729_crypt_extended(const char *key, const char *setting)
730{
731	static int initialized = 0;
732	static struct php_crypt_extended_data data;
733
734	if (!initialized) {
735		_crypt_extended_init();
736		initialized = 1;
737		data.initialized = 0;
738	}
739	return _crypt_extended_r(key, setting, &data);
740}
741
742#define crypt _crypt_extended
743
744static struct {
745	char *hash;
746	char *pw;
747} tests[] = {
748/* "new"-style */
749	{"_J9..CCCCXBrJUJV154M", "U*U*U*U*"},
750	{"_J9..CCCCXUhOBTXzaiE", "U*U***U"},
751	{"_J9..CCCC4gQ.mB/PffM", "U*U***U*"},
752	{"_J9..XXXXvlzQGqpPPdk", "*U*U*U*U"},
753	{"_J9..XXXXsqM/YSSP..Y", "*U*U*U*U*"},
754	{"_J9..XXXXVL7qJCnku0I", "*U*U*U*U*U*U*U*U"},
755	{"_J9..XXXXAj8cFbP5scI", "*U*U*U*U*U*U*U*U*"},
756	{"_J9..SDizh.vll5VED9g", "ab1234567"},
757	{"_J9..SDizRjWQ/zePPHc", "cr1234567"},
758	{"_J9..SDizxmRI1GjnQuE", "zxyDPWgydbQjgq"},
759	{"_K9..SaltNrQgIYUAeoY", "726 even"},
760	{"_J9..SDSD5YGyRCr4W4c", ""},
761/* "old"-style, valid salts */
762	{"CCNf8Sbh3HDfQ", "U*U*U*U*"},
763	{"CCX.K.MFy4Ois", "U*U***U"},
764	{"CC4rMpbg9AMZ.", "U*U***U*"},
765	{"XXxzOu6maQKqQ", "*U*U*U*U"},
766	{"SDbsugeBiC58A", ""},
767	{"./xZjzHv5vzVE", "password"},
768	{"0A2hXM1rXbYgo", "password"},
769	{"A9RXdR23Y.cY6", "password"},
770	{"ZziFATVXHo2.6", "password"},
771	{"zZDDIZ0NOlPzw", "password"},
772/* "old"-style, "reasonable" invalid salts, UFC-crypt behavior expected */
773	{"\001\002wyd0KZo65Jo", "password"},
774	{"a_C10Dk/ExaG.", "password"},
775	{"~\377.5OTsRVjwLo", "password"},
776/* The below are erroneous inputs, so NULL return is expected/required */
777	{"", ""}, /* no salt */
778	{" ", ""}, /* setting string is too short */
779	{"a:", ""}, /* unsafe character */
780	{"\na", ""}, /* unsafe character */
781	{"_/......", ""}, /* setting string is too short for its type */
782	{"_........", ""}, /* zero iteration count */
783	{"_/!......", ""}, /* invalid character in count */
784	{"_/......!", ""}, /* invalid character in salt */
785	{NULL}
786};
787
788int main(void)
789{
790	int i;
791
792	for (i = 0; tests[i].hash; i++) {
793		char *hash = crypt(tests[i].pw, tests[i].hash);
794		if (!hash && strlen(tests[i].hash) < 13)
795			continue; /* expected failure */
796		if (!strcmp(hash, tests[i].hash))
797			continue; /* expected success */
798		puts("FAILED");
799		return 1;
800	}
801
802	puts("PASSED");
803
804	return 0;
805}
806#endif
807