hedging our bets -- in case SHA-256 turns out to be insecure

[Sandy Harris]

On 11/8/09, Zooko Wilcox-O'Hearn <zooko at zooko.com> wrote:

>  Therefore I've been thinking about how to make Tahoe-LAFS robust against
> the possibility that SHA-256 will turn out to be insecure.

NIST are dealing with that via the AHS process. Shouldn't you just use
their results?

>  We could use a different hash function ...
> There are fourteen candidates left in the SHA-3
> contest at the moment.  Several of them have conservative designs and good
> performance, but there is always the risk that they will be found to have
> catastrophic design flaws or that a great advance in hash function
> cryptanalysis will suddenly show how to crack them.

Yes, but there's also a risk that whatever you come up with will turn
out to be flawed.

>  I propose the following combined hash function C, built out of two hash
> functions H1 and H2:
>
>  C(x) = H1(H1(x) || H2(x))

This requires two hash(x) operations. A naive implementation needs
two passes through the data and avoiding that does not appear to
be trivial. This is not ideal since you seem very concerned about
overheads.

What about this construction:

  C(x) = H1(H2(x) || H3(x))

H1 is something that gives the output size you require. Use SHA-256 or
choose an AHS candidate conservatively. This only hashes a few blocks
so you need not worry much about overheads here.

H2 is the 512-bit variant of a different AHS candidate, or Whirlpool, or
even Skein-1024. Here speed is a criterion, though of course not the
only one.

H3 might be some really cheap fast function invented for the situation.
As I recall, the GOST hash just used a sum of input blocks, and that's
enough to defeat the multi-block attacks. If it is simple enough, you
can code it into your implementation of H2 so you only need one
pass.

Since you are encrypting the files anyway, I wonder if you could
use one of the modes developed for IPsec where a single pass
with a block cipher gives both encrypted text and a hash-like
authentication output.  That gives you a "free" value to use as
H3 in my scheme or H2 in yours, and its security depends on
the block cipher, not on any hash.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com