xref: /PHP-7.3/ext/standard/crypt_freesec.c (revision 8d3f8ca1)
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 /*	  0000000000111111111122222222223333333333444444444455555555556666 */
174 /*	  0123456789012345678901234567890123456789012345678901234567890123 */
175 
176 static u_char m_sbox[4][4096];
177 static uint32_t psbox[4][256];
178 static uint32_t ip_maskl[8][256], ip_maskr[8][256];
179 static uint32_t fp_maskl[8][256], fp_maskr[8][256];
180 static uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128];
181 static uint32_t comp_maskl[8][128], comp_maskr[8][128];
182 
183 static inline int
ascii_to_bin(char ch)184 ascii_to_bin(char ch)
185 {
186 	signed char sch = ch;
187 	int retval;
188 
189 	retval = sch - '.';
190 	if (sch >= 'A') {
191 		retval = sch - ('A' - 12);
192 		if (sch >= 'a')
193 			retval = sch - ('a' - 38);
194 	}
195 	retval &= 0x3f;
196 
197 	return(retval);
198 }
199 
200 /*
201  * When we choose to "support" invalid salts, nevertheless disallow those
202  * containing characters that would violate the passwd file format.
203  */
204 static inline int
ascii_is_unsafe(char ch)205 ascii_is_unsafe(char ch)
206 {
207 	return !ch || ch == '\n' || ch == ':';
208 }
209 
210 void
_crypt_extended_init(void)211 _crypt_extended_init(void)
212 {
213 	int i, j, b, k, inbit, obit;
214 	uint32_t *p, *il, *ir, *fl, *fr;
215 	const uint32_t *bits28, *bits24;
216 	u_char inv_key_perm[64];
217 	u_char inv_comp_perm[56];
218 	u_char init_perm[64], final_perm[64];
219 	u_char u_sbox[8][64];
220 	u_char un_pbox[32];
221 
222 	bits24 = (bits28 = bits32 + 4) + 4;
223 
224 	/*
225 	 * Invert the S-boxes, reordering the input bits.
226 	 */
227 	for (i = 0; i < 8; i++)
228 		for (j = 0; j < 64; j++) {
229 			b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
230 			u_sbox[i][j] = sbox[i][b];
231 		}
232 
233 	/*
234 	 * Convert the inverted S-boxes into 4 arrays of 8 bits.
235 	 * Each will handle 12 bits of the S-box input.
236 	 */
237 	for (b = 0; b < 4; b++)
238 		for (i = 0; i < 64; i++)
239 			for (j = 0; j < 64; j++)
240 				m_sbox[b][(i << 6) | j] =
241 					(u_sbox[(b << 1)][i] << 4) |
242 					u_sbox[(b << 1) + 1][j];
243 
244 	/*
245 	 * Set up the initial & final permutations into a useful form, and
246 	 * initialise the inverted key permutation.
247 	 */
248 	for (i = 0; i < 64; i++) {
249 		init_perm[final_perm[i] = IP[i] - 1] = i;
250 		inv_key_perm[i] = 255;
251 	}
252 
253 	/*
254 	 * Invert the key permutation and initialise the inverted key
255 	 * compression permutation.
256 	 */
257 	for (i = 0; i < 56; i++) {
258 		inv_key_perm[key_perm[i] - 1] = i;
259 		inv_comp_perm[i] = 255;
260 	}
261 
262 	/*
263 	 * Invert the key compression permutation.
264 	 */
265 	for (i = 0; i < 48; i++) {
266 		inv_comp_perm[comp_perm[i] - 1] = i;
267 	}
268 
269 	/*
270 	 * Set up the OR-mask arrays for the initial and final permutations,
271 	 * and for the key initial and compression permutations.
272 	 */
273 	for (k = 0; k < 8; k++) {
274 		for (i = 0; i < 256; i++) {
275 			*(il = &ip_maskl[k][i]) = 0;
276 			*(ir = &ip_maskr[k][i]) = 0;
277 			*(fl = &fp_maskl[k][i]) = 0;
278 			*(fr = &fp_maskr[k][i]) = 0;
279 			for (j = 0; j < 8; j++) {
280 				inbit = 8 * k + j;
281 				if (i & bits8[j]) {
282 					if ((obit = init_perm[inbit]) < 32)
283 						*il |= bits32[obit];
284 					else
285 						*ir |= bits32[obit-32];
286 					if ((obit = final_perm[inbit]) < 32)
287 						*fl |= bits32[obit];
288 					else
289 						*fr |= bits32[obit - 32];
290 				}
291 			}
292 		}
293 		for (i = 0; i < 128; i++) {
294 			*(il = &key_perm_maskl[k][i]) = 0;
295 			*(ir = &key_perm_maskr[k][i]) = 0;
296 			for (j = 0; j < 7; j++) {
297 				inbit = 8 * k + j;
298 				if (i & bits8[j + 1]) {
299 					if ((obit = inv_key_perm[inbit]) == 255)
300 						continue;
301 					if (obit < 28)
302 						*il |= bits28[obit];
303 					else
304 						*ir |= bits28[obit - 28];
305 				}
306 			}
307 			*(il = &comp_maskl[k][i]) = 0;
308 			*(ir = &comp_maskr[k][i]) = 0;
309 			for (j = 0; j < 7; j++) {
310 				inbit = 7 * k + j;
311 				if (i & bits8[j + 1]) {
312 					if ((obit=inv_comp_perm[inbit]) == 255)
313 						continue;
314 					if (obit < 24)
315 						*il |= bits24[obit];
316 					else
317 						*ir |= bits24[obit - 24];
318 				}
319 			}
320 		}
321 	}
322 
323 	/*
324 	 * Invert the P-box permutation, and convert into OR-masks for
325 	 * handling the output of the S-box arrays setup above.
326 	 */
327 	for (i = 0; i < 32; i++)
328 		un_pbox[pbox[i] - 1] = i;
329 
330 	for (b = 0; b < 4; b++)
331 		for (i = 0; i < 256; i++) {
332 			*(p = &psbox[b][i]) = 0;
333 			for (j = 0; j < 8; j++) {
334 				if (i & bits8[j])
335 					*p |= bits32[un_pbox[8 * b + j]];
336 			}
337 		}
338 }
339 
340 static void
des_init_local(struct php_crypt_extended_data * data)341 des_init_local(struct php_crypt_extended_data *data)
342 {
343 	data->old_rawkey0 = data->old_rawkey1 = 0;
344 	data->saltbits = 0;
345 	data->old_salt = 0;
346 
347 	data->initialized = 1;
348 }
349 
350 static void
setup_salt(uint32_t salt,struct php_crypt_extended_data * data)351 setup_salt(uint32_t salt, struct php_crypt_extended_data *data)
352 {
353 	uint32_t	obit, saltbit, saltbits;
354 	int	i;
355 
356 	if (salt == data->old_salt)
357 		return;
358 	data->old_salt = salt;
359 
360 	saltbits = 0;
361 	saltbit = 1;
362 	obit = 0x800000;
363 	for (i = 0; i < 24; i++) {
364 		if (salt & saltbit)
365 			saltbits |= obit;
366 		saltbit <<= 1;
367 		obit >>= 1;
368 	}
369 	data->saltbits = saltbits;
370 }
371 
372 static int
des_setkey(const char * key,struct php_crypt_extended_data * data)373 des_setkey(const char *key, struct php_crypt_extended_data *data)
374 {
375 	uint32_t	k0, k1, rawkey0, rawkey1;
376 	int	shifts, round;
377 
378 	rawkey0 =
379 		(uint32_t)(u_char)key[3] |
380 		((uint32_t)(u_char)key[2] << 8) |
381 		((uint32_t)(u_char)key[1] << 16) |
382 		((uint32_t)(u_char)key[0] << 24);
383 	rawkey1 =
384 		(uint32_t)(u_char)key[7] |
385 		((uint32_t)(u_char)key[6] << 8) |
386 		((uint32_t)(u_char)key[5] << 16) |
387 		((uint32_t)(u_char)key[4] << 24);
388 
389 	if ((rawkey0 | rawkey1)
390 	    && rawkey0 == data->old_rawkey0
391 	    && rawkey1 == data->old_rawkey1) {
392 		/*
393 		 * Already setup for this key.
394 		 * This optimisation fails on a zero key (which is weak and
395 		 * has bad parity anyway) in order to simplify the starting
396 		 * conditions.
397 		 */
398 		return(0);
399 	}
400 	data->old_rawkey0 = rawkey0;
401 	data->old_rawkey1 = rawkey1;
402 
403 	/*
404 	 *	Do key permutation and split into two 28-bit subkeys.
405 	 */
406 	k0 = key_perm_maskl[0][rawkey0 >> 25]
407 	   | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
408 	   | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
409 	   | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
410 	   | key_perm_maskl[4][rawkey1 >> 25]
411 	   | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
412 	   | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
413 	   | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
414 	k1 = key_perm_maskr[0][rawkey0 >> 25]
415 	   | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
416 	   | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
417 	   | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
418 	   | key_perm_maskr[4][rawkey1 >> 25]
419 	   | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
420 	   | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
421 	   | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
422 	/*
423 	 *	Rotate subkeys and do compression permutation.
424 	 */
425 	shifts = 0;
426 	for (round = 0; round < 16; round++) {
427 		uint32_t	t0, t1;
428 
429 		shifts += key_shifts[round];
430 
431 		t0 = (k0 << shifts) | (k0 >> (28 - shifts));
432 		t1 = (k1 << shifts) | (k1 >> (28 - shifts));
433 
434 		data->de_keysl[15 - round] =
435 		data->en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
436 				| comp_maskl[1][(t0 >> 14) & 0x7f]
437 				| comp_maskl[2][(t0 >> 7) & 0x7f]
438 				| comp_maskl[3][t0 & 0x7f]
439 				| comp_maskl[4][(t1 >> 21) & 0x7f]
440 				| comp_maskl[5][(t1 >> 14) & 0x7f]
441 				| comp_maskl[6][(t1 >> 7) & 0x7f]
442 				| comp_maskl[7][t1 & 0x7f];
443 
444 		data->de_keysr[15 - round] =
445 		data->en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
446 				| comp_maskr[1][(t0 >> 14) & 0x7f]
447 				| comp_maskr[2][(t0 >> 7) & 0x7f]
448 				| comp_maskr[3][t0 & 0x7f]
449 				| comp_maskr[4][(t1 >> 21) & 0x7f]
450 				| comp_maskr[5][(t1 >> 14) & 0x7f]
451 				| comp_maskr[6][(t1 >> 7) & 0x7f]
452 				| comp_maskr[7][t1 & 0x7f];
453 	}
454 	return(0);
455 }
456 
457 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)458 do_des(uint32_t l_in, uint32_t r_in, uint32_t *l_out, uint32_t *r_out,
459 	int count, struct php_crypt_extended_data *data)
460 {
461 	/*
462 	 *	l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
463 	 */
464 	uint32_t	l, r, *kl, *kr, *kl1, *kr1;
465 	uint32_t	f, r48l, r48r, saltbits;
466 	int	round;
467 
468 	if (count == 0) {
469 		return(1);
470 	} else if (count > 0) {
471 		/*
472 		 * Encrypting
473 		 */
474 		kl1 = data->en_keysl;
475 		kr1 = data->en_keysr;
476 	} else {
477 		/*
478 		 * Decrypting
479 		 */
480 		count = -count;
481 		kl1 = data->de_keysl;
482 		kr1 = data->de_keysr;
483 	}
484 
485 	/*
486 	 *	Do initial permutation (IP).
487 	 */
488 	l = ip_maskl[0][l_in >> 24]
489 	  | ip_maskl[1][(l_in >> 16) & 0xff]
490 	  | ip_maskl[2][(l_in >> 8) & 0xff]
491 	  | ip_maskl[3][l_in & 0xff]
492 	  | ip_maskl[4][r_in >> 24]
493 	  | ip_maskl[5][(r_in >> 16) & 0xff]
494 	  | ip_maskl[6][(r_in >> 8) & 0xff]
495 	  | ip_maskl[7][r_in & 0xff];
496 	r = ip_maskr[0][l_in >> 24]
497 	  | ip_maskr[1][(l_in >> 16) & 0xff]
498 	  | ip_maskr[2][(l_in >> 8) & 0xff]
499 	  | ip_maskr[3][l_in & 0xff]
500 	  | ip_maskr[4][r_in >> 24]
501 	  | ip_maskr[5][(r_in >> 16) & 0xff]
502 	  | ip_maskr[6][(r_in >> 8) & 0xff]
503 	  | ip_maskr[7][r_in & 0xff];
504 
505 	saltbits = data->saltbits;
506 	while (count--) {
507 		/*
508 		 * Do each round.
509 		 */
510 		kl = kl1;
511 		kr = kr1;
512 		round = 16;
513 		while (round--) {
514 			/*
515 			 * Expand R to 48 bits (simulate the E-box).
516 			 */
517 			r48l	= ((r & 0x00000001) << 23)
518 				| ((r & 0xf8000000) >> 9)
519 				| ((r & 0x1f800000) >> 11)
520 				| ((r & 0x01f80000) >> 13)
521 				| ((r & 0x001f8000) >> 15);
522 
523 			r48r	= ((r & 0x0001f800) << 7)
524 				| ((r & 0x00001f80) << 5)
525 				| ((r & 0x000001f8) << 3)
526 				| ((r & 0x0000001f) << 1)
527 				| ((r & 0x80000000) >> 31);
528 			/*
529 			 * Do salting for crypt() and friends, and
530 			 * XOR with the permuted key.
531 			 */
532 			f = (r48l ^ r48r) & saltbits;
533 			r48l ^= f ^ *kl++;
534 			r48r ^= f ^ *kr++;
535 			/*
536 			 * Do sbox lookups (which shrink it back to 32 bits)
537 			 * and do the pbox permutation at the same time.
538 			 */
539 			f = psbox[0][m_sbox[0][r48l >> 12]]
540 			  | psbox[1][m_sbox[1][r48l & 0xfff]]
541 			  | psbox[2][m_sbox[2][r48r >> 12]]
542 			  | psbox[3][m_sbox[3][r48r & 0xfff]];
543 			/*
544 			 * Now that we've permuted things, complete f().
545 			 */
546 			f ^= l;
547 			l = r;
548 			r = f;
549 		}
550 		r = l;
551 		l = f;
552 	}
553 	/*
554 	 * Do final permutation (inverse of IP).
555 	 */
556 	*l_out	= fp_maskl[0][l >> 24]
557 		| fp_maskl[1][(l >> 16) & 0xff]
558 		| fp_maskl[2][(l >> 8) & 0xff]
559 		| fp_maskl[3][l & 0xff]
560 		| fp_maskl[4][r >> 24]
561 		| fp_maskl[5][(r >> 16) & 0xff]
562 		| fp_maskl[6][(r >> 8) & 0xff]
563 		| fp_maskl[7][r & 0xff];
564 	*r_out	= fp_maskr[0][l >> 24]
565 		| fp_maskr[1][(l >> 16) & 0xff]
566 		| fp_maskr[2][(l >> 8) & 0xff]
567 		| fp_maskr[3][l & 0xff]
568 		| fp_maskr[4][r >> 24]
569 		| fp_maskr[5][(r >> 16) & 0xff]
570 		| fp_maskr[6][(r >> 8) & 0xff]
571 		| fp_maskr[7][r & 0xff];
572 	return(0);
573 }
574 
575 static int
des_cipher(const char * in,char * out,uint32_t salt,int count,struct php_crypt_extended_data * data)576 des_cipher(const char *in, char *out, uint32_t salt, int count,
577 	struct php_crypt_extended_data *data)
578 {
579 	uint32_t	l_out = 0, r_out = 0, rawl, rawr;
580 	int	retval;
581 
582 	setup_salt(salt, data);
583 
584 	rawl =
585 		(uint32_t)(u_char)in[3] |
586 		((uint32_t)(u_char)in[2] << 8) |
587 		((uint32_t)(u_char)in[1] << 16) |
588 		((uint32_t)(u_char)in[0] << 24);
589 	rawr =
590 		(uint32_t)(u_char)in[7] |
591 		((uint32_t)(u_char)in[6] << 8) |
592 		((uint32_t)(u_char)in[5] << 16) |
593 		((uint32_t)(u_char)in[4] << 24);
594 
595 	retval = do_des(rawl, rawr, &l_out, &r_out, count, data);
596 
597 	out[0] = l_out >> 24;
598 	out[1] = l_out >> 16;
599 	out[2] = l_out >> 8;
600 	out[3] = l_out;
601 	out[4] = r_out >> 24;
602 	out[5] = r_out >> 16;
603 	out[6] = r_out >> 8;
604 	out[7] = r_out;
605 
606 	return(retval);
607 }
608 
609 char *
_crypt_extended_r(const char * key,const char * setting,struct php_crypt_extended_data * data)610 _crypt_extended_r(const char *key, const char *setting,
611 	struct php_crypt_extended_data *data)
612 {
613 	int		i;
614 	uint32_t	count, salt, l, r0, r1, keybuf[2];
615 	u_char		*p, *q;
616 
617 	if (!data->initialized)
618 		des_init_local(data);
619 
620 	/*
621 	 * Copy the key, shifting each character up by one bit
622 	 * and padding with zeros.
623 	 */
624 	q = (u_char *) keybuf;
625 	while ((size_t)(q - (u_char *) keybuf) < sizeof(keybuf)) {
626 		*q++ = *key << 1;
627 		if (*key)
628 			key++;
629 	}
630 	if (des_setkey((char *) keybuf, data))
631 		return(NULL);
632 
633 	if (*setting == _PASSWORD_EFMT1) {
634 		/*
635 		 * "new"-style:
636 		 *	setting - underscore, 4 chars of count, 4 chars of salt
637 		 *	key - unlimited characters
638 		 */
639 		for (i = 1, count = 0; i < 5; i++) {
640 			int value = ascii_to_bin(setting[i]);
641 			if (ascii64[value] != setting[i])
642 				return(NULL);
643 			count |= value << (i - 1) * 6;
644 		}
645 		if (!count)
646 			return(NULL);
647 
648 		for (i = 5, salt = 0; i < 9; i++) {
649 			int value = ascii_to_bin(setting[i]);
650 			if (ascii64[value] != setting[i])
651 				return(NULL);
652 			salt |= value << (i - 5) * 6;
653 		}
654 
655 		while (*key) {
656 			/*
657 			 * Encrypt the key with itself.
658 			 */
659 			if (des_cipher((char *) keybuf, (char *) keybuf,
660 			    0, 1, data))
661 				return(NULL);
662 			/*
663 			 * And XOR with the next 8 characters of the key.
664 			 */
665 			q = (u_char *) keybuf;
666 			while ((size_t)(q - (u_char *) keybuf) < sizeof(keybuf) && *key)
667 				*q++ ^= *key++ << 1;
668 
669 			if (des_setkey((char *) keybuf, data))
670 				return(NULL);
671 		}
672 		memcpy(data->output, setting, 9);
673 		data->output[9] = '\0';
674 		p = (u_char *) data->output + 9;
675 	} else {
676 		/*
677 		 * "old"-style:
678 		 *	setting - 2 chars of salt
679 		 *	key - up to 8 characters
680 		 */
681 		count = 25;
682 
683 		if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
684 			return(NULL);
685 
686 		salt = (ascii_to_bin(setting[1]) << 6)
687 		     |  ascii_to_bin(setting[0]);
688 
689 		data->output[0] = setting[0];
690 		data->output[1] = setting[1];
691 		p = (u_char *) data->output + 2;
692 	}
693 	setup_salt(salt, data);
694 	/*
695 	 * Do it.
696 	 */
697 	if (do_des(0, 0, &r0, &r1, count, data))
698 		return(NULL);
699 	/*
700 	 * Now encode the result...
701 	 */
702 	l = (r0 >> 8);
703 	*p++ = ascii64[(l >> 18) & 0x3f];
704 	*p++ = ascii64[(l >> 12) & 0x3f];
705 	*p++ = ascii64[(l >> 6) & 0x3f];
706 	*p++ = ascii64[l & 0x3f];
707 
708 	l = (r0 << 16) | ((r1 >> 16) & 0xffff);
709 	*p++ = ascii64[(l >> 18) & 0x3f];
710 	*p++ = ascii64[(l >> 12) & 0x3f];
711 	*p++ = ascii64[(l >> 6) & 0x3f];
712 	*p++ = ascii64[l & 0x3f];
713 
714 	l = r1 << 2;
715 	*p++ = ascii64[(l >> 12) & 0x3f];
716 	*p++ = ascii64[(l >> 6) & 0x3f];
717 	*p++ = ascii64[l & 0x3f];
718 	*p = 0;
719 
720 	return(data->output);
721 }
722 
723 #ifdef TEST
724 static char *
_crypt_extended(const char * key,const char * setting)725 _crypt_extended(const char *key, const char *setting)
726 {
727 	static int initialized = 0;
728 	static struct php_crypt_extended_data data;
729 
730 	if (!initialized) {
731 		_crypt_extended_init();
732 		initialized = 1;
733 		data.initialized = 0;
734 	}
735 	return _crypt_extended_r(key, setting, &data);
736 }
737 
738 #define crypt _crypt_extended
739 
740 static const struct {
741 	const char *hash;
742 	const char *pw;
743 } tests[] = {
744 /* "new"-style */
745 	{"_J9..CCCCXBrJUJV154M", "U*U*U*U*"},
746 	{"_J9..CCCCXUhOBTXzaiE", "U*U***U"},
747 	{"_J9..CCCC4gQ.mB/PffM", "U*U***U*"},
748 	{"_J9..XXXXvlzQGqpPPdk", "*U*U*U*U"},
749 	{"_J9..XXXXsqM/YSSP..Y", "*U*U*U*U*"},
750 	{"_J9..XXXXVL7qJCnku0I", "*U*U*U*U*U*U*U*U"},
751 	{"_J9..XXXXAj8cFbP5scI", "*U*U*U*U*U*U*U*U*"},
752 	{"_J9..SDizh.vll5VED9g", "ab1234567"},
753 	{"_J9..SDizRjWQ/zePPHc", "cr1234567"},
754 	{"_J9..SDizxmRI1GjnQuE", "zxyDPWgydbQjgq"},
755 	{"_K9..SaltNrQgIYUAeoY", "726 even"},
756 	{"_J9..SDSD5YGyRCr4W4c", ""},
757 /* "old"-style, valid salts */
758 	{"CCNf8Sbh3HDfQ", "U*U*U*U*"},
759 	{"CCX.K.MFy4Ois", "U*U***U"},
760 	{"CC4rMpbg9AMZ.", "U*U***U*"},
761 	{"XXxzOu6maQKqQ", "*U*U*U*U"},
762 	{"SDbsugeBiC58A", ""},
763 	{"./xZjzHv5vzVE", "password"},
764 	{"0A2hXM1rXbYgo", "password"},
765 	{"A9RXdR23Y.cY6", "password"},
766 	{"ZziFATVXHo2.6", "password"},
767 	{"zZDDIZ0NOlPzw", "password"},
768 /* "old"-style, "reasonable" invalid salts, UFC-crypt behavior expected */
769 	{"\001\002wyd0KZo65Jo", "password"},
770 	{"a_C10Dk/ExaG.", "password"},
771 	{"~\377.5OTsRVjwLo", "password"},
772 /* The below are erroneous inputs, so NULL return is expected/required */
773 	{"", ""}, /* no salt */
774 	{" ", ""}, /* setting string is too short */
775 	{"a:", ""}, /* unsafe character */
776 	{"\na", ""}, /* unsafe character */
777 	{"_/......", ""}, /* setting string is too short for its type */
778 	{"_........", ""}, /* zero iteration count */
779 	{"_/!......", ""}, /* invalid character in count */
780 	{"_/......!", ""}, /* invalid character in salt */
781 	{NULL}
782 };
783 
main(void)784 int main(void)
785 {
786 	int i;
787 
788 	for (i = 0; tests[i].hash; i++) {
789 		char *hash = crypt(tests[i].pw, tests[i].hash);
790 		if (!hash && strlen(tests[i].hash) < 13)
791 			continue; /* expected failure */
792 		if (!strcmp(hash, tests[i].hash))
793 			continue; /* expected success */
794 		puts("FAILED");
795 		return 1;
796 	}
797 
798 	puts("PASSED");
799 
800 	return 0;
801 }
802 #endif
803