[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 1 Dec 2007 05:50:37 +0300
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: 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".
> Also, the comments on MD5 bitslice were interesting, did anyone notice
> the claims in the media recently that Nick Breese was able to compute
> 1.4 billion hashes per second on a PS3?
I've just Google'd around to figure out what this was about. My guess
is that it's 1.4 billion partial computations of another cryptographic
primitive per second, not MD5. Probably RC4, as many articles mention
Office "documents" and the like.
> Could anyone here verify how fast Solars MD5 implementation runs on PS3??
This makes little sense. If you're referring to the proof-of-concept
bitslice implementation, then it's just that - a proof-of-concept. As
you know, it's just C code, and not the most optimal at that. More
importantly, we also know that Cell SPUs are good for implementing MD5
in the straightforward 4-way SIMD way. If they lacked bit rotates or
something, things could be different.
As to the MD5 implementation in JtR (for MD5-based crypt(3) hashes), it
only uses 32-bit words, no SIMD. The best it knows to do is mix
instructions for two MD5 computations for greater instruction-level
parallelism and to cover large instruction latencies.
Obviously, a future version of JtR should have improvements in this area.
> 1.4 billion p/s seems extremely fast..is it possible?
Probably not for MD5. Although this article specifically mentions MD5:
http://www.heise-security.co.uk/news/99674
it also almost correctly estimates that this would mean around 50 clock
cycles per "iteration". If the main CPU is used in addition to the
SPEs, this required minimum number of cycles per "iteration" to achieve
1.4 billion "iterations" per second would increase - maybe even by as
much as 50% since the main CPU is multiple-issue. So this gives us an
upper boundary for the number of cycles per "iteration" of around 80.
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.
Thus, no, 1.4 billion MD5s per second on a PS3 seems unrealistic, while
a few hundred million is realistic.
> has anyone seen Nicks presentation, or indeed code
I have not.
> 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.
--
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@...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.
