Kryptografia II stopień

W4. Szyfry blokowe i AEAD

Szyfr blokowy dla ustalonego klucza jest permutacją bloków. AES ma blok 128-bitowy. Klucze 128-, 192- i 256-bitowe nie zmieniają długości bloku. Dłuższa wiadomość wymaga trybu pracy.

Skrót AEAD oznacza uwierzytelnione szyfrowanie z danymi dodatkowymi. Oprócz ukrycia treści pozwala wykryć nieuprawnioną zmianę. Do szyfrogramu dołączamy znacznik sprawdzany za pomocą klucza. AAD to dane dodatkowe, które są jawne, ale również objęte tym sprawdzeniem. Ogólny znacznik uwierzytelnienia MAC i jego osobny dowód omówimy w W5.

AAD

Additional Authenticated Data. Dodatkowe dane uwierzytelniane, ale nieszyfrowane.

Interfejs szyfru blokowego i interfejs AEAD

Szyfr blokowy jest rodziną permutacji. Dla AES wywołanie $y=\mathsf{AES}_k(x)$ przyjmuje klucz $k$ oraz dokładnie 128-bitowy blok $x$. Zwraca 128-bitowy blok $y$. Odwrotna procedura $x=\mathsf{AES}^{-1}_k(y)$ odtwarza wejście przy tym samym kluczu. Rundy, podstawienia i macierze są wnętrzem tych procedur. Sam AES nie określa jeszcze ochrony długiej wiadomości ani jej integralności.

Schemat AEAD dodaje sposób użycia szyfru i reguły uwierzytelnienia. Po ustaleniu parametrów $pp$ i wylosowaniu $k\leftarrow\mathsf{KeyGen}(pp)$ jego wywołania mają postać

Tutaj $n$ oznacza jawny nonce, $m$ wiadomość, a $d$ jawne dane dodatkowe. $C$ zawiera zaszyfrowaną treść i znacznik. Wynik $m'$ jest wiadomością albo $\bot$. Właściwy profil określa długości i ograniczenia. Dla AES-GCM w tym kursie wymagamy niepowtarzania nonce przy jednym kluczu. Obie strony otrzymują to samo $n,d$, które mogą być jawnie przesłane razem z $C$. Poprawność to $\mathsf{Dec}(pp,k,n,\mathsf{Enc}(pp,k,n,m,d),d)=m$. Poufność i wykrywanie nieuprawnionych zmian są osobnymi gwarancjami przy spełnionych warunkach użycia.

AES-GCM

Advanced Encryption Standard in Galois/Counter Mode. Szyfr AES w trybie Galois/licznikowym. AESGCM jest nazwą klasy w bibliotece, a 256 oznacza długość klucza.

Odwracalność nie znaczy łatwego ataku

Dla każdego klucza algorytm musi być odwracalny, inaczej nie odzyskalibyśmy wiadomości. Przeciwnik również zna opis operacji odwrotnych. Brakuje mu klucza wybierającego właściwą permutację. Bezpieczeństwo nie polega na utracie danych w czasie szyfrowania, lecz na trudności wykorzystania publicznego opisu bez odpowiedniego sekretu.

Sieć podstawieniowo-permutacyjna przeplata nieliniową zamianę małych fragmentów, mieszanie pozycji i dodawanie materiału kluczowego. Gdyby wszystkie operacje były liniowe nad bitami, ich złożenie nadal byłoby liniowe. Odpowiednio dobrane wejścia pozwoliłyby odtworzyć taką zależność. Gdyby była tylko niezależna zamiana każdego bajtu, analiza rozdzielałaby się na małe zadania. Potrzebujemy zarówno nieliniowości, jak i rozpraszania zależności.

Dlaczego dodatkowy bit klucza ma znaczenie

Bit ma dwie możliwości, a bajt ma osiem bitów. Jeżeli każdy bit klucza jest niezależny i jednostajny, klucz długości $k$ bitów wybieramy spośród $N=2^k$ równie prawdopodobnych ciągów. Dla czterech bitów jest ich 16, od 0000 do 1111. Algorytm szyfrowania jest publiczny. Sekretem jest to, który z tych kluczy został wybrany.

Do każdego starego ciągu możemy dołączyć 0 albo 1. Dostajemy dwie rozłączne kopie poprzedniej przestrzeni. Dla $d$ dodatkowych niezależnych bitów:

• Jeden bit: dwa razy więcej kluczy.
• Jeden bajt, czyli osiem bitów: $2^8=256$ razy więcej kluczy, nie osiem razy.
• Dwa bajty: $2^{16}=65\,536$ razy więcej kluczy.
• 64 bity: $2^{64}\approx1{,}84\cdot10^{19}$ razy więcej kluczy.

To wzrost wykładniczy. Każdy kolejny niezależny bit mnoży poprzedni wynik przez dwa. Nie chodzi o to, że jedna operacja szyfrowania staje się dwa razy trudniejsza.

Co dokładnie liczymy przeciwnikowi

