md4-wang-collision.py

#!/usr/bin/env python3

import struct
import binascii


BYTEORDER='big'

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, BYTEORDER, 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, msg_bytes):
        #msg_bytes = _pad(msg_bytes)
        assert (len(msg_bytes) * 8) % 512 == 0
        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], BYTEORDER, 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 '{:08x}{:08x}{:08x}{:08x}'.format(self.A, self.B, self.C, self.D)
        return binascii.hexlify(
            self.A.to_bytes(4, BYTEORDER, signed=False) + \
            self.B.to_bytes(4, BYTEORDER, signed=False) + \
            self.C.to_bytes(4, BYTEORDER, signed=False) + \
            self.D.to_bytes(4, BYTEORDER, signed=False)
        ).decode('ascii')


if __name__ == '__main__':
    # via https://eprint.iacr.org/2004/199.pdf
    wang_m1a = ('4d7a9c8356cb927ab9d5a57857a7a5eede748a3cdcc'
                '366b3b683a0203b2a5d9fc69d71b3f9e99198d79f80'
                '5ea63bb2e845dd8e3197e31fe52794bf08b9e8c3e9')
    wang_m1b = ('4d7a9c83d6cb927a29d5a57857a7a5eede748a3cdcc'
                '366b3b683a0203b2a5d9fc69d71b3f9e99198d79f80'
                '5ea63bb2e845dc8e3197e31fe52794bf08b9e8c3e9')
    wang_h1 = '5f5c1a0d71b360461b5435da9b0d807a'
    wang_m2a = ('4d7a9c8356cb927ab9d5a57857a7a5eede748a3cdcc'
                '366b3b683a0203b2a5d9fc69d71b3f9e99198d79f80'
                '5ea63bb2e845dd8e3197e31fe5f713c240a7b8cf69')
    wang_m2b = ('4d7a9c83d6cb927a29d5a57857a7a5eede748a3cdcc'
                '366b3b683a0203b2a5d9fc69d71b3f9e99198d79f80'
                '5ea63bb2e845dc8e3197e31fe5f713c240a7b8cf69')
    wang_h2 = 'e0f76122c429c56cebb5e2560b809793'

    def h(inp):
        inst = MD4()
        inst.update(binascii.unhexlify(inp))
        return inst.digest()

    m1a = h(wang_m1a)
    m1b = h(wang_m1b)
    m2a = h(wang_m2a)
    m2b = h(wang_m2b)

    assert m1a == m1b and m1a == wang_h1
    assert m2a == m2b and m2a == wang_h2

    print('message 1a = {}'.format(wang_m1a))
    print('message 1b = {}'.format(wang_m1b))
    print('message 2a = {}'.format(wang_m2a))
    print('message 2b = {}'.format(wang_m2b))
    print('hash    1  = {}'.format(m1a))
    print('hash    2  = {}'.format(m1b))