hedging our bets -- in case SHA-256 turns out to be insecure
Osman Ugus
ugus11 at yahoo.com
Wed Nov 11 13:37:54 EST 2009
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
More information about the cryptography
mailing list