W przeszukiwaniu wyczerpującym przeciwnik sprawdza różne klucze, aż rozpozna właściwy. Zakładamy jeden atakowany klucz i dostatecznie dużo danych do jego sprawdzenia, np. kilka znanych par tekst–szyfrogram. Jedna para bloków nie zawsze jednoznacznie określa klucz, zwłaszcza gdy klucz jest dłuższy od bloku. Pełny test kandydata może więc wymagać kilku szyfrowań.

Nie zakładamy żadnej metody omijającej przeszukiwanie. Niech $T$ oznacza liczbę prób do znalezienia klucza, włącznie z udanym testem. Przy jednostajnym kluczu jego pozycja w ustalonej kolejności testów jest jednostajna. Najgorszy przypadek wymaga $N$ prób. Symbol $\mathbb E[T]$ oznacza wartość oczekiwaną, czyli średnią liczbę prób w wielu niezależnych doświadczeniach. Każda pozycja od 1 do $N$ ma tutaj to samo prawdopodobieństwo, więc:

Niech $Q$ oznacza budżet różnych sprawdzonych kluczy. W tym modelu szansa znalezienia właściwego klucza to:

Przy tym samym $Q\le2^k$ dodatkowy bit zmniejsza tę szansę dwukrotnie, a dodatkowy bajt 256-krotnie. Gdy napastnik dysponuje dwukrotnie większą łączną szybkością sprawdzania, jeden dodatkowy losowy bit kompensuje ten wzrost w modelu przeszukiwania. Nie kompensuje automatycznie nowego ataku algebraicznego albo wycieku klucza.

Długość klucza, siła ochrony i koszt szyfrowania

AES ma trzy zdefiniowane warianty: AES-128, AES-192 i AES-256. Przykład przejścia ze 128 do 129 bitów objaśnia wyłącznie liczenie przestrzeni. Standard nie definiuje AES-129 ani AES-136. We wszystkich trzech wariantach AES blok nadal ma 128 bitów. FIPS 197, parametry AES.

FIPS

Federal Information Processing Standards. Amerykańskie federalne standardy przetwarzania informacji.

Podwojenie długości ze 128 do 256 bitów nie oznacza tylko dwukrotnie większego przeszukiwania. Mnożymy liczbę kandydatów przez $2^{128}$. Koszt uczciwego szyfrowania jednego bloku wzrasta znacznie łagodniej, m.in. przez większą liczbę rund. Rzeczywisty czas zależy też od sprzętu, implementacji i harmonogramu klucza. Nie utożsamiamy stosunku liczby rund ze zmierzonym stosunkiem czasów.

Długość nie jest samodzielnym dowodem bezpieczeństwa. Rachunek $2^k$ liczy kandydatów. Nie dowodzi, że każda metoda ataku musi ich sprawdzać po kolei. Siłę ochrony oceniamy względem najlepszych znanych ataków w określonym modelu. Znaczenie ma także tryb pracy, ilość danych zaszyfrowanych jednym kluczem, długość znacznika, unikalność nonce i odporność implementacji na wycieki. Większy klucz nie naprawia powtórzonego nonce w CTR lub GCM. NIST SP 800-57, §5.6: siła ochrony i rozmiary kluczy.

CTR

Counter mode. Tryb licznikowy.

GCM

Galois/Counter Mode. Tryb Galois/licznikowy, łączący szyfrowanie ze sprawdzaniem integralności.

Nowe bity muszą rzeczywiście zwiększać niepewność przeciwnika. Dopisanie ośmiu znanych zer nie daje 256-krotnie większej przestrzeni do przeszukania. Tak samo zapisanie słabego hasła w polu 256-bitowym nie tworzy losowego klucza 256-bitowego. Liczy się sposób generowania i wiedza napastnika, a nie sam rozmiar bufora.

Nie przenosimy tego przelicznika na RSA. AES jest szyfrem symetrycznym. RSA jest konstrukcją asymetryczną, a długość jego klucza zwykle oznacza długość publicznego modułu. Atak może wykorzystywać strukturę algebraiczną, w szczególności faktoryzację modułu. Dodatkowy bit modułu RSA nie oznacza podwojenia kosztu najlepszego ataku. Rozmiary kluczy różnych rodzin porównujemy przez oszacowaną siłę ochrony, nie bit do bitu. RSA omówimy w W10b.

Rachunek powyżej dotyczy klasycznego przeszukiwania. Kwantowy algorytm Grovera zmienia asymptotyczną liczbę zapytań do testu klucza. To nie jest wykonanie całego przeszukiwania w jednej operacji. Ten odrębny model wraca w części postkwantowej.

Pytanie kontrolne: sprzęt sprawdza klucze 256 razy szybciej. O ile niezależnych losowych bitów trzeba wydłużyć klucz, żeby zachować tę samą szansę sukcesu przy tym samym czasie przeszukiwania i niezmienionym koszcie pojedynczego testu?

AES od wejścia do wyjścia: blok, klucz i publiczna instrukcja

