Request: UNIX crypt (DES based)

Moderator: BarsMonster

Post Reply [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
reg
Posts: 4
Joined: Mon Oct 20, 2008 7:42 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Request: UNIX crypt (DES based)

Post by reg » Mon Oct 20, 2008 8:51 am

UNIX crypt (DES)

1) Algorithm description, with pseudocode

Traditional DES-based scheme
The traditional implementation uses a modified form of the DES algorithm. The user's password is truncated to eight characters, and those are coerced down to only 7-bits each; this forms the 56-bit DES key. That key is then used to encrypt an all-bits-zero block, and then the ciphertext is encrypted again with the same key, and so on for a total of 25 DES encryptions. A 12-bit salt is used to perturb the encryption algorithm, so standard DES implementations can't be used to implement crypt(). The salt and the final ciphertext are encoded into a printable string in a form of base64.
This is technically not encryption since the data (all bits zero) is not being kept secret; it's widely known to all in advance. However, one of the properties of DES is that it's very resistant to key recovery even in the face of known plaintext situations. It is theoretically possible that two different passwords could result in exactly the same hash. Thus the password is never "decrypted": it is merely used to compute a result, and the matching results are presumed to be proof that the passwords were "the same."
The advantages of this method have been that the password can be stored in plain text and copied among Unix systems without being exposed to the system administrators or other users. This portability has worked for over 30 years across many generations of computing architecture, and across many versions of Unix from many vendors.

http://en.wikipedia.org/wiki/Data_Encryption_Standard
http://csrc.nist.gov/publications/fips/ ... ps46-3.pdf


2) Simplest possible C code which checks 1 key

Code: Select all


/*      Copyright (c) 1984,1988 AT&T */
/*        All Rights Reserved   */

#pragma ident   "%Z%%M% %I%     %E% SMI"

/*LINTLIBRARY*/
/*
 * This program implements the
 * Proposed Federal Information Processing
 *  Data Encryption Standard.
 * See Federal Register, March 17, 1975 (40FR12134)
 */

/*
 * Initial permutation,
 */
static  char    IP[] = {
        58,50,42,34,26,18,10, 2,
        60,52,44,36,28,20,12, 4,
        62,54,46,38,30,22,14, 6,
        64,56,48,40,32,24,16, 8,
        57,49,41,33,25,17, 9, 1,
        59,51,43,35,27,19,11, 3,
        61,53,45,37,29,21,13, 5,
        63,55,47,39,31,23,15, 7,
};

/*
 * Final permutation, FP = IP^(-1)
 */
static  char    FP[] = {
        40, 8,48,16,56,24,64,32,
        39, 7,47,15,55,23,63,31,
        38, 6,46,14,54,22,62,30,
        37, 5,45,13,53,21,61,29,
        36, 4,44,12,52,20,60,28,
        35, 3,43,11,51,19,59,27,
        34, 2,42,10,50,18,58,26,
        33, 1,41, 9,49,17,57,25,
};

/*
 * Permuted-choice 1 from the key bits
 * to yield C and D.
 * Note that bits 8,16... are left out:
 * They are intended for a parity check.
 */
static  char    PC1_C[] = {
        57,49,41,33,25,17, 9,
         1,58,50,42,34,26,18,
        10, 2,59,51,43,35,27,
        19,11, 3,60,52,44,36,
};

static  char    PC1_D[] = {
        63,55,47,39,31,23,15,
         7,62,54,46,38,30,22,
        14, 6,61,53,45,37,29,
        21,13, 5,28,20,12, 4,
};

/*
 * Sequence of shifts used for the key schedule.
 */
static  char    shifts[] = {
        1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1,
};

/*
 * Permuted-choice 2, to pick out the bits from
 * the CD array that generate the key schedule.
 */
static  char    PC2_C[] = {
        14,17,11,24, 1, 5,
         3,28,15, 6,21,10,
        23,19,12, 4,26, 8,
        16, 7,27,20,13, 2,
};

