Cryptopals zestaw 4 ćwiczenie 30

To zadanie to tak na prawdę dwa dwa poprzednie zadania połączone w całość, z tym że tym razem zamiast algorytmu SHA-1 zajmiemy się algorytmem MD4.

Pierwsza rzecz, którą należy zrobić to znalezienie opisu algorytmu MD4. Ja skorzystałem z dokumentu RFC1320, który można znaleźć pod adresem https://tools.ietf.org/html/rfc1320. Różnica pomiędzy MD4 a SHA-1, która jako pierwsza rzuca się w oczy to fakt, że SHA-1 produkuje skrót o długości 20 bajtów a w przypadku MD4 długość skrótu to 16 bajtów. Obydwie implementacje mają jednak tą samą wadę, czyli zwracana wartość to również stan algorytmu po przetworzeniu podanej ilości danych. Samo ćwiczenie rozwiązuje się w taki sam sposób, dlatego wkleję tu tylko swoją implementację, bo wszystko jest już opisane w poprzednim ćwiczeniu.

Implementacja MD4 z możliwością podania stanu początkowego:

def custom_md4(msg, additional_len = 0, initial_state = None):
    # Step 1. Append Padding Bits
    msg_len = len(msg)
    msg = msg + bytearray([0x80])
    pad_len = (56-len(msg))%64
    msg = msg + bytearray([0]*pad_len)
    # Step 2. Append Length
    msg = msg + struct.pack("<Q", msg_len*8)
    # Step 3. Initialize MD Buffer
    A = 0x67452301
    B = 0xefcdab89
    C = 0x98badcfe
    D = 0x10325476
    if (initial_state != None):
        A = int.from_bytes(initial_state[:4], byteorder='little')
        B = int.from_bytes(initial_state[4:8], byteorder='little')
        C = int.from_bytes(initial_state[8:12], byteorder='little')
        D = int.from_bytes(initial_state[12:16], byteorder='little')
    # Step 4. Process message in 16-Word Blocks
    chunks = [msg[i:i+64] for i in range(additional_len, len(msg)-63, 64)]
    for chunk in chunks:
        AA = A
        BB = B
        CC = C
        DD = D
        X = [0]*16
        for i in range(0, 16):
            X[i] = int.from_bytes(chunk[4*i:4*(i+1)], byteorder='little', signed=False)
        # Round 1.
        for k in range (0, 4):
            A = rotate32_left(A + md4_funF(B, C, D) + X[k*4+0], 3)
            D = rotate32_left(D + md4_funF(A, B, C) + X[k*4+1], 7)
            C = rotate32_left(C + md4_funF(D, A, B) + X[k*4+2], 11)
            B = rotate32_left(B + md4_funF(C, D, A) + X[k*4+3], 19)
        # Round 2.
        for k in range (0, 4):
            A = rotate32_left(A + md4_funG(B, C, D) + X[k] + 0x5A827999, 3)
            D = rotate32_left(D + md4_funG(A, B, C) + X[k+4] + 0x5A827999, 5)
            C = rotate32_left(C + md4_funG(D, A, B) + X[k+8] + 0x5A827999, 9)
            B = rotate32_left(B + md4_funG(C, D, A) + X[k+12] + 0x5A827999, 13)
        # Round 3.
        for k in [0, 2, 1, 3]:
            A = rotate32_left(A + md4_funH(B, C, D) + X[k] + 0x6ED9EBA1, 3)
            D = rotate32_left(D + md4_funH(A, B, C) + X[k+8] + 0x6ED9EBA1, 9)
            C = rotate32_left(C + md4_funH(D, A, B) + X[k+4] + 0x6ED9EBA1, 11)
            B = rotate32_left(B + md4_funH(C, D, A) + X[k+12] + 0x6ED9EBA1, 15)
        A = (A + AA)&0xffffffff
        B = (B + BB)&0xffffffff
        C = (C + CC)&0xffffffff
        D = (D + DD)&0xffffffff
    # Step 5. Output
    return (struct.pack("<L", A)+struct.pack("<L", B)+
            struct.pack("<L", C)+struct.pack("<L", D))

Implementacja wyroczni, w której użyta jest biblioteczna implementacja algorytmu MD4:

class OracleMD4LenghtExtension(object):
    M_SECRET = b''

    def __init__(self):
        self.M_SECRET = generateRandomDataSize(1, 40)
    
    def generateMAC(self, message):
        return hashlib.new('MD4', self.M_SECRET + message).digest()

    def validateMessage(self, message, MAC):
        expected = hashlib.new('MD4', self.M_SECRET+message).digest()
        print("Got     : ", MAC.hex())
        print("Expected: ", expected.hex())
        return expected == MAC

Implementacja rozwiązania:

def s4challenge30():
    print("Challenge 30")
    oracle = OracleMD4LenghtExtension()
    message = b"comment1=cooking%20MCs;userdata=foo;comment2=%20like%20a%20pound%20of%20bacon"
    
    additional_message = b";admin=true"
    msg_mac = oracle.generateMAC(message)
    print("Original message MAC: ", msg_mac.hex())
    for key_len in range(1, 100):
        tampered_message = b"A"*key_len + message
        msg_len = len(tampered_message)
        tampered_message = tampered_message + bytearray([0x80])
        # must append number of 0's that msg+0's+64-bit msg size is multiple of 64  
        pad_len = (56-len(tampered_message))%64
        tampered_message = tampered_message + bytearray([0] * pad_len)
        # append bit size of the message
        tampered_message = tampered_message + struct.pack("<Q", msg_len*8)
        offset_len = len(tampered_message)
        tampered_message = tampered_message + additional_message

        tmp_mac = custom_md4(tampered_message, offset_len, msg_mac)
        if oracle.validateMessage(tampered_message[key_len:], tmp_mac):
            print("Guesssed secret key length: ", pad_len)
            return
    print("Failed to tamper message")

Całość dostępna pod adresem https://gitlab.com/akoltys/cryptopals .