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 .