static  char    PC2_D[] = {
        41,52,31,37,47,55,
        30,40,51,45,33,48,
        44,49,39,56,34,53,
        46,42,50,36,29,32,
};

static struct _crypt {
        /*
         * The C and D arrays used to calculate the key schedule.
         */
        char    _C[28];
        char    _D[28];
        /*
         * The key schedule.
         * Generated from the key.
         */
        char    _KS[16][48];
        /*
         * The E bit-selection table.
         */
        char    _E[48];
        /*
         * The current block, divided into 2 halves.
         */
        char    _L[32], _R[32];
        char    _tempL[32];
        char    _f[32];
        /*
         * The combination of the key and the input, before selection.
         */
        char    _preS[48];
        /*
         * Temps for crypt
         */
        char    _ablock[66], _iobuf[16];
} *__crypt;
#define C       (_c->_C)
#define D       (_c->_D)
#define KS      (_c->_KS)
#define E       (_c->_E)
#define L       (_c->_L)
#define R       (_c->_R)
#define tempL   (_c->_tempL)
#define f       (_c->_f)
#define preS    (_c->_preS)
#define ablock  (_c->_ablock)
#define iobuf   (_c->_iobuf)

static void     _cryptinit(void);

/*
 * Set up the key schedule from the key.
 */

#ifndef CRYPT
static
#endif
void
setkey(char *key)
{
        int i, j, k;
        int t;
        struct _crypt *_c = __crypt;

        if (!_c) {
                _cryptinit();
                _c = __crypt;
        }
        /*
         * First, generate C and D by permuting
         * the key.  The low order bit of each
         * 8-bit char is not used, so C and D are only 28
         * bits apiece.
         */
        for (i=0; i<28; i++) {
                C[i] = key[PC1_C[i]-1];
                D[i] = key[PC1_D[i]-1];
        }
        /*
         * To generate Ki, rotate C and D according
         * to schedule and pick up a permutation
         * using PC2.
         */
        for (i=0; i<16; i++) {
                /*
                 * rotate.
                 */
                for (k=0; k<shifts[i]; k++) {
                        t = C[0];
                        for (j=0; j<28-1; j++)
                                C[j] = C[j+1];
                        C[27] = t;
                        t = D[0];
                        for (j=0; j<28-1; j++)
                                D[j] = D[j+1];
                        D[27] = t;
                }
                /*
                 * get Ki. Note C and D are concatenated.
                 */
                for (j=0; j<24; j++) {
                        KS[i][j] = C[PC2_C[j]-1];
                        KS[i][j+24] = D[PC2_D[j]-28-1];
                }
        }
}

/*
 * The E bit-selection table.
 */
static  char    e[] = {
        32, 1, 2, 3, 4, 5,
         4, 5, 6, 7, 8, 9,
         8, 9,10,11,12,13,
        12,13,14,15,16,17,
        16,17,18,19,20,21,
        20,21,22,23,24,25,
        24,25,26,27,28,29,
        28,29,30,31,32, 1,
};

/*
 * The 8 selection functions.
 * For some reason, they give a 0-origin
 * index, unlike everything else.
 */
static  char    S[8][64] = {
        14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
         0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
         4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
        15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13,

        15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
         3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
         0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
        13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9,

        10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
        13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
        13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
         1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12,

         7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
        13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
        10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
         3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14,

         2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
        14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
         4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
        11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3,

        12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
        10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
         9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
         4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13,

         4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
        13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
         1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
         6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12,

        13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
         1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
         7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
         2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11,
};

/*
 * P is a permutation on the selected combination
 * of the current L and key.
 */
static  char    P[] = {
        16, 7,20,21,
        29,12,28,17,
         1,15,23,26,
         5,18,31,10,
         2, 8,24,14,
        32,27, 3, 9,
        19,13,30, 6,
        22,11, 4,25,
};


/*
 * The payoff: encrypt a block.
 */