Zacznijmy od całości. W AES-128 podajemy jeden blok wiadomości o długości 16 bajtów oraz klucz o długości 16 bajtów. Otrzymujemy blok szyfrogramu o długości 16 bajtów. Liczba 128 w nazwie oznacza długość klucza w bitach. Sam AES jest deterministyczny. Ten sam blok i ten sam klucz zawsze dają ten sam wynik. Obsługą długiej wiadomości, licznika lub wektora inicjującego zajmuje się tryb pracy, a nie pojedyncza runda AES.

Wewnątrz algorytmu biegną dwie połączone ścieżki:

1. Ścieżka danych. Bajty wiadomości wpisujemy do tablicy nazywanej stanem. Kolejna operacja pobiera stan pozostawiony przez poprzednią operację i go przekształca. Nie zaczynamy każdej rundy od pierwotnej wiadomości.
2. Ścieżka klucza. Z klucza głównego $K$ procedura rozwijania klucza wylicza $K_0,K_1,\ldots,K_{10}$. Każdy ma 16 bajtów. $K_0=K$ służy do początkowego AddRoundKey. $K_j$ służy do AddRoundKey w rundzie $j$. Rozwinięcie zależy od klucza, ale nie od wiadomości.

Obie ścieżki łączy AddRoundKey. Pozostałe składniki to publiczna instrukcja AES, taka sama dla wszystkich użytkowników: tablica podstawień S-box, przesunięcia wierszy, macierz MixColumns, reguły rachunku na bajtach i stałe rozwijania klucza. Nie są dodatkowymi sekretami. Nie losujemy ich przy szyfrowaniu i nie pobieramy z wiadomości. Zmieniają się dane, do których stosujemy te reguły.

Porządek AES-128: najpierw AddRoundKey z $K_0$. Następnie dziewięć rund SubBytes → ShiftRows → MixColumns → AddRoundKey. W rundzie dziesiątej wykonujemy SubBytes → ShiftRows → AddRoundKey z $K_{10}$. Pominięcie MixColumns w ostatniej rundzie jest częścią definicji szyfru. Poniżej rozłożymy tę instrukcję na części, a w demonstratorze zachowamy obok szczegółów mapę całego przepływu.

Stan AES to szesnaście bajtów

Jeden bajt ma osiem bitów. W zapisie szesnastkowym zajmuje dwa znaki, np. $53_{\mathrm{hex}}$. Blok 16 bajtów zapisujemy jako macierz czterech wierszy i czterech kolumn. AES wypełnia ją kolumnami:

To ważna konwencja implementacyjna. Przepisanie ciągu wierszami zmienia działanie operacji, nawet jeśli rysunek wygląda podobnie. Zapis hex jest tylko reprezentacją bajtów. Dodawanie bajtów w algorytmie nie jest zwykłym dodawaniem widocznych liczb.

Na przykład początek bloku demonstratora, 6b c1 be e2, tworzy pierwszą kolumnę, od góry do dołu. Kolejne 2e 40 9f 96 tworzą drugą kolumnę. Pierwszą kolumną klucza jest 2b 7e 15 16. Początkowy AddRoundKey daje więc w pierwszej kolumnie 40 bf ab f4, ponieważ m.in. $6b_{\mathrm{hex}}\oplus2b_{\mathrm{hex}}=40_{\mathrm{hex}}$. To właśnie wynik tego XOR-u, a nie pierwotny blok, wchodzi do SubBytes pierwszej rundy.

W AES używamy ciała $\mathrm{GF}(2^8)$. Bajt reprezentuje wielomian stopnia najwyżej 7 o współczynnikach 0 lub 1. Dodawanie to XOR. Mnożenie wielomianów redukujemy modulo $z^8+z^4+z^3+z+1$. Przykładowo pomnożenie $80_{\mathrm{hex}}$ przez $02_{\mathrm{hex}}$ daje $1b_{\mathrm{hex}}$, nie liczbę całkowitą 256. Nie trzeba od razu pamiętać tablic. Trzeba wiedzieć, w jakim zbiorze wykonuje się rachunek.

Cztery kroki rundy

Jak czytać ten rachunek. Ciało jest zbiorem, w którym można dodawać, odejmować, mnożyć i dzielić przez element różny od zera. W ciele bajtowym te działania nie są zwykłym rachunkiem modulo 256. Macierz jest prostokątną tablicą. Iloczyn macierzy przez kolumnę obliczamy, mnożąc elementy każdego wiersza przez odpowiednie elementy kolumny i sumując wyniki w tym samym ciele. Przykładowo pierwszy wiersz MixColumns daje $02\cdot x_0\oplus03\cdot x_1\oplus x_2\oplus x_3$. Odwracalna macierz pozwala jednoznacznie odzyskać kolumnę wejściową.

