Kryptografia II stopień

Od definicji bezpieczeństwa do konstrukcji, redukcji i publikacji naukowych.

Pogłębienie A. Gry i dowody symetryczne

Materiał do wyboru. Rozwija W1–W5. Droga prowadzi od jednej zmiany rozkładu przez hybrydy do symulacji wyroczni deszyfrującej. Potrzebujemy modeli CPA i CCA2 z W1, pierwszej redukcji i sprzężenia z W3 oraz niepodrabialności MAC z W5.

Metoda Shoupa: co wolno zmienić między grami

Praca Victora Shoupa Sequences of Games: A Tool for Taming Complexity in Security Proofs porządkuje dowód przez małe, uzasadnione zmiany. Rozdział W3a wyjaśnia tę metodę po polsku, dowodzi lematu o różnicy i pokazuje sprzężenie krok po kroku. Poniżej przypominamy rachunek przed zastosowaniem go do uwierzytelnionego szyfrowania. Numer gry jest etykietą wersji eksperymentu. Nie zastępuje opisu losowań, tabel ani zdarzenia sukcesu.

W praktyce rozróżniamy trzy rodzaje kroku: przepisanie bez zmiany rozkładu, zmianę opartą na założeniu nierozróżnialności i zmianę widoczną tylko po określonym zdarzeniu złym. Dla każdego kroku zapisujemy osobne uzasadnienie. Dopiero potem łączymy oszacowania.

Zdarzenie złe nie jest nazwą nieudanej próby ataku. Jest zdarzeniem, po którym przestaje obowiązywać sprzężenie dwóch eksperymentów, np. powtórzeniem nonce. Jeśli gry zachowują się identycznie poza nim, różnica prawdopodobieństw sukcesu nie przekracza prawdopodobieństwa tego zdarzenia. Trzeba wskazać grę, w której je liczymy.

Konkretny łańcuch dla szyfrowania z PRF

Wróćmy do reguły szyfrowania $c=m\oplus F_k(r)$ , z wysyłanym publicznie $r$ . Każde wywołanie szyfrujące losuje nowe $r\overset{\$}{\leftarrow}\{0,1\}^n$ . Przeciwnik może wybierać wiadomości przed wyzwaniem i po nim. Łącznie, wraz z wyzwaniem, przewidujemy najwyżej $t\le 2^n$ szyfrowań. To pozwala zdefiniować także grę, w której identyfikatory wybieramy bez powtórzeń.

Gra	Zmiana	Uzasadnienie
$G_0$	Oryginalny eksperyment IND-CPA	To cel twierdzenia
$G_1$	Zamiast $F_k$ używamy jednej losowej funkcji $R$	Redukcja do PRF
$G_2$	Losujemy identyfikatory bez powtórzeń	Sprzężenie do pierwszej kolizji
$G_3$	Nieużyte wcześniej wartości $R(r)$ zastępujemy świeżymi maskami	Identyczny rozkład

Redukcja PRF dostaje dostęp do nieznanej wyroczni $O$ , będącej rzeczywistą funkcją albo losową. Szyfruje przez pytania $O(r)$ , więc nie potrzebuje klucza. W grze $G_3$ maska wyzwania jest niezależna od wszystkich pozostałych masek. Obserwacja innych szyfrowań, nawet adaptacyjnych, nie pomaga poznać bitu.

Jeżeli $\epsilon_{\mathrm{prf}}$ ogranicza przewagę tej redukcji w konwencji różnicy prawdopodobieństw, otrzymujemy konserwatywnie:

\operatorname{Adv}^{\mathrm{ind}}_{\mathcal A} \le \epsilon_{\mathrm{prf}}+\frac{t\cdot(t-1)}{2^{n+1}}.

Nie dodajemy kosztu każdej wiadomości po raz drugi, skoro jedno zastąpienie wyroczni obsługuje wszystkie wywołania. Liczba zapytań redukcji do $O$ wynosi najwyżej $t$ . Jej czas obejmuje czas przeciwnika i własną obsługę komunikatów. Twierdzenie bez tych parametrów jest mniej użyteczne przy doborze konkretnego limitu danych.

Pomyłka, która zmienia dowód

Gdyby w $G_1$ powtórzone $r$ dostawało świeżą maskę, nie byłaby to już losowa funkcja. Taki program bezpodstawnie ukrywałby problem powtórzenia nonce. Dlatego tabela z pierwszego rozdziału ma znaczenie także tutaj. Spójność odpowiedzi to element modelu, nie detal implementacyjny.

Inna pomyłka polega na oszacowaniu kolizji w $G_0$ z użyciem niezależności, którą uzyskaliśmy dopiero w innej grze. Kolejność i warunkowanie trzeba zapisać. W tym przykładzie identyfikatory są losowane niezależnie już przez algorytm szyfrujący, więc prosty rachunek urodzinowy ma podstawę.

