[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sun, 30 Sep 2007 20:32:38 -0700 (PDT)
From: ByteRage <byterage@...oo.com>
To: john-users@...ts.openwall.com
Subject: potential MySQL optimization
Given the MySQL password hash function:
Code:
void
hash_password(ulong *result, const char *password) {
register ulong nr = 1345345333L, add = 7, nr2
= 0x12345671L;
ulong tmp;
for (; *password ; password++) {
if (*password == ' ' || *password ==
'\t')
continue;
tmp = (ulong) (unsigned char)
*password;
nr ^= (((nr & 63) + add) * tmp) + (nr
<< 8);
nr2 += (nr2 << 8) ^ nr;
add += tmp;
}
result[0] = nr & (((ulong) 1L << 31) -1L);
result[1] = nr2 & (((ulong) 1L << 31) -1L);
}
We can clearly see 2 new unsigned longs are being
calculated for every new character of the passwords
within the for-loop.
This enables an optimization where the cracker
enumerates the passwords as follows to crack the
hashes faster by keeping track of the intermediate 2
unsigned longs:
when checking 2 character passwords:
character1: 'A'
(calculate 2 ulong values for "A", store in array at
pos 0)
character2: 'A'-'Z' (based on the value in array at
pos 0)
character1: 'B'
character2: 'A'-'Z'
...
when checking 3 character passwords:
character1: 'A'
(calculating 2 ulong values for "A", store in array at
pos 0)
character2: 'A'
(calculating 2 ulong values for "AA", store in array
at pos 1)
character3: 'A'-'Z' (based on the value in array at
pos 1)
etc...
(there's code on the internet that implements this
faster mysql cracking method)
A possible improvement which I think is potentially
useful for optimizing the MySQL module in JtR is to
use a hashtable as follows:
Keep track of checked passwords:
pwds[pwd char1 % ...][pwd char2 % ...]... = "..."
Keep track of 2 ulongs for every precalculated char in
the cached pwds:
prec[pwd char1 % ...][pwd char2 %
...]...[MAXPRECALCULATEDLEN][2] = "..."
Now it is possible to have a speed optimization due to
matching prefixes between checked passwords and those
that are being checked.
Example:
MAXPRECALCULATEDLEN = 6
char indexes go through % 32 f.e., space required:
32*32*32*6 bytes (192kB) for pwds 32*32*32*6*2*4 bytes
(1536kB) for unsigned longs of all prefixes
123456 was checked, hence
pwds[1][2][3] = "123456"
prec[1][2][3][0][0] & prec[1][2][3][0][1]
precalculated values for "1"
prec[1][2][3][1][0] & prec[1][2][3][1][1]
precalculated values for "12"
prec[1][2][3][2][0] & prec[1][2][3][2][1]
precalculated values for "123"
prec[1][2][3][3][0] & prec[1][2][3][3][1]
precalculated values for "1234"
prec[1][2][3][4][0] & prec[1][2][3][4][1]
precalculated values for "12345"
prec[1][2][3][5][0] & prec[1][2][3][5][1]
precalculated values for "123456"
"12aze" is to be checked, "12" matches and needn't be
calculated, calculation continues from prefix "12"...
"1234abcd" is to be checked, "1234" matches and
needn't be calculated, calculation continues from
prefix "1234"...
cheers,
Joachim De Zutter
____________________________________________________________________________________
Luggage? GPS? Comic books?
Check out fitting gifts for grads at Yahoo! Search
http://search.yahoo.com/search?fr=oni_on_mail&p=graduation+gifts&cs=bz
--
To unsubscribe, e-mail john-users-unsubscribe@...ts.openwall.com and reply
to the automated confirmation request that will be sent to you.
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
