headers
Solar Designer | 1 Dec 2007 03:50
Favicon

Re: AES Bitslice and the PS3 MD5 cracking.

On Fri, Nov 30, 2007 at 11:01:38PM +0000, Larry Bonner wrote:
> I hope Solar Designer doesn't mind me putting this question to some on
> the mailing list.

It's OK as long as these discussion threads don't run for too long, and
the majority of postings are still directly related to JtR.

> I'm just curious how complicated it would be to implement AES as a
> bitslice algorithm, as i've read that for CORE2 CPU, its actually
> faster than "normal" way to compute AES.

I haven't looked into this myself, but it's quite possible.  A Google
search for "bitslice AES" (without the quotes) gives some references,
including to a sci.crypt discussion that ended with:

"Short answer: yes, on architectures with 128 bits words or more."

As to your "how complicated" question, I think it's the same order of
complexity for most popular ciphers and cryptographic hashes that are
reasonable to implement in this way at all.  Things can get a lot more
difficult when you try to achieve a certain level of performance - such
as to outperform another implementation.

The URL for a presentation on PS3/Cell that I had posted a while ago:

	http://www.hyperelliptic.org/SPEED/slides/Osvik_cell-speed.pdf

also briefly describes a non-bitslice but architecture-specific
implementation of AES for the Cell and mentions that "bitslice AES would
be very interesting".
(Continue reading)

Permalink | Reply | 7 comments |
headers
Russell Fulton | 1 Dec 2007 07:54
Picon
Picon
Favicon

Re: AES Bitslice and the PS3 MD5 cracking.


Solar Designer wrote:
> to see if his claims are not just hype?
>   
>
> I doubt that he made such claims.  For example, he might have mentioned
> MD5 in some context, then proceeded to give numbers for RC4.  The press
> did the rest.  Of course, that's just my guess.
>
>   
I believe Nick to be a reputable researcher and I think Solar is correct
in his guess.  I should have been at the conference since it is local
(well Wellington is 500 miles away but it still a hell of a lot closer
than anything overseas ;)  but things were frantic at work and I never
got around to registering :(

I will see if I can get some more information about the details.

Russell.

--

-- 
To unsubscribe, e-mail
john-users-unsubscribe@... and reply
to the automated confirmation request that will be sent to you.
Permalink | Reply | 5 comments |
headers
Simon Marechal | 1 Dec 2007 12:56

Re: AES Bitslice and the PS3 MD5 cracking.

Solar Designer wrote:
> Well, a full MD5 compression function computation involves 64 rounds,
> with each round consisting of 7-8 operations.  Even if only half the
> rounds need to be computed (which might be possible when trying to match
> one specific hash value and trying candidate passwords in a hashing
> algorithm-dependent order) and each round is reduced to half the number
> of instructions (due to availability of suitable multi-op instructions -
> I have no idea if this is the case for the Cell - probably it is not),
> this still gives us over 100 instructions per "iteration".  Since the
> SPUs are single-issue, this is also the lower boundary for the number of
> clock cycles.

I did the same calculations and have the same conclusion. I wrote a POC
NT cracker that achieves 180M NT/s without any optimization (naive
implementation), so I guess that it should be possible to go faster than
200M MD5/s with a bit of work.

Using the PS3 devkit (7500$) would let a developper use the 7th core and
the GPU. It might be possible to use the GPU as elcomsoft claimed and
perhaps double that performance.

But the main conclusion of this presentation is totally true : you can
get your employer to buy you a PS3 :)

--

-- 
To unsubscribe, e-mail
john-users-unsubscribe@... and reply
to the automated confirmation request that will be sent to you.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Russell Fulton | 4 Dec 2007 04:43
Picon
Picon
Favicon

Re: AES Bitslice and the PS3 MD5 cracking.

Reading the paper reports in local computerworld we found that when they
quoted Nick directly he referred to md5 *cycles* per second.  My
knowledge of md5 is hazy at best but iirc for each hash there are 64 of
cycles.

Does this make sense?

Russell

