Back to index

php5  5.3.10
crypt_freesec.c
Go to the documentation of this file.
00001 /*
00002   $Id: crypt_freesec.c 295340 2010-02-22 00:05:02Z pajoye $ 
00003 */
00004 /*
00005  * This version is derived from the original implementation of FreeSec
00006  * (release 1.1) by David Burren.  I've reviewed the changes made in
00007  * OpenBSD (as of 2.7) and modified the original code in a similar way
00008  * where applicable.  I've also made it reentrant and made a number of
00009  * other changes.
00010  * - Solar Designer <solar at openwall.com>
00011  */
00012 
00013 /*
00014  * FreeSec: libcrypt for NetBSD
00015  *
00016  * Copyright (c) 1994 David Burren
00017  * All rights reserved.
00018  *
00019  * Redistribution and use in source and binary forms, with or without
00020  * modification, are permitted provided that the following conditions
00021  * are met:
00022  * 1. Redistributions of source code must retain the above copyright
00023  *    notice, this list of conditions and the following disclaimer.
00024  * 2. Redistributions in binary form must reproduce the above copyright
00025  *    notice, this list of conditions and the following disclaimer in the
00026  *    documentation and/or other materials provided with the distribution.
00027  * 3. Neither the name of the author nor the names of other contributors
00028  *    may be used to endorse or promote products derived from this software
00029  *    without specific prior written permission.
00030  *
00031  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
00032  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00033  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00034  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
00035  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00036  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00037  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00038  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00039  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00040  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00041  * SUCH DAMAGE.
00042  *
00043  *     $Owl: Owl/packages/glibc/crypt_freesec.c,v 1.4 2005/11/16 13:08:32 solar Exp $
00044  *     $Id: crypt_freesec.c 295340 2010-02-22 00:05:02Z pajoye $
00045  *
00046  * This is an original implementation of the DES and the crypt(3) interfaces
00047  * by David Burren <davidb at werj.com.au>.
00048  *
00049  * An excellent reference on the underlying algorithm (and related
00050  * algorithms) is:
00051  *
00052  *     B. Schneier, Applied Cryptography: protocols, algorithms,
00053  *     and source code in C, John Wiley & Sons, 1994.
00054  *
00055  * Note that in that book's description of DES the lookups for the initial,
00056  * pbox, and final permutations are inverted (this has been brought to the
00057  * attention of the author).  A list of errata for this book has been
00058  * posted to the sci.crypt newsgroup by the author and is available for FTP.
00059  *
00060  * ARCHITECTURE ASSUMPTIONS:
00061  *     This code used to have some nasty ones, but these have been removed
00062  *     by now.  The code requires a 32-bit integer type, though.
00063  */
00064 
00065 #include <sys/types.h>
00066 #include <string.h>
00067 
00068 #ifdef TEST
00069 #include <stdio.h>
00070 #endif
00071 
00072 #include "crypt_freesec.h"
00073 
00074 #define _PASSWORD_EFMT1 '_'
00075 
00076 static u_char IP[64] = {
00077        58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12,  4,
00078        62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16,  8,
00079        57, 49, 41, 33, 25, 17,  9,  1, 59, 51, 43, 35, 27, 19, 11,  3,
00080        61, 53, 45, 37, 29, 21, 13,  5, 63, 55, 47, 39, 31, 23, 15,  7
00081 };
00082 
00083 static u_char key_perm[56] = {
00084        57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
00085        10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
00086        63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
00087        14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
00088 };
00089 
00090 static u_char key_shifts[16] = {
00091        1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
00092 };
00093 
00094 static u_char comp_perm[48] = {
00095        14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
00096        23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
00097        41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
00098        44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
00099 };
00100 
00101 /*
00102  *     No E box is used, as it's replaced by some ANDs, shifts, and ORs.
00103  */
00104 
00105 static u_char sbox[8][64] = {
00106        {
00107               14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
00108                0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
00109                4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
00110               15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13
00111        },
00112        {
00113               15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
00114                3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
00115                0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
00116               13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9
00117        },
00118        {
00119               10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
00120               13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
00121               13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
00122                1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12
00123        },
00124        {
00125                7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
00126               13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
00127               10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
00128                3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14
00129        },
00130        {
00131                2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
00132               14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
00133                4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
00134               11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3
00135        },
00136        {
00137               12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
00138               10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
00139                9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
00140                4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13
00141        },
00142        {
00143                4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
00144               13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
00145                1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
00146                6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12
00147        },
00148        {
00149               13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
00150                1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
00151                7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
00152                2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
00153        }
00154 };
00155 
00156 static u_char pbox[32] = {
00157        16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
00158         2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
00159 };
00160 
00161 static uint32_t bits32[32] =
00162 {
00163        0x80000000, 0x40000000, 0x20000000, 0x10000000,
00164        0x08000000, 0x04000000, 0x02000000, 0x01000000,
00165        0x00800000, 0x00400000, 0x00200000, 0x00100000,
00166        0x00080000, 0x00040000, 0x00020000, 0x00010000,
00167        0x00008000, 0x00004000, 0x00002000, 0x00001000,
00168        0x00000800, 0x00000400, 0x00000200, 0x00000100,
00169        0x00000080, 0x00000040, 0x00000020, 0x00000010,
00170        0x00000008, 0x00000004, 0x00000002, 0x00000001
00171 };
00172 
00173 static u_char bits8[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
00174 
00175 static unsigned char ascii64[] =
00176         "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
00177 /*       0000000000111111111122222222223333333333444444444455555555556666 */
00178 /*       0123456789012345678901234567890123456789012345678901234567890123 */
00179 
00180 static u_char m_sbox[4][4096];
00181 static uint32_t psbox[4][256];
00182 static uint32_t ip_maskl[8][256], ip_maskr[8][256];
00183 static uint32_t fp_maskl[8][256], fp_maskr[8][256];
00184 static uint32_t key_perm_maskl[8][128], key_perm_maskr[8][128];
00185 static uint32_t comp_maskl[8][128], comp_maskr[8][128];
00186 
00187 static inline int
00188 ascii_to_bin(char ch)
00189 {
00190        signed char sch = ch;
00191        int retval;
00192 
00193        retval = sch - '.';
00194        if (sch >= 'A') {
00195               retval = sch - ('A' - 12);
00196               if (sch >= 'a')
00197                      retval = sch - ('a' - 38);
00198        }
00199        retval &= 0x3f;
00200 
00201        return(retval);
00202 }
00203 
00204 /*
00205  * When we choose to "support" invalid salts, nevertheless disallow those
00206  * containing characters that would violate the passwd file format.
00207  */
00208 static inline int
00209 ascii_is_unsafe(char ch)
00210 {
00211        return !ch || ch == '\n' || ch == ':';
00212 }
00213 
00214 void
00215 _crypt_extended_init(void)
00216 {
00217        int i, j, b, k, inbit, obit;
00218        uint32_t *p, *il, *ir, *fl, *fr;
00219        uint32_t *bits28, *bits24;
00220        u_char inv_key_perm[64];
00221        u_char u_key_perm[56];
00222        u_char inv_comp_perm[56];
00223        u_char init_perm[64], final_perm[64];
00224        u_char u_sbox[8][64];
00225        u_char un_pbox[32];
00226 
00227        bits24 = (bits28 = bits32 + 4) + 4;
00228 
00229        /*
00230         * Invert the S-boxes, reordering the input bits.
00231         */
00232        for (i = 0; i < 8; i++)
00233               for (j = 0; j < 64; j++) {
00234                      b = (j & 0x20) | ((j & 1) << 4) | ((j >> 1) & 0xf);
00235                      u_sbox[i][j] = sbox[i][b];
00236               }
00237 
00238        /*
00239         * Convert the inverted S-boxes into 4 arrays of 8 bits.
00240         * Each will handle 12 bits of the S-box input.
00241         */
00242        for (b = 0; b < 4; b++)
00243               for (i = 0; i < 64; i++)
00244                      for (j = 0; j < 64; j++)
00245                             m_sbox[b][(i << 6) | j] =
00246                                    (u_sbox[(b << 1)][i] << 4) |
00247                                    u_sbox[(b << 1) + 1][j];
00248 
00249        /*
00250         * Set up the initial & final permutations into a useful form, and
00251         * initialise the inverted key permutation.
00252         */
00253        for (i = 0; i < 64; i++) {
00254               init_perm[final_perm[i] = IP[i] - 1] = i;
00255               inv_key_perm[i] = 255;
00256        }
00257 
00258        /*
00259         * Invert the key permutation and initialise the inverted key
00260         * compression permutation.
00261         */
00262        for (i = 0; i < 56; i++) {
00263               u_key_perm[i] = key_perm[i] - 1;
00264               inv_key_perm[key_perm[i] - 1] = i;
00265               inv_comp_perm[i] = 255;
00266        }
00267 
00268        /*
00269         * Invert the key compression permutation.
00270         */
00271        for (i = 0; i < 48; i++) {
00272               inv_comp_perm[comp_perm[i] - 1] = i;
00273        }
00274 
00275        /*
00276         * Set up the OR-mask arrays for the initial and final permutations,
00277         * and for the key initial and compression permutations.
00278         */
00279        for (k = 0; k < 8; k++) {
00280               for (i = 0; i < 256; i++) {
00281                      *(il = &ip_maskl[k][i]) = 0;
00282                      *(ir = &ip_maskr[k][i]) = 0;
00283                      *(fl = &fp_maskl[k][i]) = 0;
00284                      *(fr = &fp_maskr[k][i]) = 0;
00285                      for (j = 0; j < 8; j++) {
00286                             inbit = 8 * k + j;
00287                             if (i & bits8[j]) {
00288                                    if ((obit = init_perm[inbit]) < 32)
00289                                           *il |= bits32[obit];
00290                                    else
00291                                           *ir |= bits32[obit-32];
00292                                    if ((obit = final_perm[inbit]) < 32)
00293                                           *fl |= bits32[obit];
00294                                    else
00295                                           *fr |= bits32[obit - 32];
00296                             }
00297                      }
00298               }
00299               for (i = 0; i < 128; i++) {
00300                      *(il = &key_perm_maskl[k][i]) = 0;
00301                      *(ir = &key_perm_maskr[k][i]) = 0;
00302                      for (j = 0; j < 7; j++) {
00303                             inbit = 8 * k + j;
00304                             if (i & bits8[j + 1]) {
00305                                    if ((obit = inv_key_perm[inbit]) == 255)
00306                                           continue;
00307                                    if (obit < 28)
00308                                           *il |= bits28[obit];
00309                                    else
00310                                           *ir |= bits28[obit - 28];
00311                             }
00312                      }
00313                      *(il = &comp_maskl[k][i]) = 0;
00314                      *(ir = &comp_maskr[k][i]) = 0;
00315                      for (j = 0; j < 7; j++) {
00316                             inbit = 7 * k + j;
00317                             if (i & bits8[j + 1]) {
00318                                    if ((obit=inv_comp_perm[inbit]) == 255)
00319                                           continue;
00320                                    if (obit < 24)
00321                                           *il |= bits24[obit];
00322                                    else
00323                                           *ir |= bits24[obit - 24];
00324                             }
00325                      }
00326               }
00327        }
00328 
00329        /*
00330         * Invert the P-box permutation, and convert into OR-masks for
00331         * handling the output of the S-box arrays setup above.
00332         */
00333        for (i = 0; i < 32; i++)
00334               un_pbox[pbox[i] - 1] = i;
00335 
00336        for (b = 0; b < 4; b++)
00337               for (i = 0; i < 256; i++) {
00338                      *(p = &psbox[b][i]) = 0;
00339                      for (j = 0; j < 8; j++) {
00340                             if (i & bits8[j])
00341                                    *p |= bits32[un_pbox[8 * b + j]];
00342                      }
00343               }
00344 }
00345 
00346 static void
00347 des_init_local(struct php_crypt_extended_data *data)
00348 {
00349        data->old_rawkey0 = data->old_rawkey1 = 0;
00350        data->saltbits = 0;
00351        data->old_salt = 0;
00352 
00353        data->initialized = 1;
00354 }
00355 
00356 static void
00357 setup_salt(uint32_t salt, struct php_crypt_extended_data *data)
00358 {
00359        uint32_t      obit, saltbit, saltbits;
00360        int    i;
00361 
00362        if (salt == data->old_salt)
00363               return;
00364        data->old_salt = salt;
00365 
00366        saltbits = 0;
00367        saltbit = 1;
00368        obit = 0x800000;
00369        for (i = 0; i < 24; i++) {
00370               if (salt & saltbit)
00371                      saltbits |= obit;
00372               saltbit <<= 1;
00373               obit >>= 1;
00374        }
00375        data->saltbits = saltbits;
00376 }
00377 
00378 static int
00379 des_setkey(const char *key, struct php_crypt_extended_data *data)
00380 {
00381        uint32_t      k0, k1, rawkey0, rawkey1;
00382        int    shifts, round;
00383 
00384        rawkey0 =
00385               (uint32_t)(u_char)key[3] |
00386               ((uint32_t)(u_char)key[2] << 8) |
00387               ((uint32_t)(u_char)key[1] << 16) |
00388               ((uint32_t)(u_char)key[0] << 24);
00389        rawkey1 =
00390               (uint32_t)(u_char)key[7] |
00391               ((uint32_t)(u_char)key[6] << 8) |
00392               ((uint32_t)(u_char)key[5] << 16) |
00393               ((uint32_t)(u_char)key[4] << 24);
00394 
00395        if ((rawkey0 | rawkey1)
00396            && rawkey0 == data->old_rawkey0
00397            && rawkey1 == data->old_rawkey1) {
00398               /*
00399                * Already setup for this key.
00400                * This optimisation fails on a zero key (which is weak and
00401                * has bad parity anyway) in order to simplify the starting
00402                * conditions.
00403                */
00404               return(0);
00405        }
00406        data->old_rawkey0 = rawkey0;
00407        data->old_rawkey1 = rawkey1;
00408 
00409        /*
00410         *     Do key permutation and split into two 28-bit subkeys.
00411         */
00412        k0 = key_perm_maskl[0][rawkey0 >> 25]
00413           | key_perm_maskl[1][(rawkey0 >> 17) & 0x7f]
00414           | key_perm_maskl[2][(rawkey0 >> 9) & 0x7f]
00415           | key_perm_maskl[3][(rawkey0 >> 1) & 0x7f]
00416           | key_perm_maskl[4][rawkey1 >> 25]
00417           | key_perm_maskl[5][(rawkey1 >> 17) & 0x7f]
00418           | key_perm_maskl[6][(rawkey1 >> 9) & 0x7f]
00419           | key_perm_maskl[7][(rawkey1 >> 1) & 0x7f];
00420        k1 = key_perm_maskr[0][rawkey0 >> 25]
00421           | key_perm_maskr[1][(rawkey0 >> 17) & 0x7f]
00422           | key_perm_maskr[2][(rawkey0 >> 9) & 0x7f]
00423           | key_perm_maskr[3][(rawkey0 >> 1) & 0x7f]
00424           | key_perm_maskr[4][rawkey1 >> 25]
00425           | key_perm_maskr[5][(rawkey1 >> 17) & 0x7f]
00426           | key_perm_maskr[6][(rawkey1 >> 9) & 0x7f]
00427           | key_perm_maskr[7][(rawkey1 >> 1) & 0x7f];
00428        /*
00429         *     Rotate subkeys and do compression permutation.
00430         */
00431        shifts = 0;
00432        for (round = 0; round < 16; round++) {
00433               uint32_t      t0, t1;
00434 
00435               shifts += key_shifts[round];
00436 
00437               t0 = (k0 << shifts) | (k0 >> (28 - shifts));
00438               t1 = (k1 << shifts) | (k1 >> (28 - shifts));
00439 
00440               data->de_keysl[15 - round] =
00441               data->en_keysl[round] = comp_maskl[0][(t0 >> 21) & 0x7f]
00442                             | comp_maskl[1][(t0 >> 14) & 0x7f]
00443                             | comp_maskl[2][(t0 >> 7) & 0x7f]
00444                             | comp_maskl[3][t0 & 0x7f]
00445                             | comp_maskl[4][(t1 >> 21) & 0x7f]
00446                             | comp_maskl[5][(t1 >> 14) & 0x7f]
00447                             | comp_maskl[6][(t1 >> 7) & 0x7f]
00448                             | comp_maskl[7][t1 & 0x7f];
00449 
00450               data->de_keysr[15 - round] =
00451               data->en_keysr[round] = comp_maskr[0][(t0 >> 21) & 0x7f]
00452                             | comp_maskr[1][(t0 >> 14) & 0x7f]
00453                             | comp_maskr[2][(t0 >> 7) & 0x7f]
00454                             | comp_maskr[3][t0 & 0x7f]
00455                             | comp_maskr[4][(t1 >> 21) & 0x7f]
00456                             | comp_maskr[5][(t1 >> 14) & 0x7f]
00457                             | comp_maskr[6][(t1 >> 7) & 0x7f]
00458                             | comp_maskr[7][t1 & 0x7f];
00459        }
00460        return(0);
00461 }
00462 
00463 static int
00464 do_des(uint32_t l_in, uint32_t r_in, uint32_t *l_out, uint32_t *r_out,
00465        int count, struct php_crypt_extended_data *data)
00466 {
00467        /*
00468         *     l_in, r_in, l_out, and r_out are in pseudo-"big-endian" format.
00469         */
00470        uint32_t      l, r, *kl, *kr, *kl1, *kr1;
00471        uint32_t      f, r48l, r48r, saltbits;
00472        int    round;
00473 
00474        if (count == 0) {
00475               return(1);
00476        } else if (count > 0) {
00477               /*
00478                * Encrypting
00479                */
00480               kl1 = data->en_keysl;
00481               kr1 = data->en_keysr;
00482        } else {
00483               /*
00484                * Decrypting
00485                */
00486               count = -count;
00487               kl1 = data->de_keysl;
00488               kr1 = data->de_keysr;
00489        }
00490 
00491        /*
00492         *     Do initial permutation (IP).
00493         */
00494        l = ip_maskl[0][l_in >> 24]
00495          | ip_maskl[1][(l_in >> 16) & 0xff]
00496          | ip_maskl[2][(l_in >> 8) & 0xff]
00497          | ip_maskl[3][l_in & 0xff]
00498          | ip_maskl[4][r_in >> 24]
00499          | ip_maskl[5][(r_in >> 16) & 0xff]
00500          | ip_maskl[6][(r_in >> 8) & 0xff]
00501          | ip_maskl[7][r_in & 0xff];
00502        r = ip_maskr[0][l_in >> 24]
00503          | ip_maskr[1][(l_in >> 16) & 0xff]
00504          | ip_maskr[2][(l_in >> 8) & 0xff]
00505          | ip_maskr[3][l_in & 0xff]
00506          | ip_maskr[4][r_in >> 24]
00507          | ip_maskr[5][(r_in >> 16) & 0xff]
00508          | ip_maskr[6][(r_in >> 8) & 0xff]
00509          | ip_maskr[7][r_in & 0xff];
00510 
00511        saltbits = data->saltbits;
00512        while (count--) {
00513               /*
00514                * Do each round.
00515                */
00516               kl = kl1;
00517               kr = kr1;
00518               round = 16;
00519               while (round--) {
00520                      /*
00521                       * Expand R to 48 bits (simulate the E-box).
00522                       */
00523                      r48l   = ((r & 0x00000001) << 23)
00524                             | ((r & 0xf8000000) >> 9)
00525                             | ((r & 0x1f800000) >> 11)
00526                             | ((r & 0x01f80000) >> 13)
00527                             | ((r & 0x001f8000) >> 15);
00528 
00529                      r48r   = ((r & 0x0001f800) << 7)
00530                             | ((r & 0x00001f80) << 5)
00531                             | ((r & 0x000001f8) << 3)
00532                             | ((r & 0x0000001f) << 1)
00533                             | ((r & 0x80000000) >> 31);
00534                      /*
00535                       * Do salting for crypt() and friends, and
00536                       * XOR with the permuted key.
00537                       */
00538                      f = (r48l ^ r48r) & saltbits;
00539                      r48l ^= f ^ *kl++;
00540                      r48r ^= f ^ *kr++;
00541                      /*
00542                       * Do sbox lookups (which shrink it back to 32 bits)
00543                       * and do the pbox permutation at the same time.
00544                       */
00545                      f = psbox[0][m_sbox[0][r48l >> 12]]
00546                        | psbox[1][m_sbox[1][r48l & 0xfff]]
00547                        | psbox[2][m_sbox[2][r48r >> 12]]
00548                        | psbox[3][m_sbox[3][r48r & 0xfff]];
00549                      /*
00550                       * Now that we've permuted things, complete f().
00551                       */
00552                      f ^= l;
00553                      l = r;
00554                      r = f;
00555               }
00556               r = l;
00557               l = f;
00558        }
00559        /*
00560         * Do final permutation (inverse of IP).
00561         */
00562        *l_out = fp_maskl[0][l >> 24]
00563               | fp_maskl[1][(l >> 16) & 0xff]
00564               | fp_maskl[2][(l >> 8) & 0xff]
00565               | fp_maskl[3][l & 0xff]
00566               | fp_maskl[4][r >> 24]
00567               | fp_maskl[5][(r >> 16) & 0xff]
00568               | fp_maskl[6][(r >> 8) & 0xff]
00569               | fp_maskl[7][r & 0xff];
00570        *r_out = fp_maskr[0][l >> 24]
00571               | fp_maskr[1][(l >> 16) & 0xff]
00572               | fp_maskr[2][(l >> 8) & 0xff]
00573               | fp_maskr[3][l & 0xff]
00574               | fp_maskr[4][r >> 24]
00575               | fp_maskr[5][(r >> 16) & 0xff]
00576               | fp_maskr[6][(r >> 8) & 0xff]
00577               | fp_maskr[7][r & 0xff];
00578        return(0);
00579 }
00580 
00581 static int
00582 des_cipher(const char *in, char *out, uint32_t salt, int count,
00583        struct php_crypt_extended_data *data)
00584 {
00585        uint32_t      l_out, r_out, rawl, rawr;
00586        int    retval;
00587 
00588        setup_salt(salt, data);
00589 
00590        rawl =
00591               (uint32_t)(u_char)in[3] |
00592               ((uint32_t)(u_char)in[2] << 8) |
00593               ((uint32_t)(u_char)in[1] << 16) |
00594               ((uint32_t)(u_char)in[0] << 24);
00595        rawr =
00596               (uint32_t)(u_char)in[7] |
00597               ((uint32_t)(u_char)in[6] << 8) |
00598               ((uint32_t)(u_char)in[5] << 16) |
00599               ((uint32_t)(u_char)in[4] << 24);
00600 
00601        retval = do_des(rawl, rawr, &l_out, &r_out, count, data);
00602 
00603        out[0] = l_out >> 24;
00604        out[1] = l_out >> 16;
00605        out[2] = l_out >> 8;
00606        out[3] = l_out;
00607        out[4] = r_out >> 24;
00608        out[5] = r_out >> 16;
00609        out[6] = r_out >> 8;
00610        out[7] = r_out;
00611 
00612        return(retval);
00613 }
00614 
00615 char *
00616 _crypt_extended_r(const char *key, const char *setting,
00617        struct php_crypt_extended_data *data)
00618 {
00619        int           i;
00620        uint32_t      count, salt, l, r0, r1, keybuf[2];
00621        u_char        *p, *q;
00622 
00623        if (!data->initialized)
00624               des_init_local(data);
00625 
00626        /*
00627         * Copy the key, shifting each character up by one bit
00628         * and padding with zeros.
00629         */
00630        q = (u_char *) keybuf;
00631        while (q - (u_char *) keybuf < sizeof(keybuf)) {
00632               if ((*q++ = *key << 1))
00633                      key++;
00634        }
00635        if (des_setkey((u_char *) keybuf, data))
00636               return(NULL);
00637 
00638        if (*setting == _PASSWORD_EFMT1) {
00639               /*
00640                * "new"-style:
00641                *     setting - underscore, 4 chars of count, 4 chars of salt
00642                *     key - unlimited characters
00643                */
00644               for (i = 1, count = 0; i < 5; i++) {
00645                      int value = ascii_to_bin(setting[i]);
00646                      if (ascii64[value] != setting[i])
00647                             return(NULL);
00648                      count |= value << (i - 1) * 6;
00649               }
00650               if (!count)
00651                      return(NULL);
00652 
00653               for (i = 5, salt = 0; i < 9; i++) {
00654                      int value = ascii_to_bin(setting[i]);
00655                      if (ascii64[value] != setting[i])
00656                             return(NULL);
00657                      salt |= value << (i - 5) * 6;
00658               }
00659 
00660               while (*key) {
00661                      /*
00662                       * Encrypt the key with itself.
00663                       */
00664                      if (des_cipher((u_char *) keybuf, (u_char *) keybuf,
00665                          0, 1, data))
00666                             return(NULL);
00667                      /*
00668                       * And XOR with the next 8 characters of the key.
00669                       */
00670                      q = (u_char *) keybuf;
00671                      while (q - (u_char *) keybuf < sizeof(keybuf) && *key)
00672                             *q++ ^= *key++ << 1;
00673 
00674                      if (des_setkey((u_char *) keybuf, data))
00675                             return(NULL);
00676               }
00677               memcpy(data->output, setting, 9);
00678               data->output[9] = '\0';
00679               p = (u_char *) data->output + 9;
00680        } else {
00681               /*
00682                * "old"-style:
00683                *     setting - 2 chars of salt
00684                *     key - up to 8 characters
00685                */
00686               count = 25;
00687 
00688               if (ascii_is_unsafe(setting[0]) || ascii_is_unsafe(setting[1]))
00689                      return(NULL);
00690 
00691               salt = (ascii_to_bin(setting[1]) << 6)
00692                    |  ascii_to_bin(setting[0]);
00693 
00694               data->output[0] = setting[0];
00695               data->output[1] = setting[1];
00696               p = (u_char *) data->output + 2;
00697        }
00698        setup_salt(salt, data);
00699        /*
00700         * Do it.
00701         */
00702        if (do_des(0, 0, &r0, &r1, count, data))
00703               return(NULL);
00704        /*
00705         * Now encode the result...
00706         */
00707        l = (r0 >> 8);
00708        *p++ = ascii64[(l >> 18) & 0x3f];
00709        *p++ = ascii64[(l >> 12) & 0x3f];
00710        *p++ = ascii64[(l >> 6) & 0x3f];
00711        *p++ = ascii64[l & 0x3f];
00712 
00713        l = (r0 << 16) | ((r1 >> 16) & 0xffff);
00714        *p++ = ascii64[(l >> 18) & 0x3f];
00715        *p++ = ascii64[(l >> 12) & 0x3f];
00716        *p++ = ascii64[(l >> 6) & 0x3f];
00717        *p++ = ascii64[l & 0x3f];
00718 
00719        l = r1 << 2;
00720        *p++ = ascii64[(l >> 12) & 0x3f];
00721        *p++ = ascii64[(l >> 6) & 0x3f];
00722        *p++ = ascii64[l & 0x3f];
00723        *p = 0;
00724 
00725        return(data->output);
00726 }
00727 
00728 #ifdef TEST
00729 static char *
00730 _crypt_extended(const char *key, const char *setting)
00731 {
00732        static int initialized = 0;
00733        static struct php_crypt_extended_data data;
00734 
00735        if (!initialized) {
00736               _crypt_extended_init();
00737               initialized = 1;
00738               data.initialized = 0;
00739        }
00740        return _crypt_extended_r(key, setting, &data);
00741 }
00742 
00743 #define crypt _crypt_extended
00744 
00745 static struct {
00746        char *hash;
00747        char *pw;
00748 } tests[] = {
00749 /* "new"-style */
00750        {"_J9..CCCCXBrJUJV154M", "U*U*U*U*"},
00751        {"_J9..CCCCXUhOBTXzaiE", "U*U***U"},
00752        {"_J9..CCCC4gQ.mB/PffM", "U*U***U*"},
00753        {"_J9..XXXXvlzQGqpPPdk", "*U*U*U*U"},
00754        {"_J9..XXXXsqM/YSSP..Y", "*U*U*U*U*"},
00755        {"_J9..XXXXVL7qJCnku0I", "*U*U*U*U*U*U*U*U"},
00756        {"_J9..XXXXAj8cFbP5scI", "*U*U*U*U*U*U*U*U*"},
00757        {"_J9..SDizh.vll5VED9g", "ab1234567"},
00758        {"_J9..SDizRjWQ/zePPHc", "cr1234567"},
00759        {"_J9..SDizxmRI1GjnQuE", "zxyDPWgydbQjgq"},
00760        {"_K9..SaltNrQgIYUAeoY", "726 even"},
00761        {"_J9..SDSD5YGyRCr4W4c", ""},
00762 /* "old"-style, valid salts */
00763        {"CCNf8Sbh3HDfQ", "U*U*U*U*"},
00764        {"CCX.K.MFy4Ois", "U*U***U"},
00765        {"CC4rMpbg9AMZ.", "U*U***U*"},
00766        {"XXxzOu6maQKqQ", "*U*U*U*U"},
00767        {"SDbsugeBiC58A", ""},
00768        {"./xZjzHv5vzVE", "password"},
00769        {"0A2hXM1rXbYgo", "password"},
00770        {"A9RXdR23Y.cY6", "password"},
00771        {"ZziFATVXHo2.6", "password"},
00772        {"zZDDIZ0NOlPzw", "password"},
00773 /* "old"-style, "reasonable" invalid salts, UFC-crypt behavior expected */
00774        {"\001\002wyd0KZo65Jo", "password"},
00775        {"a_C10Dk/ExaG.", "password"},
00776        {"~\377.5OTsRVjwLo", "password"},
00777 /* The below are erroneous inputs, so NULL return is expected/required */
00778        {"", ""}, /* no salt */
00779        {" ", ""}, /* setting string is too short */
00780        {"a:", ""}, /* unsafe character */
00781        {"\na", ""}, /* unsafe character */
00782        {"_/......", ""}, /* setting string is too short for its type */
00783        {"_........", ""}, /* zero iteration count */
00784        {"_/!......", ""}, /* invalid character in count */
00785        {"_/......!", ""}, /* invalid character in salt */
00786        {NULL}
00787 };
00788 
00789 int main(void)
00790 {
00791        int i;
00792 
00793        for (i = 0; tests[i].hash; i++) {
00794               char *hash = crypt(tests[i].pw, tests[i].hash);
00795               if (!hash && strlen(tests[i].hash) < 13)
00796                      continue; /* expected failure */
00797               if (!strcmp(hash, tests[i].hash))
00798                      continue; /* expected success */
00799               puts("FAILED");
00800               return 1;
00801        }
00802 
00803        puts("PASSED");
00804 
00805        return 0;
00806 }
00807 #endif