1. SubBytes. Każdy bajt przechodzi przez tę samą nieliniową, odwracalną tablicę S-box. Konstrukcja używa odwrócenia w ciele, z osobną konwencją dla zera, i transformacji afinicznej bitów. Jeden bajt na wejściu nadal daje jeden bajt na wyjściu. To nie jest haszowanie.
2. ShiftRows. Wiersze przesuwamy cyklicznie o 0, 1, 2 i 3 pozycje w lewo. Wartości bajtów się nie zmieniają, ale trafiają do innych kolumn.
3. MixColumns. Każdą kolumnę mnożymy przez ustaloną odwracalną macierz nad $\mathrm{GF}(2^8)$. Jeden bajt wpływa na kilka wyjść. Jest to operacja liniowa, nie sekretna tablica.
4. AddRoundKey. Stan łączymy przez XOR z 16 bajtami klucza rundy. Ten krok zależy od sekretu. XOR z tym samym kluczem jest własną odwrotnością.

Macierz MixColumns, zapisana bajtami hex, ma postać:

Każdy iloczyn i suma w tej macierzy należą do ciała bajtowego. Np. $03\cdot x=(02\cdot x)\oplus x$. Można to prześledzić na pojedynczej kolumnie, a następnie sprawdzić całą rundę.

Skąd bierze się S-box

S-box to stała tablica 256 wyników, nie część klucza. Jest skrótem obliczenia, które można wykonać dla każdego bajtu z osobna. Dla bajtu $b\ne00_{\mathrm{hex}}$ znajdujemy odwrotność $a=b^{-1}$ w ciele bajtowym, czyli $b\cdot a=01_{\mathrm{hex}}$. Dla wejścia $b=00_{\mathrm{hex}}$ przyjmujemy $a=00_{\mathrm{hex}}$. Jest to osobna reguła, a nie dzielenie przez zero.

Następnie mieszamy bity $a$ przez ustaloną transformację afiniczną. Niech $\operatorname{rotl}_t(a)$ oznacza cykliczny obrót ośmiu bitów jednego bajtu o $t$ pozycji w lewo. Bit wypadający z lewej wraca na prawy koniec. Definicję tablicy można wtedy zapisać tak:

Stała $63_{\mathrm{hex}}$, obroty i wielomian definiujący ciało są ustalone w AES. Przykładowo odwrotnością $53_{\mathrm{hex}}$ jest $ca_{\mathrm{hex}}$. Po mieszaniu bitów otrzymujemy $\operatorname{SBOX}(53_{\mathrm{hex}})=ed_{\mathrm{hex}}$. Dla zera wynik wynosi $63_{\mathrm{hex}}$. W demonstratorze tablica powstaje z tego rachunku, a SubBytes odczytuje z niej wynik dla każdego z 16 bieżących bajtów stanu. Ten odczyt nie zmienia pozycji bajtu.

Odwrócenie w ciele wprowadza nieliniowość. Sam XOR i przestawianie bitów byłyby przekształceniami afinicznymi, które można składać i analizować jako układ równań liniowych. S-box jest odwracalny, żeby odbiorca mógł cofnąć podstawienie. Nie jest funkcją skrótu.

Skąd biorą się przesunięcia i współczynniki MixColumns

ShiftRows nie wylicza przesunięcia z klucza. Numery wierszy liczymy od 0. Numer wiersza określa liczbę pozycji obrotu w lewo: 0, 1, 2 lub 3. Są to ustalone przesunięcia bajtów między kolumnami. Nie należy ich mylić z obrotami bitów wewnątrz bajtu w definicji S-box ani z obrotem słowa klucza opisanym niżej.

Macierz MixColumns jest wybranym przez projektantów, publicznym składnikiem AES. Jej współczynniki 01, 02, 03 nie są fragmentami klucza ani wynikiem wcześniejszej rundy. Ta sama macierz działa na każdą z czterech kolumn i w każdej rundzie, w której występuje MixColumns. Zmienia się natomiast kolumna wejściowa, bo pochodzi ze stanu po bieżącym ShiftRows. Kolumnę mnożymy przez macierz. Nie dzielimy jej przez macierz.

Skąd bierze się użyteczność tego wyboru? Mieszanie jest odwracalne, a każdy bajt wyniku zależy od wszystkich czterech bajtów kolumny. W połączeniu z przesunięciami wierszy kolejna runda przenosi te zależności między kolumnami. Małe współczynniki pozwalają przy tym sprawnie wykonać rachunek. Nie oznacza to, że dowolna odwracalna macierz zapewniłaby bezpieczeństwo AES.

Mnożenie przez 01 zostawia bajt bez zmian. Przez 02 mnożymy następująco: przesuwamy bity o jedną pozycję w lewo i pozostawiamy osiem bitów. Jeśli przed przesunięciem najwyższy bit był równy 1, wykonujemy jeszcze XOR z 1b. Ta poprawka wynika z redukcji przez $z^8+z^4+z^3+z+1$. Wartość $1b_{\mathrm{hex}}$ zapisuje jego cztery niższe składniki. Przez 03 mnożymy, dodając XOR-em pierwotny bajt do wyniku mnożenia przez 02.

Prześledźmy pierwszą kolumnę pierwszej rundy dla domyślnych danych. Po ShiftRows wynosi ona 09 28 7f 47. Pierwszy wiersz stałej macierzy daje:

