Help wanted with md2 hash algorithm

[Tom Anderson]

On Sun, 8 Jan 2006, Tom Anderson wrote:

> On Fri, 6 Jan 2006 wjb131 at web.de wrote:
>
>> below you find my simple python version of MD2 algorithm as described 
>> in RFC1319 (http://rfc1319.x42.com/MD2). It produces correct results 
>> for strings shorter than 16 Bytes and wrong results for longer strings.
>
> I guess the thing to do is extract the C code from the RFC and compile 
> it, verify that it works, then stick loads of print statements in the C 
> and the python, to see where the states of the checksum engines diverge.

Okay, i've done this. I had to fiddle with the source a bit - added a 
#include "global.h" to md2.h (it needs it for the PROTO_LIST macro) and 
took the corresponding includes out of md2c.c and mddriver.c (to avoid 
duplicate definitions) - but after that, it built cleanly with:

gcc -DMD=2 *.c *.h -o mddriver

A couple of pairs of (somewhat spurious) parentheses in mddriver.c, and it 
even built cleanly with -Wall.

Running the test suite with mddriver -x gives results matching the test 
vectors in the RFC - a good start!

Patching the code to dump the checksums immediately after updating with 
the pad, and before updating with the checksum:

*** checksum after padding = 623867b6af52795e5f214e9720beea8d
MD2 ("") = 8350e5a3e24c153df2275c9f80692773
*** checksum after padding = 19739cada3ba281693348e9d256fff31
MD2 ("a") = 32ec01ec4a6dac72c0ab96fb34c0b5d1
*** checksum after padding = 19e29d1b7304368e595a276f302f57cc
MD2 ("abc") = da853b0d3f88d99b30283a69e6ded6bb
*** checksum after padding = 56d65157dedfcd75a7b1e82d970eec4b
MD2 ("message digest") = ab4f496bfb2a530b219ff33031fe06b0
*** checksum after padding = 4a42d3a377b7e9988fb9289699e4d3a3
MD2 ("abcdefghijklmnopqrstuvwxyz") = 4e8ddff3650292ab5a4108c3aa47940b
*** checksum after padding = c3db7592ee1dd9b84505cfb4e2f9a765
MD2 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = da33def2a42df13975352846c30338cd
*** checksum after padding = 59ca5673c8f931bc41214f56b5c6c01
MD2 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = d5976f79d83d3a0dc9806c3c66f3efd8

And here's my python code with the same modification, running the test 
suite:

*** checksum after padding =  623867b6af52795e5f214e9720beea8d
MD2 ("") = 8350e5a3e24c153df2275c9f80692773
*** checksum after padding =  19739cada3ba281693348e9d256fff31
MD2 ("a") = 32ec01ec4a6dac72c0ab96fb34c0b5d1
*** checksum after padding =  19e29d1b7304368e595a276f302f57cc
MD2 ("abc") = da853b0d3f88d99b30283a69e6ded6bb
*** checksum after padding =  56d65157dedfcd75a7b1e82d970eec4b
MD2 ("message digest") = ab4f496bfb2a530b219ff33031fe06b0
*** checksum after padding =  539ba695f264f365bcabc5c8b10913c7
MD2 ("abcdefghijklmnopqrstuvwxyz") = 65182bb8c569485fcba44dbc66a02b56
*** checksum after padding =  365fe0617f5f56a56090af1cfd6caac3
MD2 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = a1ccc835ea9654d6a2926c21f0b20813
*** checksum after padding =  9acf39425d22c4e3b4ddbdc563d23716
MD2 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 8f1f49dc8de490b9aa7c99cec3fbccdf

As you can see, the checksums start to go wrong when we hit 16 bytes.

So, let us turn our attention to the checksum function.

Here's the python i wrote:

def checksum_old(c, buf): # c is checksum array, buf is input block
 	l = c[-1]
 	for i in xrange(digest_size):
 		l = S[(buf[i] ^ l)]
 		c[i] = l

Here's the C from the RFC:

   unsigned int i, j, t;
   t = checksum[15];
   for (i = 0; i < 16; i++)
     t = checksum[i] ^= PI_SUBST[block[i] ^ t];

Spot the difference. Yes, the assignment into the checksum array is a ^=, 
not a straight = - checksum bytes get set to 
current-value-of-checksum-byte xor S-box-transformation-of (input-byte xor 
accumulator). Translating that into python, we get:

def checksum(c, buf):
 	l = c[-1]
 	for i in xrange(digest_size):
 		l = S[(buf[i] ^ l)] ^ c[i]
 		c[i] = l

And when we put that back into the code, we get the right digests out. 
Victory!

However, here's what the pseudocode in the RFC says:

          For j = 0 to 15 do
             Set c to M[i*16+j].
             Set C[j] to S[c xor L].
             Set L to C[j].
           end /* of loop on j */

I certainly don't see any sign of a xor with the 
current-value-of-checksum-byte in there - it looks like the C and 
pseudocode in the RFC don't match up.

And, yes, googling for "RFC 1319 errata" brings up a report correcting 
this. They really ought to amend RFCs to mention errata!

Correct code here:

http://urchin.earth.li/~twic/md2.py

tom

-- 
Mathematics is the door and the key to the sciences. -- Roger Bacon