GPU cracking source code.

Martyr

Some source codes for calculating MD5 hashes using the GeForce 8 series GPU and CUDA SDK have been posted online recently.

http://majuric.org/software/cudamd5/

The performance isn't that impressive tbh, but the code is there to be modified freely - its not optimized for GPU AFAIK.

Although Elcomsoft have claimed to do this first since October last year, there was no source code provided.

Computing on the GPU has become popular in the last year (although its been discussed for good number of years now) since the CUDA SDK came out.

At blackhat europe 2k8, due to take place now in couple of days - Nick Breese will apparently unveil source code to his 'Crackstation' project using a PS3.

He claims that the code calculates close to 2 billion md5 hashes a second..which would mean administrators seriously having to re-consider what crypto to use for passwords.

ressem

There have been methods described and implemented of generating an MD5 collision using a standard laptop in under a minute.
http://eprint.iacr.org/2006/105.pdf

Replacing MD5 authentication seems easier said than done though. Take a Redhat linux server and it's user logins. You would think that they would have added twofish, aes or even blowfish hashing to supplement MD5 and DES in pam_unix.so or a replacement library.

However there doesn't appear to be a port of Debian's libpam_unix2.so (which supports the old blowfish), so you're stuck with learning and setting up kerberos 5 or the like.

Martyr

MD5Crypt is still pretty good IMHO, but if Nicks claims are valid, it would be possible to test 2 million MD5Crypt hashes a second..
Normally, a desktop PC computes < 10,000 k/s using JTR.

i noticed that sha-crypt is based on md5crypt and is planned to be replacement at some point in future.

It has the main difference of using either SHA-256 or SHA-512 with a modular number of rounds in the main loop..looks good, but i think bcrypt is still stronger.

Martyr

i was lookin recently to optimize md5crypt for parallel implementation, and i noticed that this routine is main cpu intensive task.

[PHP] /*
* And now, just to make sure things don't run too fast. On a 60 MHz
* Pentium this takes 34 msec, so you would need 30 seconds to build
* a 1000 entry dictionary...
*/
for (i = 0; i < 1000; i++) {
MD5_Init(&ctx1);

if ((i & 1) != 0)
MD5_Update(&ctx1, (const unsigned char *)pw, pwl);
else
MD5_Update(&ctx1, final, 16);

if ((i % 3) != 0)
MD5_Update(&ctx1, (const unsigned char *)sp, sl);

if ((i % 7) != 0)
MD5_Update(&ctx1, (const unsigned char *)pw, pwl);

if ((i & 1) != 0)
MD5_Update(&ctx1, final, 16);
else
MD5_Update(&ctx1, (const unsigned char *)pw, pwl);

MD5_Final(final, &ctx1);
}[/PHP]

the above code only ever generates 8 different combinations of the password,salt and hash.
its possible to store an index of each different buffer in an array.

[PHP]; *****************************************************************
;
; The logical/arithmetic tests in the main 1000 iterative loop
; can be simplified using a 42 element array.
;
; Each element represents a buffer that will be processed by md5
;
buf_index dd 0,1,2,3,2,1,4
dd 5,2,3,2,1,4,1
dd 6,3,2,1,4,1,2
dd 7,2,1,4,1,2,3
dd 6,1,4,1,2,3,2
dd 5,4,1,2,3,2,1
dd 0[/PHP]

and the loop is simplified

[PHP] mov ebx,1000
mov ebp,42

hash_loop:
mov esi,[buf_index+4*ebp] ; load buffer index
mov edi,[buf_index+4*ebp-4] ; load next buffer index

mov esi,[buf_ptr +4*esi] ; load start of buffer
mov edi,[buf_ptr2+4*edi] ; load next buffer

call md5_block_x86_one ; process input

sub ebp,1 ; decrease buffer index
jnz decrease_loop

mov ebp,42 ; re-initialize index

decrease_loop:
sub ebx,1
jnz hash_loop[/PHP]

this allows the algorithm, including the new SHA-Crypt routine to be attacked on SIMD architectures efficiently, because the buffers only have to be initialized once, not 1000 or N times for either algorithm.

Martyr

Nick Breese gave his presentation on PS3 cracking MD5.

Considering to buy a PS3 for experiments with other algorithms..but i'm still a little perplexed about the calculations that he claims its capable of computing that everyone else seems to have missed..

In the presentation, there is a comparison chart of computing 10,000,000 hashes on a Centrino 2.2 Ghz CPU and the PS3 SPE's - using a scaler version of MD5.
The centrino takes about ~2.5 seconds and with PS3 ~2.1 seconds.

Neither of those are impressive and sound very slow IMO, a SIMD implementation on Q6600 can compute ~80,000,000 k/s

Then there is the CELL (PS3) SIMD version which is claimed can compute 1.9 billion calculations per second..that is fast, but is it realistic?

The only speed test for each SPE thread is 80 million iterations, which i thought was strange..given 6 SPE's - each one would be computing ~320 million k/s

The data input is hardcoded - you'll know that compilers with optimization usually omit alot of instructions for this, i'm wondering if this is anyway the reason for its fast speed??

has anyone done any programming for CELL or PS3 so far?

PDF presentation

MD5-SPU source code

Martyr

Andrey Belenko from elcomsoft is giving talk at www.troopers08.org

Step-by-step tutorial on how to write basic MD5 password cracker for GPU. Video, source code and slides should be available on website after 24th of April.

Nick breese currently gets 80 million keys a second on ps3, seems his timings were all wrong!

it was the optimization part that killed it