Math/crypto question

[dsrtao]

Let's say I have downloaded a file and I want to make sure of its integrity. The source has provided a hash and widely distributed it, so I'm fully convinced that the hash is genuine.

Given that the source has provided an MD5 hash and a SHA-1 hash, is it significantly more difficult for Mallory to come up with engineered malware that fits both the MD5 hash and the SHA-1 hash, than it is to duplicate one but not the other? How much more difficult?

The computational cost to the source of providing both hashes is relatively small -- they do about twice the work they would have otherwise. The computational cost to me is the same increase.

Let's suppose that the file is quite large -- 200MB or so, the size of a Debian network-install boot CD. Mallory wants to write a payload that needs about 10MB of changes, and is OK with changing the other 190MB in any way necessary to match the hashes.

Comments

[metahacker.livejournal.com]

Depends on the independence of the two hashes. Taking a trivial example, imagine three idiotic hash functions:
Odd(n)
Even(n)
Prime(n)

Something hashed with both Odd and Even gains no security from being hashed by the other; the two functions are 0% independent. But something hashed with Prime gets a tiny improvement from being hashed by Even (100% correlated output except for the case of 2); the functions are 1/m independent, where m is the size of your output space.

Something like Even(n) and Log(n) are nearly independent; there is no correlation in their output.

My gut reaction is that f(g(n)) is about as secure as the product of f and g's security for completely independent (I.e. Ideal) hashes.

[metahacker.livejournal.com]

Better thought experiment: imagine two hashes, one of which just happens to output the first half of SHA-1, the other the second half...