Does randomness prevent collision attacks?

Question

Google have recently announced a practical SHA-1 collision.

A few years ago MD5 had similar issues and researchers even created a fake CA.

This would not be possible today - even with MD5 - because CA's must include at least 20-bits of random data in the serial number (see Mozilla requirements).

My question is a bit more general: do collision attacks matter if signed messages include random data generated by the signer?

For all the uses of hashes, I think that it's only signatures where collisions matter. And then, only when the signer is signing a message from someone untrusted. Are there other use cases where it matters? And in this use case, if the signer always includes random data in the message, does that prevent collision attacks.

BTW, I still think ditching SHA-1 is a good idea, this question is more theoretical.

Answer 1

Yes, randomness that is controlled by the signer and that (crucially) is unpredictable by the attacker eliminates the potential for a collision to be generated, including the chosen-prefix style of collision attacks that were used by researcher to create a fake CA in 2008, and the authors of the Flame malware to create a fake signing certificate a few years later.

The reason is this: To create a collision attack, the attacker must have control over both inputs. That doesn't mean that both inputs are necessarily entirely arbitrary./ Indeed as you know, they certainly aren't, either for the forged certificates, or for the PDFs that Google created in their experiment. There is quite a lot of structure in fact. However, they attacker still needs to know exactly what the fixed components of the two inputs are, in order to be able to generate the components of both inputs that will ultimately allow the hashes of the full inputs to collide.

So, when the attacker does not control and cannot predict what the final form of one of the input is, he cannot create in advance the data that would need to be in the input he submits to the signer to sign. He only discovers afterwards the full input data (including the nonce) and the resulting hash. This fundamentally changes the problem from the need to create a collision, to the need to create a second pre-image, which as you've noted is a much, much harder problem, and something that is not even currently possible with MD5, if it ever will be.

So, I would say that yes, the introduction of unpredictable randomness does indeed eliminate the potential for collision attacks as a class.

Answer 2

"My question is a bit more general: do collision attacks matter if signed messages include random data generated by the signer?"

Random data can improve security by making collision attacks harder. Without full information on the attack, it's impossible to answer for sure, but it seems like random data doesn't improve security in this scenario, because the attacker can generate the collision on demand, on the basis of an arbitrary starting message.

"Are there other use cases where it matters?"

Yes. Google, in their article on the topic, notes that someone could send two different contracts with identical hashes, but different terms in the contract. This could be a trusted party trying to screw you over (that does happen!) or it could be someone posing as the trusted party. The hash there would be used for file integrity verification, not as a signature. Another use case is git. Git uses sha1 hashes to identify code. If someone can generate new code with identical hashes, git is unable to distinguish between the two, and a git user might build/execute malicious software.