Wszystkie wartości w tym rachunku są bajtami hex. Pozostałe trzy wiersze macierzy dają 9f, 16, c2. Cała kolumna wyjściowa to zatem 52 9f 16 c2. Jest to nowa wartość stanu, którą dopiero potem połączymy XOR-em z odpowiednią kolumną klucza $K_1$.

Klucz rundy nie jest nowym niezależnym kluczem

Harmonogram klucza (key schedule) deterministycznie rozwija klucz główny. W AES-128 dzielimy jego 16 bajtów na cztery kolejne słowa czterobajtowe $w_0,w_1,w_2,w_3$. Są to cztery kolumny $K_0$. Wyliczamy jeszcze 40 słów, aż do $w_{43}$. Każde cztery kolejne słowa tworzą klucz jednej rundy:

Symbol $\Vert$ oznacza tu zapisanie ciągów bajtów jeden za drugim. Do obliczenia nowego słowa potrzebujemy poprzedniego słowa i słowa sprzed czterech pozycji. Przy rozpoczynaniu nowego klucza rundy najpierw przekształcamy poprzednie słowo:

1. RotWord obraca cztery bajty o jedną pozycję w lewo. Nie obraca bitów w bajcie.
2. SubWord zastępuje każdy z tych czterech bajtów przez wartość z tej samej publicznej tablicy S-box, której używa SubBytes.
3. Dodajemy XOR-em Rcon, czyli round constant, stałą rundy. To słowo postaci $(r_j,00,00,00)$. Pierwszy bajt zaczyna się od 01, a następne otrzymujemy przez mnożenie przez 02 w ciele bajtowym. Dla rund 1–10 są to 01 02 04 08 10 20 40 80 1b 36. Są publiczne i nie zależą od klucza. Wprowadzają zależność od numeru rundy.

Precyzyjnie, dla $4\le i\le43$:

Przykład z klucza demonstratora. Pierwsze słowo to 2b 7e 15 16, a czwarte to 09 cf 4f 3c. Aby wyliczyć $w_4$, obracamy czwarte słowo do cf 4f 3c 09. SubWord daje 8a 84 eb 01. XOR ze stałą 01 00 00 00 daje 8b 84 eb 01. Na końcu łączymy to z pierwszym słowem klucza:

Następnie $w_5=w_1\oplus w_4$, $w_6=w_2\oplus w_5$ i $w_7=w_3\oplus w_6$. Otrzymujemy $K_1$ w postaci a0fafe17 88542cb1 23a33939 2a6c7605. Stąd pochodzi klucz rundy widoczny przy pierwszym MixColumns i AddRoundKey. Na przykład bajt 52 z wyliczonej wyżej kolumny zostaje połączony z a0, co daje f2. Obie liczby mają więc wskazane źródło: jedna ze ścieżki danych, druga ze ścieżki klucza.

Rozwinięcie można obliczyć przed szyfrowaniem bloków pod tym kluczem. 176 bajtów rozwinięcia nie oznacza 176 niezależnych losowych bajtów. Wszystkie klucze rund są powiązane i wynikają ze 128-bitowego klucza głównego. Nie wolno w dowodzie uznać ich bez uzasadnienia za niezależne losowania.

Przed rundami wykonujemy AddRoundKey. AES-128 ma następnie 10 rund, AES-192 ma 12, a AES-256 ma 14. Ostatnia runda pomija MixColumns. Nie jest to opcjonalna optymalizacja demonstratora. Tak jest zdefiniowany szyfr. Warianty różnią się również harmonogramem klucza, więc AES-256 nie powstaje przez samo wydłużenie pętli AES-128.

Rzeczywisty przebieg AES-128

Mapa pokazuje jednocześnie ścieżkę danych i pochodzenie kluczy rund. Rysunek szczegółowy zachowuje stan przed operacją i stan po operacji. Obok rachunku podane są źródło bieżącego stanu, publiczna reguła albo bajt wyliczonego klucza oraz miejsce zapisu wyniku. W ShiftRows bajty wędrują cyklicznie w lewo. W MixColumns najpierw powstają cztery iloczyny w ciele, następnie ich suma XOR. S-box zmienia wartość bajtu, a AddRoundKey łączy go z bajtem klucza na tej samej pozycji.

Niżej znajduje się osobne porównanie dwóch wejść. Lewa macierz dotyczy wpisanego bloku, prawa bloku z opcjonalną zmianą jednego bitu. Oba przebiegi używają tego samego klucza. Obramowane komórki różnią się między przebiegami. To samo wskazują liczniki bajtów i bitów, więc odczyt nie wymaga rozróżniania kolorów.

Co właściwie pokazuje rozpraszanie różnicy

Po zmianie jednego bajtu SubBytes nadal zmienia tylko tę pozycję. ShiftRows przestawia pozycję. MixColumns rozprzestrzenia różnicę w kolumnie. W kolejnej rundzie przesunięcia kierują te bajty do różnych kolumn, a kolejne mieszanie rozszerza zależność na stan. S-box wprowadza nieliniowe zależności między bitami.

