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 majord...@metzdowd.com