5
$\begingroup$

So my understanding is that if we've got some hash function $H$ then a 2nd pre-image attack is one where given a message-hash pair $(m, H(m))$ we can find some $m' \neq m : H(m') = H(m)$, while a collision attack is to find any old $m, m'$ such that $H(m) = H(m')$.

Everywhere I see people talking about collision attacks it really seems that they mean 2nd preimage. What would be the usefulness of a pure collision attack where you have no control over $m$ or $m'$? There are all those results about how SHA-1 is broken w.r.t. collision attacks, but it seems that people really mean 2nd pre-image. Is this just a convention that people are not strict about, or am I missing something?

For example, in this SE question the author of the accepted answer gives an example of where a collision attack could be used to swap out malware for a valid Windows update. But to me that seems to be a 2nd pre-image attack, not a pure collision attack, because the attacker needs to ensure that the hash of the malware matches a particular hash, i.e. that of the Windows update.

$\endgroup$
4
$\begingroup$

What would be the usefulness of a pure collision attack where you have no control over $m$ or $m'$?

One example is when $m$ and $m'$ are or contain randomly selected material. If they're using cryptography correctly, the honest parties generally choose keys, random IVs or similar material randomly, and thus have no control over what their values are either. This affords many opportunities for attacks that require finding some collision but don't care about what the colliding values are.

One example is secure coin tossing. If Alice is calling the toss and Bob is throwing it, they execute this protocol:

  1. Alice secretly picks her call (Heads or Tails) for the toss, and a sufficiently large random salt;
  2. Alice computes commitment = hash(salt || call);
  3. Alice sends commitment to Bob.
  4. Bob tosses a coin, gets outcome;
  5. Bob sends outcome to Alice;
  6. Alice sends call and salt to Bob;
  7. Bob verifies that commitment = hash(salt || call). If it checks out, Bob knows Alice didn't cheat.
  8. If outcome = call then Alice won the coin toss, otherwise she lost.

If Alice can find any pair of salts such that hash(salt1 || Heads) = hash(salt2 || Tails), then she can break the protocol. It doesn't matter what the values of salt1 and salt2 are as long as they lead to a collision in this context. So collision resistance implies Alice can't cheat this protocol.


To address Ross Snider's answer you linked from another SE site. I'll boldface one really important bit:

Bob can use a collision attack to his advantage in many ways. Here is one of the simpliest: Bob finds a collision between two binaries $b$ and $b′$ ($H(b)=H(b′)$) such that $b$ is a valid Microsoft Windows security patch and $b′$ is malware. (Bob works for Windows). Bob sends his security patch up the chain of command, where behind a vault they sign the code and ship the binary to Windows users around the world to fix a flaw. Bob can now contact and infect all Windows computers around the world with $b′$ and the signature that Microsoft computed for $b$.

But to me that seems to be a 2nd pre-image attack, not a pure collision attack, because the attacker needs to ensure that the hash of the malware matches a particular hash, i.e. that of the Windows update.

It is a collision attack indeed, not a second preimage attack, and it hinges on these points:

  • "Bob works for Windows." This may be a parenthetical in the quote, but it is a critical assumption. The scenario assumes (perhaps less than explicitly) that Bob is the author of both the legitimate patch and the malware, and gets to craft them together as a colliding pair. That's the assumption that you're missing; if instead Bob was trying to construct a malware patch that matched a legitimate one that somebody else constructed, then you would be right and it would indeed be a second preimage attack.
  • Executable file formats allow for arbitrary data to be embedded into a file without affecting the program's runtime behavior. This means that Bob gets a lot of latitude to embed random data into both the legitimate patch and the malware.

Those two factors taken together are what allows Bob the opportunity to try a much cheaper collision attack instead of a second preimage attack.

$\endgroup$
  • $\begingroup$ that's a fantastic example, thanks! Regarding the other part of my question, would you say that people tend to be rather casual about what strictly is a 2nd preimage attack vs collision attack or are there nuances of definition that I'm not appreciating? Or are there so commonly random aspects to $m$ and $m'$ that strict 2nd preimage attacks are rare? $\endgroup$ – alfalfa Apr 18 '17 at 18:31
  • $\begingroup$ The term "collision" is routinely abused by most programmers (and the term "hash," for that matter). I have also edited my question to address the SE answer you linked. $\endgroup$ – Luis Casillas Apr 19 '17 at 2:00
1
$\begingroup$

A pure collision with no useful control may be of little use, but unless the attack ia using some property specific to the inital value it should be possible to mount it fron any or at least many starting values. This is far more usefull and is still not a second preimage attack. Formally, given m find x and x' such that H(m || x) = H(m || x') By virtue of the way nearly all hash functions are constructed this will also make H(m || x || y) = H(m || x' || y) for any y. Now this is already very usefull for forging messages. Since when we cryptographicly sign a message we are actually signing the hash if we can craft such messages and con someone to sign one we will get a valid signature on the other. Using fancy pdf or post script or many other file formats we can create document pairs which have arbitrary visible text and still have the same hash. This is what the shattered attack demonstrated.

$\endgroup$
  • $\begingroup$ So you're saying that attacks like the one against SHA-1 aren't considered 2nd preimage attacks because they don't work with an entire initial message $m$, they only work with a middle segment of it? $\endgroup$ – alfalfa Apr 18 '17 at 22:10
  • $\begingroup$ Correct, therr are no remotely practical 2nd preimage attacks on Sha-1 $\endgroup$ – Meir Maor Apr 19 '17 at 3:06

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.