Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 18 Oct 2008 05:48:05 +0000 (UTC)
From:  Marc Bevand <m.bevand@...il.com>
To: john-users@...ts.openwall.com
Subject:  Re: Breaking UNIX crypt() on the PlayStation 3

Solar Designer <solar@...> writes:
> 
> Isn't the PPU capable of issuing more instructions per cycle (than the
> SPUs)?  If not more AltiVec instructions, then maybe more PowerPC
> instructions intermixed with AltiVec ones?

Oh you are right. The PPU is a dual-issue design. So I guess it
could be capable of 140-180% the perf of 1 SPU !

> > [...running sbox-gen for other arches...]
> This should probably be done, including for architectures that do have a
> mux instruction.

Yeah I think I'll try it.

> Yes.  It is also possible to start with any bit number, not necessarily
> bit 1, and proceed to add gates for other bits in any order - then
> choose the best solution.  This will make the search roughly 4! = 24
> times slower, which is two days instead of two hours.  Of course, this
> will likely not find the most optimal solution, so this approach can be
> combined with what you describe above.

sbox-gen already tries the 4! different possibilities of ordering the
output bits. And the 6! possibilities for the input bits as well.

> BTW, another way to "satisfy" the latencies for the Cell would be by
> using 256-bit or longer "virtual" vectors, with repeated instructions.
> You have enough registers for that.

Something Simon already suggested to me :) In reality I am already
using 64 of the 128 registers to store the 32 "left" and 32 "right"
bits of each DES Feistel round, and most of the 64 others to implement
the S-boxes. So I don't have that many unused registers and couldn't
implement that idea.

But fortunately I have been very happy with the results of manually
reordering the S-box instructions. Only a negligible number of
instructions depend on the immediately preceding one (2 or 3 per
S-box).

> > And maybe not worth 
> > it because a human can do these optimizations pretty easily, after you 
> > give him or her a good, low-gate count output of sbox-gen.
> 
> Have you tried doing that for MMX or 8-register SSE2?   It's not easy
> for a human to do at all.

Nope I haven't tried. But you are correct, it was much easier in my
case, I had 128 registers...

-marc


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