Cryptopals zestaw 3 ćwiczenie 17

przez | 15 sierpnia 2020

Pierwsze zadanie z zestawu trzeciego i przynajmniej na razie ostatnie związane z trybem CBC. Zadanie jest bardzo ciekawe ponieważ pokazuje, że do odszyfrowania danych które wcześniej zostały zaszyfrowane AES w trybie CBC wystarczy informacja o tym, czy padding danych był prawidłowy.

Tradycyjnie już, zanim przejdziemy do rozwiązywania zadania, musimy przygotować wyrocznię. Tym razem nasza nowa wyrocznia na początku wybiera jeden z dziesięciu przygotowany przez autorów sekret, generuje losowy klucz. Pierwsza z funkcji dodaje do wiadomości padding a następnie szyfruje dane przy pomocy AES w trybie CBC i zwraca zaszyfrowane dane oraz IV (wektor inicjalizujący) – dokładnie to zwraca tablicę bajtów w którzej pierwszy blok jest wektorem inicjalizującym. Druga funkcja odszyfrowuje dane (pierwszego bloku używa jako wektora inicjalizującego) i sprawdza padding, jeżeli jest on poprawny funkcja zwraca True w przeciwnym razie False. Moja implementacja poniżej (funkcja stripPKCS7 jest omówiona w opisie ćwiczenia 15: https://koltys.info/blog/2020/07/28/cryptopals-zestaw-2-cwiczenie-15/):

class OracleCbcPadding(object):
    M_SECRETS = [
        (b'MDAwMDAwTm93IHRoYXQgdGhlIHBhcnR5IGlzIGp1bXBpbmc='),
        (b'MDAwMDAxV2l0aCB0aGUgYmFzcyBraWNrZWQgaW4gYW5kIHRoZSBWZWdhJ3MgYXJlIHB1bXBpbic='),
        (b'MDAwMDAyUXVpY2sgdG8gdGhlIHBvaW50LCB0byB0aGUgcG9pbnQsIG5vIGZha2luZw=='),
        (b'MDAwMDAzQ29va2luZyBNQydzIGxpa2UgYSBwb3VuZCBvZiBiYWNvbg=='),
        (b'MDAwMDA0QnVybmluZyAnZW0sIGlmIHlvdSBhaW4ndCBxdWljayBhbmQgbmltYmxl'),
        (b'MDAwMDA1SSBnbyBjcmF6eSB3aGVuIEkgaGVhciBhIGN5bWJhbA=='),
        (b'MDAwMDA2QW5kIGEgaGlnaCBoYXQgd2l0aCBhIHNvdXBlZCB1cCB0ZW1wbw=='),
        (b'MDAwMDA3SSdtIG9uIGEgcm9sbCwgaXQncyB0aW1lIHRvIGdvIHNvbG8='),
        (b'MDAwMDA4b2xsaW4nIGluIG15IGZpdmUgcG9pbnQgb2g='),
        (b'MDAwMDA5aXRoIG15IHJhZy10b3AgZG93biBzbyBteSBoYWlyIGNhbiBibG93')
    ]
    
    M_SECRET = None
    M_ENCRYPTION_KEY = b''
    
    def __init__(self):
        self.M_SECRET = addPaddingPKCS7(choice(self.M_SECRETS), 16)
        self.M_ENCRYPTION_KEY = generateRandomData(16)
    
    def getCookie(self):
        iv = generateRandomData(16)
        cipher = AES.new(self.M_ENCRYPTION_KEY, AES.MODE_CBC, iv)
        return bytearray(iv) + bytearray(cipher.encrypt(self.M_SECRET))
    
    def consumeCookie(self, cookie):
        cipher = AES.new(self.M_ENCRYPTION_KEY, AES.MODE_CBC, cookie[:16])
        data = cipher.decrypt(cookie[16:])
        try:
            stripPKCS7(data, 16)
        except:
            return False
        else:
            return True

I teraz nasuwa się oczywiście pytanie, jak rozszyfrować dane mając jedynie informacje o tym, czy padding ma prawidłową wartość? Okazuje się, że nie tylko jest to możliwe, ale również dość proste. Jeżeli zmienimy wartość ostatniego bajtu w przedostatnim bloku danych przekazanych do drugiej funkcji (w moim wypadku nazywa się ona consumeCookie) i okaże się, że padding jest prawidłowy to znaczy, że wartość paddingu najprawdopodobniej wynosi 0x01. Oczywiście może okazać się, że prawidłowa wartość paddingu o wartości 0x01 jest dla niezmienionej wiadomości. O tym dowiemy się, jeżeli sprawdzimy wszystkie pozostałe wartości i dla żadnej padding nie będzie prawidłowy. Jeżeli już znamy wartość jaka znajduje się na końcu przedostatniego bloku zmodyfikowanej wiadomości to możemy przy pomocy kilku operacji XOR obliczyć wartość ostatniego bajtu całej wiadomości.

Wiemy, że podczas odszyfrowywania wiadomości zaszyfrowanej przy pomocy AES w trybie CBC, ostatnia operacja to XOR z poprzednim blokiem. Czyli jeżeli mamy dane od długości dwóch bloków, po 16 bajtów każdy:
plainData[0:31] – dane niezaszyfrowane,
cipheredData[0:31] -dane zaszyfrowane.
To aby uzyskać niezaszyfrowane dane z ostatniego bloku musimy w ostatniej operacji:
1. Odszyfrować ostatni blok czyli cipheredData[16:31] – odszyforwane dane nazwijmy dla wygody midData[16:31],
2. Wykonać operację XOR midData[16:31] z cipheredData[0:15].

To co aktualnie wiemy to:
1. Jaka jest wartość ostatniego bajtu w wiadomości,
2. Jaka jest wartość ostatniego bajtu w przedostatnim bloku wiadomości.
3. Jaka była oryginalna wartość ostatniego bajtu w przedostatnim bloku wiadomości.
midData[31]^cipheredData[15] = plainData[31].
Oznaczmy, nasz nasza zmodyfikowaną wiadomość jako cipheredDataBis:
midData[31]^cipheredDataBis[15] = 0x01.
W tym równaniu jest tylko jedna niewiadoma midData[31]! Mamy proste równanie z jedną niewiadomą, wykorzystując właściwości funkcji XOR otrzymujemy:
midData[31] = 0x01 ^ cipheredDataBis[15]. Teraz wróćmy do pierwotnego równania dla niezmodyfikowanej wiadomości:
plainData[31] = midData[31]^cipheredData[15].
Teraz mamy już tylko jedną niewiadomą! Podstawiamy wcześniej obliczony wzór na midData[31] i otrzymujemy:
plainData[31] = 0x01 ^ cipheredDataBis[15] ^ cipheredData[15].
W ten sposób obliczyliśmy wartość ostatniego bajtu w odszyfrowanej wiadomości. Teraz będziemy modyfikowali dwa ostatnie bajty przedostatniego bloku, tak żeby usykać prawidłowy padding o wartości 0x02. Czy po odszyfrowaniu dwa ostanie bajty będą miały wartość 0x02. Nie musimy sprawdzać wszystkich 65536 kombinacji, ponieważ znając ostatni bajt oryginalnej wiadomości możemy obliczyć jaka powinna być wartość ostatniego bajtu w przedostatnim bloku:
cipheredDataBis[15] = plainData[31]^ cipheredData[15] ^ paddingValue.
plainData[31] – obliczyliśmy w poprzedniej iteracji,
cipheredData[15] – wartość oryginalnej zaszyftowanej wiadomości,
paddingValue – wartość paddingu jaką chcemy uzyskać po odszyfrowaniu zmodyfikowanej wiadomości.
W przypadku przedostatniego bajtu w przedostatnim bloku postępujemy tak jak poprzednio, czyli sprawdzamy wszystkie wartości od 0 do 255 (oprócz oryginalnej wartości) do momentu, aż okaże się, że padding jest prawidłowy (jeżeli żadna wartość nie pozwoli uzyskać prawidłowego paddingu oznacza to, że szukaną przez nas wartością jest ta pierwotna). Korzystamy z naszego wzoru ale tym razem wiemy, że:
midData[30] = 0x02 ^ cipheredDataBis[14],
Dla kolejnych bajtów postępujemy analogicznie:
midData[29] = 0x03 ^ cipheredDataBis[13],
midData[28] = 0x04 ^ cipheredDataBis[12],
midData[27] = 0x05 ^ cipheredDataBis[11],
itd.
Kiedy już odszyfrujemy ostatni blok danych, skracamy wiadomość o ten jeden blok i powtarzamy wszystko od nowa do momentu aż zostanie nam tylko jeden blok danych – jest to wektor inicjalizujący. Moja implementacja poniżej:

def s3challenge17():
    print("Challenge 17")
    oracle = OracleCbcPadding()
    secret = oracle.getCookie()
    decSecret = []
    print("Secret: ", secret)
    while (len(secret) >= 32):
        tmpSecret = bytearray(secret)
        decChunk = []
        for padSize in range(1, 17):
            tmpChunk = secret[-32:-16]
            tmpVal = secret[-16-padSize]
            for padVal in range(0, 256):
                if (padVal != secret[-16-padSize]):
                    tmpChunk[-padSize] = padVal
                    for idx in range(0, len(decChunk)):
                        tmpChunk[-padSize+1+idx] = decChunk[idx]^padSize ^\
                                                   secret[-padSize+idx+1-16]
                    tmpSecret = bytearray([0*x for x in range(0,16)]) + \
                                secret[:-32]+tmpChunk+secret[-16:]
                    if (oracle.consumeCookie(tmpSecret) == True):
                        tmpVal = padVal
                        break
            orgVal = secret[-16-padSize]
            decVal = tmpVal ^ orgVal ^ padSize
            decChunk = [decVal] + decChunk

        decSecret = decChunk + decSecret
        secret = secret[:-16]
    print("Deciphered secret: ", [chr(x) for x in decSecret])
    print(bytearray(decSecret))

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

Dodaj komentarz

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