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