Żyjemy w świecie zdominowanym przez transmisję danych za pośrednictwem różnych mediów. Bezpieczeństwo tej transmisji traktujemy jako oczywistość i wiele o niej nie myślimy – spójrzmy na kilka przypadków:
- Hasła dostępu do naszych kont bankowych czy mediów społecznościowych, które w jakiś sposób muszą zostać bezpiecznie przekazane do serwera uwierzytelniającego, by nikt ich „po drodze” nie wykradł.
- Mimo wielu tysięcy samochodów danego modelu, kluczyk bezprzewodowo otworzy tylko i wyłącznie nasze auto.
- Inteligentne domy w coraz popularniejszym „Internecie rzeczy”, gdzie mikser potrzebuje dostępu do naszej sieci wi-fi. Wszystko się ze sobą komunikuje.
Do naszego hipotetycznego scenariusza życia, w którym korzystamy z tych wszelkich dobrodziejstw technologicznych, wprowadźmy dodatkową postać – atakującego. Załóżmy, że nie dba on o fizyczne blokady, które przed nim postawimy. W końcu zamknięte drzwi można siłowo otworzyć, okno roztłuc, a telefon należący do śpiącego turysty na lotnisku widział bezpieczniejsze miejsca niż zewnętrzna kieszeń plecaka. Naszym zadaniem jest go powstrzymać.
Z perspektywy życiowej fakt, że na zabezpieczenie swoich dóbr materialnych trzeba uważać, jest oczywisty. Z danymi cyfrowymi – na przykład hasłami dostępu – jest jednak nieco trudniej. My, jako deweloperzy, mamy obowiązek zapewnienia poufności danych, które powinny być znane tylko przez dwóch zainteresowanych – nadawcę i odbiorcę. W jaki sposób zabezpieczyć dane na dysku, który został skradziony i ktoś, kto teraz chce się do nich dostać, ma dostęp do całej współczesnej technologii, by je stamtąd wyciągnąć?
Wróćmy do codzienności. W projekcie, w którym pracujemy, dostajemy nowe zadanie: nowy moduł do systemu, nad którym pracujemy, zabezpieczający dane użytkownika. Ma być kompatybilny z innymi na rynku, bezpieczny, gruntownie przetestowany oraz tak szybki, by jego używanie dla końcowego użytkownika było niezauważalne. Zadanie zostało oszacowane w poniedziałek – mamy na to tydzień.
Im bardziej w ten temat się zagłębiamy, tym łatwiej zdać sobie sprawę, że bezpieczeństwo przekazywanych danych nie jest prostą sprawą. Po drugiej stronie barykady są już ludzie inteligentniejsi od nas, których teraz musimy jakoś powstrzymać.
Na szczęście mam dobrą wiadomość – większość tej pracy już jest zrobiona.
Dla kogo jest ten artykuł?
Temat jest dosyć obszerny, a my zajmiemy się tutaj tylko niewielkim kawałkiem kryptografii.
Postaram się omówić tematy od podstaw, aby każdy był w stanie rozumieć pełny obraz tego, co aktualnie poruszamy. Z tego powodu znajdą się tu fragmenty mogące być oczywistymi dla bardziej wtajemniczonych.
Mam nadzieję, że mimo tego zarówno ktoś dopiero zaczynający swoją przygodę z programowaniem, jak i ktoś zaawansowany, znajdzie tu element chociaż pobudzający ciekawość. Nie wszystko trzeba zrozumieć od razu i nie wszystko, co proste trzeba pominąć, „aby nie tracić czasu”.
Nie każda definicja będzie wytłumaczona, więc jeżeli coś nie brzmi znajomo, zachęcam do indywidualnego zgłębienia znaczenia danego słowa czy konceptu.
Dane, na których będziemy pracować, będą reprezentowane w formacie szesnastkowym, więc jeżeli nie brzmi to znajomo, zacznijmy od tego: szesnastkowy model liczbowy.
Przeczytane? No to zaczynamy!
Kocham Standaryzację Trudnych Problemów
W 1977 roku opublikowany został nowy algorytm szyfrujący o generycznej nazwie Data Encryption Standard (DES). Opisywał on problem bezpieczeństwa danych i oferował jego algorytmiczne rozwiązanie. Niestety, wraz ze wzrostem mocy obliczeniowej komputerów jego bezpieczeństwo stopniowo malało, aż nadszedł czas na emeryturę i szukanie następcy.
W 1997 ogłoszono konkurs na algorytm będący następcą DES-a. Z wielu propozycji finalnie wygrał algorytm autorstwa dwóch belgijskich kryptologów – Joana Daemena i Vincenta Rijmena. Połączyli swoje nazwiska w chwytliwą nazwę Rijndael i po przyjęciu przez Narodowy Instytut Standaryzacji i Technologii (NIST) stał się znany światu jako Advanced Encryption Standard – AES.
(* Pewna klaryfikacja – sam Rijndael to nie konkretny algorytm, lecz cała rodzina szyfrów o różnych długościach klucza oraz różnych rozmiarach bloku. NIST wybrał oficjalnie trzech kandydatów AES128, AES192 i AES256, każdy z blokiem o rozmiarze 128 bitów.)
Cała idea jego użycia dla większości deweloperów opiera się na traktowaniu go jako certyfikowany black-box. Nie potrzebujemy znać szczegółów implementacyjnych – wkładamy dane, dajemy hasło (klucz) i uzyskujemy wynik, który magicznie, za pomocą tego samego klucza, możemy przetransformować z powrotem w nasze dane wejściowe.
Szczegóły jego działania są fascynujące. Co takiego robi z tymi danymi, że gwarantuje takie bezpieczeństwo? Zapraszam do zagłębienia się w szczegóły czegoś, co otacza nas na każdym kroku, w niemalże każdym sprzęcie, w tak wielu codziennych scenariuszach 🙂
Nieco „inna” matematyka
Zanim zaczniemy rozpracowywać nasz algorytm, musimy omówić pewien problem, który pojawia się, gdy przekładamy obliczenia, które chcemy wykonać, na kod.
Liczby w komputerach reprezentowane są przez kombinacje bitów – zer i jedynek.
Przez to, że posiadamy ograniczoną ilość bitów do reprezentacji wartości (każda liczba zajmuje określoną ilość miejsca w pamięci), operujemy tylko na podzbiorze liczb całkowitych oraz wyłącznie na wymiernych przybliżeniach liczb zmiennoprzecinkowych. Zwyczajnie nie starcza nam kombinacji bitów, by zaprezentować każdą możliwą wartość!
Przykładową konsekwencją tego faktu jest tzw. problem overflow – błąd przepełnienia. Jeżeli wykonujemy obliczenia na liczbach o rozmiarze jednego bajtu, przyjmują one wartości od 0 do 255. Gdy dodajemy dwie liczby do siebie, możliwe jest, że nasz oczekiwany wynik przekroczy „maksymalną” dopuszczalną granicę wartości. Nie możemy rozwiązać tego zwyczajnie, oferując więcej miejsca w pamięci – to jedynie przesuwa naszą granicę dalej. Niektórych wyników obliczeń po prostu nie jesteśmy w stanie zaprezentować na X bajtach, mimo, że części składowe danych obliczeń indywidualnie się w tym zakresie mieszczą.
Oznacza to, że wychodzimy poza domenę, w której nasze operacje mają sens. Dla szybkiego przypomnienia, domena danej funkcji f(x) określa „czym może być x”. Na zajęciach matematyki w szkole często trzeba było taką domenę wyznaczać – pilnować, byśmy przez przypadek nie podzielili gdzieś przez 0, czy nie brali pierwiastka z liczby ujemnej (i chociaż tu można by zrobić dygresję na temat ominięcia tematu liczb zespolonych w takich przypadkach, zostawmy to w spokoju ;)).
To zalążek naszego problemu. Matematyka opiera się na aksjomatach – pewnych założeniach, które traktujemy jako fundamentalne i zakładamy, że są prawdziwe. Inaczej wszelkie matematyczne dowody musiałby zacząć od udowadniania trywialnych z punktu praktycznego rzeczy.
Zerknijmy na jeden z nich i upewnijmy się, czy ma on dla nas zastosowanie:
I choć wygląda nieco strasznie, ten aksjomat jest podstawą do tego, byśmy mogli wykonać prawidłowo operację dzielenia – w końcu dzielenie to mnożenie przez liczbę odwrotną.
Szybko możemy zauważyć pewien problem – tu także działamy w innej domenie. Mamy dostępne tylko wartości, które mieszczą się nam w jednym bajcie – od 0 do 255.
No cóż, spróbujmy i tak – znajdźmy odwrotność jakiejś przykładowej wartości: 58
Po przejrzeniu wszystkich kombinacji (mnożąc dwie wartości i „odcinając” z wyniku wszystko ponad 1 bajt) okazuje się, że 58 nie posiada liczby odwrotnej w naszej domenie. Ba, co więcej, żadna liczba parzysta nie posiada liczby odwrotnej! I co z naszym dzieleniem?
Gdybyśmy zaczęli się przyglądać innym aksjomatom, zobaczymy, że mamy tu o wiele więcej problemów. Tradycyjna, znana nam ze szkoły matematyka, okazuje się niewystarczająca. I tu, kiedy wszystko wydaje się być stracone, pojawia się nam Ciało Skończone.
Ciało Skończone, GF(2^8)
Aby poradzić sobie z wykonywaniem obliczeń w ograniczonych domenach, AES korzysta z konceptu operacji wewnątrz ciała skończonego znanego także jako ciała Galois, rzędu 2^8.
Co to w praktyce oznacza?
W ciele skończonym mamy – jak sama nazwa wskazuje – skończoną ilość elementów.
Dowolna operacja matematyczna na dwóch elementach ciała skończonego kończy się wynikiem, który także do tego ciała skończonego należy.
Każdy bajt danych można zapisać jako wielomian 7 stopnia.
Gdzie b reprezentuje wartość bitu na danej pozycji.
Wygląda znajomo – przecież tak wygląda konwersja pomiędzy systemem binarnym a decymalnym:
Każdy z takich wielomianów to element naszego ciała. Oznacza to, że posiadamy 256 elementów (jako, że każdy bajt jest reprezentowany przez inny wielomian, ma 8 bitów i każdy bit może być 1 lub 0).
Jednocześnie operacje matematyczne muszą spełniać niektóre z wybranych aksjomatów, by dany zbiór można było takim ciałem skończonym nazwać.
Aby nasze aksjomaty dodawania, odejmowania, mnożenia i dzielenia były poprawne, zmieńmy nieco znaną nam definicję tego, co to znaczy dodawać i mnożyć ze sobą wartości:
- Dodawanie w naszym GF będziemy realizować przez znany nam XOR.
- Mnożenie w naszym GF to mnożenie dwóch bajtów jako wielomianów, modulo odgórnie ustalony wielomian wyższego rzędu. W przypadku AES-a został wybrany
Pełne zrozumienie teorii ciał skończonych zostawiam jako zadanie domowe dla czytelnika 😉
Nie dość, że dzięki temu jesteśmy w stanie dodać, odjąć, pomnożyć i podzielić przez siebie dowolne bajty, mamy gwarancję, że nigdy nie zostanie nam reszta z dzielenia (powodująca pewną stratę informacji, jeżeli byśmy jej prawidłowo nie obsłużyli), ani nigdy nie wyjdziemy poza zakres jednego bajtu – od razu rozwiązując nasz problem overflow! I oto mamy cały matematyczny świat dostępny do bezpiecznego przetwarzania danych!
W ramach ciekawostki – Ciało Galois 2^8 jest perfekcyjne do pracy z bajtami, lecz cały koncept ciał skończonych pierwszy raz został ogłoszony światu przez E. H. Moore’a w roku… 1893. I tak jak transformata Fouriera, która towarzyszy nam nieodłącznie w świecie przetwarzania sygnałów, niektóre rzeczy znajdują swoje zastosowania dopiero po jakimś – niekiedy i wielopokoleniowym – czasie. Stąd ostrzegłbym o rychłym mówieniu „a po co to komu” w kontekście matematycznych odkryć 😉
Nieco o kryptografii
Kryptografia to złożony temat. Sam algorytm leży u jej podstaw, lecz aby zapewnić odpowiedni poziom bezpieczeństwa, dane na których pracujemy i klucze, które mamy dostępne, przechodzą skomplikowaną trasę.
Jak wymienić klucze dające de facto dostęp do naszych danych pomiędzy nadawcą a odbiorcą? Jak chronić sam algorytm, by metodą prób i błędów nie móc wydedukować naszego sekretnego klucza? Tym akurat zajmować się nie będziemy, gdyż, choć pasjonujące (dla zapewne konkretnego typu człowieka), miejsca na półce by nie starczyło, by przechować o tym całą literaturę w domu.
Rozłóżmy często pojawiający się skrót na części pierwsze.
Kto zajmował się kryptografią, mógł zobaczyć przykładowy ciąg znaków:
AES128-GCM AEAD. Co to ze sobą niesie?
- AES – Advanced Encryption Standard, czyli nasz algorytm.
- 128 – długość używanego klucza, w bitach. Wspierane są klucze o długości 128, 192 lub 256 bitów.
- GCM – Galois Counter Mode. Tryb enkrypcji, który określa, jak dany blok podczas szyfrowania wpływa na kolejny.
- AEAD – Authenticated Encryption with Associated Data. Dodatkowa gwarancja integralności danych, które przekazujemy.
W tym tekście zajmiemy się wyłącznie AES-ową częścią enkrypcji, czyli szczegółami algorytmu szyfrującego każdy blok danych. O właśnie, blok. Co to w zasadzie znaczy?
Koncept AES-a
AES jest algorytmem blokowym. Oznacza to, że w danym momencie operujemy tylko na ograniczonej ilości danych i dokonujemy transformacji na nich, by wygenerować nasz finalny szyfr. Będzie on pochodną danych wejściowych oraz tajnego klucza dostępnego tylko dla stron, które będą się ze sobą komunikować.
Jeden blok składa się z 16 bajtów – 128 bitów. Na samym początku, ładujemy nasze dane wejściowe do AES-owego „stanu”. Jest on tablicą o wymiarach 4×4, na której owe transformacje będziemy wykonywać.
Następnie wykonujemy N rund, gdzie N jest odgórnie ustaloną wartością w zależności od długości klucza (10,12,14 rund dla kluczy o długości 128,192,256 bitów), gdzie każda runda to zestaw operacji:
1. Podmiana bajtów (SUB BYTES)
Każdy z bajtów w stanie jest zamieniany na inny na podstawie swojej wartości, korzystając z tak zwanego S-Boxa (o S-boxie powiemy sobie nieco później)
2. Przesunięcie rzędów (SHIFT ROWS)
Każdy z rzędów przesuwamy o M pozycji w lewo, gdzie M to indeks danego rzędu (zaczynając od indeksu 0):
3. Mieszanie kolumn (MIX COLUMNS)
Mieszamy kolumny stanu, by każdy bajt wpływał na wszystkie inne w danej kolumnie. Dokonywane jest to przez proste mnożenie macierzy, gdzie traktujemy naszą kolumnę jako macierz 4×1, przez którą mnożymy stałą macierz:
4. Dodanie klucza rundy (ADD ROUND KEY)
Do stanu dodajemy wartość klucza dla danej rundy. O kluczu rundy powiemy sobie także później.
W dokładnej implementacji, przed pierwszą rundą wykonujemy dodatkową operację ADD ROUND KEY, a w ostatniej rundzie pomijamy MIX COLUMNS.
AES S-Box
AES Substitution Box, znany jako AES S-Box, jest fundamentalną częścią algorytmu. Można go przedstawić w formie tabeli z szesnastkowymi wartościami. Kiedy w dowolnym momencie algorytmu robimy operację podmiany z S-Boxem, oznacza to, że zastępujemy dany bajt innym. Górne 4 bity naszego podmienianego bajtu określają nam rząd, a dolne 4 bity określają kolumnę w owym S-Boxie, która tego bajtu dotyczy.
Dane wewnątrz nie wzięły się oczywiście z niczego. Można skonstruować takiego S-Boxa, wyliczając go przy każdej okazji, gdy jest potrzebny, lecz dla wygody i szybkości, praktycznie zawsze jest dostępny jako tzw. lookup table, obliczony (lub zwyczajnie przekopiowany) zawczasu i trzymany w statycznej pamięci RAM.
Fakt, że S-Box jest publicznie znany i zawsze taki sam okazał się pewną słabością tego algorytmu.
Odnaleziono, iż istnieje Persistent Fault Attack (PFA), gdzie atakujący strzela laserem w pamięć działającego urządzenia elektronicznego i zmienia wartość jednego z bajtów S-Boxa. Taki bajt pozostaje zmieniony aż do resetu urządzenia i mimo braku znajomości, który z tych bajtów ani na jaką wartość został zmieniony, twórcy tego dokumentu wyciągnęli sekretny klucz AES-a w 1641 szyfrach.
Sposób poradzenia sobie z takowym PFA proponowany przez autorów, to trzymanie znanego wyniku szyfrowania pewnych stałych danych wejściowych i weryfikowanie go, dokonując takiego szyfrowania za każdym razem, kiedy dokonujemy operacji na „prawdziwych” danych. Jest to jednak czasochłonne, a jednocześnie potrzebny byłby taki ciąg danych wejściowych, który „dotyka” każdego bajtu z S-Boxa.
Ukazała się ciekawa praca naukowa na temat tej słabości i dodatkowej idei, jak z nią walczyć. Obejmuje ona wykorzystanie faktu, że wewnątrz AES-owego S-Boxa można znaleźć 5 zamkniętych pętli. Na tej podstawie twórcy dokumentu zaproponowali algorytm wykrywania PFA.
Key Expansion
Jako, że AES składa się z wielu rund, a klucz, jaki jest używany, to jedyna niejawna część całego algorytmu, każda runda AES-a używa innego klucza.
„Ale chwileczkę, przecież klucz nie jest tak długi, nie starczy go na wszystkie rundy” powiesz Ty, uważny czytelniku. Fakt!
Do tego wytworzony został algorytm rozszerzenia klucza. Nie musimy zagłębiać się w jego szczegóły, lecz, opisując w skrócie, używa on podobnie jak sam AES kombinacji operacji podmiany bajtów z S-Boxem (SUB BYTES), rotacji bajtów (SHIFT ROWS) oraz operacji XOR z odgórnie określoną wartością nazywaną „stałą rundy”, aby finalnie stworzyć unikatowy 16-bajtowy klucz dla każdej rundy naszego AES-a, całkowicie pochodny od naszego początkowego klucza.
Zainteresowanych odsyłam do oficjalnego NIST-owego dokumentu opisującego szczegóły każdego etapu algorytmu.
Propagacja wpływu danych wejściowych
Każdy z tematów jest swoistą króliczą norą, którą można zgłębiać oraz dokopywać się badań i odkryć (Skąd taka wartość? Dlaczego akurat tak?). Chciałem jednak jeszcze powrócić do wątku wpływu naszego klucza na dane wejściowe.
Cały algorytm jest jawnie opisany. Na bitach, które przekazujemy w kluczu, spoczywa więc obowiązek ukrycia danych wejściowych. Dlatego prześledźmy jeden z bajtów klucza.
Poniżej możemy zaobserwować symulację jednej rundy AES-a nie pod kątem wartości a wpływu danych wzajemnie na siebie. Wybrałem losowy bajt w kluczu i zmieniłem jego tło na niebieskawe. Kiedy ten konkretny bajt klucza będzie miał wpływ na jakąś „komórkę” (bajt) stanu, jej kolor się zmieni.
Jak widać, już zaledwie po dwóch rundach, nasz wybrany bajt wpłynął na każdą komórkę stanu. Nie uwzględniamy w tej symulacji faktu, że klucze kolejnych rund są pochodne od naszego oryginalnego klucza, więc poza tym, co widzimy na animacji, nasz wybrany bajt z oryginalnego klucza wpływa dodatkowo na dane w każdej późniejszej rundzie.
To także dobrze obrazuje dlaczego runda AES-a składa się z tych konkretnych kroków.
- SUB WORDS – zapewnia, że pojedynczy bit ma wpływ na zmianę wartości wszystkich innych bitów w bajcie w którym się zawiera, gdyż zmiana dowolnego z nich spowoduje zastąpienie całego bajtu zupełnie inną wartością z S-Boxa.
- MIX COLUMNS – zapewnia, że zmiana jednego bajtu wpływa na wszystkie pozostałe w tej samej kolumnie stanu, propagując zmianę bajtu „w pionie”.
- SHIFT ROWS – zapewnia, że każda kolumna będzie posiadała po jednym bajcie z każdej pozostałej, propagując zmianę bajtu „w poziomie”.
Na zakończenie
Wyjaśnienie szczegółów algorytmicznych oparłem na ich fundamentalnej idei zgodnie z oficjalną dokumentacją. Ważne jest jednak, aby pamiętać, że te funkcje i algorytmy mają dużo miejsca do optymalizacji.
W praktycznych zastosowaniach faktyczna implementacja może się znacząco różnić lub nawet być dopasowana do danego scenariusza użycia. Przykładowo, jeżeli wiadomym jest, że chcemy korzystać wyłącznie z AES-128, algorytm rozszerzenia klucza można znacząco uprościć. Mnożenie w GF(2^8) można zaimplementować na wiele różnych sposobów. I tak dalej…
Wszystkie etapy opisane tutaj dotyczyły procesu szyfrowania. Deszyfrowanie dokonywane jest analogicznie „od tyłu”, gdzie trzeba korzystać z innego S-Boxa, który jest oczywiście znacząco spokrewniony z tym już nam znanym. Jako dobre ćwiczenie polecam zerknąć sobie na tzw. InvSBox (Inverse S-Box) i zastanowić się, dlaczego w danym miejscu znajduje się akurat taka wartość 😉
Animacje widoczne w tym artykule zostały wygenerowane za pomocą biblioteki manim. Dane do wizualizacji pobrane zostały bezpośrednio z zaprogramowanego AES-a zgodnie z NIST-ową dokumentacją.
Zostaw komentarz