Liczba zmienionych bitów nie musi rosnąć w każdym kroku. XOR z tym samym kluczem rundy zachowuje różnicę XOR dwóch stanów. Przestawienie bajtów zachowuje liczbę różnych bitów. Nieliniowa zamiana i mieszanie mogą ją zwiększyć lub zmniejszyć. Wartość około połowy bitów w wielu próbach jest obrazem efektu lawinowego, a nie certyfikatem bezpieczeństwa.

Atak różnicowy bada, jak różnica wejść wpływa na rozkład różnic wyjść. Atak liniowy szuka użytecznych odchyleń od przypadkowych relacji między bitami. Projekt rund utrudnia utrzymanie prostych, wysoko prawdopodobnych zależności przez cały szyfr. Nie można jednak powiedzieć, że każda runda zmniejsza szansę każdego ataku o stały czynnik. Możliwe są różne ścieżki, ich sumowanie i zależności między rundami. Analiza pełnego szyfru jest osobnym zadaniem kryptoanalitycznym.

Gdy znamy klucz, odwracamy te same kroki i odzyskujemy wszystkie bity. Gdy go nie znamy, trudność wynika z całej konstrukcji i jej parametrów, nie z fizycznego znikania informacji. Dowody bezpiecznych trybów pracy zwykle przyjmują, że szyfr zachowuje się jak trudna do odróżnienia permutacja. Nie są dowodami tej własności dla samego AES.

Źródła i wektory sprawdzające: FIPS 197, stany pośrednie AES-128, NIST, COSIC: konstrukcja AES i wide-trail. Demonstrator pokazuje algorytm dydaktycznie. Nie jest implementacją stałoczasową do ochrony rzeczywistych sekretów.

COSIC

Computer Security and Industrial Cryptography. Bezpieczeństwo komputerowe i kryptografia przemysłowa. Nazwa grupy badawczej KU Leuven.

• ECB: jednakowe bloki dają jednakowe szyfrogramy. Ukrycie pojedynczego bloku nie ukrywa struktury pliku.

  ECB

  Electronic Codebook. Tryb niezależnego szyfrowania bloków, tradycyjnie nazywany elektroniczną książką kodową.

• CBC: blok tekstu jest łączony XOR-em z poprzednim szyfrogramem. Warunki na IV, dopełnienie i błędy należą do schematu.

  CBC

  Cipher Block Chaining. Tryb wiązania bloków szyfrogramu.

  IV

  Initialization Vector. Wektor inicjalizujący. Wymagania wobec niego zależą od trybu szyfrowania.

• CTR: szyfrujemy kolejne wartości licznika i otrzymujemy maski. Powtórzenie licznika pod tym samym kluczem powtarza maskę.
• AEAD: szyfrogram ma znacznik uwierzytelniający. Dane dodatkowe są jawne, ale chronione przed zmianą.

AES-GCM otrzymuje klucz, nonce, wiadomość i AAD. Nonce musi być unikalny dla klucza. W laboratorium używamy 96-bitowego nonce i znacznika 128-bitowego. Deszyfrowanie daje tekst albo błąd $\bot$. Aplikacja nie może użyć tekstu przed sprawdzeniem znacznika. RFC 5116 określa interfejs AEAD.

RFC

Request for Comments. Dokument z serii opisującej m.in. protokoły internetowe. Nie każdy RFC jest standardem.

Od rundy do długiej wiadomości

Pojedyncza permutacja 16 bajtów nie określa jeszcze szyfrowania pliku. Tryb pracy ustala, jak łączymy bloki, skąd bierze się losowość i co trzeba przesłać odbiorcy poza właściwym szyfrogramem. Błąd w tych regułach może zniweczyć bezpieczeństwo nawet przy poprawnej implementacji AES.

Dla CBC oznaczmy poprzedni szyfrogram przez $c_{i-1}$, a początkowo $c_0=\mathrm{IV}$:

Dopełnienie uzupełnia ostatni niepełny blok. Klasyczny argument poufności CBC wymaga odpowiednio nieprzewidywalnego IV. Jawność IV nie oznacza, że można pozwolić przeciwnikowi na dowolną zmianę bez konsekwencji. Różnice komunikatów błędów po deszyfrowaniu mogą tworzyć wyrocznię dopełnienia. Współczesne zastosowanie powinno wybierać właściwy profil uwierzytelnionego szyfrowania, a nie ręcznie sklejać tryb i obsługę błędów.

CTR używa wejść $T_i$ do szyfru blokowego:

Wszystkie $T_i$ pod tym samym kluczem muszą być różne, również pomiędzy wiadomościami. Część wejścia może identyfikować wiadomość, a reszta numerować bloki. Licznik nie może się przepełnić. Ostatni blok wykorzystuje potrzebny prefiks maski, bez dopełniania tekstu.

W GCM szyfrowaniu licznikowemu towarzyszy uwierzytelnienie oparte na wielomianowym rachunku w ciele binarnym. Sekretny klucz tego rachunku nie jest funkcją haszującą do krzywej. Powtórzenie nonce może zagrozić zarówno poufności, jak i integralności. Dlatego test „odszyfrowało się poprawnie” nie wystarcza do oceny zarządzania nonce.

