As a personal project, I want to implement MD5 on an FPGA, but I have some doubts about the specifics of the implementation. My first source of how the algorithm is implemented was the RFC 1321, where there is a pseudocode that explains that round 1 will be performed the following way:

 /* Round 1. */
 /* Let [abcd k s i] denote the operation
      a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
 /* Do the following 16 operations. */
 [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
 [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
 [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
 [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

Ok. Fair enough. It broke my dreams to be able to parallelize the algorithm, since in each step one variable (A,B,C or D) is updated and each step needs the previous values.

So, looking for some way to parallelize some part of the algorithm I found this chapter of a book: www.springer.com/cda/content/document/cda_downloaddocument/9781441980793-c1.pdf. Table 2.1 of page 31(5) gives another formula for the algorithm. Sure, it is similar, but is not the same. According to this book the only value ever update is only B. Clearly, this is not the same as the original implementation as seen on RFC 1321.

My questions are:

  • Is this another form of the original implementation with the exact same results? (I suppose so, but as the book does not explains the steps that led to the equations, I want to be sure)
  • And how are those new equations derived?
  • $\begingroup$ Is there some reason you chose MD5? It is known to be a broken hash function (at least for collision resistance, but likely breaks in other properties will follow later). If you can chose, use a more modern hash function. $\endgroup$ – Paŭlo Ebermann Feb 11 '13 at 18:29
  • $\begingroup$ There is no special reason. I will not use it for anything serious, I just wanted a simple cryptographic hash function to implement on an FPGA with the purpose to learn and MD5 seemed appropiate. Nevertheless, I may follow your advice (maybe SHA 256?). But anyway, I am still curious about this "discrepancy" $\endgroup$ – Fackelmann Feb 11 '13 at 18:37
  • 3
    $\begingroup$ Actually, if you're looking at a parallizable hash, you might want to look at SHA-3. $\endgroup$ – poncho Feb 11 '13 at 19:16
  • $\begingroup$ Yeah, Keccak is probably a good idea, it has been designed for parallel operation (at least the primitive itself). You can try a smaller permutation for testing in a "restrained environment". $\endgroup$ – Maarten Bodewes Feb 12 '13 at 0:58
  • $\begingroup$ Thank you very much for the hint about SHA-3. I have been looking into it and it seems interesting. I think I'll give it a try. $\endgroup$ – Fackelmann Feb 13 '13 at 14:07

The description in RFC 1321 is correct. So is the one in the book sample. The difference amounts to notation. What is noted A B C D in the book amounts to the first, second, third and fourth arguments of the [abcd k s i] notation in RFC 1321, and the question.

The only variation I know in MD5 is getting the byte order wrong in the 32-bit words. That happened in the first publication giving an MD5 collision, which was promptly corrected.

| improve this answer | |
  • $\begingroup$ Ok, I am oficially stupid. Now I understand it. Thank you very much. It was so simple, yet I thought there was some sort of derivation along the way, thank you! $\endgroup$ – Fackelmann Feb 11 '13 at 19:05

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.