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 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
346static void
347des_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
356static void
357setup_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
378static int
379des_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
463static int
464do_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
581static int
582des_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
615char *
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
730static char *
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
746static 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
790int 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