# MD5 implementation

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?
-
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. – Paŭlo Ebermann Feb 11 '13 at 18:29
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" – Daniel González Feb 11 '13 at 18:37
Actually, if you're looking at a parallizable hash, you might want to look at SHA-3. – poncho Feb 11 '13 at 19:16
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". – Maarten Bodewes Feb 12 '13 at 0:58
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. – Daniel González Feb 13 '13 at 14:07