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