Cryptopals zestaw 4 ćwiczenie 29

przez | 13 kwietnia 2021

Po tym jak w poprzednim zadaniu, stworzona została implementacja SHA-1 czas na użycie jej do zaprezentowania podatności tego algorytmu. Zadanie polegać będzie na dodaniu nowej zawartości do danych zabezpieczonych wartością MAC wygenerowaną przy pomocy SHA-1 i obliczeniu nowej poprawnej wartości MAC.

Przed przystąpieniem do tego zadania trzeba będzie zmodyfikować implementację algorytmu SHA-1. Można zauważyć, że zwracana wartość skrótu to tak na prawdę zapisany stan algorytmu po przetworzeniu pewnej ilości danych. Gdyby dodać dodatkowe dane i wznowić algorytm od momentu w którym się on zakończył dla pierwotnych danych otrzymamy prawidłową wartość skrótu. Problem polega na tym, że przed właściwymi danymi dodany jest sekretny kluczy szyfrujący, którego nie znamy a za danymi dodany jest ciąg bajtów, który wyrównuje długość całości do odpowiedniej wartości.

Oryginalne dane wyglądały następująco:
[Sekretny klucz] + [Dane użytkownika] + [Dane wyrównujące]
Posiadamy wartość skrótu tych danych, czyli nie potrzebujemy zgadywać wartości sekretnego klucza, danych użytkownika ani danych wyrównujących, ponieważ zostały już one przetworzone przez algorytm. Musimy wznowić działanie algorytmu od miejsca w którym skończył.

Tworzymy nową wiadomość:
[Dane o długości sekretnego klucza] + [Dane użytkownika] + [Dawne wyrównujące] + [Dodatkowe dane] + [Dane wyrównujące nową wiadomość]
Wiemy jaka jest wartość danych użytkownika a znając długość sekretnego klucza jesteśmy wstanie spreparować dane wyrównujące. Jedyna niewiadoma to długość sekretnego klucza – nie musimy znać jego dokładnej wartości a jedynie długość, ponieważ algorytm już przetworzył sam klucz. Długość klucza jest nam natomiast potrzebna, żebyśmy mogli obliczyć prawidłową długość nowej wiadomości oraz długość nowych danych wyrównujących.

Kiedy będziemy wiedzieli ile danych już zostało przetworzonych nasze zadanie staje się banalne – musimy jedynie wznowić działanie algorytmu tam gdzie się zakończył. Moja implementacja zmodyfikowanego algorytmu SHA-1, który jest w stanie wznawiać pracę od podanego stanu poniżej:

def custom_sha1(msg, additional_len = 0, initial_state = None):
    h0 = 0x67452301
    h1 = 0xefcdab89
    h2 = 0x98badcfe
    h3 = 0x10325476
    h4 = 0xc3d2e1f0
    if (initial_state != None):
        h0 = int.from_bytes(initial_state[:4], byteorder='big')
        h1 = int.from_bytes(initial_state[4:8], byteorder='big')
        h2 = int.from_bytes(initial_state[8:12], byteorder='big')
        h3 = int.from_bytes(initial_state[12:16], byteorder='big')
        h4 = int.from_bytes(initial_state[16:], byteorder='big')
    msg_len = len(msg)
    msg = msg + bytearray([0x80])
    # must append number of 0's that msg+0's+64-bit msg size is multiple of 64  
    pad_len = (56-len(msg))%64
    msg = msg + bytearray([0] * pad_len)
    # append bit size of the message
    msg = msg + struct.pack(">Q", msg_len*8)
    chunks = [msg[i:i+64] for i in range(additional_len, len(msg)-63, 64)]
    for chunk in chunks:
        w = [0]*80
        for i in range(0, 16):
            w[i] = int.from_bytes(chunk[4*i:4*(i+1)], byteorder='big', signed=False)

        for i in range (16, 80):
            w[i] = w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]
            w[i] = rotate32_left(w[i], 1)
        
        a = h0
        b = h1
        c = h2
        d = h3
        e = h4
        
        for i in range(0, 80):
            if i <= 19:
                k = 0x5a827999
                tmp = rotate32_left(a, 5)+((b&c)|((~b)&d))+e+w[i]+k
                
            elif i <= 39:
                k = 0x6ed9eba1
                tmp = rotate32_left(a, 5)+(b^c^d)+e+w[i]+k
            elif i <= 59:
                k = 0x8f1bbcdc
                tmp = rotate32_left(a, 5)+((b&c)|(b&d)|(c&d))+e+w[i]+k
            else:
                k = 0xca62c1d6
                tmp = rotate32_left(a, 5)+(b^c^d)+e+w[i]+k
            tmp = tmp&0xffffffff
            e = d
            d = c
            c = rotate32_left(b, 30)
            b = a
            a = tmp
            
        h0 = (h0 + a)&0xffffffff
        h1 = (h1 + b)&0xffffffff
        h2 = (h2 + c)&0xffffffff
        h3 = (h3 + d)&0xffffffff
        h4 = (h4 + e)&0xffffffff
    return (struct.pack(">L", h0)+struct.pack(">L", h1)+
            struct.pack(">L", h2)+struct.pack(">L", h3)+
            struct.pack(">L", h4))

Do zadania potrzebujemy również wyroczni, która będzie obliczała MAC dla podanych przez użytkownika danych oraz sprawdzała czy podany przez użytkownika skrót jest prawidłowym skrótem dla podanych przez użytkownika danych. Implementacja wyroczni poniżej:

class OracleSha1LenghtExtension(object):
    M_SECRET = b''

    def __init__(self):
        self.M_SECRET = generateRandomDataSize(1, 40)
    
    def generateMAC(self, message):
        return sha1(self.M_SECRET + message).digest()

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

Implementacja rozwiązania:

def s4challenge29():
    print("Challenge 29")
    oracle = OracleSha1LenghtExtension()
    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_sha1(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 w repozytorium: https://gitlab.com/akoltys/cryptopals .

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *