Does a practical collision attack on a cryptographic hash function also mean it fails “indistinguishable from random data”?

Question

It is knowns that SHA-1 has been broken in practice using collision attacks. Related to SHA-1 this mainly had a negative impact on the security of

• Digital Certificate signatures
• Email PGP/GPG signatures
• Software vendor signatures
• Software updates
• ISO checksums
• Backup systems
• Deduplication systems
• etc.

Thinking about a LUKS related Q&A at our site, I'm wondering if a collision attack also means that the broken hash like SHA-1 can – or maybe even should - also be considered “distinguishable from random data” (from a cryptographic point of view).

Does a practical collision attack on a cryptographic hash function also mean we can (or should) consider it to fail “indistinguishable from random data”? Or does a collision attack have no influence on that?

Answer 1

Does a practical collision attack on a cryptographic hash function also mean we can (or should) consider it to fail “indistinguishable from random data”? Or does a collision attack have no influence on that?

For a random oracle with output length $n$, it takes $2^{n/2}$ time to find a collision. So if you have a hash function with output length $n$ as well but for which there's an attack that finds a collision in less than $2^{n/2}$ time, then the hash function doesn't behave like a random oracle, period. The function has some property that a random oracle does not have.

Note that even before we ever found a collision, we already knew that Merkle-Damgård hash functions like MD5, SHA-1 and SHA-2 don't behave like random oracles, because they're vulnerable to length extension attacks: for any choice of message $m$, an adversary who knows the result of $\mathrm{hash}(m)$ and the message length $|m|$ can use this knowledge to "shortcut" the calculation of $\mathrm{hash}(m || \mathrm{pad}(|m|) || s)$ for any choice of $s$. A random oracle doesn't have this property—knowing the hash for any message is of no help for predicting the hash of any extension of it.

This doesn't mean that it's impossible to find some construction that uses the hash function in a carefully restricted way such that its output is indistinguishable from random (and indeed, HMAC-SHA1 is claimed to be a pseudorandom function—a function such that if you pick a secret key at random, the adversary can't tell it apart from a random function). It means that from the point of view of an adversary that has control over the input of the hash function, they can very easily tell that it doesn't behave like a random function would.

(Note that I have been careful to talk about random oracles and random functions instead of just the outputs of a function; the very stringent question we ask of a hash function is how it behaves from the point of view of an adversary who can choose what inputs to feed to it. Again, this doesn't rule out the possibility that in a weaker attack model—one where the adversary has fewer powers—the adversary might not succeed.)

Answer 2

A collision attack essentially occurs as a consequence of an output being random, rather than not as you're suggesting. A collision occurs naturally around 2^(block width /2) inputs for any arbitrary pseudo random function. Biv's very detailed answer to how your SHAttered attack works shows much being made of the Merkle–Damgård architecture, supported by the nature of a PDF's internals.

The output of SHA1 is still as random looking as ever, and so we maintain this hash for random number generators like inside Java's SecureRandom and mixing inside /dev/random. There is still no distinguisher for a SHA1 stream. You will see that pseudo random generators /steam ciphers are not on the SHAttered list, and you can safely consider it's output as uniformly random.