Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 12 Nov 2007 07:00:21 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: bitslice MD5 (was: bitslice implementation of ORACLE hash cracking)

I wrote:
> > As to SHA-1 (as well as MD4 and MD5, for that matter), bitslice
> > implementations are possible,

On Sun, Nov 11, 2007 at 07:38:02PM +0000, Larry Bonner wrote:
> have you got or know of any code that demonstrates it? to play around with.

I've attached my proof-of-concept bitslice implementation of the MD5
compression function.  Very recent versions of gcc are able to
meaningfully compile this into SSE2 code (and likely AltiVec as well,
but I have not tested that).  The performance is not impressive, but
there's lots of room for improvement.

On Athlon64 3200+ (2.0 GHz) running Linux/x86-64 (Owl-current), I get:

amd!solar:~/md5slice$ gcc md5slice.c -o md5slice -Wall -s -O3 -fomit-frame-pointer -funroll-loops
amd!solar:~/md5slice$ time ./md5slice
vector size = 64 bits
c09c4c1f 21876746 18aed2 70b452f0

real    0m0.463s
user    0m0.460s
sys     0m0.010s

amd!solar:~/md5slice$ PATH=~/gcc-4.1.0/bin:$PATH gcc md5slice.c -o md5slice -Wall -s -O3 -fomit-frame-pointer -funroll-loops -DVECTOR
amd!solar:~/md5slice$ time ./md5slice
vector size = 128 bits
c09c4c1f 21876746 18aed2 70b452f0

real    0m0.388s
user    0m0.390s
sys     0m0.000s

The latter corresponds to roughly 2.5 million computations of the MD5
compression function per second, which is 3 times lower than what the
double-MD5 code currently in JtR achieves on the same system:

amd!solar:~$ john -te -fo=md5
Benchmarking: FreeBSD MD5 [32/64 X2]... DONE
Raw:    7458 c/s real, 7458 c/s virtual

(these numbers need to be multiplied by 1000 to get the number of MD5
compression function computations).

Feel free to experiment with this on Core 2, on AltiVec, with more
recent gcc, and to improve the implementation.

-- 
Alexander Peslyak <solar at openwall.com>
GPG key ID: 5B341F15  fp: B3FB 63F4 D7A3 BCCC 6F6E  FC55 A2FC 027C 5B34 1F15
http://www.openwall.com - bringing security into open computing environments

View attachment "md5slice.c" of type "text/plain" (7785 bytes)

-- 
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.