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

[Jack Lloyd]

On Wed, Nov 11, 2009 at 10:03:45AM +0800, Sandy Harris wrote:

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

If performance is really an issue one could code a combined H1/H2
function which would interleave the operations, which would prevent
needing two passes (which _is_ really important since memory and disk
latencies are usually the biggest factor in performance). Direct
interleaving would also offer better ILP.

But even updating both hashes at the same time would prevent needing
two full passes; something like the code below would offer much better
cache utilization, and would not be at all difficult to implement:

while data_left:
  block = input.read_one_block()
  h1.compress(block)
  h2.compress(block)

If it was really important, choosing a nonstandard H2 could offer even
better performance; for instance let H1=SHA-256 and H2=SHA-~256, where
SHA-~256 is precisely SHA-256 but with all of its constants bitwise
inverted. One could compute both functions in parallel using SIMD
(SSE2, ARM's NEON, etc) [and they could share the message expansion,
which is quite costly in SHA-2]. It's not clear from a quick read of
the paper Zooko referenced ("On the Strength of the Concatenated Hash
Combiner when All the Hash Functions are Weak") if this would actually
meet the requirements of "sufficiently different" for the results
there to apply, though.

> What about this construction:
> 
>   C(x) = H1(H2(x) || H3(x))

One trouble with this construction that Zooko's does not have is that
it can fail even if H1 is collision resistant due to an inner
collision.

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

The GOST hash does use the sum of input blocks (as the final input to
the compression function) but it has a number of other components; it
is actually quite slow compared to modern hashes.

-Jack

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