void
encrypt(char *block, int edflag)
{
        int     i, ii;
        int t, j, k;
        struct _crypt *_c = __crypt;

        if (!_c) {
                _cryptinit();
                _c = __crypt;
        }
        /*
         * First, permute the bits in the input
         */
        for (j=0; j<64; j++)
                L[j] = block[IP[j]-1];
        /*
         * Perform an encryption operation 16 times.
         */
        for (ii=0; ii<16; ii++) {
                /*
                 * Set direction
                 */
#ifdef CRYPT
                if (edflag)
                        i = 15-ii;
                else
#endif
                        i = ii;
                /*
                 * Save the R array,
                 * which will be the new L.
                 */
                for (j=0; j<32; j++)
                        tempL[j] = R[j];
                /*
                 * Expand R to 48 bits using the E selector;
                 * exclusive-or with the current key bits.
                 */
                for (j=0; j<48; j++)
                        preS[j] = R[E[j]-1] ^ KS[i][j];
                /*
                 * The pre-select bits are now considered
                 * in 8 groups of 6 bits each.
                 * The 8 selection functions map these
                 * 6-bit quantities into 4-bit quantities
                 * and the results permuted
                 * to make an f(R, K).
                 * The indexing into the selection functions
                 * is peculiar; it could be simplified by
                 * rewriting the tables.
                 */
                for (j=0; j<8; j++) {
                        t = 6*j;
                        k = S[j][(preS[t+0]<<5)+
                                (preS[t+1]<<3)+
                                (preS[t+2]<<2)+
                                (preS[t+3]<<1)+
                                (preS[t+4]<<0)+
                                (preS[t+5]<<4)];
                        t = 4*j;
                        f[t+0] = (k>>3)&01;
                        f[t+1] = (k>>2)&01;
                        f[t+2] = (k>>1)&01;
                        f[t+3] = (k>>0)&01;
                }
                /*
                 * The new R is L ^ f(R, K).
                 * The f here has to be permuted first, though.
                 */
                for (j=0; j<32; j++)
                        R[j] = L[j] ^ f[P[j]-1];
                /*
                 * Finally, the new L (the original R)
                 * is copied back.
                 */
                for (j=0; j<32; j++)
                        L[j] = tempL[j];
        }
        /*
         * The output L and R are reversed.
         */
        for (j=0; j<32; j++) {
                t = L[j];
                L[j] = R[j];
                R[j] = t;
        }
        /*
         * The final output
         * gets the inverse permutation of the very original.
         */
        for (j=0; j<64; j++)
                block[j] = L[FP[j]-1];
}

char *
_crypt(char *pw, char *salt)
{
        int i, j, c;
        int     temp;
        struct _crypt *_c = __crypt;

        if (!_c) {
                _cryptinit();
                _c = __crypt;
        }
        for(i=0; i<66; i++)
                ablock[i] = 0;
        for(i=0; (c= *pw) && i<64; pw++){
                for(j=0; j<7; j++, i++)
                        ablock[i] = (c>>(6-j)) & 01;
                i++;
        }

        setkey(ablock);

        for(i=0; i<66; i++)
                ablock[i] = 0;

        for(i=0;i<48;i++)
                E[i] = e[i];

        for(i=0;i<2;i++){
                c = *salt++;
                iobuf[i] = c;
                if(c > 'Z')
                        c -= 6;
                if(c > '9')
                        c -= 7;
                c -= '.';
                for(j=0;j<6;j++){
                        if((c>>j) & 01){
                                temp = E[6*i+j];
                                E[6*i+j] = E[6*i+j+24];
                                E[6*i+j+24] = temp;
                        }
                }
        }

        for(i=0; i<25; i++)
                encrypt(ablock,0);

        for(i=0; i < 11; i++) {
                c = 0;
                for(j=0; j<6; j++){
                        c <<= 1;
                        c |= ablock[6*i+j];
                }
                c += '.';
                if(c > '9')
                        c += 7;
                if(c > 'Z')
                        c += 6;
                iobuf[i+2] = c;
        }
        iobuf[i+2] = 0;
        if(iobuf[1]==0)
                iobuf[1] = iobuf[0];
        return(iobuf);
}

