8

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.

4

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.

-1

"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.

  • 1
    "the attacker can generate the collision on demand" - that was certainly not my understanding of the paper. They had to control both PDF files to make them collide; if someone external put random data into each, they would then have different hashes. – paj28 Feb 23 '17 at 23:26
  • "If someone external" wasn't part of the original question. The presence of random data doesn't preclude the attack - the fact that the random data is fed in by a trusted party (for example, a CA) and not controlled by an attacker is significant. That said, your implied scenario of an attacker trying to intercept and replace a signed message between two other parties is likely defeated by the presence of random data. – Jesse K Feb 24 '17 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.