Lemat hybrydowy

Niech $S_i$ oznacza zdarzenie sukcesu w grze $G_i$ i niech $p_i=\Pr[S_i]$ , zgodnie z W3a. Teleskopowanie i nierówność trójkąta dają:

|p_0-p_t| =\left|\sum_{i=0}^{t-1}(p_i-p_{i+1})\right| \le\sum_{i=0}^{t-1}|p_i-p_{i+1}|.

Jeżeli różnica końców wynosi $\epsilon$ , pewien krok ma różnicę co najmniej $\epsilon/t$ . Aby był to dowód kryptograficzny, potrzebujemy algorytmu odtwarzającego dwie sąsiednie gry z wyzwania. Nazwanie gry losową nie wyjaśnia, jak odpowiedzieć przeciwnikowi.

W szyfrowaniu $(r,m\oplus F_k(r))$ jedna redukcja ma wyrocznię $O$ będącą $F_k$ albo $R$ . Każde szyfrowanie wykonuje przez $O(r)$ . Zastępuje więc całą funkcję naraz, bez dodatkowego zgadywania wiadomości. W losowej grze definiujemy $\mathrm{Bad}$ jako powtórzenie $r$ . Sprzęgamy gry tak, aby były identyczne do pierwszego $\mathrm{Bad}$ . Ich różnica jest co najwyżej $\Pr[\mathrm{Bad}]$ .

Encrypt-then-MAC

Cel i założenia przed redukcją. Chcemy osiągnąć IND-CCA2, czyli poufność mimo pytań o odszyfrowanie innych rekordów, przed wyzwaniem i po nim. Zakaz dotyczy dokładnego rekordu wyzwania z jego kontekstem. Przyjmijmy najpierw deterministyczny MAC z dokładnie jednym akceptowanym znacznikiem dla danej wiadomości i klucza. Fałszerstwo MAC oznacza wtedy poprawny znacznik dla nowej, wcześniej nieuwierzytelnianej wiadomości. To model poznany w W5.

Użyj szyfrowania IND-CPA i takiego MAC z niezależnymi kluczami. Wyślij $c=\mathsf{Enc}_{k_E}(m)$ i $\tau=\mathsf{MAC}_{k_M}(\operatorname{enc}(\mathrm{AAD},c))$ . Tutaj $\operatorname{enc}$ jest jednoznacznym kodowaniem pól w bajty, nie algorytmem szyfrującym $\mathsf{Enc}$ . Najpierw weryfikuj znacznik, dopiero potem deszyfruj.

Redukcja zna klucz MAC. Dodaje znaczniki do szyfrogramów z wyroczni szyfrującej i zapisuje tabelę wydanych par oraz wiadomości. Znana para daje odpowiedź z tabeli, poza zakazanym wyzwaniem. Nowa poprawna para oznacza fałszerstwo MAC. Po wykluczeniu tego zdarzenia pozostałe nowe zapytania zwracają $\bot$ bez deszyfrowania.

Pozostaje problem IND-CPA. Granicę tworzy suma kosztu tego rozróżniania i osobno ograniczonego prawdopodobieństwa fałszerstwa MAC. Redukcja do MAC jest innym algorytmem niż redukcja CPA i nie otrzymuje jego tajnego klucza. Musi rozliczyć liczbę prób weryfikacji. W modelu z jednym końcowym fałszerstwem można zgadywać pozycję pierwszej nowej akceptacji, płacąc czynnikiem liczby tych prób.

Jeżeli MAC dopuszcza różne poprawne znaczniki dla tej samej wiadomości, potrzebujemy silnej niepodrabialności: przeciwnik nie może wytworzyć nowej poprawnej pary wiadomość–znacznik, nawet dla wiadomości już pytanej. Inaczej zmiana samego znacznika wyzwania mogłaby ominąć zakaz jego deszyfrowania. To dodatkowe wymaganie, nie automatyczny wniosek z modelu W5.

Nonce i AAD muszą należeć do uwierzytelnianego kontekstu, jeśli stanowią wejście aplikacji. Dowód dla innego interfejsu nie uzasadnia ich późniejszego dopisania jako niechronionych metadanych.

Czytanie granic

Wypisz czas, liczbę szyfrowań i weryfikacji oraz długość danych. Składnik urodzinowy może zależeć od liczby bloków, nie plików. Pesymistyczna górna granica nie dowodzi istnienia ataku osiągającego tę wartość.

Źródła i porównanie organizacji materiału: Boneh–Shoup, MIT Foundations of Cryptography.