Help wanted with md2 hash algorithm

[wjb131@web.de]

hi all,

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 can't find what's wrong.

Can anybody help?

Regards
Wolfgang

-------------------------------------

#--- MD2 validation data
md2_test = [
('', '8350e5a3e24c15 3df2275c9f80692 773'),
("a", '32ec01ec4a6dac 72c0ab96fb34c0b 5d1'),
("abc", 'da853b0d3f88d9 9b30283a69e6ded 6bb'),
("message digest", 'ab4f496bfb2a53 0b219ff33031fe0 6b0'),
("abcdefghijklm nopqrstuvwxyz",
'4e8ddff3650292 ab5a4108c3aa479 40b'),
("ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz012345 6789",
'da33def2a42df1 3975352846c3033 8cd'),

("1234567890123 456789012345678 901234567890123 456789012345678 901234567890123 4567890",

'd5976f79d83d3a 0dc9806c3c66f3e fd8' )
]


#--- 256-byte "random" permutation constructed from the digits of pi
PI_SUBST = [41, 46, 67, 201, 162, 216, 124, 1, 61, 54, 84, 161, 236,
240, 6,
19, 98, 167, 5, 243, 192, 199, 115, 140, 152, 147, 43, 217, 188,
76, 130, 202, 30, 155, 87, 60, 253, 212, 224, 22, 103, 66, 111, 24,
138, 23, 229, 18, 190, 78, 196, 214, 218, 158, 222, 73, 160, 251,
245, 142, 187, 47, 238, 122, 169, 104, 121, 145, 21, 178, 7, 63,
148, 194, 16, 137, 11, 34, 95, 33, 128, 127, 93, 154, 90, 144, 50,
39, 53, 62, 204, 231, 191, 247, 151, 3, 255, 25, 48, 179, 72, 165,
181, 209, 215, 94, 146, 42, 172, 86, 170, 198, 79, 184, 56, 210,
150, 164, 125, 182, 118, 252, 107, 226, 156, 116, 4, 241, 69, 157,
112, 89, 100, 113, 135, 32, 134, 91, 207, 101, 230, 45, 168, 2, 27,
96, 37, 173, 174, 176, 185, 246, 28, 70, 97, 105, 52, 64, 126, 15,
85, 71, 163, 35, 221, 81, 175, 58, 195, 92, 249, 206, 186, 197,
234, 38, 44, 83, 13, 110, 133, 40, 132, 9, 211, 223, 205, 244, 65,
129, 77, 82, 106, 220, 55, 200, 108, 193, 171, 250, 36, 225, 123,
8, 12, 189, 177, 74, 120, 136, 149, 139, 227, 99, 232, 109, 233,
203, 213, 254, 59, 0, 29, 57, 242, 239, 183, 14, 102, 88, 208, 228,
166, 119, 114, 248, 235, 117, 75, 10, 49, 68, 80, 180, 143, 237,
31, 26, 219, 153, 141, 51, 159, 17, 131, 20]


PADDING = ["".join(map(chr , [i]*i)) for i in range(17)]
SIZE = 16

#----------------------------------------------------------
def md2(m):

## (1) prepare message

#--- append to m i byte with value i, len(m) % 16 == 0
padLen = SIZE - len(m) % SIZE
m += PADDING[padLen]

#--- compute checksum C of m and append it to m
C = [0] * SIZE
L = 0
for i in range(len(m) / SIZE):
m16 = m[i*SIZE : (i+1)*SIZE]
for j in range(SIZE):
c = ord(m16[j])
C[j] = PI_SUBST[ c ^ L ]
L = C[j]
C = "".join( map(chr, C) )
m += C

## (2) compress message

X = [0] * 48 # 'compressor'

for i in range(len(m) / SIZE):

# fill X
m16 = m[i*SIZE : (i+1)*SIZE]
X[16:32] = map(ord, m16)
X[32:48] = [ a^b for (a,b) in zip(X[16:48], X[:16]) ]

# compress m
t = 0
for j in range(18):
for k in range(48):
t = X[k] ^ PI_SUBST[t]
X[k] = t
t = (t+j) % 256

X = "".join(map(lam bda d: "%02x" % d, X[:SIZE]))
return X


def test():
for (i, j) in md2_test:
md = md2(i)
print "Message: %s" % i
print "My MD:%s" % md
print "Test MD:%s" % j
print "%s" % (md== j)
print

if __name__ == "__main__":
test()

[Tom Anderson]

Re: Help wanted with md2 hash algorithm

On Fri, 6 Jan 2006 wjb131@web.de wrote:
[color=blue]
> 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 can't find what's wrong.
>
> Can anybody help?[/color]

Okay, i've reimplemented the code from scratch, based on the RFC, without
even looking at your code, as a basis for comparison.

The trouble is, i get exactly the same results as you!

Here's mine:

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

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.

tom

--
Death to all vowels! The Ministry of Truth says vowels are plus
undoublethink. Vowels are a Eurasian plot! Big Brother, leading us proles
to victory!

[Paul Rubin]

Re: Help wanted with md2 hash algorithm

wjb131@web.de writes:[color=blue]
> 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.[/color]

Why do you want to use MD2? It's very slow and it's also been
deprecated for security reasons. Use SHA1 (built into Python library)
or SHA256/384/512 (implementation s are circulating) instead.

[wjb131@web.de]

Re: Help wanted with md2 hash algorithm


Paul Rubin wrote:[color=blue]
> wjb131@web.de writes:[color=green]
> > 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.[/color]
>
> Why do you want to use MD2? It's very slow and it's also been
> deprecated for security reasons. Use SHA1 (built into Python library)
> or SHA256/384/512 (implementation s are circulating) instead.[/color]

I want to understand it, and -- therefor ;-) -- I want to implement it
in pure Pyhton.

[Paul Rubin]

Re: Help wanted with md2 hash algorithm

wjb131@web.de writes:[color=blue]
> I want to understand it, and -- therefor ;-) -- I want to implement it
> in pure Pyhton.[/color]

OK. It should be pretty easy to implement. You should find the
official rfc at ietf.org. I remember there was some minor erratum in
the original version that may or may not have been corrected, but it
shouldn't cause any serious confusion. I implemented it in Javascript
a long time ago and as I remember, all the test vectors passed.

[wjb131@web.de]

Re: Help wanted with md2 hash algorithm


Paul Rubin wrote:[color=blue]
> wjb131@web.de writes:[color=green]
> > I want to understand it, and -- therefor ;-) -- I want to implement it
> > in pure Pyhton.[/color]
>
> OK. It should be pretty easy to implement. You should find the
> official rfc at ietf.org. I remember there was some minor erratum in
> the original version that may or may not have been corrected, but it
> shouldn't cause any serious confusion. I implemented it in Javascript
> a long time ago and as I remember, all the test vectors passed.[/color]

I thought I had build a proper implementation in Python. The error you
mention can be avoided by studying the C implementation in RFC 1319.
BUT: Some of the test vectors failed. That's my problem ;-(
And therefore I asked for help.
Wolfgang

[Paul Rubin]

Re: Help wanted with md2 hash algorithm

wjb131@web.de writes:[color=blue]
> I thought I had build a proper implementation in Python. The error you
> mention can be avoided by studying the C implementation in RFC 1319.
> BUT: Some of the test vectors failed. That's my problem ;-(
> And therefore I asked for help.[/color]

You might check PyCrypt against the test vectors.

http://www.amk.ca/python/writing/pycrypt/

[wjb131@web.de]

Re: Help wanted with md2 hash algorithm


Paul Rubin wrote:[color=blue]
> wjb131@web.de writes:[color=green]
> > I thought I had build a proper implementation in Python. The error you
> > mention can be avoided by studying the C implementation in RFC 1319.
> > BUT: Some of the test vectors failed. That's my problem ;-(
> > And therefore I asked for help.[/color]
>
> You might check PyCrypt against the test vectors.
>
> http://www.amk.ca/python/writing/pycrypt/[/color]

Already done before my first posting. But the problem was there. I
studied the C sources of MD2 of that package, too. But all test cases
failed.

[wjb131@web.de]

Re: Help wanted with md2 hash algorithm


Paul Rubin wrote:[color=blue]
> wjb131@web.de writes:[color=green]
> > I thought I had build a proper implementation in Python. The error you
> > mention can be avoided by studying the C implementation in RFC 1319.
> > BUT: Some of the test vectors failed. That's my problem ;-(
> > And therefore I asked for help.[/color]
>
> You might check PyCrypt against the test vectors.
>
> http://www.amk.ca/python/writing/pycrypt/[/color]

Already done before my first posting. But the problem was there. I
studied the C sources of MD2 of that package, too. But all test cases
with more than 16 bytes failed.
Wolfgang

[Paul Rubin]

Re: Help wanted with md2 hash algorithm

wjb131@web.de writes:[color=blue]
> Already done before my first posting. But the problem was there. I
> studied the C sources of MD2 of that package, too. But all test cases
> with more than 16 bytes failed.[/color]

Hmm, did the test cases work for the RFC 1319 reference code? What
about OpenSSL?

I thought when I did my JS implementation, I checked all the test
vectors, but it was a long time ago and I can't absolutely be sure.

[Paul Rubin]

Re: Help wanted with md2 hash algorithm

Paul Rubin <http://phr.cx@NOSPAM.i nvalid> writes:[color=blue]
> Hmm, did the test cases work for the RFC 1319 reference code? What
> about OpenSSL?[/color]

I just checked OpenSSL and all the test values it computes match the RFC.

[Tom Anderson]

Re: Help wanted with md2 hash algorithm

On Sun, 8 Jan 2006, Tom Anderson wrote:
[color=blue]
> On Fri, 6 Jan 2006 wjb131@web.de wrote:
>[color=green]
>> 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.[/color]
>
> 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.[/color]

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 = 623867b6af52795 e5f214e9720beea 8d
MD2 ("") = 8350e5a3e24c153 df2275c9f806927 73
*** checksum after padding = 19739cada3ba281 693348e9d256fff 31
MD2 ("a") = 32ec01ec4a6dac7 2c0ab96fb34c0b5 d1
*** checksum after padding = 19e29d1b7304368 e595a276f302f57 cc
MD2 ("abc") = da853b0d3f88d99 b30283a69e6ded6 bb
*** checksum after padding = 56d65157dedfcd7 5a7b1e82d970eec 4b
MD2 ("message digest") = ab4f496bfb2a530 b219ff33031fe06 b0
*** checksum after padding = 4a42d3a377b7e99 88fb9289699e4d3 a3
MD2 ("abcdefghijklm nopqrstuvwxyz") = 4e8ddff3650292a b5a4108c3aa4794 0b
*** checksum after padding = c3db7592ee1dd9b 84505cfb4e2f9a7 65
MD2 ("ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz012345 6789") = da33def2a42df13 975352846c30338 cd
*** checksum after padding = 59ca5673c8f931b c41214f56b5c6c0 1
MD2 ("1234567890123 456789012345678 901234567890123 456789012345678 901234567890123 4567890") = d5976f79d83d3a0 dc9806c3c66f3ef d8

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

*** checksum after padding = 623867b6af52795 e5f214e9720beea 8d
MD2 ("") = 8350e5a3e24c153 df2275c9f806927 73
*** checksum after padding = 19739cada3ba281 693348e9d256fff 31
MD2 ("a") = 32ec01ec4a6dac7 2c0ab96fb34c0b5 d1
*** checksum after padding = 19e29d1b7304368 e595a276f302f57 cc
MD2 ("abc") = da853b0d3f88d99 b30283a69e6ded6 bb
*** checksum after padding = 56d65157dedfcd7 5a7b1e82d970eec 4b
MD2 ("message digest") = ab4f496bfb2a530 b219ff33031fe06 b0
*** checksum after padding = 539ba695f264f36 5bcabc5c8b10913 c7
MD2 ("abcdefghijklm nopqrstuvwxyz") = 65182bb8c569485 fcba44dbc66a02b 56
*** checksum after padding = 365fe0617f5f56a 56090af1cfd6caa c3
MD2 ("ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz012345 6789") = a1ccc835ea9654d 6a2926c21f0b208 13
*** checksum after padding = 9acf39425d22c4e 3b4ddbdc563d237 16
MD2 ("1234567890123 456789012345678 901234567890123 456789012345678 901234567890123 4567890") = 8f1f49dc8de490b 9aa7c99cec3fbcc df

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_s ize):
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_s ize):
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

[wjb131@web.de]

Re: Help wanted with md2 hash algorithm


Tom Anderson wrote:[color=blue]
> On Sun, 8 Jan 2006, Tom Anderson wrote:
>[color=green]
> > On Fri, 6 Jan 2006 wjb131@web.de wrote:
> >[color=darkred]
> >> 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.[/color]
> >
> > 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.[/color]
>
> 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 = 623867b6af52795 e5f214e9720beea 8d
> MD2 ("") = 8350e5a3e24c153 df2275c9f806927 73
> *** checksum after padding = 19739cada3ba281 693348e9d256fff 31
> MD2 ("a") = 32ec01ec4a6dac7 2c0ab96fb34c0b5 d1
> *** checksum after padding = 19e29d1b7304368 e595a276f302f57 cc
> MD2 ("abc") = da853b0d3f88d99 b30283a69e6ded6 bb
> *** checksum after padding = 56d65157dedfcd7 5a7b1e82d970eec 4b
> MD2 ("message digest") = ab4f496bfb2a530 b219ff33031fe06 b0
> *** checksum after padding = 4a42d3a377b7e99 88fb9289699e4d3 a3
> MD2 ("abcdefghijklm nopqrstuvwxyz") = 4e8ddff3650292a b5a4108c3aa4794 0b
> *** checksum after padding = c3db7592ee1dd9b 84505cfb4e2f9a7 65
> MD2 ("ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz012345 6789") = da33def2a42df13 975352846c30338 cd
> *** checksum after padding = 59ca5673c8f931b c41214f56b5c6c0 1
> MD2 ("1234567890123 456789012345678 901234567890123 456789012345678 901234567890123 4567890") = d5976f79d83d3a0 dc9806c3c66f3ef d8
>
> And here's my python code with the same modification, running the test
> suite:
>
> *** checksum after padding = 623867b6af52795 e5f214e9720beea 8d
> MD2 ("") = 8350e5a3e24c153 df2275c9f806927 73
> *** checksum after padding = 19739cada3ba281 693348e9d256fff 31
> MD2 ("a") = 32ec01ec4a6dac7 2c0ab96fb34c0b5 d1
> *** checksum after padding = 19e29d1b7304368 e595a276f302f57 cc
> MD2 ("abc") = da853b0d3f88d99 b30283a69e6ded6 bb
> *** checksum after padding = 56d65157dedfcd7 5a7b1e82d970eec 4b
> MD2 ("message digest") = ab4f496bfb2a530 b219ff33031fe06 b0
> *** checksum after padding = 539ba695f264f36 5bcabc5c8b10913 c7
> MD2 ("abcdefghijklm nopqrstuvwxyz") = 65182bb8c569485 fcba44dbc66a02b 56
> *** checksum after padding = 365fe0617f5f56a 56090af1cfd6caa c3
> MD2 ("ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz012345 6789") = a1ccc835ea9654d 6a2926c21f0b208 13
> *** checksum after padding = 9acf39425d22c4e 3b4ddbdc563d237 16
> MD2 ("1234567890123 456789012345678 901234567890123 456789012345678 901234567890123 4567890") = 8f1f49dc8de490b 9aa7c99cec3fbcc df
>
> 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_s ize):
> 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_s ize):
> 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[/color]


Hi Tom,

thank you very much for your analysis and your solution. Great.
(My knowledge of C language is not that good.)
Wolfgang