Pablo Averbuj

Multiple Hashing for Security

With all the talk of MD5 and SHA-1 collision attacks it got me wondering the other morning: would storing two different hashes of the same data result in a more secure environment rather than just moving on to the next new hash algorithm?It’s not an easy case to make, but suspend disbelief for me.

The case I’m addressing is one of hashes as signatures, such as software delivery. The collision risk here is that an attacker breaks into a popular source of software (let’s say gnu.org) and replaces the good files with compromised files that share the same size/hash. When a user downloads the file and compares the hashes they find a match and proceed to trust the software. But what if instead of just providing the result of a single hash (let’s say MD5) the provider supplied both SHA-1 and MD5 hashes of the file. Now an attacker has to compose a file that collides on both algorithms. As a general method (regardless of algorithms) this seems like it would mitigate attacks and give longer life to hash implementations.

Consider Debian for a moment. The Debian package lists include a MD5 hash of the package file. If/when they decide to switch to SHA-256 (a reasonable choice right now), it would require a lot of retooling. Since they have to keep the MD5 hashes anyway for backwards compatibility, why not retool to support both hashes. Now an attacker who compromises a package has (what I would imagine to be) an exponentially more difficult task.

My coworker, Will, brought up an interesting question. In the case where the data is secret such as storing the hash of a password, does computing multiple hashes of the secret data provide an opportunity for an attacker to glean information about the secret data? Storing two hashes of a password would slightly decrease the efficacy of brute-force attacks, but also increase the efficacy of attack via rainbow tables. If there’s a potential for information leakage the medicine may be worse than the disease.

Update: Doug found a paper that addresses the first part of the question here. It concludes that concatenation is a hedge, but doesn’t quantify how much value it adds.