Do bibliotecznego użycia AES-GCM w L1.1–5 wystarczy ten interfejs. Własny GHASH w L1.6 jest późniejszym pogłębieniem: po rachunku ciał binarnych z W6 przejdź do budowy bloków i znacznika GCM. Tam rozdzielamy dopełnienie, kolejność bitów, klucz mnożenia i końcową maskę AES.

Dlaczego permutacja może zastępować funkcję

PRP oznacza pseudolosową permutację: rodzinę odwracalnych funkcji, której nie umiemy wydajnie odróżnić od losowej permutacji przy określonym dostępie. PRF z W2 nie musi być odwracalna. To rozróżnienie pozwala połączyć model szyfru blokowego z wcześniejszym dowodem używającym funkcji pseudolosowej.

PRP

pseudorandom permutation. Permutacja pseudolosowa.

Losowa permutacja nie powtarza wyjścia dla różnych wejść, a losowa funkcja może. Dla $t$ różnych zapytań na $n$-bitowych blokach różnicę ogranicza prawdopodobieństwo kolizji, najwyżej $t(t-1)/2^{n+1}$. To lemat przełączania PRP/PRF dla odpowiedniego dostępu do wyroczni. Zapytania odwrotne wymagają właściwego rozszerzenia modelu.

Granica urodzinowa nie jest zalecanym limitem użycia konkretnego AEAD. Limity uwzględniają też długości danych, znaczniki i próby weryfikacji.

Ten sam rekord, pięć prób odbioru

W poniższym doświadczeniu nie porównujemy tylko wzorów. Przeglądarka wykonuje szyfrowanie i deszyfrowanie AES-GCM. Wariant bez zmian powinien zwrócić wiadomość. Zmiana wybranego bitu szyfrogramu, znacznika lub nonce albo zmiana AAD prowadzi do kontroli integralności na rzeczywiście otrzymanych bajtach. Błąd oznacza, że aplikacja nie otrzymała tekstu.

JSON

JavaScript Object Notation. Tekstowy format zapisu danych strukturalnych.

W prawdziwej aplikacji klucz może obsługiwać wiele rekordów, ale nonce nie może się powtórzyć pod tym kluczem. Demonstrator tworzy nowy klucz dla każdego przebiegu. Wymagania konstrukcji podaje NIST SP 800-38D, a zachowanie operacji przeglądarkowych opisuje Web Cryptography API.

Powiązania: C2, L1, FIPS 197.

W5. Hasze, MAC i integralność

Interfejsy narzędzi przed protokołami

Hash, PRF i MAC nie są zamiennymi nazwami tej samej funkcji. Uporządkujmy ich wywołania. Poniżej $x$ jest ciągiem wejściowym, $k$ tajnym kluczem, $m$ wiadomością, a $\tau$ znacznikiem. Parametry profilu ustalamy wcześniej.

KDF

Key Derivation Function. Funkcja wyprowadzania kluczy.

W opisie KDF $\mathrm{ctx}$ oznacza kontekst zastosowania, a $\mathrm{label}$ jego etykietę. Dokładne dziedziny i długości ustala konkretny profil. Dla MAC mamy rodzinę algorytmów $(\mathsf{KeyGen},\mathsf{Tag},\mathsf{Check})$ oraz warunek $\mathsf{Check}(k,m,\mathsf{Tag}(k,m))=1$ dla poprawnie utworzonego klucza. Czasem Tag nazywa się po prostu MAC, co zastosujemy w opisie SIGMA. MAC nie jest podpisem publicznym: weryfikator znający $k$ potrafi również tworzyć znaczniki.

SIGMA

SIGn-and-MAc. Podejście łączące podpis cyfrowy i kod uwierzytelnienia wiadomości.

Funkcja skrótu $\mathcal D:\{0,1\}^*\to\{0,1\}^n$ jest publiczna. Odporność na kolizje utrudnia znalezienie różnych wiadomości o jednym skrócie. Odporność na przeciwobraz dotyczy odtworzenia wejścia dla zadanego wyniku. Drugiego przeciwobrazu szukamy dla już zadanej wiadomości.

Sam skrót nie uwierzytelnia. Przeciwnik może zmienić plik i ponownie policzyć skrót. MAC używa sekretu. W eksperymencie niepodrabialności przeciwnik pyta o znaczniki, a potem przedstawia poprawny znacznik nowej wiadomości.

Dowód MAC z PRF

Niech $\tau=F_k(m)$ ma $n$ bitów. Rozważamy jedno końcowe fałszerstwo. Zastępujemy $F_k$ przez $R$. Dla nowego $m^*$ wartość $R(m^*)$ pozostaje jednostajna niezależnie od wcześniejszych znaczników. Trafienie ma prawdopodobieństwo $2^{-n}$. Redukcja PRF odpowiada na zapytania i sprawdza fałszerstwo własną wyrocznią:

Wiele prób wymaga osobnego rozliczenia. HMAC ma konkretną konstrukcję i analizę. Nie wynika z niej, że dowolne $\mathcal D(k\|m)$ jest poprawnym MAC. Kodowanie i rozszerzalność części funkcji skrótu mają znaczenie.

