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

[Osman Ugus]

Jerry Leichter <leichter <at> lrw.com> writes:

> 
> On Nov 8, 2009, at 6:30 AM, Zooko Wilcox-O'Hearn wrote:
> > I propose the following combined hash function C, built out of two  
> > hash functions H1 and H2:
> >
> > C(x) = H1(H1(x) || H2(x))
> I'd worry about using this construction if H1's input block and output  
> size were the same, since one might be able to leverage some kind of  
> extension attack.  That's not a problem for SHA256 or SHA512, but it's  
> something to keep in mind if this is supposed to be a general  
> construction, given that all likely hash functions will be constructed  
> by some kind of iteration over fixed-size blocks.
> 
> Rather than simply concatenating H1(x) and H2(x), you might do better  
> to interlace them.  Even alternating bytes - cheap enough that you'd  
> never notice - should break up any structure that designs of practical  
> hash functions might exhibit.  (As a matter of theory, a vulnerability  
> of alternate bytes is as likely as a vulnerability of leading bytes;  
> but given the way we actually build hash functions, as a practical  
> matter the latter seems much more likely.)
>                                                          -- Jerry
> 
>
 
Let me give also some comments on this construction:
C(x) = H1(H1(x) || H2(x))

I am not really sure, but, I think the above construction for C(X) is just as 
secure as H1.

let 
y = C(X) = H1(H1(X) || H2(X)) = H1(X') with X' = (X'1 || X'2)
 
Consider the H1(X') part of the construction. 2^(|H1|+|H2|)-bit inputs are 
mapped to 2^(|H1|)-bit outputs. This means for every output "y" that are 2^(|
H2|) possible inputs.

Now, consider the probability of the following event:

y = C(K) = H1(H1(K) || H2(K)) = H1(X').

That is

  = Pr[H1(K) = X'1 and H2(K) = X'2]*(2^(|H2|))
  = Pr[H1(K) = X'1] * Pr[ H2(K) = X'2] (since H1 != H2, also independent)
  = 1/2^(|H1|)

Obviously, this is equal to the security level of H1. 







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