Russell Fulton wrote:
> Solar Designer wrote:
>   
>> to see if his claims are not just hype?
>>   
>>
>> I doubt that he made such claims.  For example, he might have mentioned
>> MD5 in some context, then proceeded to give numbers for RC4.  The press
>> did the rest.  Of course, that's just my guess.
>>
>>   
>>     
> I believe Nick to be a reputable researcher and I think Solar is correct
> in his guess.  I should have been at the conference since it is local
> (well Wellington is 500 miles away but it still a hell of a lot closer
> than anything overseas ;)  but things were frantic at work and I never
> got around to registering :(
>
> I will see if I can get some more information about the details.
>
> Russell.
(Continue reading)

Permalink | Reply | 4 comments |
headers
Larry Bonner | 4 Dec 2007 18:55
Picon

Re: AES Bitslice and the PS3 MD5 cracking.

the media probably thought "1.4 billion" and "100 times faster"
sounded more sensational.

--

-- 
To unsubscribe, e-mail
john-users-unsubscribe@... and reply
to the automated confirmation request that will be sent to you.
Permalink | Reply | 0 comments |
headers
Erik Winkler | 4 Dec 2007 19:51
Picon

Re: bitslice MD5 (was: bitslice implementation of ORACLE hash cracking)

Finally got around to testing this on a PowerPC with altivec:

$gcc md5slice.c -o md5slice -Wall -s -O3 -fomit-frame-pointer -funroll- 
loops
$time ./md5slice
vector size = 32 bits
c09c4c1f 21876746 18aed2 70b452f0

real		0m1.847s
user	0m1.448s
sys		0m0.024s

$gcc md5slice.c -o md5slice -Wall -s -O3 -fomit-frame-pointer -funroll- 
loops -maltivec -DVECTOR
$ time ./md5slice
vector size = 128 bits
c09c4c1f 21876746 18aed2 70b452f0

real		0m0.545s
user	0m0.456s
sys		0m0.008s

The vectorized version shows a significant speed increase.  This is a  
1.33 Ghz G4 processor.

Erik

> 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-
(Continue reading)

Permalink | Reply | 0 comments |
headers
Solar Designer | 5 Dec 2007 01:21
Favicon

Re: PS3 MD5 cracking

On Tue, Dec 04, 2007 at 04:43:29PM +1300, Russell Fulton wrote:
> Reading the paper reports in local computerworld we found that when they
> quoted Nick directly he referred to md5 *cycles* per second.  My
> knowledge of md5 is hazy at best but iirc for each hash there are 64 of
> cycles.
> 
> Does this make sense?

I'm afraid not.  In MD5, there are four "rounds", where each round
consists of 16 "steps", although the word "step" is only used in the part
of RFC 1321 that describes differences between MD4 and MD5.  No "cycles".

Moreover, it hardly makes sense to refer to the rate of MD5 rounds or
steps computed per second because the four rounds are different - and
they are even more different in implementations optimized (or cut down)
for cracking just one MD5 hash.  Even the number of steps to compute for
a given round may be reduced.

BTW, I incorrectly referred to the steps as rounds in my previous posting.

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

--

-- 
To unsubscribe, e-mail
john-users-unsubscribe@... and reply
to the automated confirmation request that will be sent to you.
(Continue reading)

Permalink | Reply | 0 comments |
headers
madfran | 14 Dec 2007 16:41

hash from pwdump and external functions

Hi,

I donwload a hash from a Windows 2000 target using pwdump6.
The first half of the password it will cracked using LC5.
With the second half I have some problem and I am afraid I do some mistake.
I wonder in the second half are some special character and I try to use
the external functions of John.

The external function is:

**********************************************************************
[List.External:prepend-pims]
void init()
{
        int i;

	word[0] = 'A';
	word[1] = '%';
	word[2] = 'D';
	word[3] = 'M';
	word[4] = 'I';
	word[5] = 'N';
	word[6] = '7';
	word[7] = 'I';
	word[8] = 0x20;
	word[9] = 0x20 - 1;
	word[10] = 0x20 - 2;
	word[11] = 0x20 - 3;
	word[12] = 0x20 - 4;
	word[13] = 0x20 - 5;
(Continue reading)

Permalink | Reply | 1 comment |
headers
Solar Designer | 15 Dec 2007 06:11
Favicon

Re: hash from pwdump and external functions

On Fri, Dec 14, 2007 at 04:41:44PM +0100, madfran wrote:
> I donwload a hash from a Windows 2000 target using pwdump6.
> The first half of the password it will cracked using LC5.

Chances are that JtR with default settings would crack it a bit quicker.

> I wonder in the second half are some special character and I try to use
> the external functions of John.
...
> [List.External:prepend-pims]
> void init()
> {
>         int i;

You aren't using that variable in init().

> 	word[0] = 'A';
> 	word[1] = '%';
> 	word[2] = 'D';
> 	word[3] = 'M';
> 	word[4] = 'I';
> 	word[5] = 'N';
> 	word[6] = '7';

The above sets the known password half.  It would make sense, except
that JtR cracks the LM hash halves separately - so you do not need to
provide the first half at all when you're after the second one.

For the same reason, you don't need to go for lengths beyond 7.
(Continue reading)

Permalink | Reply | 0 comments |

Gmane