HMAC

Hash-based Message Authentication Code. Kod uwierzytelnienia wiadomości oparty na funkcji haszującej. Przyrostek SHA-256 wskazuje użyty hasz.

Przedłużanie skrótu nie wymaga kolizji

Wyjaśnijmy, co może pójść źle w takim prefiksowym znaczniku. SHA-256 przetwarza 512-bitowe bloki. Do wejścia długości $\ell$ bitów dopisuje bit 1, tyle zer, aby długość przed polem długości była równa 448 modulo 512, oraz 64-bitowy zapis $\ell$. Oznaczmy to dopełnienie przez $\mathsf{pad}(\ell)$. Funkcja kompresująca aktualizuje stan po każdym bloku, a skrót SHA-256 ujawnia cały stan końcowy.

Przeciwnik znający $\tau=\mathcal D(k\Vert m)$ oraz długość $|k|+|m|$ może użyć $\tau$ jako stanu początkowego dalszego przetwarzania. Nie odtwarza klucza. Dla wybranego dodatku $x$ wyznacza skrót wejścia $k\Vert m\Vert\mathsf{pad}(|k|+|m|)\Vert x$, z nowym dopełnieniem dla całej przedłużonej długości. W efekcie potrafi utworzyć znacznik wiadomości

Przykładowo przy kluczu długości 16 bajtów i wiadomości długości 3 bajtów pierwsze dopełnienie ma 45 bajtów. Zaczyna się od 80, ma 36 zerowych bajtów i kończy 8-bajtowym zapisem liczby 152. Stan $\tau$ odpowiada już przetworzeniu 64 bajtów. Po dopisaniu 1 bajtu $x$ nowe pole długości koduje 520 bitów. Dołączone do $m'$ dopełnienie jest częścią bajtów fałszerstwa, nie niewidzialną instrukcją dla odbiorcy.

Jeżeli długość klucza jest nieznana, można próbować uzasadnionych kandydatów. Weryfikacja i parser aplikacji określają, które wiadomości mogą zostać przyjęte. Ten mechanizm nie wymaga znalezienia dwóch różnych wejść o tym samym skrócie. Nie działa w tej postaci dla każdej funkcji skrótu, w szczególności nie jest opisem SHA-3 ani HMAC. HMAC wykorzystuje osobne haszowanie wewnętrzne i zewnętrzne. Jego bezpieczeństwa nie zastępuje samo stwierdzenie, że ten konkretny atak nie działa. SHA-256 i dopełnienie, RFC 6234, §4 i §6.2, HMAC, RFC 2104.

Kodowanie, domeny i wyprowadzanie kluczy

Złożone wejścia kodujemy jednoznacznie, np. długość pola i jego bajty. Role hasza rozdzielamy etykietą domeny. Dwie różne krotki nie mogą stać się tym samym wejściem przez konkatenację bez granic.

KDF, funkcja wyprowadzania klucza, zamienia odpowiedni tajny materiał wejściowy na bajty kluczy o potrzebnych długościach. Dołącza się kontekst oraz osobne etykiety zastosowań. Nie tworzy sekretu z publicznych danych i nie naprawia przewidywalnego wejścia. Przykładem jest HKDF, opisany w RFC 5869. W W10 zastosujemy ten interfejs do wspólnego elementu grupy.

HKDF

HMAC-based Extract-and-Expand Key Derivation Function. Funkcja wyprowadzania kluczy oparta na HMAC, z etapami ekstrakcji i rozszerzania.

Dwa różne doświadczenia z haszowaniem

Najpierw skracamy SHA-256 do $n$ początkowych bitów. To celowe osłabienie, dzięki któremu rzeczywista kolizja pojawia się szybko. Dla ustalonej liczby $t$ niezależnych jednostajnych wyników dokładne prawdopodobieństwo co najmniej jednej kolizji wynosi:

Założenie o losowych wynikach służy rachunkowi teoretycznemu. Sam SHA-256 jest deterministycznym algorytmem. Wyszukiwanie zatrzymujemy po pierwszej kolizji lub po 2048 próbach. Wynikiem jest konkretna para różnych wiadomości z równymi krótkimi skrótami. Pełne skróty pozostają dostępne, aby nie pomylić tego zdarzenia ze złamaniem pełnego SHA-256.

Drugi eksperyment nie szuka kolizji. Pokazuje, dlaczego zgodny publiczny skrót nie potwierdza nadawcy. Po zmianie wiadomości przeciwnik liczy nowy skrót bez sekretu. Nie potrafi w ten sam sposób poprawić skopiowanego znacznika HMAC.

Nieudana próba z jednym starym MAC nie jest pełnym dowodem niepodrabialności. Jest świadkiem różnicy między dwoma interfejsami: publicznym liczeniem skrótu i tajnym tworzeniem znacznika. Analizę HMAC należy wiązać z jego konkretną konstrukcją, a nie z dowolną funkcją zawierającą klucz.

Powiązania: C4, Encrypt-then-MAC, RFC 2104.