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 stateW 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 wJest 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 sFunkcje 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 sFunkcje 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 sTo 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.