Create a gist now

Instantly share code, notes, and snippets.

@prokls /md4.py forked from tristanwietsma/md4.py
Last active Apr 9, 2016

What would you like to do?
MD4 in pure Python 3.4. Based on @tristanwietsma's MD4 implementation: https://gist.github.com/tristanwietsma/5937448
#!/usr/bin/env python3
import binascii
def _pad(msg):
n = len(msg)
bit_len = n * 8
index = n & 0x3f
pad_len = 120 - index
if index < 56:
pad_len = 56 - index
padding = b'\x80' + b'\x00' * 63
suffix = bit_len.to_bytes(8, 'little', signed=False)
padded_msg = msg + padding[:pad_len] + suffix
return padded_msg
def _left_rotate(n, b):
return ((n << b) | ((n & 0xffffffff) >> (32 - b))) & 0xffffffff
def _if(x, y, z):
return x & y | ~x & z
def _maj(x, y, z):
return x & y | x & z | y & z
def _xor3(x, y, z):
return x ^ y ^ z
def _f1(a, b, c, d, k, s, X):
return _left_rotate(a + _if(b, c, d) + X[k], s)
def _f2(a, b, c, d, k, s, X):
return _left_rotate(a + _maj(b, c, d) + X[k] + 0x5a827999, s)
def _f3(a, b, c, d, k, s, X):
return _left_rotate(a + _xor3(b, c, d) + X[k] + 0x6ed9eba1, s)
class MD4:
def __init__(self):
self.A = 0x67452301
self.B = 0xefcdab89
self.C = 0x98badcfe
self.D = 0x10325476
def update(self, message_string):
msg_bytes = _pad(message_string)
for i in range(0, len(msg_bytes), 64):
self._compress(msg_bytes[i:i+64])
def _compress(self, block):
a, b, c, d = self.A, self.B, self.C, self.D
x = []
for i in range(0, 64, 4):
x.append(int.from_bytes(block[i:i+4], 'little', signed=False))
a = _f1(a, b, c, d, 0, 3, x)
d = _f1(d, a, b, c, 1, 7, x)
c = _f1(c, d, a, b, 2, 11, x)
b = _f1(b, c, d, a, 3, 19, x)
a = _f1(a, b, c, d, 4, 3, x)
d = _f1(d, a, b, c, 5, 7, x)
c = _f1(c, d, a, b, 6, 11, x)
b = _f1(b, c, d, a, 7, 19, x)
a = _f1(a, b, c, d, 8, 3, x)
d = _f1(d, a, b, c, 9, 7, x)
c = _f1(c, d, a, b, 10, 11, x)
b = _f1(b, c, d, a, 11, 19, x)
a = _f1(a, b, c, d, 12, 3, x)
d = _f1(d, a, b, c, 13, 7, x)
c = _f1(c, d, a, b, 14, 11, x)
b = _f1(b, c, d, a, 15, 19, x)
a = _f2(a, b, c, d, 0, 3, x)
d = _f2(d, a, b, c, 4, 5, x)
c = _f2(c, d, a, b, 8, 9, x)
b = _f2(b, c, d, a, 12, 13, x)
a = _f2(a, b, c, d, 1, 3, x)
d = _f2(d, a, b, c, 5, 5, x)
c = _f2(c, d, a, b, 9, 9, x)
b = _f2(b, c, d, a, 13, 13, x)
a = _f2(a, b, c, d, 2, 3, x)
d = _f2(d, a, b, c, 6, 5, x)
c = _f2(c, d, a, b, 10, 9, x)
b = _f2(b, c, d, a, 14, 13, x)
a = _f2(a, b, c, d, 3, 3, x)
d = _f2(d, a, b, c, 7, 5, x)
c = _f2(c, d, a, b, 11, 9, x)
b = _f2(b, c, d, a, 15, 13, x)
a = _f3(a, b, c, d, 0, 3, x)
d = _f3(d, a, b, c, 8, 9, x)
c = _f3(c, d, a, b, 4, 11, x)
b = _f3(b, c, d, a, 12, 15, x)
a = _f3(a, b, c, d, 2, 3, x)
d = _f3(d, a, b, c, 10, 9, x)
c = _f3(c, d, a, b, 6, 11, x)
b = _f3(b, c, d, a, 14, 15, x)
a = _f3(a, b, c, d, 1, 3, x)
d = _f3(d, a, b, c, 9, 9, x)
c = _f3(c, d, a, b, 5, 11, x)
b = _f3(b, c, d, a, 13, 15, x)
a = _f3(a, b, c, d, 3, 3, x)
d = _f3(d, a, b, c, 11, 9, x)
c = _f3(c, d, a, b, 7, 11, x)
b = _f3(b, c, d, a, 15, 15, x)
# update state
self.A = (self.A + a) & 0xffffffff
self.B = (self.B + b) & 0xffffffff
self.C = (self.C + c) & 0xffffffff
self.D = (self.D + d) & 0xffffffff
def digest(self):
return binascii.hexlify(
self.A.to_bytes(4, 'little', signed=False) + \
self.B.to_bytes(4, 'little', signed=False) + \
self.C.to_bytes(4, 'little', signed=False) + \
self.D.to_bytes(4, 'little', signed=False)
).decode('ascii')
if __name__ == '__main__':
def check(msg, sig):
m = MD4()
m.update(msg.encode('ascii'))
print(m.digest() == sig)
check("", '31d6cfe0d16ae931b73c59d7e0c089c0')
check("a", 'bde52cb31de33e46245e05fbdbd6fb24')
check("abc", 'a448017aaf21d8525fc10ae87aa6729d')
check("message digest",
'd9130a8164549fe818874806e1c7014b')
check("abcdefghijklmnopqrstuvwxyz",
'd79e1c308aa5bbcdeea8ed63df412da9')
check("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
'043f8582f241db351ce627e153e7f0e4')
check("12345678901234567890123456789012345678901234567890123456789012345678901234567890",
'e33b4ddc9c38f2199c3e7b164fcc0536')
Owner

prokls commented Apr 9, 2016

It is important to recognize that in this design two consecutive calls to update will yield a different result than one call with the parameter concatenated. This behavior was inherited by @tristanwietsma's implementation.

m = MD4()
m.update(b"abc")
m.update(b"d")

m2 = MD4()
m2.update(b"abcd")

assert m.digest() == m2.digest()  # will fail
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment