I read that hash chaining can be used to prevent hash collisions, while the chosen prefix attack allows hash collisions for algorithms like MD5. How are they related? Does hash chaining prevent the chosen prefix attack?

  • 1
    $\begingroup$ You might want to edit the question to (1) define what you mean by hash chaining, (2) tell us what research you've done so far, and (3) where you've gotten stuck. $\endgroup$ – D.W. Sep 1 '13 at 4:03
  • $\begingroup$ Please note that a "chosen prefix" collision attack is just a (more powerful) subtype of a general collision attack, where the attacker can succeed to create a collision with a chosen common prefix of the input strings. For MD5 methods to create such collisions are known. $\endgroup$ – Paŭlo Ebermann Sep 1 '13 at 15:08

Hash chaining does not itself prevent hash collisions. It sounds like you might have walked away with the wrong lesson from your reading. You might want to read about the Merkle-Damgaard construction, which takes a collision-resistant compression function (for fixed-length inputs) and shows how to extend it to a hash function (for variable-length inputs). Note: to prevent collisions, you need the compression function to be collision-resistant, and you need to use a proper chaining scheme.

Most modern hash functions, including MD5, use Merkle-Damgaard or some other chaining scheme. Obviously, in the case of MD5, it doesn't prevent the chosen-prefix attack on MD5.

  • $\begingroup$ A lot of readings include chaining and open addressing as the 2 best known method to prevent collisions, including mit: courses.csail.mit.edu/6.006/fall09/lecture_notes/lecture05.pdf $\endgroup$ – user2726531 Sep 1 '13 at 12:19
  • 3
    $\begingroup$ @user2726531, those lecture notes relate to non-cryptographic hashes. Here we are talking about cryptographic hashes. Moreover, now that I see the lecture notes, your use of the phrase "hash chaining" was ambiguous; in cryptography, the most natural interpretation of the word "chaining" is the Merkle-Damgaard construction used to build a hash function, which is apparently not what you meant. That's why I asked you to edit your question to define what you meant by hash chaining, but it seems you still haven't done that... $\endgroup$ – D.W. Sep 1 '13 at 16:23
  • $\begingroup$ @D.W. Then why is it mentioned that chaining prevents collisions? $\endgroup$ – user129789 Sep 2 '13 at 2:58
  • 1
    $\begingroup$ @user129789, it doesn't prevent collisions; it is just a strategy for dealing with collisions when building a hash table. And, the context of those lecture notes has nothing to do with cryptography, and thus nothing to do with this site. $\endgroup$ – D.W. Sep 2 '13 at 3:14
  • 2
    $\begingroup$ @user129789, no it doesn't. That's a totally different sort of chaining than the one in the lecture notes you posted in your earlier comment. Like I said in my comment on the question, first you need to be clear about what you mean by "hash chaining", and edit the question to make that clear. You seem unclear on what you even mean by that phrase -- so how do you expect us to answer your question, if you're not even clear on what you're asking? $\endgroup$ – D.W. Sep 4 '13 at 0:41

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.