static void
_cryptinit(void)
{
        struct _crypt *_c = __crypt;
        int i;

        if (_c)
                return;
        _c = __crypt = (struct _crypt *)calloc(1, sizeof (struct _crypt));
        if (_c == 0)
                abort();

        for(i=0;i<48;i++)
                E[i] = e[i];
}


void main()
{

        char hash[]="5qHv/iv0ODpLg";
        char salt[2];
        char * new_hash;
        char password[]="abcd";

        strncpy(salt,hash,2);

        new_hash =  _crypt(password,salt);

        if( strcmp(hash, new_hash) == 0)
                printf("PASSWORD FOUND\n");
        else
                printf("password NOT found\n");


}

3) If that is combined algorithm like md5(md5(key)) - if md5 hash is binary, or text. If that is text - if it is 8 bit text, or unicode (like in MS CACHE)

4) Examples key->hash, at least 4-5, with keys with different lengths

Code: Select all

Password: a      Salt: 5q    HASH: 5qIWUfsWUzOHM
Password: ab     Salt: 5q    HASH: 5qevGRMb9Z2jI
Password: abc    Salt: 5q    HASH: 5qBuWo16i4.kE
Password: abcd   Salt: 5q    HASH: 5qHv/iv0ODpLg
Password: ab     Salt: 4q    HASH: 4qLNyMlJBpjps
Password: abc    Salt: ca    HASH: carjeKAN635/I
Password: abcd   Salt: 45    HASH: 45Yl02wkqll.c

Ido
Posts: 2
Joined: Tue Oct 14, 2008 2:06 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Request: UNIX crypt (DES based)

Post by Ido » Tue Oct 21, 2008 5:35 pm

Tested the client you linked to and just wondering why GPU goes slower then CPU or iam i wrong?

reg
Posts: 4
Joined: Mon Oct 20, 2008 7:42 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Request: UNIX crypt (DES based)

Post by reg » Thu Oct 23, 2008 7:51 am

Tested too the client (8800 GTX), it sucks... 2.5M p/s very slow... (on a single core cpu you can reach 1M p/s without problem).

I hope will be implemented on BarsWF ;)

x4d3
Posts: 29
Joined: Tue Oct 14, 2008 4:10 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Request: UNIX crypt (DES based)

Post by x4d3 » Tue Nov 04, 2008 5:10 pm

Just a status update.

Working for the simplest cases:

Image

Few more days to finish the release and do some otimizations.

x4d3

reg
Posts: 4
Joined: Mon Oct 20, 2008 7:42 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Request: UNIX crypt (DES based)

Post by reg » Tue Nov 04, 2008 10:29 pm

:joy: :joy:

I just saw that "Extreme GPU Bruteforcer" as implemented unix des too, but seem slow... are you getting the same problem or it's just him code?

Thank you a lot for your work

x4d3
Posts: 29
Joined: Tue Oct 14, 2008 4:10 am
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Request: UNIX crypt (DES based)

Post by x4d3 » Tue Nov 04, 2008 11:11 pm

reg wrote::joy: :joy:

I just saw that "Extreme GPU Bruteforcer" as implemented unix des too, but seem slow... are you getting the same problem or it's just him code?

Thank you a lot for your work

Do you have any benchmark on that one, so I can compare?

RudiRatlos
Posts: 4
Joined: Tue Nov 04, 2008 4:49 pm
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Re: Request: UNIX crypt (DES based)

Post by RudiRatlos » Tue Nov 04, 2008 11:37 pm

egb des(unix)
Hashes: 1. Average speed: 1.56M p/s.
and xzerg version
DES(Unix) V2.01 Win:v5.01
1:CudaV1.01 GeForce 9800 GTX, Processors: 128 Clock rate: 1.674 Mg.
CharSet loweralpha-numeric = abcdefghijklmnopqrstuvwxyz0123456789
Restart ---- AT
Salt DES(Unix) count 1
Start with 2 passwords 7-8
001 001 etvekma Speed = 4361 k.pas/sec Time: 0.00.08

Post Reply
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable

Who is online

Users browsing this forum: No registered users and 1 guest