Cryptopals zestaw 2 ćwiczenie 14

przez | 16 lipca 2020

To zadanie jest kontynuacją z ćwiczenia 12. Logika użyta w tym zadaniu, jest identyczna, to co musimy to lekkie zmodyfikowanie algorytmu tak, żeby działał, niezależnie od tego czy kontrolowane przez nas dane znajdują się na początku (tak jak w zadaniu 12) czy gdzieś w środku zaszyfrowanego bloku.

To co musimy zrobić w pierwszej kolejności to wykryć ilość bajtów poprzedzających nasze dane aby móc użyć tej wartości jako offsetu w algorytmie z poprzedniego ćwiczenia.

def detectOraclePrefixSize(oracle):
    block_size = 16
    test_data = b'A'*(block_size*2)
    while True:
        ciphered_data = oracle.encrypt(test_data)
        offset = 0;
        while offset < (len(ciphered_data)-(2*block_size)):
            first_block = ciphered_data[offset:offset+block_size]
            second_block = ciphered_data[offset+block_size: offset+(2*block_size)]
            if first_block == second_block:
                padSize = len(test_data)%block_size
                return offset-padSize
            offset += 16
        test_data = test_data + b'A'
    return -1

Zasada działania tego algorytmu jest bardzo prosta: przekazujemy dwa bloki o takich samych wartościach do wyroczni i sprawdzamy czy wśród zaszyfrowanych danych też znajdziemy dwa powtarzające się bloki. Jeżeli będzie to prawda dla pierwszych dwóch bloków czyli bajty pod indeksami od 0 do 15 będą takie same jak pod indeksami od 15 do 31 to wiemy, że nasze dane wylądowały na początku (w związku z tym, że nie jest to kod produkcyjny nie pokrywa on przypadków kiedy dane których nie kontrolujemy również się powtarzają, aczkolwiek obejście tego problemu nie było by zbyt problematyczne).

Przykład 1:
Pierwsze dwa bloki się powtarzają w związku z tym:
padSize = 32%16 = 0
offset = 0
Długość danych poprzedzających nasze dane = 0 – 0 = 0.

Przykład 2
Trzeci i czwarty blok się powtarzają a długość danych testowych to 37, w związku z tym:
padSize = 37%16 = 5
offset = 32
długość danych poprzedzających nasze dane = 32 – 5 = 27.

Przykład 3
Trzeci i czwarty blok się powtarzają a długość danych testowych to 32, w związku z tym:
padSize = 32%16 = 0
offset = 32
Długość danych poprzedzających nasze dane = 32 – 0 = 32.

padSize to ilość danych ponad wielokrotność długości bloku czyli 16. Ta wartość mówi nam ile bajtów musieliśmy dodać do początkowych danych, żeby kolejne dwa bloki zawierały tylko nasze dane. Wiemy dzięki temu ile naszych bajtów zostało dodanych do bloków których nie kontrolujemy. Wiemy, w który blok jest pierwszym który się powtarza w związku z tym wiemy ile bajtów poprzedza nasze dane, musimy jedynie odjąć od nich ilość naszych dodatkowych bajtów, które wyrównały nasze dwa powtarzające się bloki. Posiadając tą informację możemy bez problemu rozwiązać to zadanie.

def s2challenge14():
    print("Challenge 14 start")
    secret_base64 = "Um9sbGluJyBpbiBteSA1LjAKV2l0aCBteSByYWctdG9wIGRvd24gc28gbXkg" \
                    "aGFpciBjYW4gYmxvdwpUaGUgZ2lybGllcyBvbiBzdGFuZGJ5IHdhdmluZyBq" \
                    "dXN0IHRvIHNheSBoaQpEaWQgeW91IHN0b3A/IE5vLCBJIGp1c3QgZHJvdmUg" \
                    "YnkK"
    oracle = OracleAesECBHarder(secret_base64)
    detected_block_size = detectOracleBlockSize(oracle)
    detected_ecb_mode = detectOracleECBMode(oracle)
    detected_prefix_size = detectOraclePrefixSize(oracle)
    detected_prefix_pad_size = detected_block_size - (detected_prefix_size%detected_block_size)
    detected_offfset = detected_prefix_size + detected_prefix_pad_size
    print("Secret size: ", len(secret_base64)*3/4)
    print("Detected block size: ", detected_block_size)
    print("Detected ECB mode: ", detected_ecb_mode)
    print("Detected prefix size: ", detected_prefix_size)
    print("Detected prefix pad size: ", detected_prefix_pad_size)
    block_num = 0
    deciphered_message = []
    previous_block = [ord('A')]*(detected_block_size+detected_prefix_pad_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
            oldBlock = ciphered_block[detected_offfset+block_offset:
                                      detected_offfset+block_offset+detected_block_size]
            newBlock = tmp_ciphered_block[detected_offfset:
                                          detected_offfset+detected_block_size]
            while newBlock != oldBlock 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))
                newBlock = tmp_ciphered_block[detected_offfset:
                                              detected_offfset+detected_block_size]
            deciphered_block += [test_val]
            pad_size += 1
        previous_block = [ord('A')]*detected_prefix_pad_size + 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))

Na początku musimy jeszcze wyliczyć offset do pierwszego bloku który jest przez nas kontrolowany. Mamy ilość danych dodawanych przez wyrocznię przed naszymi danymi i znamy długość bloku, więc wystarczy zaokrąglić do najbliższej wielokrotności długości bloku np. 27 -> 32, 5 -> 16, itd.

Posiadając te informacje można w prosty sposób zmodyfikować kod z zadania 12.

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

Dodaj komentarz

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