Cryptopals zestaw 4 ćwiczenie 28

Tym razem pozornie mało kreatywne ćwiczenie, żeby nie powiedzieć odtwórcze, ale warto jest się do niego przyłożyć i postarać się jak najlepiej zrozumieć co dokładnie robi algorytm który mamy zaimplementować.

W tym zadaniu naszym celem jest implementacja algorytmu SHA-1 i nie wystarczy użyć gotowej implementacji oferowanej przez język programowania, którego używamy do rozwiązywania tych ćwiczeń. Nasza implementacja przyda się nam później do rozwiązywania kolejnych ćwiczeń, ponieważ łatwiej będzie nam modyfikować sposób w jaki działa.

Co to w ogóle jest SHA-1 i do czego służy? Sama nazwa pochodzi od Secure Hash Algorithm, a numer 1 oznacza wersję algorytmu (więcej na temat temat rodziny algorytmów SHA można przeczytać na Wikipedii -> https://pl.wikipedia.org/wiki/SHA). Sam algorytm jest funkcją skrótu albo inaczej funkcją hashującą – na podstawie danych o dowolnej długości przy pomocy pewnych operacji na tych danych oblicza krótki ciąg wartości. Algorytm SHA-1 tworzy 160-bitowy ciąg skrótu danych wejściowych.

Moja implementacja SHA-1 bazuje na pseudokodzie dostępnym na Wikipedii i wygląda następująco:

def rotate32_left(val, n):
    val = val & 0xffffffff
    return (val<<n | val >> (32-n))&0xffffffff  

def custom_sha1(msg):
    h0 = 0x67452301
    h1 = 0xefcdab89
    h2 = 0x98badcfe
    h3 = 0x10325476
    h4 = 0xc3d2e1f0
    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)
    print("Msg: ", msg)
    print("Len: ", len(msg), " AppLen: ", pad_len)
    # append bit size of the message
    msg = msg + struct.pack(">Q", msg_len*8)
    print("Msg: ", msg)
    print("Len: ", len(msg))
    chunks = [msg[i:i+64] for i in range(0, len(msg)-63, 64)]
    for chunk in chunks:
        print("Chunk size:", len(chunk), "Chunk: ", chunk)
        w = [0]*80
        for i in range(0, 16):
            w[i] = int.from_bytes(chunk[4*i:4*(i+1)], byteorder='big', signed=False)
            print("W[", i,"]= ", hex(w[i]), " raw= ", chunk[4*i:4*(i+1)])
        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
    print("Final state: ", hex(h0), hex(h1), hex(h2), hex(h3), hex(h4))
    return (struct.pack(">L", h0)+struct.pack(">L", h1)+
            struct.pack(">L", h2)+struct.pack(">L", h3)+
            struct.pack(">L", h4))

Mamy już funkcję hashującą teraz przy jej pomocy możemy stworzyć MAC – czyli Message Authentication Code czyli skrót dzięki któremu będziemy w stanie czy otrzymane przez nas dane nie zostały przez nikogo zmodyfikowane, albo innymi słowy je uwierzytelnić. Samo obliczenie skrótu nie jest wystarczające, ponieważ ktoś mógłby podmienić dane i obliczyć nowy skrót i dostarczyć je nam zamiast danych, które faktycznie mieliśmy otrzymać. Aby rozwiązać ten problem, do danych dodawany jest klucz. Jeżeli klucz jest znany jedynie nadawcy i odbiorcy to znacznie trudniej jest osobie trzeciej podrobić wartość skrótu tak aby po podmienieniu danych skrót nadal był prawidłowy.

Samo działanie jest banalne i polega na doklejeniu klucza przed danymi. Moja implementacja poniżej:

def s4challenge28():
    print("Challenge 28")
    test_message = b'Hello, World'
    tmp_mac1 = custom_sha1(b'secret_key1'+test_message)
    tmp_mac2 = custom_sha1(b'secret_key2'+test_message)
    tmp_mac3 = custom_sha1(b'secret_key3'+test_message)
    tmp_mac4 = custom_sha1(b'secret_key4'+test_message)
    print("Hash1: ", tmp_mac1.hex())
    print("Hash2: ", tmp_mac2.hex())
    print("Hash3: ", tmp_mac3.hex())
    print("Hash4: ", tmp_mac4.hex())

W ramach testu obliczane są wartości skrótów dla tej samej wiadomości, ale przy użyciu czterech różnych kluczy. Pomimo tego, że klucze różnią się zaledwie jednym bajtem to wartość samego skrótu jest za każdym razem zupełnie inna.

Kod dostępny na https://gitlab.com/akoltys/cryptopals.