Cryptopals zestaw 4 ćwiczenie 25

Nowy, czwarty już, zestaw ćwiczeń zaczynamy od powrotu do AES w trybie CTR. Po raz kolejnym musimy odszyfrować tekst zaszyfrowany wyżej wymienionym sposobem.

Zgodnie z tradycją zanim przystąpimy do odszyfrowywania sekretu musimy najpierw przygotować sobie wyrocznię, którą będziemy „atakowali”. Założenia są następujące:

1. Wyrocznie przechowuje sekret, a użytkownik może otrzymać jego zaszyfrowaną postać.
2. Użytkownik może modyfikować zawartość sekretu, poprzez podanie offsetu i wartości na jaką wybrany fragment ma być podmieniony.

Autorzy udostępniają plik zawierający dane zaszyfrowane AES ECB przy użyciu klucza „YELLOW SUBMARINE”. Dane należy odszyfrować i przekazać naszej wyroczni.

Moja implementacja wyroczni:

class OracleRandomAccessRWCtr(object):
    M_ENCRYPTION_KEY = b''
    M_SECRET = b''
    M_NONCE = b''
    
    def __init__(self, data):
        cipher = CustomAES()
        self.M_NONCE = c_uint64(abs(randint(0, 0xffffffffffffffff)))
        self.M_ENCRYPTION_KEY = generateRandomData(16)
        self.M_SECRET = cipher.encode(data, self.M_ENCRYPTION_KEY,
                                      CustomAES.Mode.CTR, self.M_NONCE)
    
    def getSecret(self):
        return self.M_SECRET
    
    def updateSecret(self, value, offset):
        cipher = CustomAES()
        start_blk = int(offset/16)
        num_blk = offset%16 + int(len(value)/16)
        num_blk = num_blk + 1 if ((offset+len(value))%16) > 0 else num_blk
        tmp = self.M_SECRET[start_blk*16:(start_blk+num_blk)*16]
        tmp = cipher.decode(tmp, self.M_ENCRYPTION_KEY,
                            CustomAES.Mode.CTR, self.M_NONCE, start_blk)
        tmp[offset%16:offset%16+len(value)] = value
        tmp = cipher.encode(tmp, self.M_ENCRYPTION_KEY,
                            CustomAES.Mode.CTR, self.M_NONCE, start_blk)
        self.M_SECRET[start_blk*16:(start_blk+num_blk)*16] = tmp
    
    def getPlain(self):
        cipher = CustomAES()
        return cipher.decode(self.M_SECRET, self.M_ENCRYPTION_KEY,
                            CustomAES.Mode.CTR, self.M_NONCE)

Wyrocznia generuje losowy klucz szyfrujący i losową wartość NONCE. Dodatkowo dodałem metodę getPlain(), w celu ułatwienia weryfikacji czy sekret został prawidłowo odszyfrowany. Sama funkcja podmiany części sekretu na nową wartość działa bardzo prosto, należ jedynie pamiętać, żeby podmieniać całe bloki danych wyrównane do długości bloku czyli 16 bajtów. Przykładowo jeżeli chcemy podmienić dane pod offsetem 0 i długości 5 bajtów to musimy podmienić bajty od 0 do 15 czyli pierwszy blok danych. Gdyby użytkownik chciał podmienić dane pod offsetem 33 o długości 36 bajtów to musimy podmienić bajty od 32 do 80 czyli 3, 4 i 5 blok danych.

Sam atak jest bardzo prosty, ponieważ zmieniamy jedynie wartość sekrety i nie zmieniamy klucza szyfrującego ani wartości NONCE to możemy wykorzystać właściwość trybu CTR, która mówi o tym, że dane same w sobie nie są szyfrowane a jedynie xorowane z jakąś wartością która została zaszyfrowana jakimś kluczem.
SEKRET ^ XXXXXXXXXXXXXXXX = ZASZYFROWANE_DANE.
Po zmianie danych pod wybranym offsetem:
NOWY_SEKRET ^ XXXXXXXXXXXXXXXX = NOWE_ZASZYFROWANE_DANE.
Znamy wartość zaszyfrowanych danych przed naszymi zmianami, znamy nową wartość sekretu i znamy nową wartość zaszyfrowanych danych.
Jeżeli nowe zaszyfrowane dane xorujemy z nową wartością sekretu to dostaniemy wartość z którą była xorowana pierwotna wartość sekretu (oznaczona przeze mnie jako XXXXXXXXXXXXXXXX). Znając tą wartość możemy xorować ją z pierwotną wartością zaszyfrowanych danych i w ten sposób otrzymamy odszyfrowany sekret. Jeżeli każemy wyroczni podmienić dane na wartości 0x00 to od razu otrzymamy wartości z którymi był xorowany sekret ponieważ XY ^ 0x00 = XY.

Moje rozwiązanie zadanie:

def s4challenge25():
    print("Challenge 25")
    with open('testfiles/25.txt') as f:
        plain_data = f.read().replace('\n', '')
    plain_data = bytes_from_base64(plain_data)
    cipher = AES.new(b'YELLOW SUBMARINE', AES.MODE_ECB)
    plain_data = cipher.decrypt(plain_data)
    
    oracle = OracleRandomAccessRWCtr(plain_data)
    print(oracle.getPlain())
    secret = b''+oracle.getSecret()
    print(secret)
    oracle.updateSecret(bytearray([0]*len(secret)), 0)
    tmp_secret = oracle.getSecret()
    print(bytes_xor(secret, tmp_secret))

Ja założyłem, że można podmienić dowolną ilość danych, natomiast gdyby było ograniczenie na to ile znaków może być jednocześnie zmienionych, trzeba by było wykonać odpowiednią ilość iteracji.

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