I tym razem będziemy wykorzystywali własność trybu ECB, ale teraz dostaniemy bardzo twardy dowód na to, że używanie AES w tym trybie to bardzo zły pomysł.
Na początek będziemy potrzebowali tzw. wyroczni, albo po angielsku Oracle. Wyrocznia to taki fajny i bardzo interesujący byt, posiada losowo wygenerowany klucz przy pomocy którego szyfrowane są dane przekazywane przez użytkownika. Na potrzeby tego zadania stworzyłem klasę OracleAesECB.
class OracleAesECB(object):
M_ENCRYPTION_KEY = b''
M_CIPHER = None
M_TARGET = b''
def __init__(self, payload):
self.M_ENCRYPTION_KEY = generateRandomData(16)
self.M_TARGET = bytes_from_base64(payload)
def encrypt(self, input_data):
self.M_CIPHER = AES.new(self.M_ENCRYPTION_KEY, AES.MODE_ECB)
plain = input_data + self.M_TARGET
plain = addPaddingPKCS7(plain, 16)
return self.M_CIPHER.encrypt(plain)Konstruktor klasy generuje losowy klucz o długości 16 bajtów i zapisuje go w zmiennej M_ENCRYPTION_KEY oraz odkodowuje z base64 sekret przekazany jako parametr i zapisuje go w zmiennej M_TARGET. M_TARGET to sekret, który będziemy musieli odzyskać. Oprócz konstruktora klasa ma jeszcze jedną metodę, której będziemy używali do odzyskania sekretu. Metoda do danych przekazanych przez użytkownika w zmiennej input_data dodaje sekret i wyrównuje długość całości, tak aby była wielokrotnością długości pojedyńczego bloku, dodając odpowiedni „padding” a następnie wszystko szyfruje AES w trybie ECB i zwraca zaszyfrowane dane użytkownikowi.
W kolejnym kroku stworzyłem funkcję, która wykrywa długość bloku używanego przez wyrocznię:
def detectOracleBlockSize(oracle):
test_data = b''
empty_size = len(oracle.encrypt(test_data))
next_size = empty_size
while empty_size == next_size:
test_data = test_data + b'A'
next_size = len(oracle.encrypt(test_data))
return (next_size-empty_size)Zasada działania tej funkcji jest prosta: przy do metody encrypt przekazujemy dane o długości 0 bajtów i zapamiętujemy długość zaszyfrowanych danych. W kolejnym kroku przekazujemy do metody encrypt dane o długości 1, 2, 3 itd. bajtów do momentu aż długość otrzymanych zaszyfrowanych danych będzie inna niż ta otrzymana na początku (kiedy przekazaliśmy dane o długości 0 bajtów). Różnica między nową i starą długością danych jest długością bloku używanego przez wyrocznię. To działa ponieważ używany jest padding, który wyrównuje dane tak aby były wielokrotnością długości jednego bloku danych. W związku z tym przekazując coraz to dłuższe dane do metody encrypt w pewnym momencie dochodzimy do momentu kiedy dane zwiększą się o kolejny blok.
Funkcję do wykrywania w jakim trybie działa dana wyrocznia omawiałem w poprzednim wpisie (https://koltys.info/blog/2020/06/30/cryptopals-zestaw-2-cwiczenie-11/).
Na tym etapie, wiemy już że wyrocznia używa AES w trybie ECB oraz znamy długość bloku. Dodatkowo wiemy, że do naszych danych dodawane są dane, których treść chcemy poznać. Okazuje się, że jest na to bardzo prosty sposób (oczywiście pod warunkiem, że mamy „wyrocznię”). Zgodnie z właściwością trybu ECB, która jest wałkowana już od kilku ćwiczeń:
Takie same bloki danych wejściowych zawsze produkują takie same bloki danych wyjściowych.
Jeżeli nasze dane będą krótsze o jeden bajt niż wynosi długość bloku danych to na końcu będzie znajdował pierwszy bajt sekretnej wiadomości. Jeżeli nasze dane będą krótsze o dwa bajty, na końcu będą dwa bajty sekretnej wiadomości itd. Poniżej przykład dla bloku danych o długości 8 bajtów.
| D1 | D2 | D3 | D4 | D5 | D6 | D7 | S1 | S2 | S3 | … | Sn-1 | Sn |
| D1 | D2 | D3 | D4 | D5 | D6 | S1 | S2 | S3 | … | Sn-1 | Sn | X |
| D1 | D2 | D3 | D4 | D5 | S1 | S2 | S3 | … | Sn-1 | Sn | X | X |
Na początku przygotowujemy, dane krótsze o 1 bajt niż używana przez wyrocznię długość bloku i „prosimy” wyrocznię, żeby nam je zaszyfrowała. Wiemy, że w zaszyfrowanych danych pierwszy blok zawiera tylko jeden bajt którego wartości nie znamy. Zapamiętujemy sobie ten blok. Teraz „poprosimy” wyrocznię, żeby jeszcze raz coś nam zaszyfrowała, ale tym razem nasze dane będą miały długość równą długości bloku używanego przez wyrocznię. Jako ostatni bajt będziemy podawali po kolei wartości od 0 do 255 do momentu aż pierwszy blok zaszyfrowanych danych będzie miał taką samą wartość jak zapamiętany przez nas blok który uzyskaliśmy przy pierwszym wywołaniu np.:
- Wyrocznia ma długość bloku 16 bajtów i pracuje w trybie ECB.
- Do wyroczni za pierwszym razem przekazaliśmy wartość „AAAAAAAAAAAAAAA” (15 znaków 'A’) i dostaliśmy jakieś zaszyfrowane dane.
- W następnym kroku sprawdzamy co otrzymamy kiedy przekażemy do wyroczni wartość „AAAAAAAAAAAAAAA\x00” (15 znaków 'A’ i bajt o wartości 0x00). Jeżeli pierwszy blok zaszyfrowanych danych jest taki sam jak ten otrzymany w punkcie 1. oznacza to, że znamy pierwszą wartość sekretnej wiadomości, jeżeli nie próbujemy „AAAAAAAAAAAAAAA\x01”, „AAAAAAAAAAAAAAA\x02” itd. aż do „AAAAAAAAAAAAAAA\xff”.
- Znamy już pierwszy bajt sekretu – załóżmy, że ma on wartość 'S’, więc tym przekazujmy wyroczni wartość „AAAAAAAAAAAAAA” (14 znaków 'A’). i dostajemy jakieś zaszyfrowane dane. Teraz też, znamy wartości pierwszych piętnastu bajtów: „AAAAAAAAAAAAAAS” i znów musimy odgadnąć tylko wartość ostatniego bajtu. Postępujemy tak samo jak w punkcie 3. ale tym razem próbujemy wartości „AAAAAAAAAAAAAAS\x00”, „AAAAAAAAAAAAAAS\x01” itd. aż do „AAAAAAAAAAAAAAS\xff”.
- Teraz wiemy już, że drugi bajt ma wartość np. E. Powtarzamy tą procedurę do momentu aż odszyfrujemy cały pierwszy blok danych. Za każdym razem musimy sprawdzić w najgorszym przypadku 256 możliwości.
- Jeżeli sekretna wiadomości jest dłuższa niż jeden blok danych (najprawdopodobniej tak będzie) to po odszyfrowaniu pierwszego bloku, powtarzamy czynność od początku ale tym razem zapamiętujemy nie pierwszy a drug blok danych. Jeżeli podaliśmy wyroczni dane o długości 15 bajtów to w drugim bloku będzie 15 znanych nam bajtów i jeden bajt z kolejnego bloku. Cała procedura wygląda identycznie jak w pierwszym bloku danych, po prostu porównujemy drugie bloki zamiast pierwszych.
- Po odszyfrowaniu drugiego bloku znowu zaczynamy od początku ale tym razem zapamiętujemy trzeci blok danych itd. aż w końcu odszyfrujemy całą wiadomość.
Moja implementacja tego algorytmu wygląda następująco:
def s2challenge12():
print("Challenge 12 start")
secret_base64 = "Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg" \
"aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq" \
"dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg" \
"YnkK"
oracle = OracleAesECB(secret_base64)
detected_block_size = detectOracleBlockSize(oracle)
detected_ecb_mode = detectOracleECBMode(oracle)
print("Secret size: ", len(secret_base64)*3/4)
print("Detected block size: ", detected_block_size)
print("Detected ECB mode: ", detected_ecb_mode)
block_num = 0
deciphered_message = []
previous_block = [ord('A')]*(detected_block_size)
decyphering_running = True
while decyphering_running:
deciphered_block = []
pad_size = 1
while pad_size <= detected_block_size:
test_block = previous_block[pad_size:]
ciphered_block = oracle.encrypt(bytearray(test_block))
test_val = 0x0
tmp_block = test_block+deciphered_block+[test_val]
tmp_ciphered_block = oracle.encrypt(bytearray(tmp_block))
block_offset = block_num*detected_block_size
while tmp_ciphered_block[0:detected_block_size] != ciphered_block[block_offset:block_offset+detected_block_size] and test_val < 255:
test_val = test_val + 1
tmp_block = test_block+deciphered_block+[test_val]
tmp_ciphered_block = oracle.encrypt(bytearray(tmp_block))
deciphered_block += [test_val]
pad_size += 1
previous_block = deciphered_block
deciphered_message += deciphered_block
block_num += 1
if block_num >= len(ciphered_block)/detected_block_size:
decyphering_running = False
print(bytearray(deciphered_message))Cały kod można znaleźć na: https://gitlab.com/akoltys/cryptopals .
[AKTUALIZACJA]
Ten atak można przeprowadzić również na dane zaszyfrowane w trybie CBC. W tym wypadku fakt, że takie same bloki danych wejściowych produkują takie same bloki danych wyjściowych też ma tu zastosowanie ponieważ kontrolujemy dane znajdujące się przed sekretem, więc mamy wpływ na to z czym są XORowane następne bloki, więc sytuacja jest identyczna.