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