Cryptopals zestaw 1 ćwiczenie 7

przez | 25 maja 2020
Evariste galois.jpg
https://pl.wikipedia.org/wiki/%C3%89variste_Galois

Tym razem ćwiczenie, które można rozwiązać w „5 minut” albo spędzić z nim trochę więcej czasu i się czegoś przy okazji nauczyć. Naszym zadaniem będzie odszyfrowanie zawartości pliku podanego przez autorów. Twórcy zadania podli nawet klucz użyty do zaszyfrowania treści jak i użyty tryb AES. Wszystko podane jak na dłoni. Nic tylko pobrać PyCrypto i przejść do kolejnego zadania.

Na początku tak właśnie zrobiłem. Nie poszło mi tak gładko bo używam Pythona w wersji 3.7 w związku z tym nie mogłem zainstalować PyCrypto i musiałem pogrzebać trochę w google, żeby znaleźć PyCryptodome (https://pycryptodome.readthedocs.io/en/latest/), ale potem przeszedłem do kolejnego ćwiczenia. Potem wróciłem do tego zadania, żeby zrobić ten wpis, przeczytałem jeszcze raz jego treść i zdałem sobie sprawę, że moje rozwiązani działa, ale autorom chodziło o coś zupełnie innego. Mamy zobaczyć jak działa sam algorytm AES w trybie ECB. Dlatego stwierdziłem, że muszę to zadanie zrobić od nowa, tym razem bez żadnych dróg na skróty.

AES jest opisany np. w tym dokumencie https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf. Jest w nim zawarty pseudokod na podstawie którego można przygotować własną implementację, oczywiście nie polecam używać takiej implementacji w celach innych niż edukacyjne – jeżeli potrzebujemy kryptografii to korzystamy z gotowych produktów, które są przetestowane i używane przez wielu użytkowników. Implementacja którą tu przedstawię powstała tylko po to, żeby zdobyć elementarną wiedzę co dzieje się kiedy dane są szyfrowane/odszyfrowywane przy pomocy AESa. W skrócie: zróbcie swoją implementację, sprawdźcie czy działa, jak działa i NIGDY jej nie używajcie w poważnych projektach.

Szkielet funkcji używanych do szyfrowania/rozszyfrowywania jednego bloku danych wygląda tak:

    def encode_block(self, data, w):
        if (len(data) != 16):
            return None
        state = data
        nb = self.NB
        nr = self.NR
        
        state = self.add_round_key(state, w[0:nb])
        
        for round_nbr in range(1, nr):
            state = self.sub_bytes(state)
            state = self.shift_rows(state)
            state = self.mix_columns(state)
            state = self.add_round_key(state, w[round_nbr*nb:(round_nbr+1)*nb])
        
        state = self.sub_bytes(state)
        state = self.shift_rows(state)
        state = self.add_round_key(state, w[nr*nb:(nr+1)*nb])
        
        return state
    
    def decode_block(self, data, w):
        if (len(data) != 16):
            return None
        state = data
        nb = self.NB
        nr = self.NR
        
        state = self.add_round_key(state, w[nr*nb:(nr+1)*nb])
        for round_nbr in range(nr-1, 0, -1):
            state = self.inv_shift_rows(state)
            state = self.inv_sub_bytes(state)
            state = self.add_round_key(state, w[round_nbr*nb:(round_nbr+1)*nb])
            state = self.inv_mix_coluns(state)
        
        state = self.inv_shift_rows(state)
        state = self.inv_sub_bytes(state)
        state = self.add_round_key(state, w[0:nb])
        
        return state

W prawdziwym życiu, powyższy kod używany jest w różnych tryb trybach AESa, dziś będziemy zajmowali się najprostszym trybem – ECB. Tryb ECB polega na tym, że dane są dzielone na 16-bajtowe bloki a następnie każdy z bloków jest jest niezależnie od siebie szyfrowany, dlatego każdy blok zawierający takie same dane produkuje na wyjściu taki sam blok z zaszyfrowanymi danymi. W kolejnych ćwiczeniach przekonamy się dlaczego używanie trybu ECB jest kiepskim pomysłem.


    def encode_ecb(self, data, key):
        key_expanded = self.key_expansion(key)
        return self.encode_block(data, key_expanded)
    
    def encode(self, data, key, mode = Mode.ECB):
        if (isinstance(data, str)):
            data = bytearray(data, 'ascii')
        if (isinstance(key, str)):
            key = bytearray(key, 'ascii')
        
        if mode == self.Mode.ECB:
            return self.encode_ecb(data, key)

    def decode_ecb(self, data, key):
        result = []
        data_chunks = self.get_blocks(data)
        key_expanded = self.key_expansion(key)
        for data_chunk in data_chunks:
            result += self.decode_block(data_chunk, key_expanded)
        return bytearray(result).decode('ascii')
    
    def decode(self, data, key, mode = Mode.ECB):
        if (isinstance(data, str)):
            data = bytearray(data, 'ascii')
        if (isinstance(key, str)):
            key = bytearray(key, 'ascii')
        
        if mode == self.Mode.ECB:
            return self.decode_ecb(data, key)

Zarówno w przypadku funkcji szyfrującej jak i deszyfrującej mamy do czynienia z 4 podstawowymi funkcjami, które są używane w pętli. Ilość rund czyli inaczej to ile razy na podanym bloku danych wykonają się ter cztery funkcjie zależy od długości użytego klucza. Ta implementacja działa tylko z kluczem 128 bitowym (Przynajmniej na chwilę obecną, być może na potrzebę przyszłych zadań trzeba to będzie rozszerzyć o inne długości klucza i tryby działania).

NB – ilość bajtów w bloku – 16 (w specyfikacji jest opis dla słów 32-bitowych dlatego ta wartość jest cztery razy większa).

NR – ilość rund aktualnie ustawiona na 10, ponieważ klucz może być tylko 128-bitowy. Dla kluczy 192-bitowych było by 12 rund a dla 256-bitowych 14.

NK – ilość bajtów składających się na klucz. Klucz 128-bitowy – 16 bajtów, 192-bitowy – 24 bajty, 256-bitowy – 32 bajty (tak jak w przypadku NB – specyfikacja podaje wartości cztery razy większe ponieważ operuje na słowach 32-bitowych ).

Niezależnie od tego czy chcemy coś odszyfrować czy zaszyfrować, najpierw musimy rozszerzyć klucz – AES używa innej wartości klucza w każdej kolejnej rundzie.

    def key_expansion(self, key):
        nk = self.NK
        nb = self.NB
        nr = self.NR
        w = [0]*nb*(nr+1)
        for i in range(0, nk):
            w[i] = key[i]
        
        for i in range(nk, nb*(nr+1), 4):
            temp = w[i-4:i]
            if i%nk == 0:
                temp = self.sub_bytes(self.rot_word(temp))
                idx = int(i/nk)
                temp[0] = temp[0] ^ self.R_CON[idx]
            elif nk > 6 and i%nk == 0:
                temp = self.sub_bytes(temp)
            w[i] = w[i-nk] ^ temp[0]
            w[i+1] = w[i-nk+1] ^ temp[1]
            w[i+2] = w[i-nk+2] ^ temp[2]
            w[i+3] = w[i-nk+3] ^ temp[3]
        
        return w

Jest to implementacja pseudokodu podanego we wcześniej wspomnianym dokumencie, więc nie będę się rozpisywał nad zasadą jego działania. Chcę jednak zwrócić uwagę na moment kiedy zmienna temp jest XORowana z wartościami ze stałej tablicy R_CON. To, że tylko najmłodszy bajt jest XORowany a pozostałe zostają niezmienione to nie błąd, w mojej implementacji R_CON to tablica stałych wartości 8-bitowych, w specyfikacji jest to słowo 32-bitowe w którym najstarsze trzy bajty mają wartość 0 w związku z tym XOR z nimi nic nie zmienia.

Wartości tablicy R_CON można wyliczyć ze wzoru:
1 jeżeli i = 1
RCON[i] = 2*RCON[i-1] jeżeli RCON[i-1] < 0x80
2*RCON[i-1] +0x1B jeżeli RCON[i-1] >= 0x80
Ja obliczone wartości umieściłem w tablicy, dodatkowo pod indeksem 0 wstawiłem wartość 0.

    def rot_word(self, w):
        return [w[1], w[2], w[3], w[0]]

Funkcja rot_word przesuwa wszystkie bajty w prawo (tak jak byśmy dzielili przez 256) i ustawia najmłodszy jako najstarszy.

    def sub_bytes(self, s):
        for i in range(0, len(s)):
            s[i] = self.S_BOX[s[i]]
        return s

    def inv_sub_bytes(self, s):
        for i in range(0, len(s)):
            s[i] = self.INVS_BOX[s[i]]
        return s

Funkcje sub_bytes i inv_sub_bytes robią to samo tylko używają innej tablicy stałych S_BOX lub INVS_BOX – są to tablice stałych podane w specyfikacji.

    def shift_rows(self, s):
        s[0], s[4], s[8] , s[12] = s[0] , s[4] , s[8] , s[12] 
        s[1], s[5], s[9] , s[13] = s[5] , s[9] , s[13], s[1] 
        s[2], s[6], s[10], s[14] = s[10], s[14], s[2] , s[6] 
        s[3], s[7], s[11], s[15] = s[15], s[3] , s[7] , s[11]
        return s

    def inv_shift_rows(self, s):
        s[0], s[4], s[8] , s[12] = s[0] , s[4] , s[8] , s[12] 
        s[1], s[5], s[9] , s[13] = s[13], s[1] , s[5] , s[9] 
        s[2], s[6], s[10], s[14] = s[10], s[14], s[2] , s[6] 
        s[3], s[7], s[11], s[15] = s[7] , s[11], s[15], s[3]
        return s

Funkcje shift_rows oraz inv_shift_rows przesuwają wiersze w bloku 16-bajtowym. Funkcja shift_rows przesuwa bajty w lewo:
– w pierwszym wierszu żaden bajt nie jest przesunięty.
– w drugim wierszy pierwszy bajt przesuwamy na koniec a pozostałe trzy bajty są przesunięte o jedną pozycję w lewo
– w trzecim wierszu pierwsze dwa bajty przesuwamy na koniec a pozostałe dwa bajty o dwie pozycje w lewo.
– w czwartym wierszu pierwsze trzy bajty przesuwamy na koniec a ostatni bajt o trzy pozycje w lewo.
Funkcja inv_shift_rows działa w przeciwnym kierunku:
– w pierwszym wierszu żaden bajt nie jest przesunięty.
– w drugim wierszu ostatni bajt przesuwamy na początek a pozostały bajty przesuwamy o jedną pozycją w prawo.
– w trzecim wierszu ostatnie dwa bajty przesuwamy na początek a pozostałe dwa bajty o dwie pozycje w prawo.
– w czwartym wierszy ostatnie trzy bajty przesuwamy na początek a pierwszy baj o trzy pozycje w prawo.

    def galois_mul(self, a, b):
        result = 0x0
        for i in range(0, 8):
            if b&0x1 != 0:
                result = result ^ a
            
            hbit = (a&0x80 != 0)
            a = (a<<1)&0xff
            if (hbit):
                a = a ^ 0x1B
            b = (b>>1)&0xff
        return (result&0xff)

    def mix_column(self, r0, r1, r2, r3):
        a = [r0, r1, r2, r3]
        r0 = (self.galois_mul(2, a[0]) ^ self.galois_mul(3, a[1]) ^ a[2] ^ a[3])&0xFF
        r1 = (self.galois_mul(2, a[1]) ^ self.galois_mul(3, a[2]) ^ a[3] ^ a[0])&0xFF
        r2 = (self.galois_mul(2, a[2]) ^ self.galois_mul(3, a[3]) ^ a[0] ^ a[1])&0xFF
        r3 = (self.galois_mul(2, a[3]) ^ self.galois_mul(3, a[0]) ^ a[1] ^ a[2])&0xFF
        return r0, r1, r2, r3
    
    def mix_columns(self, s):
        s[0] , s[1] , s[2] , s[3]  = self.mix_column(s[0] , s[1] , s[2] , s[3])
        s[4] , s[5] , s[6] , s[7]  = self.mix_column(s[4] , s[5] , s[6] , s[7])
        s[8] , s[9] , s[10], s[11] = self.mix_column(s[8] , s[9] , s[10], s[11])
        s[12], s[13], s[14], s[15] = self.mix_column(s[12], s[13], s[14], s[15])
        return s
    
    def inv_mix_column(self, r0, r1, r2, r3):
        a = [r0, r1, r2, r3]
        r0 = (self.galois_mul(14, a[0]) ^ self.galois_mul(11, a[1]) ^ self.galois_mul(13, a[2]) ^ self.galois_mul(9, a[3]))&0xFF
        r1 = (self.galois_mul(14, a[1]) ^ self.galois_mul(11, a[2]) ^ self.galois_mul(13, a[3]) ^ self.galois_mul(9, a[0]))&0xFF
        r2 = (self.galois_mul(14, a[2]) ^ self.galois_mul(11, a[3]) ^ self.galois_mul(13, a[0]) ^ self.galois_mul(9, a[1]))&0xFF
        r3 = (self.galois_mul(14, a[3]) ^ self.galois_mul(11, a[0]) ^ self.galois_mul(13, a[1]) ^ self.galois_mul(9, a[2]))&0xFF
        return r0, r1, r2, r3    
    
    def inv_mix_coluns(self, s):
        s[0] , s[1] , s[2] , s[3]  = self.inv_mix_column(s[0] , s[1] , s[2] , s[3])
        s[4] , s[5] , s[6] , s[7]  = self.inv_mix_column(s[4] , s[5] , s[6] , s[7])
        s[8] , s[9] , s[10], s[11] = self.inv_mix_column(s[8] , s[9] , s[10], s[11])
        s[12], s[13], s[14], s[15] = self.inv_mix_column(s[12], s[13], s[14], s[15])
        return s

To była dla mnie najtrudniejsza część, sam algorytm jest prosty natomiast pochopnie założyłem, że podane we wzorze działanie mnożenia to zwykły iloczyn w związku z tym otrzymywałem błedne wyniki. Operacja odwrotna różni się jedynie współczynnikami przez które wymnażamy podany blok danych.

MIX_COLUMNS: a(x) = {03}x^3 + {01}x^2 + {01}x + {02}
INV MIX_COLUMNS: a^-1(x) = {0b}x^3 + {0d}x^2 + {09}x + {0e}

Już na pierwszy rzut oka widać, że to nie może być tak proste. Jeżeli kogoś interesuje jak to dokładnie działa polecam zacząć od: https://pl.wikipedia.org/wiki/Cia%C5%82o_sko%C5%84czone .

Na początku oczywiście w implementacji wkradły się błędy w związku z tym algorytmem nie dało się niczego odkodować, nawet informacji wcześniej nim zaszyfrowanych. W wyszukiwaniu błędów bardzo pomocne były przykładowe wywołania funkcji rozszerzania klucza oraz szyfrowania. Podane są wartości danych wejściowych i to jak się one zmieniają w każdej rundzie, w związku z tym bardzo szybko można namierzyć miejsce w którym się popełniło błąd.

Moją implementację można znaleźć tutaj: https://gitlab.com/akoltys/cryptopals.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *