[tor-dev] SHA-3 isn't looking so hot to me (was: Draft sketch document with ideas for future crypto ops)

[Zooko O'Whielacronx]

On Tue, Nov 1, 2011 at 1:36 PM, Watson Ladd <watsonbladd at gmail.com> wrote:
>
>> See Fig. 17 of http://eprint.iacr.org/2009/510.pdf .
>
> Its wonderful that you provided references, and even told me what diagram to look for.
> But figure 17 has every finalist other then Skein outperforming SHA2 in hardware (last column is bits per second), and that was optimizing for speed. In the case of Keccak, that performance is impressively greater. Its possible at the 512 level these reverse, but I don't see that in there.

I'm sorry, once again I failed to spell out explicitly what I was thinking.

In this case it is that the relevant metric is area rather than
throughput. This is because of what Marsh Ray brought up—the prospect
that future chips might come with a SHA-3 or a SHA-256 circuit built
in. The advantage to a chip designer of adding such a circuit in is,
of course, that their customers may want it and so buy their chip
instead of their competitors'. The disadvantage is the cost in design
complexity (~= time) and die area (~= marginal cost to print one of
these chips). I'm told that some of these embedded chips are
exquisitely sensitive to marginal costs, such that a few pennies can
make the difference between success and failure of the product!

Therefore, in the context of whether we can expect SHA-3 and/or
SHA-256 circuits to come built into our chips in the future, the fact
that SHA-256 can be implemented in a smaller circuit means it would be
cheaper for a chip maker to include it.

As for performance, note that the vertical axis of Fig. 17 is in
Gbit/s. Even the slowest implementation of SHA-256 was at something
like 0.8 Gbit/s, which is about 0.1 Gbyte/s which is about 100
MByte/s, which is more than any one circuit will probably be asked to
handle. If the chip designer expects the user to need more than 100
MByte/s throughput, he can put multiple circuits in there. For example
the new SPARC T4 chip comes with 8 CPU cores, each with its own
SHA-256 circuit (as well as AES and other algorithms).

On the other hand, I still think back to Marsh's observation that the
*perception* of superiority of SHA-3 over SHA-2 might mean that the
actual chips of the future come with SHA-3 even if it is more
expensive.

Oh neat! I just learned that the 64-bit ARMv8 is going to come with
SHA-256: http://www.theregister.co.uk/2011/10/28/arm_holdings_arm_v8/

Very cool.

Another factor which might prolong SHA-256's life is its role as the
proof-of-work in Bitcoin. This causes there to be a global race for
efficient SHA-256 implementation, and whoever gets even a little bit
ahead in that race can rake in profits. The current leading
technologies are ATI GPUs and FPGAs, but if there were a chip with an
efficient enough SHA-256 built in, perhaps they could sell it to
Bitcoin miners.

Regards,

Zooko