Wrocław University of Science and TechnologyDepartment of Fundamentals of Computer Science

Kryptografia II stopień

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

W3. Tajność doskonała, OTP i szyfry strumieniowe

Pierwszy pełny schemat: OTP

Cel: ukryć jedną wiadomość o ustalonej długości przed obserwatorem szyfrogramu. Zasób: nadawca i odbiorca mają już ten sam tajny, jednostajny klucz. Sam schemat nie dostarcza sposobu bezpiecznego przekazania tego klucza.

Szyfr z kluczem jednorazowym: algorytmy i przepływ

Π=(Setup,KeyGen,Enc,Dec)\Pi=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})
Setup(1λ)\mathsf{Setup}(1^\lambda)⟶pp=ℓ\longrightarrow pp=\ell
M={0,1}ℓ\mathcal M=\{0,1\}^\ell
KeyGen(pp)\mathsf{KeyGen}(pp)⟶k\longrightarrow k
k←${0,1}ℓk\overset{\$}{\leftarrow}\{0,1\}^\ell

Ten sam tajny klucz dostarczono już obu stronom.

Enc(pp,k,m)\mathsf{Enc}(pp,k,m)⟶c\longrightarrow c
c=m⊕kc=m\oplus k

Sprawdź długość. Nie używaj k dla drugiej wiadomości.

Dec(pp,k,c)\mathsf{Dec}(pp,k,c)⟶m\longrightarrow m
m=c⊕km=c\oplus k

Odrzuć błędną długość szyfrogramu.

Szyfr z kluczem jednorazowym: czynności i komunikatyNadawcaOdbiorcaEncPrzekazywany jest tylko szyfrogramDec

Szyfr z kluczem jednorazowym

Nadawca: pp,k,mpp,k,m

Odbiorca: pp,kpp,k

  1. Nadawca, Enc: c=m⊕kc=m\oplus k
  2. Nadawca → Odbiorca: cc Przekazywany jest tylko szyfrogram
  3. Odbiorca, Dec: m=c⊕km=c\oplus k
Klucz k nie płynie razem z c. Dostarczenie wspólnego sekretu jest założeniem, nie wynikiem OTP.

Jak działa jednorazowa maska

Setup ustala długość ℓ=ℓ(λ)\ell=\ell(\lambda). Wiadomość, klucz i szyfrogram mają po ℓ\ell bitów. KeyGen losuje klucz niezależnie od wiadomości. Nadawca wywołuje Enc z wiadomością i tym kluczem. Odbiorca uruchamia Dec z szyfrogramem i własną kopią tego samego klucza. Na strzałce między nimi znajduje się tylko szyfrogram cc.

Poprawność: (m⊕k)⊕k=m(m\oplus k)\oplus k=m. Ograniczenie: OTP nie wykrywa celowej zmiany szyfrogramu. Teraz sprawdzimy jego poufność, a następnie zobaczymy, dlaczego ponowne użycie klucza niszczy tę gwarancję.

Tajność jako równość rozkładów

Niech MM oznacza losową wiadomość, a CC odpowiadający jej szyfrogram. Małe litery m,cm,c są ich konkretnymi wartościami. W tajności doskonałej obserwacja szyfrogramu nie zmienia rozkładu wiadomości:

Pr⁡[M=m∣C=c]=Pr⁡[M=m]\Pr[M=m\mid C=c]=\Pr[M=m]

dla każdego cc o dodatnim prawdopodobieństwie. W one-time pad wiadomość i klucz mają długość ℓ\ell, klucz jest jednostajny, niezależny od wiadomości i użyty raz. Szyfrowanie to c=m⊕kc=m\oplus k. Dla ustalonych m,cm,c dokładnie jeden klucz daje ten szyfrogram. Stąd Pr⁡[C=c∣M=m]=2−ℓ\Pr[C=c\mid M=m]=2^{-\ell} niezależnie od mm. Również Pr⁡[C=c]=2−ℓ\Pr[C=c]=2^{-\ell}, bo uśredniamy tę samą wartość po wszystkich wiadomościach. Podstawiamy do wzoru Bayesa, który zamienia kierunek warunkowania:

Pr⁡[M=m∣C=c]=Pr⁡[C=c∣M=m]⋅Pr⁡[M=m]Pr⁡[C=c]=Pr⁡[M=m].\Pr[M=m\mid C=c] =\frac{\Pr[C=c\mid M=m]\cdot\Pr[M=m]}{\Pr[C=c]} =\Pr[M=m].

Przy dwóch bitach każda ustalona wiadomość może dać dowolny z czterech szyfrogramów. Dla każdego jest dokładnie jeden z czterech kluczy. To mała wersja tego samego argumentu, nie założenie o równomiernym rozkładzie wiadomości.

Jednorazowość jest częścią konstrukcji

Przy ponownym użyciu maski:

c1⊕c2=m1⊕m2.c_1\oplus c_2=m_1\oplus m_2.

Poznanie jednej wiadomości ujawnia drugą. Bez znajomości wiadomości pozostaje ujawniona relacja. Dla szyfru strumieniowego problemem jest powtórzenie pary klucz–nonce, nie samo użycie jednego klucza do poprawnie rozdzielonych strumieni.

OTP · dwie wiadomości, jedna maska

Lokalny rachunek na bajtach. Dwa wejścia szesnastkowe muszą mieć tę samą długość.

Maski szyfrujące

Gotowe do rozpoczęcia.

Szyfry strumieniowe zastępują długi losowy klucz pseudolosowym strumieniem. ChaCha20 jest przykładem takiego mechanizmu. Sam strumień nie zapewnia integralności. Zmiana bitu szyfrogramu zmienia odpowiedni bit tekstu. Praktyczny kanał potrzebuje uwierzytelniania, np. konstrukcji AEAD.

Poznaliśmy już oba składniki następnego argumentu: definicję PRG w W2 oraz niezależność szyfrogramu OTP od wiadomości. Możemy teraz wyjaśnić, jak założenie o generatorze przenosi się na bezpieczeństwo szyfrowania.

Dlaczego pojawiają się gry numerowane

Mamy już eksperyment określający sukces przeciwnika. Teraz chcemy oszacować jego prawdopodobieństwo. Bezpośredni rachunek bywa trudny, bo jednocześnie występują klucze, hasze, odpowiedzi i warunki akceptacji. Tworzymy więc kolejne wersje tego samego eksperymentu, zmieniając po jednym elemencie.

G0G_0 oznacza wersję wyjściową. G1G_1 to wersja po pierwszej zmianie, a nie nowy typ algorytmu lub nowa grupa algebraiczna. Przeciwnik próbuje osiągnąć ten sam cel. Dla każdej zmiany pytamy: czy jego widok ma ten sam rozkład, czy odróżnienie wymagałoby złamania założenia, czy też różnica zachodzi tylko po rzadkim zdarzeniu?

Jeśli w ostatniej grze szyfrogram jest zupełnie niezależny od ukrytego bitu, zgadywanie daje 1/21/2. Jeżeli umiemy ograniczyć wszystkie różnice między sąsiednimi grami, wracamy do początkowego systemu. Nie wystarczy nazwać kolejnych etapów grami. Każda strzałka wymaga uzasadnienia.

Eksperyment rzeczywistyukryty bit i szyfrogramJedna uzasadniona zmianaten sam cel przeciwnikaEksperyment uproszczonyłatwo policzyć sukces
G0, p0G_0,\ p_0
G1, p1G_1,\ p_1
G2, p2G_2,\ p_2
∣p0−p2∣≤∣p0−p1∣+∣p1−p2∣|p_0-p_2|\le |p_0-p_1|+|p_1-p_2|
Najpierw określamy program każdej gry i zdarzenie sukcesu. Dopiero potem ograniczamy różnice prawdopodobieństw. Numer gry nie jest założeniem bezpieczeństwa.

Redukcja jest algorytmem wykorzystującym atak

Przyjmujemy hipotetyczny skuteczny atak A\mathcal A na konstrukcję. Budujemy program B\mathcal B, który dostaje trudne zadanie, uruchamia A\mathcal A, przygotowuje mu widok i wykorzystuje jego odpowiedź do rozwiązania tego zadania. Jeśli przygotowany widok jest właściwy i koszt nie jest zbyt duży, skuteczność A\mathcal A przeczyłaby naszemu założeniu.

To kierunek od ataku do rozwiązania trudnego problemu. Redukcja nie musi znać sekretów uczciwej implementacji. Musi umieć zastąpić ich użycie przy generowaniu widoku. Gdy w rzekomym dowodzie do symulacji podpisu potrzebujemy nieznanego klucza z wyzwania, konstrukcja redukcji jest niekompletna.

Trzy sposoby tworzenia maski: pełne tablice

Wszystkie trzy konstrukcje szyfrują przez XOR. Różni je źródło maski. Ta różnica rozstrzyga, jakie bezpieczeństwo otrzymujemy i czego musimy pilnować. Zanim przejdziemy do dowodu, prześledzimy kompletne, małe tablice. Są to jawne przykłady dydaktyczne, nie propozycje bezpiecznych parametrów.

Konstrukcja Sekret Maska długości ℓ\ell Wysyłany szyfrogram Długość szyfrogramu
OTP świeży U←${0,1}ℓU\xleftarrow{\$}\{0,1\}^{\ell} UU C=M⊕UC=M\oplus U ℓ\ell
PRG tajny S←${0,1}sS\xleftarrow{\$}\{0,1\}^{s} G(S)G(S) C=M⊕G(S)C=M\oplus G(S) ℓ\ell
PRF tajny K←${0,1}κK\xleftarrow{\$}\{0,1\}^{\kappa} FK(R)F_K(R) (R,C)=(R,M⊕FK(R))(R,C)=(R,M\oplus F_K(R)) r+ℓr+\ell

W ostatnim wierszu RR jest publicznym argumentem długości rr. Będziemy go losować niezależnie dla każdego szyfrowania albo zapewniać jego niepowtarzalność. Długość klucza κ\kappa, długość argumentu rr i długość maski ℓ\ell pełnią różne role. Publiczny RR nie jest tajnym zarodkiem PRG.

OTP: cała tablica szyfrowania

Dla dwóch bitów wypiszmy wszystkie wiadomości i wszystkie klucze. Wiersz wybiera wiadomość, kolumna wybiera maskę. Komórka zawiera szyfrogram.

Wiadomość / maska00011011
0000011011
0101001110
1010110001
1111100100

W każdym wierszu każdy szyfrogram pojawia się dokładnie raz. Dla ustalonej wiadomości mm i szyfrogramu cc istnieje dokładnie jedna maska u=m⊕cu=m\oplus c. Jeśli maska jest jednostajna i niezależna od wiadomości, to:

Pr⁡[C=c∣M=m]=Pr⁡[U=m⊕c]=14.\Pr[C=c\mid M=m]=\Pr[U=m\oplus c]=\frac14.

Nie zakładamy, że wiadomości są równie prawdopodobne. Niech pm=Pr⁡[M=m]p_m=\Pr[M=m] będzie dowolnym rozkładem wiadomości. Wówczas:

Pr⁡[M=m,C=c]=pm⋅14,Pr⁡[C=c]=∑mpm⋅14=14,Pr⁡[M=m∣C=c]=pm⋅(1/4)1/4=pm.\begin{aligned} \Pr[M=m,C=c]&=p_m\cdot\frac14,\\ \Pr[C=c]&=\sum_m p_m\cdot\frac14=\frac14,\\ \Pr[M=m\mid C=c]&=\frac{p_m\cdot(1/4)}{1/4}=p_m. \end{aligned}

Szyfrogram nie zmienia wiedzy o wiadomości. Jeśli przed obserwacją pewna wiadomość była bardziej prawdopodobna, pozostaje taka także po obserwacji. Doskonała tajność nie wyrównuje prawdopodobieństw wiadomości. Sprawia, że obserwacja szyfrogramu ich nie zmienia. Dla długości ℓ\ell zastępujemy 1/41/4 przez 2−ℓ2^{-\ell}.

Co oznacza ukrycie kolumny z kluczem

Pełny zapis doświadczenia zawiera (M,U,C)(M,U,C). Przeciwnik otrzymuje tylko CC. Przejście do jego widoku jest projekcją pełnego stanu, a obliczenie rozkładu widoku wymaga zsumowania prawdopodobieństw po wszystkich ukrytych wartościach:

Pr⁡[C=c∣M=m]=∑u∈{0,1}ℓPr⁡[U=u]⋅1[c=m⊕u].\Pr[C=c\mid M=m]=\sum_{u\in\{0,1\}^{\ell}}\Pr[U=u]\cdot\mathbf1[c=m\oplus u].

Symbol 1[E]\mathbf1[E] ma wartość 11, gdy warunek EE zachodzi, i 00 w przeciwnym przypadku. Nie wybieramy jednego wygodnego wiersza i nie usuwamy pozostałych. Sumujemy ich wagi. W OTP ten rachunek daje taki sam wynik dla każdego mm. To jest matematyczny powód tajności.

PRG: sekret wybiera jeden wiersz

Teraz s=3s=3, ℓ=6\ell=6, a wiadomością jest M=101100M=101100. Publiczny generator jest określony przez całą poniższą tablicę. Tajny jest tylko wybór SS.

SSG(S)G(S)101100⊕G(S)101100\oplus G(S)
000011010110110
001110001011101
010001111100011
011100100001000
100111000010100
101010110111010
110000101101001
111101011000111

Prześledźmy jeden wiersz. Zarodek S=011S=011 wybiera maskę G(011)=100100G(011)=100100. Dla naszej wiadomości otrzymujemy:

C=101100⊕100100=001000.C=101100\oplus100100=001000.

Odbiorca, znając ten sam zarodek, oblicza 001000⊕100100=101100001000\oplus100100=101100. Przeciwnik widzi 001000001000, ale nie dostaje oznaczenia wybranego wiersza.

Znając SS, odbiorca odtwarza maskę i oblicza M=C⊕G(S)M=C\oplus G(S). Formalna składnia tej jednorazowej konstrukcji to:

Setup(1λ)→(G,s,ℓ),KeyGen:S←${0,1}s,EncS(M)=M⊕G(S),DecS(C)=C⊕G(S).\begin{aligned} \mathsf{Setup}(1^\lambda)&\to(G,s,\ell),\\ \mathsf{KeyGen}&:\quad S\xleftarrow{\$}\{0,1\}^{s},\\ \mathsf{Enc}_S(M)&=M\oplus G(S),\\ \mathsf{Dec}_S(C)&=C\oplus G(S). \end{aligned}

Parametry są publiczne, a SS jest kluczem tajnym. Dziedzina wiadomości to {0,1}ℓ\{0,1\}^{\ell}. Poprawność wynika z dwukrotnego XOR z tą samą maską. Nazwa „jednorazowa” jest częścią warunków użycia: tej samej maski nie wolno użyć do dwóch wiadomości.

Co daje pełna tablica, a czego nie obiecuje założenie

W przykładzie istnieje osiem różnych masek zamiast wszystkich 6464. Ich prawdopodobieństwa wynoszą 1/81/8, a pozostałych masek 00. Odległość statystyczna od rozkładu jednostajnego wynosi 1−8/64=7/81-8/64=7/8. Każdy może to sprawdzić, bo tablica jest mała. Ten generator nie jest kryptograficznie bezpieczny.

W dużej konstrukcji przeciwnik też zna algorytm GG. Nie ukrywamy przed nim definicji funkcji. Założenie PRG mówi, że przy losowym, ukrytym SS nie znajdzie efektywnego testu rozpoznającego rozkład G(S)G(S) z niezaniedbywalną przewagą. Nie mówi, że wszystkie maski są możliwe albo równie prawdopodobne.

Ukrycie kolumny SS na rysunku samo niczego nie dowodzi. Rozkład widoku nadal jest rozkładem wynikającym z GG. Aby zastąpić go równomiernym, potrzebujemy kroku obliczeniowego opartego na założeniu PRG. Nie jest to tożsamość rozkładów.

PRF: sekret wybiera kolumnę, publiczny argument wybiera wiersz

Przyjmijmy κ=2\kappa=2, r=3r=3, ℓ=6\ell=6. Wypiszmy całą małą rodzinę. Każda kolumna jest jedną deterministyczną funkcją. Klucz wybieramy raz, a kolejne publiczne argumenty wybierają wiersze tej samej kolumny.

Rodzina PRF · tajna kolumna i publiczny wiersz
Klucz w przykładzie dydaktycznym
Publiczny argument R
RRF00(R)F_{00}(R)F01(R)F_{01}(R)F10(R)F_{10}(R)F11(R)F_{11}(R)
000000110101001011010111100
001110011001101101101010010
010011101110000000110100011
011101000011110111100001011
100010111100101010011110110
101111010000100101101011000
110001001111111110000101010
111100100010001001011000101
K = 10, R = 100. Maska 010011. Szyfrogram (100, 111111).

Przy K=10K=10, R=100R=100 i M=101100M=101100 otrzymujemy F10(100)=010011F_{10}(100)=010011, więc wysyłamy:

(R,C)=(100, 101100⊕010011)=(100,111111).(R,C)=(100,\,101100\oplus010011)=(100,111111).

Zauważmy, że F10(001)=F10(101)=101101F_{10}(001)=F_{10}(101)=101101. Są to dwa różne argumenty i taki sam wynik. To kolizja wyjść, a nie powtórzenie argumentu. Nie zabrania jej definicja PRF. Podana mała rodzina jest ilustracją indeksowania, nie implementacją bezpiecznej PRF. Cztery klucze można wyczerpująco sprawdzić.

Funkcja losowa: każda komórka jest losowana niezależnie

Losowa funkcja f:{0,1}r→{0,1}ℓf:\{0,1\}^{r}\to\{0,1\}^{\ell} ma jedną odpowiedź dla każdego z 2r2^r argumentów. Jej pełną tablicę można wyobrazić sobie jako 2r2^r niezależnych losowań po ℓ\ell bitów. Oto jeden możliwy wynik takiego doświadczenia:

RRf(R)f(R)
000010101
001101100
010111000
011010101
100000011
101110010
110100001
111011110

Wartości dla 000000 i 011011 są równe. Nie poprawiamy tablicy i nie losujemy ich ponownie. Niezależne nie oznacza różne. Liczba bitów potrzebnych do zapisania wszystkich odpowiedzi wynosi ℓ⋅2r\ell\cdot2^r, a liczba funkcji:

(2ℓ)2r=2ℓ⋅2r.\left(2^\ell\right)^{2^r}=2^{\ell\cdot2^r}.

Dla r=3r=3, ℓ=6\ell=6 są to 4848 bitów i 2482^{48} funkcji. Rodzina kluczowana dwubitowym kluczem zawiera najwyżej cztery różne funkcje. Ogólnie klucz o długości κ\kappa może wybrać najwyżej 2κ2^\kappa różnych funkcji. Nierozróżnialność PRF nie jest zatem twierdzeniem, że te dwa zbiory są równe. Jest ograniczeniem skuteczności efektywnego obserwatora mającego określony interfejs.

Leniwe losowanie: sprawdź, dopisz albo odczytaj

Nie trzeba losować całej ogromnej tablicy przed pierwszym pytaniem. Wystarczy utrzymywać początkowo pustą tablicę TT i losować tylko potrzebne odpowiedzi. To lazy sampling, czyli leniwe losowanie. Daje dokładnie taki sam rozkład odpowiedzi jak wcześniejsze wylosowanie całej funkcji.

RF(x):jesˊli x∉dom⁡T:y←${0,1}ℓ,T[x]←y,zwroˊcˊ T[x].\begin{aligned} \mathsf{RF}(x):\quad &\text{jeśli }x\notin\operatorname{dom}T:\quad y\xleftarrow{\$}\{0,1\}^{\ell},\quad T[x]\gets y,\\ &\text{zwróć }T[x]. \end{aligned}

Pierwsze pytanie o xx tworzy wpis. Każde kolejne pytanie o ten sam xx odczytuje istniejący wpis. Dla nowego argumentu losowanie jest jednostajne z całego {0,1}ℓ\{0,1\}^{\ell}, także z wartości już użytych w innych wierszach. Zabronienie powtarzania odpowiedzi dałoby inny obiekt, a nie funkcję losową.

Leniwa tablica · sprawdzenie poprzedza losowanie
Argument następnego zapytania
Źródło odpowiedzi dla nowych wpisów
Odczyt albo dopisanie wartości funkcji losowejPo sprawdzeniu argumentu istniejący wpis jest odczytywany. Tylko nowy argument wywołuje niezależne losowanie i zapis.ZapytanieSprawdź wpisOdczytaj stary wpisLosuj i zapamiętajOdpowiedźtaknie
xxT[x]T[x]Pochodzenie
Tablica T jest pusta. Każde zapytanie ma cztery kroki.

W demonstracji tablica jest widoczna dla czytelnika, aby wyjaśnić mechanizm. W dowodzie szyfrowania to wewnętrzny stan eksperymentu. Przeciwnik nie dostaje jej jako dodatkowego źródła masek. Gdyby otrzymał wyrocznię ff i publiczny RR szyfrogramu wyzwania, zapytałby o f(R)f(R) i odczytał wiadomość.

Dlaczego wyrocznia świeżych masek jest inna

Procedura FreshPad\mathsf{FreshPad} przy każdym wywołaniu losuje nowy, niezależny Pi←${0,1}ℓP_i\xleftarrow{\$}\{0,1\}^{\ell}. Jej lista jest indeksowana numerem wywołania ii. Tablica TT funkcji losowej jest indeksowana argumentem RR. Jeśli RR się powtórzy, funkcja musi wrócić do starego wpisu, ale świeża maska nie musi.

Nowa maska może przypadkiem być równa wcześniejszej. To wciąż nowe, niezależne losowanie. Nie zamieniamy OTP w losowanie bez zwracania.

Światy, role i widoki przeciwnika

W grze szyfrowania przeciwnik A\mathcal A wybiera pary wiadomości (Mi,0,Mi,1)(M_{i,0},M_{i,1}) tej samej długości ℓ\ell. Challenger, czyli strona prowadząca eksperyment, losuje jeden ukryty bit b←${0,1}b\xleftarrow{\$}\{0,1\} na cały przebieg. Za każdym razem szyfruje wiadomość Mi,bM_{i,b}. Przeciwnik zna obie proponowane wiadomości, ale nie wie, która została wybrana.

Wersja wielozapytaniowa nosi nazwę left-or-right, czyli „lewa albo prawa wiadomość”. Jest tu modelem nierozróżnialności wobec ataku z wybranym tekstem jawnym, IND-CPA (indistinguishability under chosen-plaintext attack). Słowo „wybranym” oznacza uprawnienie przeciwnika do zadawania takich pytań, a nie znajomość tajnego klucza. Nie ma on wyroczni deszyfrującej.

Zapytanie (M,M)(M,M) daje szyfrowanie tej samej, znanej przeciwnikowi wiadomości niezależnie od bb. W ten sposób model obejmuje także zwykłe zapytania o szyfrowanie wybranego tekstu. Takie pytania mogą dostarczać materiału do analizy, ale nie ujawniają bezpośrednio bitu wyboru.

Przeciwnik może wykonać własne obliczenia przed pytaniem, między pytaniami i po odpowiedzi. Może też zakończyć wcześniej. Przyjmujemy górny limit qq zapytań. Na końcu zwraca bit b^\widehat b. Zakończenie jest momentem zgłoszenia decyzji, nie zakazem wcześniejszego wnioskowania.

Adv⁡enc(A)=∣Pr⁡[b^=b]−12∣.\operatorname{Adv}^{\mathrm{enc}}(\mathcal A)=\left|\Pr[\widehat b=b]-\frac12\right|.

W tej konwencji największa przewaga wynosi 1/21/2. Inne źródła czasem mnożą tę definicję przez 22. Wtedy przez 22 trzeba pomnożyć także odpowiednie prawe strony naszych granic. Nie można przenosić stałych między tymi konwencjami bez sprawdzenia definicji.

Redukcja · uprawnienia zależą od roli
Przeciwnik, redukcja i wyroczniaPary wiadomości trafiają do redukcji. Tylko redukcja pyta wyrocznię o maskę. Przeciwnik dostaje nonce i szyfrogram.Przeciwnik ARedukcja BZna b, nie zna świata OWyrocznia OA otrzymuje szyfrogram, nie dostęp do wyroczni masek

Trzy różne widoki tej samej tabeli

Obserwator Co zna Czego nie wolno mu dopisać do wiedzy
Autor objaśnienia pełną tablicę przykładu, bit bb, klucz, maski i oba światy porównania ta wszechwiedza nie jest interfejsem przeciwnika
Przeciwnik szyfrowania A\mathcal A publiczne parametry, własne monety, wybrane pary, odpowiedzi (Ri,Ci)(R_i,C_i) klucza, masek, bitu bb, prywatnej tablicy TT i etykiety świata
Rozróżniacz PRF BB w redukcji własny bit bb, pary zadawane przez A\mathcal A, odpowiedzi swojej wyroczni O(Ri)O(R_i) tego, czy O=FKO=F_K, czy O=fO=f, oraz ukrytego klucza wyroczni

Przeciwnik zna własne losowe monety ρA\rho_{\mathcal A}. Jego widok po tt odpowiedziach możemy zapisać jako:

Vt=(pp,ρA,(Mi,0,Mi,1,Ri,Ci)i=1t).V_t=\left(\mathrm{pp},\rho_{\mathcal A}, \bigl(M_{i,0},M_{i,1},R_i,C_i\bigr)_{i=1}^{t}\right).

Publiczne parametry oznaczono przez pp\mathrm{pp}. Wewnętrzne zmienne challengera nie występują w VtV_t. Przeciwnik może jednak wyciągać z VtV_t konsekwencje, np. porównać publiczne argumenty albo testować klucze. Nie zakładamy, że po ukryciu kolumn przestaje myśleć.

Kiedy naprawdę wolno „wymazać kolumny”

Projekcja widoku: usunięcie niewysyłanych kolumn opisuje interfejs. To nie jest jeszcze dowód bezpieczeństwa. Rozkład pozostałych kolumn musi uwzględniać sumowanie po ukrytych zmiennych. Zależności nie znikają tylko dlatego, że nie rysujemy ich przyczyn.

Równość rozkładów: jeśli dwa pełne eksperymenty dają identyczny rozkład VtV_t, każda decyzja zależna wyłącznie od tego widoku ma taki sam rozkład. To krok informacyjny, bez założenia obliczeniowego.

Nierozróżnialność obliczeniowa: jeśli widoki są tylko obliczeniowo nierozróżnialne, nie wolno napisać, że są równe. Wolno powiedzieć, że żaden dopuszczony efektywny test nie rozróżnia ich z dużą przewagą. Taki krok musi wskazywać PRG albo PRF i konkretną redukcję.

Sprzężenie do zdarzenia złego: możemy zestawić dwa światy tak, aby ich widoki zgadzały się aż do określonego zdarzenia. Różnicę szans sukcesu ograniczamy wtedy prawdopodobieństwem tego zdarzenia. Nie jest to globalna równość rozkładów.

Przykład ostrzegawczy: przy powtórzeniu Ri=RjR_i=R_j można ukryć obie maski w tabeli, ale przeciwnik nadal widzi powtórzenie RR i oblicza Ci⊕Cj=Mi,b⊕Mj,bC_i\oplus C_j=M_{i,b}\oplus M_{j,b}. Ukrycie kolumny nie usuwa tej zależności.

Jednorazowe szyfrowanie z PRG: pełna redukcja

Przeciwnik wybiera jedną parę M0,M1∈{0,1}ℓM_0,M_1\in\{0,1\}^{\ell} i otrzymuje szyfrogram jednej z nich. W świecie H0H_0 maską jest G(S)G(S). W świecie H1H_1 maską jest U←${0,1}ℓU\xleftarrow{\$}\{0,1\}^{\ell}. Pozostałe reguły nie zmieniają się.

Gra Maska Odpowiedź dla przeciwnika
H0H_0 G(S)G(S) dla tajnego losowego SS Mb⊕G(S)M_b\oplus G(S)
H1H_1 świeże U←${0,1}ℓU\xleftarrow{\$}\{0,1\}^{\ell} Mb⊕UM_b\oplus U

Rozróżniacz DD otrzymuje ciąg ZZ o długości ℓ\ell, który jest albo G(S)G(S), albo jednostajnym UU. Uruchamia A\mathcal A, odbiera parę wiadomości, sam losuje bb, przekazuje C=Mb⊕ZC=M_b\oplus Z, odbiera b^\widehat b i zwraca 11 dokładnie wtedy, gdy b^=b\widehat b=b. Nie musi znać zarodka SS.

Jeśli Z=G(S)Z=G(S), obsługa jest dokładnie światem H0H_0. Jeśli Z=UZ=U, jest dokładnie światem H1H_1. W drugim świecie OTP daje szansę sukcesu 1/21/2. Dlatego dla tak skonstruowanego DD:

Adv⁡enc(A)=∣Pr⁡[WinH0]−Pr⁡[WinH1]∣=Adv⁡Gprg(D).\operatorname{Adv}^{\mathrm{enc}}(\mathcal A) =\left|\Pr[\mathsf{Win}_{H_0}]-\Pr[\mathsf{Win}_{H_1}]\right| =\operatorname{Adv}^{\mathrm{prg}}_G(D).

Zatem ograniczenie przewagi PRG ogranicza przewagę ataku na szyfr. Narzut redukcji to jedno XOR długości ℓ\ell i prosta obsługa gry. Nie ma tu zdarzenia kolizji publicznych argumentów, bo nie ma publicznego RR ani wielu użyć maski.

Granica tej konstrukcji

Jeżeli użyjemy tego samego SS do dwóch pełnych wiadomości, otrzymamy:

C1⊕C2=(M1⊕G(S))⊕(M2⊕G(S))=M1⊕M2.C_1\oplus C_2=(M_1\oplus G(S))\oplus(M_2\oplus G(S))=M_1\oplus M_2.

Założenie PRG nie usuwa tej algebraicznej zależności. To niewłaściwe użycie dobrego prymitywu. Jeśli jedna wiadomość jest znana, odczytamy drugą. Nawet bez tego poznajemy relację między nimi. Rozłączne fragmenty odpowiednio długiego, bezpiecznego strumienia to inne użycie niż dwukrotne użycie tego samego fragmentu.

Szyfrowanie z PRF: algorytmy i trzy światy

Definiujemy schemat dla wiadomości długości ℓ\ell. Każde szyfrowanie losuje własny publiczny argument długości rr. Klucz jest wspólny dla wszystkich szyfrowań:

Setup(1λ)→(F,κ,r,ℓ),KeyGen:K←${0,1}κ,EncK(M):R←${0,1}r,C←M⊕FK(R),zwroˊcˊ (R,C),DecK(R,C):zwroˊcˊ C⊕FK(R).\begin{aligned} \mathsf{Setup}(1^\lambda)&\to(F,\kappa,r,\ell),\\ \mathsf{KeyGen}&:\quad K\xleftarrow{\$}\{0,1\}^{\kappa},\\ \mathsf{Enc}_K(M)&:\quad R\xleftarrow{\$}\{0,1\}^{r},\quad C\gets M\oplus F_K(R),\quad\text{zwróć }(R,C),\\ \mathsf{Dec}_K(R,C)&:\quad\text{zwróć }C\oplus F_K(R). \end{aligned}

Odbiorca nie musi zgadywać RR, bo otrzymuje je wraz z szyfrogramem. Algorytmy odrzucają dane o niewłaściwych długościach. Z samych tych algorytmów nie wynika jednak wykrywanie modyfikacji poprawnej długości. Do tego wrócimy przy integralności.

Niech αj=Pr⁡[b^=b w Gj]\alpha_j=\Pr[\widehat b=b\text{ w }G_j]. W każdym świecie przeciwnik ma ten sam interfejs i ten sam limit qq. Losowania publicznych argumentów są niezależne i jednostajne.

Świat Źródło maski w wywołaniu ii Co zachowujemy
G0G_0 FK(Ri)F_K(R_i) jeden klucz KK na cały przebieg
G1G_1 f(Ri)f(R_i) jedną funkcję losową i tablicę TT na cały przebieg
G2G_2 świeże Pi←${0,1}ℓP_i\xleftarrow{\$}\{0,1\}^{\ell} nowe niezależne losowanie przy każdym wywołaniu

W każdym wierszu odpowiedzią jest (Ri,Mi,b⊕maska)(R_i,M_{i,b}\oplus\text{maska}). Świat G2G_2 jest eksperymentem porównawczym, nie implementacją deszyfrowania z tego samego KK i RR. Odbiorca musiałby osobno otrzymać odpowiednie jednorazowe maski. W dowodzie badamy widok przeciwnika, a nie proponujemy magicznej bezkluczowej implementacji OTP.

Krok 1: PRF zastępujemy funkcją losową

Rozróżniacz BB dostaje wyrocznię OO, która jest albo FKF_K, albo ff. Sam losuje bb i uruchamia A\mathcal A. Na pytanie (Mi,0,Mi,1)(M_{i,0},M_{i,1}) losuje RiR_i, pyta O(Ri)O(R_i) i odpowiada (Ri,Mi,b⊕O(Ri))(R_i,M_{i,b}\oplus O(R_i)). Na końcu zwraca 11 wtedy i tylko wtedy, gdy b^=b\widehat b=b.

Ta obsługa odtwarza dokładnie G0G_0 albo G1G_1. Powtórzone argumenty nie są przeszkodą. Obie wyrocznie zwracają wtedy wcześniejszy wynik. Dlatego:

∣α0−α1∣=Adv⁡Fprf(B).|\alpha_0-\alpha_1|=\operatorname{Adv}^{\mathrm{prf}}_F(B).

Nie mnożymy tej przewagi dodatkowo przez qq. Założenie PRF już obejmuje cały interfejs z wieloma adaptacyjnymi zapytaniami. Rozróżniacz wykonuje najwyżej qq zapytań i ma czas TB=TA+O(q⋅(r+ℓ))T_B=T_{\mathcal A}+O(q\cdot(r+\ell)), poza standardowym kosztem obsługi interfejsu. Budżet zapytań i czas trzeba podać przy konkretnej granicy PRF.

Krok 2: funkcję losową porównujemy ze świeżymi maskami

Zdefiniujmy złe zdarzenie:

Badin={∃i<j: Ri=Rj}.\mathsf{Bad}_{\mathrm{in}}=\{\exists i<j:\ R_i=R_j\}.

Indeks „in” oznacza wejście funkcji. Sprzęgamy gry tak, aby dla nowego argumentu RiR_i świeża maska PiP_i świata G2G_2 była jednocześnie wpisana jako T[Ri]T[R_i] w świecie G1G_1. To prawidłowe losowanie niezależnego wpisu. Dopóki argument jest nowy, szyfrogramy i cała historia przeciwnika są identyczne.

Przy powtórzonym argumencie G1G_1 musi użyć wcześniejszego T[Ri]T[R_i]. Świat G2G_2 nadal losuje nowe PiP_i. Oba światy zachowują swój prawidłowy rozkład, ale mogą się rozejść. Nawet wtedy nowe PiP_i może przypadkiem równać się starej masce. Zdarzenie złe jest warunkiem koniecznym możliwej różnicy w tym sprzężeniu, nie gwarancją różnicy w każdej realizacji.

Funkcja losowa i OTP · zachowany kontekst sześciu wywołań
Widok
Sprzężenie masek bez kolizji wejśćDwa światy korzystają z tych samych niezależnych masek dla nowych argumentów. Powtórzony argument wymusza odczyt starej maski tylko po lewej stronie.Publiczny argumentG₁ · funkcja z pamięciąG₂ · nowa maskaNowy argument: wspólna maska. Powtórzenie: możliwa różnica.
iRiR_iMiM_iPiP_if(Ri)f(R_i)Ci(1)C_i^{(1)}Ci(2)C_i^{(2)}
1001110010ukryte101100ukryte101100ukryte011110011110
2100001101ukryte000011ukryte000011ukryte001110001110
3011111000ukryte010101ukryte010101ukryte101101101101
4000000111ukryte010101ukryte010101ukryte010010010010
5001010101ukryte111001ukryte101100ukryte111001101100
6101101010ukryte110010ukryte110010ukryte011000011000
Pełna tablica przykładu. Krok rozpoczyna pierwsze wywołanie.

Porównujemy dwa osobne eksperymenty. Przeciwnik z jednego uruchomienia widzi tylko jedną kolumnę szyfrogramów. Ukrycie wiadomości dotyczy wybranej Mᵢ. Przeciwnik zna własne pary kandydatów.

Jak czytać sześć wierszy porównania

Wiersze 3 i 4 używają różnych argumentów, ale tej samej sześciobitowej wartości maski. Nie ma problemu: dwie niezależne maski OTP też mogą być równe. Oba światy wciąż dają ten sam widok.

W wierszu 5 wraca R=001R=001. Funkcja losowa odczytuje wcześniejsze 101100101100, natomiast nowa maska OTP wynosi 111001111001. Dla wiadomości 010101010101 powstają odpowiednio szyfrogramy 111001111001 i 101100101100. Tu widoki mogą się różnić.

Wiersz 6 przedstawia dalszy krok ustalonej z góry sekwencji przykładowej. Nie oznacza, że całe historie znów są identyczne. W prawdziwym adaptacyjnym ataku kolejne pytania po rozbieżności mogą już być różne. Dowód potrzebuje zgodności tylko do pierwszego złego zdarzenia.

Z lematu o grach identycznych do złego zdarzenia otrzymujemy:

∣α1−α2∣≤Pr⁡[Badin].|\alpha_1-\alpha_2|\le\Pr[\mathsf{Bad}_{\mathrm{in}}].

To zastosowanie metody opisanej przez Victora Shoupa w Sequences of Games, §1.1. Następna część wykładu omawia tę metodę i sam lemat osobno.

Dwa poprawne warianty dowodu. Tutaj przechodzimy bezpośrednio od funkcji losowej do świeżych masek, zachowując losowanie argumentów z powtórzeniami. W następnym rozdziale wstawimy dodatkową grę, która najpierw usuwa powtórzenia argumentów, a dopiero potem zastępuje funkcję świeżymi maskami. Tam oznaczenia G0,G1,G2,G3G_0,G_1,G_2,G_3 należą do nowego, czterogrowego porównania. W szczególności tamtego G2G_2 nie należy utożsamiać z tutejszym G2G_2. W obu dowodach trzeba opłacić tę samą możliwość kolizji argumentów.

Krok 3: w świecie świeżych masek bit jest ukryty

Warunkujemy po dowolnej dotychczasowej historii. Przeciwnik może na jej podstawie dobrać następną parę wiadomości, ale nowa maska PiP_i pozostaje jednostajna i niezależna. XOR z dowolnym z dwóch wybranych ciągów daje jednostajny szyfrogram. Publiczne RiR_i również jest niezależne od bb.

Indukcyjnie cały widok, łącznie z adaptacyjnie wybranymi kolejnymi pytaniami, ma taki sam rozkład dla b=0b=0 i b=1b=1. Zatem α2=1/2\alpha_2=1/2. Z nierówności trójkąta:

Adv⁡enc(A)=∣α0−12∣≤∣α0−α1∣+∣α1−α2∣+∣α2−12∣≤Adv⁡Fprf(B)+Pr⁡[Badin].\begin{aligned} \operatorname{Adv}^{\mathrm{enc}}(\mathcal A) &=|\alpha_0-\tfrac12|\\ &\le|\alpha_0-\alpha_1|+|\alpha_1-\alpha_2|+|\alpha_2-\tfrac12|\\ &\le\operatorname{Adv}^{\mathrm{prf}}_F(B)+\Pr[\mathsf{Bad}_{\mathrm{in}}]. \end{aligned}

Które kolizje liczymy i od jakiej długości zależą

Dla dokładnie qq niezależnych, jednostajnych argumentów z {0,1}r\{0,1\}^r prawdopodobieństwo braku kolizji wynosi:

Pr⁡[¬Badin]=∏j=0q−1(1−j2r)(q≤2r).\Pr[\neg\mathsf{Bad}_{\mathrm{in}}]=\prod_{j=0}^{q-1}\left(1-\frac{j}{2^r}\right)\qquad(q\le2^r).

Pierwszy argument może być dowolny. Drugi musi ominąć jedną wartość. Trzeci musi ominąć dwie. Stąd kolejne czynniki. Odejmując od jedności i stosując sumowanie prawdopodobieństw po parach, dostajemy:

Pr⁡[Ri=Rj]=2−r,Pr⁡[Badin]≤∑1≤i<j≤qPr⁡[Ri=Rj]=(q2)⋅2−r.\Pr[R_i=R_j]=2^{-r},\qquad \Pr[\mathsf{Bad}_{\mathrm{in}}]\le\sum_{1\le i<j\le q}\Pr[R_i=R_j] =\binom q2\cdot2^{-r}.

Par jest (q2)=q⋅(q−1)/2\binom q2=q\cdot(q-1)/2. Ich zdarzenia nie muszą być niezależne. Nierówność sumy działa także wtedy, gdy kilka par zderzy się w jednym przebiegu. Dlatego:

Pr⁡[Badin]=1−∏j=0q−1(1−j2r)≤min⁡(1,q⋅(q−1)2r+1).\Pr[\mathsf{Bad}_{\mathrm{in}}]=1-\prod_{j=0}^{q-1}\left(1-\frac{j}{2^r}\right) \le\min\left(1,\frac{q\cdot(q-1)}{2^{r+1}}\right).

Gdy q>2rq>2^r, kolizja jest pewna. Gdy przeciwnik może zakończyć przed limitem qq, wyrażenie dla qq jest górną granicą, niekoniecznie dokładnym prawdopodobieństwem jego przebiegu. Możemy dopełnić niewykorzystane losowania do ustalonego limitu na potrzeby tego oszacowania.

Po podstawieniu do oszacowania bezpieczeństwa otrzymujemy pełną granicę:

Adv⁡enc(A)≤Adv⁡Fprf(B)+q⋅(q−1)2r+1.\operatorname{Adv}^{\mathrm{enc}}(\mathcal A) \le\operatorname{Adv}^{\mathrm{prf}}_F(B)+\frac{q\cdot(q-1)}{2^{r+1}}.

To granica wystarczająca, nie twierdzenie o jej optymalności. Aby uzyskać znikomość całej prawej strony w analizie asymptotycznej, oprócz bezpiecznej PRF wymagamy znikomości (q(λ)2)⋅2−r(λ)\binom{q(\lambda)}2\cdot2^{-r(\lambda)}. Stały, zbyt krótki argument nie spełni tego wymagania przy rosnącej liczbie szyfrowań.

Kolizje argumentów · wynik i granica
Długość argumentu r

Dokładne prawdopodobieństwo
0,58984375

Górna granica
0,75

151/256. Granica: 3/4. Założenie PRF nie jest mierzone tym kalkulatorem.

Przykład mały: dla r=3r=3 i q=4q=4 dokładny wynik to 151/256151/256, czyli około 58,98%58{,}98\%. Oszacowanie sumą po parach daje 6/8=3/46/8=3/4, czyli 75%75\%. Granica może być luźna i nie jest równością.

1−88⋅78⋅68⋅58=151256.1-\frac88\cdot\frac78\cdot\frac68\cdot\frac58=\frac{151}{256}.

Przykład dużych parametrów: przy q=232q=2^{32} i r=96r=96 granica jest mniejsza niż 2−332^{-33}. Przy tej samej liczbie szyfrowań i r=128r=128 jest mniejsza niż 2−652^{-65}. W mianowniku występuje długość argumentu rr, a nie długość maski ℓ\ell ani długość klucza κ\kappa. Wydłużenie samej maski nie zmniejsza ryzyka powtórzenia RR.

Równe wyjścia nie są tym samym złym zdarzeniem

Dla dwóch ustalonych, różnych argumentów x≠yx\ne y funkcji losowej mamy, dla dowolnych wartości a,b∈{0,1}ℓa,b\in\{0,1\}^{\ell}:

Pr⁡[f(x)=a,f(y)=b]=2−2ℓ.\Pr[f(x)=a,f(y)=b]=2^{-2\ell}.

Obejmuje to także przypadek a=ba=b. Prawdopodobieństwo równości dwóch odpowiedzi wynosi 2−ℓ2^{-\ell}. Tak samo zachowują się dwa niezależne klucze OTP. Po XOR z ustalonymi wiadomościami para szyfrogramów nadal jest jednostajna na całym zbiorze par.

Dla ustalonych wiadomości m1,m2m_1,m_2 oraz dowolnych części szyfrogramów c,dc,d możemy zobaczyć to bezpośrednio:

Pr⁡[C1=c,C2=d∣M1=m1,M2=m2]=Pr⁡[f(x)=c⊕m1,f(y)=d⊕m2]=2−2ℓ.\begin{aligned} \Pr[C_1=c,C_2=d\mid M_1=m_1,M_2=m_2] &=\Pr[f(x)=c\oplus m_1,f(y)=d\oplus m_2]\\ &=2^{-2\ell}. \end{aligned}

Wynik nie zależy od m1,m2m_1,m_2. Jednorazowość oznacza tutaj, że nie używamy ponownie tej samej próbki maski. Nie oznacza, że każda niezależnie wylosowana próbka ma obowiązek różnić się od wszystkich wcześniejszych.

Jeszcze prostszy przykład: wylosujmy trzy niezależne jednobitowe maski. Co najmniej dwie muszą być równe, bo istnieją tylko dwie wartości bitu. Mimo tego cały wektor trzech masek jest jednostajny na ośmiu możliwościach, więc trzy jednobitowe szyfrogramy doskonale ukrywają trzy bity wiadomości. Sam fakt, że gdzieś musiała wystąpić równość, nie łamie OTP.

Ważne zastrzeżenie: nie przekazujemy przeciwnikowi dodatkowej informacji wskazującej, które tajne maski są równe. Taki interfejs mógłby ujawnić relacje między wiadomościami. Nasza demonstracja pokazuje te równości czytelnikowi jako autorowi analizy, nie jako dodatkową wyrocznię dostępną atakującemu.

Przy powtórzeniu publicznego RR sytuacja jest inna. Przeciwnik widzi równość argumentów i z deterministyczności wie, że maska została ponownie użyta. Może wtedy wiarygodnie zastosować zależność XOR. Dlatego w tej redukcji złym zdarzeniem jest kolizja wejść.

Niepowtarzalny nonce i dłuższe wiadomości

Nonce to wartość, która w danym zastosowaniu nie powinna się powtarzać pod tym samym kluczem. Publiczny licznik może zapewnić unikalność bez losowania. Jeśli wszystkie argumenty są różne, Pr⁡[Badin]=0\Pr[\mathsf{Bad}_{\mathrm{in}}]=0, a granica pozostaje równa przewadze PRF. Jest to bezpieczeństwo przy przestrzeganiu niepowtarzalności nonce, a nie odporność na dowolne ponowne użycie.

Trzeba określić, kto przydziela argumenty, jak zachowuje stan po restarcie i co dzieje się po wyczerpaniu zakresu. Dwa urządzenia lub dwa kierunki komunikacji nie mogą przypadkiem użyć tej samej pary klucz–argument. Pomagają osobne klucze albo jednoznacznie rozdzielone przestrzenie argumentów.

Rozwinięcie maski blok po bloku

Jeśli jedna odpowiedź ma ww bitów, dłuższą wiadomość dzielimy na bloki. Wprowadzamy osobną, poprawnie typowaną rodzinę:

Fblk:{0,1}κ×{0,1}r+t⟶{0,1}w.F^{\mathrm{blk}}:\{0,1\}^{\kappa}\times\{0,1\}^{r+t}\longrightarrow\{0,1\}^{w}.

Argument składa się z rr-bitowego nonce i tt-bitowego kodowania numeru bloku. Dla 0≤j<2t0\le j<2^t:

Pj=FKblk(R∥⟨j⟩t),Cj=Mj⊕Pj.P_j=F^{\mathrm{blk}}_K(R\mathbin\|\langle j\rangle_t),\qquad C_j=M_j\oplus P_j.

Ostatni niepełny blok używa tylko potrzebnego prefiksu maski. Zapis ∥\| oznacza konkatenację. Stałe długości pól gwarantują jednoznaczność kodowania. Licznik bloku nie może się zawinąć. Nie wolno bez wyjaśnienia podać r+tr+t bitów do funkcji zdefiniowanej wcześniej dla rr bitów.

Rozróżniacz PRF ma teraz budżet QQ, czyli łączną liczbę bloków, a nie liczbę wiadomości. Jeżeli każda wiadomość losuje własny rr-bitowy nonce, oszacowanie powtórzeń nonce nadal liczy qq wiadomości. Osobno pilnujemy poprawnego numerowania bloków w każdej z nich.

Gdzie pojawia się PRP i dlaczego nie wolno mieszać kolizji

PRP
pseudorandom permutation. Permutacja pseudolosowa.

PRP oznacza pseudorandom permutation, czyli permutację pseudolosową. Szyfr blokowy taki jak AES jest dla ustalonego klucza permutacją bloków, nie dowolną funkcją. Dla różnych wejść nie ma równych wyjść. Funkcja losowa może je mieć.

Przy przejściu od losowej permutacji na nn bitach do losowej funkcji na nn bitach, dla obserwatora z najwyżej QQ zapytaniami w przód, standardowa granica przełączania wynosi:

Adv⁡switch≤min⁡(1,Q⋅(Q−1)2n+1).\operatorname{Adv}^{\mathrm{switch}}\le\min\left(1,\frac{Q\cdot(Q-1)}{2^{n+1}}\right).

Powtórzone pytanie w obu światach odczytuje starą odpowiedź. Tutaj porównanie może się rozejść, gdy funkcja losowa dla nowego wejścia wylosuje już użyte wyjście, czego permutacja nie robi. To inny krok dowodu niż powtórzenie nonce. Nie udowodniliśmy w ten sposób bezpieczeństwa samego AES. Wykorzystanie go wymaga założenia o jego pseudolosowości i poprawnej konstrukcji trybu pracy. W4: szyfr blokowy i PRP rozwija ten temat.

Przejście Uzasadnienie Co trzeba kontrolować
G(S)G(S) → jednostajny ciąg założenie PRG tajny, jednostajny zarodek i jednorazowe użycie maski
FKF_K → ff założenie PRF cały adaptacyjny interfejs i jego budżet
f(Ri)f(R_i) → niezależne PiP_i identyczność do Badin\mathsf{Bad}_{\mathrm{in}} powtórzenia argumentów długości rr
losowa permutacja → losowa funkcja lemat przełączania PRP/PRF kolizje wyjść długości nn w tym osobnym porównaniu

Co zostało założone, a czego nie otrzymaliśmy

  • GG i FF są publicznymi, deterministycznymi algorytmami wielomianowymi. Tajne, jednostajne wejście kluczujące jest niezależne od początkowej losowości przeciwnika.
  • PRG spełnia definicję nierozróżnialności wyjścia. Dla jednorazowego szyfru nie powtarzamy maski. Mały przykład tabelaryczny nie spełnia wymagań parametrów bezpieczeństwa.
  • PRF spełnia definicję nierozróżnialności interfejsu dla adaptacyjnych zapytań, w tym zapytań powtórzonych. Nie wystarcza równomierność pojedynczej odpowiedzi.
  • W modelu losowych nonce każde RiR_i jest jednostajne i niezależne od klucza oraz historii. W modelu unikalnych nonce obowiązuje jawny warunek niepowtarzalności. Nie mieszamy tych modeli w jednym rachunku.
  • Pary wiadomości mają jednakową długość. Konstrukcja ujawnia długość i publiczny argument. Nie obiecuje ich ukrycia.
  • Przeciwnik szyfrowania otrzymuje tylko wskazany interfejs. Nie dostaje tajnej maski ani wyroczni, która pozwala ją odczytać dla szyfrogramu wyzwania.
  • Nie zakładamy różnowartościowości generatora lub PRF ani odporności PRF na kolizje w sensie funkcji skrótu.
  • Granice obowiązują dla podanych czasów i liczby zapytań. W naszym zapisie przewaga szyfrowania jest odchyleniem od 1/21/2, bez dodatkowego mnożnika 22.

Poufność to nie integralność. Przy XOR przeciwnik może zmienić CC na C′=C⊕δC'=C\oplus\delta. Odbiorca otrzyma wtedy M′=M⊕δM'=M\oplus\delta. Nie musi to ujawnić MM, ale pozwala go zmodyfikować. Dlatego praktyczne rozwiązania łączą szyfrowanie z uwierzytelnianiem, np. ChaCha20-Poly1305. AEAD rozwijamy jako authenticated encryption with associated data, czyli szyfrowanie uwierzytelnione z danymi dodatkowymi. RFC 8439 opisuje konkretną konstrukcję, jej licznik, nonce i wymagania ich użycia. Sama nazwa „losowy” albo „pseudolosowy” nie zapewnia tych własności.

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

Ćwiczenie do samodzielnego sprawdzenia: odtwórz XOR w każdym wierszu sześciowierszowej tabeli. Wskaż pierwszą kolizję wejść i pierwszą kolizję wyjść dla różnych wejść. Następnie ukryj kolumny masek i wyjaśnij, co przeciwnik może nadal rozpoznać na podstawie publicznych argumentów. Na końcu uzasadnij, dlaczego w granicy nonce pojawia się rr, a nie ℓ\ell.

Powiązania: C1: tajność doskonała, C3: pseudolosowość i redukcje, L2: skutki ponownego użycia losowości, metoda gier, pełniejsza ścieżka dowodów symetrycznych.

Literatura: Bellare i Rogaway, Introduction to Modern Cryptography, rozdziały o PRF i szyfrowaniu symetrycznym, Shoup, Sequences of Games, Rogaway, Nonce-Based Symmetric Encryption.

Dwa narzędzia do dalszych dowodów

Hybryda jest pośrednią wersją eksperymentu. Jeśli każdy sąsiedni krok zmienia szansę sukcesu najwyżej o określoną wartość, całkowitą zmianę ograniczamy sumą tych wartości. To nierówność trójkąta, a nie nowe założenie o szyfrze. Pełny zapis podaje pogłębienie A.

Sprzężenie losowań (coupling) pozwala porównać dwa eksperymenty we wspólnym doświadczeniu. Każdy z osobna musi zachować swój prawidłowy rozkład. Przykład: jeden eksperyment losuje identyfikatory z powtórzeniami, drugi bez powtórzeń. Korzystają z tej samej propozycji losowej, dopóki jest nowa. Gdy propozycja się powtórzy, pierwszy ją zachowuje, a drugi losuje jednostajnie spośród nieużytych. Każdy ma właściwy rozkład, a historie są identyczne do pierwszego powtórzenia.

W tym wspólnym doświadczeniu różnica wyników wymaga kolizji, więc jej prawdopodobieństwo ogranicza różnicę szans sukcesu. To narzędzie analizy, nie dodatkowy interfejs przeciwnika ani wiedza symulatora. Takiego porównania użyjemy później przy FDH i UC. Metoda gier Shoupa, oryginał. Pełne wyjaśnienie po polsku z animacją i rachunkiem.

FDH
Full Domain Hash. Haszowanie o pełnej dziedzinie wyników.
UC
Universal Composability. Uniwersalna kompozycyjność, czyli formalna analiza bezpieczeństwa przy składaniu protokołów.

Pytanie kontrolne: test częstości bitów bada jedną własność rozkładu. Dlaczego nie wyklucza algorytmu odzyskującego stan generatora?

Powiązania: C1: tajność doskonała, C3: generatory i redukcje, L2: ataki na losowość.

W3a. Metoda gier: kompletny dowód krok po kroku

Cel: przejść od zdania „ten atak nie powinien działać” do twierdzenia, w którym wiadomo, od czego zależy szansa jego powodzenia. Potrzebne są eksperymenty z rozdziału o modelach, funkcja pseudolosowa z W2 i jednorazowa maska z W3. Nie potrzebujemy jeszcze grup ani krzywych eliptycznych.

Punktem odniesienia jest Victor Shoup, Sequences of Games: A Tool for Taming Complexity in Security Proofs, §1.1. Tytuł można oddać jako „Ciągi gier: narzędzie porządkowania złożonych dowodów bezpieczeństwa”. Chodzi o złożoność rozumowania, nie o pomiar czasu działania. Poniżej rozwijamy własny przykład szyfrowania z W3, z pełnym rachunkiem i obliczeniami do prześledzenia.

1. Gra nie jest pojedynczym przebiegiem

Gra jest opisem całego doświadczenia losowego. Określa losowanie klucza, interfejs przeciwnika, odpowiedzi na pytania i warunek wygranej. Jeden uruchomiony przykład jest tylko jednym możliwym wynikiem tego doświadczenia. Prawdopodobieństwo liczymy po wszystkich losowaniach, w tym po losowości przeciwnika.

Ustalmy jednego przeciwnika A\mathcal A. Numer ii oznacza wersję eksperymentu GiG_i, a SiS_i zdarzenie jego sukcesu. Zapisujemy pi=Pr⁡[Si]p_i=\Pr[S_i]. W tym rozdziale sukces zawsze oznacza b′=bb'=b, czyli odgadnięcie ukrytego bitu. Zmieniamy obsługę eksperymentu, a nie cel ani program przeciwnika. Jego następne pytania mogą jednak zmienić się po otrzymaniu innych odpowiedzi.

Challenger prowadzi grę zgodnie z jej regułami. Redukcja jest innym programem, który próbuje odtworzyć tę obsługę, korzystając z otrzymanego trudnego zadania. Autor dowodu porównuje rozkłady. Nie wolno przenosić jego wiedzy, np. znajomości obu porównywanych światów, do interfejsu redukcji lub przeciwnika.

2. Każda zmiana musi mieć osobne uzasadnienie

W terminologii Shoupa występują trzy rodzaje przejścia. Bridging step to równoważne przepisanie doświadczenia. Indistinguishability transition korzysta z nierozróżnialności. Failure-event transition ogranicza różnicę przez zdarzenie, poza którym porównanie działa identycznie. Oryginał, §1.1.

Rodzaj kroku Co rzeczywiście musimy wykazać Co wpisujemy do rachunku
Równoważne przepisanie Każdy możliwy widok ma taki sam rozkład, również po adaptacyjnych pytaniach ∣pi−pi+1∣=0\lvert p_i-p_{i+1}\rvert=0
Nierozróżnialność obliczeniowa Redukcja potrafi obsłużyć obie gry i jej przewaga równa się rozważanej różnicy Przewagę konkretnej redukcji, z jej czasem i liczbą zapytań
Zdarzenie rozbieżności W poprawnym wspólnym doświadczeniu gry dają te same wyniki poza Bad\mathrm{Bad} ∣pi−pi+1∣≤Pr⁡[Bad]\lvert p_i-p_{i+1}\rvert\le\Pr[\mathrm{Bad}]

Możliwy jest również bezpośredni argument statystyczny o odległości rozkładów. Nie wymaga on ograniczenia czasu przeciwnika. Założenie obliczeniowe jest czymś innym: dwa rozkłady mogą być różne, lecz nie pozwalać na wydajne odróżnianie.

3. Z czego składa się lemat o różnicy

Sprzężenie to wspólne losowanie dwóch eksperymentów, które zachowuje właściwy rozkład każdego z nich osobno. Nie wymaga ich niezależności. Właśnie zależność pozwala powiedzieć, że w konkretnym wspólnym losowaniu zachowują się tak samo aż do wskazanego zdarzenia.

Niech Bad\mathrm{Bad} będzie zdarzeniem w tej wspólnej przestrzeni. Zakładamy, że poza nim sukces w jednej grze zachodzi dokładnie wtedy, gdy zachodzi w drugiej. Lemat o różnicy Shoupa daje wtedy ograniczenie przez Pr⁡[Bad]\Pr[\mathrm{Bad}]. Difference Lemma, lemat 1.

Odtwórzmy rachunek, aby zrozumieć, dlaczego nie pojawia się dodatkowy czynnik 2. Rozdzielamy sukces na część wewnątrz i poza Bad\mathrm{Bad}:

pi=Pr⁡[Si∩¬Bad]+Pr⁡[Si∩Bad].p_i=\Pr[S_i\cap\neg\mathrm{Bad}]+\Pr[S_i\cap\mathrm{Bad}].

Pierwsza część jest taka sama w obu grach i znika przy odejmowaniu. Pozostaje:

∣pi−pi+1∣=∣Pr⁡[Si∩Bad]−Pr⁡[Si+1∩Bad]∣≤Pr⁡[Bad].|p_i-p_{i+1}|=|\Pr[S_i\cap\mathrm{Bad}]-\Pr[S_{i+1}\cap\mathrm{Bad}]| \le\Pr[\mathrm{Bad}].

Obie odejmowane liczby należą do przedziału od zera do Pr⁡[Bad]\Pr[\mathrm{Bad}]. Ich odległość nie przekracza długości tego przedziału. Bad nie oznacza jeszcze udanego ataku. Oznacza miejsce, w którym kończy się nasza gwarancja zgodności dwóch światów. Także po nim wyniki mogą przypadkiem pozostać równe.

Nie wystarczy napisać „zakładamy, że Bad nie wystąpi”. Warunkowanie usuwa część przebiegów i może zmienić rozkład. Nie wystarczy też nadać zmiennym w dwóch niezależnych uruchomieniach te same nazwy. Trzeba zbudować ich wspólne losowanie i sprawdzić oba rozkłady.

4. Twierdzenie, które teraz udowodnimy

Rozważamy rodzinę funkcji Fk:{0,1}n→{0,1}ℓF_k:\{0,1\}^n\to\{0,1\}^{\ell}. Klucz kk jest tajny. Wiadomość mm ma dokładnie ℓ\ell bitów, a identyfikator rr ma nn bitów. Każde szyfrowanie losuje go niezależnie i jednostajnie. Reguły są następujące:

r←${0,1}n,c=m⊕Fk(r),Enck(m)=(r,c).r\overset{\$}{\leftarrow}\{0,1\}^n,\qquad c=m\oplus F_k(r),\qquad \mathsf{Enc}_k(m)=(r,c).
Deck(r,c)=c⊕Fk(r)=m.\mathsf{Dec}_k(r,c)=c\oplus F_k(r)=m.

Powtórzenie identyfikatora jest dopuszczone przez algorytm, choć może zaszkodzić bezpieczeństwu. Identyfikator nie jest drugim tajnym kluczem. Jest przesyłany jawnie wraz z szyfrogramem. Poprawność wynika z dwukrotnego XOR tej samej maski. Nie wynika z niej poufność.

Model. Przeciwnik otrzymuje jedno wyzwanie dla wybranych m0,m1m_0,m_1 i może pytać o szyfrowanie przed nim oraz po nim. Wszystkie teksty mają długość ℓ\ell. Nie ma wyroczni deszyfrującej, odczytu klucza ani możliwości ustawiania rr. To eksperyment IND-CPA z jednym wyzwaniem. Łączna liczba szyfrowań, wraz z wyzwaniem, nie przekracza t≤2nt\le 2^n.

Twierdzenie. Dla każdego takiego przeciwnika istnieje redukcja B\mathcal B wykonująca najwyżej tt zapytań do swojej wyroczni, dla której:

∣Pr⁡[S0]−12∣⏟przewaga zgadywania≤Adv⁡Bprf⏟odroˊz˙nienie funkcji+t⋅(t−1)2n+1⏟koszt moz˙liwych powtoˊrzenˊ.\underbrace{\left|\Pr[S_0]-\frac12\right|}_{\text{przewaga zgadywania}} \le \underbrace{\operatorname{Adv}^{\mathrm{prf}}_{\mathcal B}}_{\text{odróżnienie funkcji}} +\underbrace{\frac{t\cdot(t-1)}{2^{n+1}}}_{\text{koszt możliwych powtórzeń}}.

Jest to konserwatywna granica, nie równość opisująca najlepszy atak. Teraz uzasadnimy każdy jej składnik. Pełny łańcuch pozostaje widoczny na rysunku.

Trzy strzałki, trzy różne uzasadnienia
Łańcuch czterech gierG0 do G1: redukcja do PRF. G1 do G2: pierwsza kolizja identyfikatorów. G2 do G3: równość rozkładów, koszt zero.Rzeczywista funkcja
G0: Fk(r)G_0:\ F_k(r)
r z powtórzeniamiPRFLosowa funkcja
G1: R(r)G_1:\ R(r)
r z powtórzeniamiBadBez powtórzeń
G2: R(r)G_2:\ R(r)
r bez powtórzeń0Niezależne maski
G3: z←${0,1}ℓG_3:\ z\overset{\$}{\leftarrow}\{0,1\}^\ell
r bez powtórzeń

We wszystkich grach sukces oznacza odgadnięcie tego samego rodzaju ukrytego bitu. Ostatnia gra ma szansę sukcesu 1/21/2.

5. Pierwsza strzałka: redukcja zastępuje funkcję

W G0G_0 działa rzeczywiste FkF_k. W G1G_1 używamy jednej losowej funkcji RR o tej samej dziedzinie i zbiorze wyników. Dla nowego argumentu losujemy jej wartość. Dla powtórzonego zwracamy wartość zapamiętaną. To nie jest nowa maska przy każdym pytaniu.

Redukcja B\mathcal B dostaje wyrocznię OO. Nie wie, czy jest to FkF_k dla losowego klucza, czy RR. Nie dostaje klucza, kodu wybranej funkcji ani jej całej tabeli. Otrzymuje tylko odpowiedzi na własne pytania.

Redukcja odpowiada na pytania bez znajomości klucza
Interfejs redukcji PRFPrzeciwnik pyta redukcję o szyfrowanie. Redukcja losuje identyfikator, pyta własną wyrocznię i dodaje uzyskaną maskę do wiadomości przez XOR. Klucz nie jest przekazywany redukcji.Przeciwnik Awybiera wiadomościRedukcja B
(r,m⊕O(r))(r,m\oplus O(r))
losuje r oraz bit bzwraca 1, gdy b′ = bWyrocznia O
FkalboRF_k\quad\text{albo}\quad R
m lub para(r, c)r
O(r)O(r)

Strzałki pokazują interfejsy. Przeciwnik nie ma bezpośredniego dostępu do OO. Redukcja zna bit bb, ponieważ sama przygotowuje wyzwanie.

  1. Uruchamia A\mathcal A i samodzielnie obsługuje jego pytania o szyfrowanie. Losuje rr, pyta o O(r)O(r) i oddaje (r,m⊕O(r))(r,m\oplus O(r)).
  2. Po otrzymaniu m0,m1m_0,m_1 losuje ukryty bit bb i tak samo szyfruje mbm_b. Obsługuje również dalsze pytania.
  3. Odbiera b′b' i zwraca 1 dokładnie wtedy, gdy b′=bb'=b. Potrafi to sprawdzić, bo to ona wylosowała bb.

Gdy O=FkO=F_k, widok jest dokładnie widokiem G0G_0. Gdy O=RO=R, widok jest dokładnie widokiem G1G_1. W obu przypadkach obejmuje również adaptacyjnie wybrane pytania. Dlatego, w konwencji różnicy prawdopodobieństw:

Adv⁡Bprf=∣Pr⁡[BFk=1]−Pr⁡[BR=1]∣=∣p0−p1∣.\operatorname{Adv}^{\mathrm{prf}}_{\mathcal B} =|\Pr[\mathcal B^{F_k}=1]-\Pr[\mathcal B^R=1]| =|p_0-p_1|.

Nie zgadujemy pozycji wyzwania. Redukcja zastępuje cały interfejs funkcji i obsługuje wszystkie szyfrowania. Nie ma więc dodatkowego mnożenia przewagi PRF przez tt. Jej czas to czas A\mathcal A oraz obsługa najwyżej tt szyfrowań i komunikatów. Gdy operację wyroczni liczymy jako jedno zapytanie, narzut bitowy poza nią wynosi O(t⋅(n+ℓ))O(t\cdot(n+\ell)). W rzeczywistym pomiarze trzeba doliczyć koszt wykonania samej funkcji.

6. Druga strzałka: porównujemy losowania identyfikatorów

W G1G_1 identyfikatory losujemy z powtórzeniami. W G2G_2 wybieramy je jednostajnie spośród dotąd nieużytych. To inny algorytm obsługi gry, a nie przemilczany warunek narzucony na G1G_1.

Zbudujmy sprzężenie. W obu światach wykorzystujemy te same losowe bity przeciwnika i ten sam ukryty bit. Przed pierwszą rozbieżnością wybory wiadomości są więc takie same. Niech UU oznacza zbiór identyfikatorów użytych w G2G_2, a N=2nN=2^n.

  1. Losujemy wspólną propozycję rr jednostajnie z NN możliwości. Gra G1G_1 zawsze ją przyjmuje.
  2. Jeżeli r∉Ur\notin U, gra G2G_2 również ją przyjmuje. W przeciwnym razie losuje zamiennik jednostajnie z N−∣U∣N-|U| wolnych identyfikatorów.
  3. Przed pierwszą rozbieżnością wspólny nowy identyfikator dostaje wspólną świeżą maskę. Po rozbieżności każda gra nadal przestrzega własnej tabeli i rozkładu. Pytania przeciwnika nie muszą już być jednakowe.

Dlaczego drugi świat naprawdę losuje jednostajnie bez powtórzeń? Jeśli wykorzystano jj identyfikatorów, każdy ustalony wolny identyfikator vv zostanie przyjęty bezpośrednio z prawdopodobieństwem 1/N1/N. Może też zostać zamiennikiem po trafieniu jednej z jj zajętych pozycji. Łącznie:

Pr⁡[rG2=v]=1N+jN⋅1N−j=1N−j.\Pr[r_{G_2}=v]=\frac1N+\frac jN\cdot\frac1{N-j}=\frac1{N-j}.

Zatem obie strony zachowują wymagane rozkłady. Poza zdarzeniem pierwszego powtórzenia propozycji historie i wyniki są identyczne. To jest hipoteza lematu o różnicy, a nie tylko podobieństwo rysunków.

Poniżej ii jest numerem szyfrowania, rr przyjętym identyfikatorem, mm wiadomością, zz maską, a c=m⊕zc=m\oplus z częścią szyfrogramu. Wiersze są historią szyfrowań, nie osobnymi wpisami funkcji. Jeśli w G1G_1 identyfikator wraca, odczytujemy istniejący wpis R(r)R(r).

Dwa światy i pierwsza rozbieżność
Wybrany przebieg
Sprzężone losowania i tabeleG1 zachowuje powtórzony identyfikator i jego starą maskę. G2 zastępuje zajęty identyfikator wolnym i używa nowej maski. Wybór 2, 5, 2, 7 rozdziela światy przy trzecim szyfrowaniu.Wspólna propozycja
ri∈{0,…,7}r_i\in\{0,\ldots,7\}
G₁ · zachowaj rR: wpis istnieje?tak: stara maskanie: nowa maskaG₂ · wybierz rU: już użyty?tak: zamiennikzapisz nową maskę

G1G_1 · z powtórzeniami

iirrmmzzcc
1––––
2––––
3––––
4––––

G2G_2 · bez powtórzeń

iirrmmzzcc
1––––
2––––
3––––
4––––

W trzecim szyfrowaniu propozycja 2 powtarza pierwszy identyfikator. Lewa tabela używa maski 9 ponownie. Prawa używa identyfikatora 3 i maski 10.

W demonstracji porównujemy cztery zwykłe szyfrowania wybranych wiadomości. Małe wartości to czterobitowe bloki, a identyfikatory należą do zbioru od 0 do 7. Jest to jawnie dobrany zapis możliwego przebiegu, nie losowanie bezpiecznego klucza. Tabele pokazujemy studentowi, nie przeciwnikowi. Przykład ilustruje sprzężenie i ponowne użycie maski, a nie mierzy przewagi PRF.

7. Skąd bierze się granica urodzinowa

W G1G_1 mamy niezależne propozycje r1,…,rtr_1,\ldots,r_t z NN wartości. Przy wcześniejszym zakończeniu eksperymentu możemy dolosować niewykorzystane propozycje tylko na potrzeby analizy. Nie zmieniają widoku przeciwnika i dają górną granicę dla liczby co najwyżej tt szyfrowań.

Dla ustalonej pary i<ji<j szansa ri=rjr_i=r_j wynosi 1/N1/N. Par jest t⋅(t−1)/2t\cdot(t-1)/2. Oszacowanie sumą (union bound) mówi, że prawdopodobieństwo co najmniej jednego zdarzenia nie przekracza sumy ich prawdopodobieństw. Nie wymaga niezależności tych zdarzeń. Tutaj kolizje poszczególnych par nie są rozłączne.

Pr⁡[Bad]≤∑i<jPr⁡[ri=rj]=t⋅(t−1)2⋅N.\Pr[\mathrm{Bad}] \le\sum_{i<j}\Pr[r_i=r_j] =\frac{t\cdot(t-1)}{2\cdot N}.

Dla dokładnie tt propozycji możemy również policzyć wynik bez oszacowania. Pierwsza nie powoduje kolizji. Druga unika jednej zajętej wartości. Trzecia unika dwóch, pod warunkiem że wcześniej kolizji nie było. Stąd:

Pr⁡[Bad]=1−∏j=0t−1(1−jN).\Pr[\mathrm{Bad}] =1-\prod_{j=0}^{t-1}\left(1-\frac jN\right).

Iloczyn wynika z kolejnych prawdopodobieństw warunkowych. Nie zakładamy niezależności zdarzeń „dotąd nie było kolizji”. Dla N=8N=8 i t=4t=4 mamy 1−(8⋅7⋅6⋅5)/84=151/2561-(8\cdot7\cdot6\cdot5)/8^4=151/256. Granica sumą to 6/8=3/46/8=3/4. Większa liczba jest ograniczeniem, nie błędem w dokładnym rachunku.

Dokładne prawdopodobieństwo i jego górna granica
Długość identyfikatora nn w bitach
Dokładne prawdopodobieństwo
0,58984375
Granica sumą, nie więcej niż 1
0,75000000

Dokładny ułamek: 151/256.

Liczymy zdarzenie kolizji w G1G_1. Do końcowej granicy bezpieczeństwa dochodzi jeszcze przewaga redukcji PRF, której ten kalkulator nie mierzy.

8. Ostatnia strzałka: maski stają się niezależne

W G2G_2 nigdy nie pytamy RR o ten sam identyfikator dwa razy. Wartość losowej funkcji na nowym argumencie jest jednostajna i niezależna od wcześniejszych odpowiedzi. Możemy więc usunąć tabelę i przy każdym szyfrowaniu losować nową maskę z∈{0,1}ℓz\in\{0,1\}^{\ell}. Tak otrzymujemy G3G_3. Nadal losujemy identyfikatory bez powtórzeń. Nie zmieniamy dwóch reguł naraz.

To przejście ma koszt zero. Sprawdźmy je także dla adaptacyjnego przeciwnika. Dla każdego możliwego dotychczasowego widoku następne pytanie ma tę samą regułę wyboru po obu stronach. W obu światach odpowiedź używa świeżej maski o tym samym rozkładzie. Indukcja po pytaniach daje identyczny rozkład całego widoku.

W wyzwaniu c=mb⊕zc=m_b\oplus z mamy dla każdego ustalonego mbm_b i każdego cc dokładnie jedną maskę, która daje ten wynik. Zatem cc jest jednostajne. Pozostałe szyfrowania korzystają z innych, niezależnych masek i nie ujawniają bitu. Dotyczy to również pytań po wyzwaniu, wybieranych na podstawie dotychczasowych szyfrogramów. W G3G_3 cały widok jest niezależny od bb, więc p3=1/2p_3=1/2.

9. Składamy dowód i kontrolujemy stałe

Dodajemy i odejmujemy prawdopodobieństwa gier pośrednich, a następnie korzystamy z nierówności trójkąta:

∣p0−12∣≤∣p0−p1∣+∣p1−p2∣+∣p2−p3∣≤Adv⁡Bprf+Pr⁡[Bad]+0.\left|p_0-\frac12\right| \le |p_0-p_1|+|p_1-p_2|+|p_2-p_3| \le\operatorname{Adv}^{\mathrm{prf}}_{\mathcal B}+\Pr[\mathrm{Bad}]+0.

Po wstawieniu granicy z punktu 7 dostajemy twierdzenie. Możemy użyć dokładnego iloczynu zamiast granicy sumą. Wynik wolno dodatkowo ograniczyć przez 1/21/2, ponieważ tyle maksymalnie wynosi przyjęta przewaga zgadywania.

Czynnik 2 zależy od definicji przewagi. Tutaj przewagą jest odległość szansy trafienia od 1/21/2. Jeśli inne źródło definiuje ją jako ∣2⋅Pr⁡[S0]−1∣|2\cdot\Pr[S_0]-1|, trzeba pomnożyć prawą stronę przez 2. Sama zmiana nazw nie zmienia matematyki, ale pominięcie normalizacji zmienia twierdzenie.

Liczba gier też jest parametrem. Dla hh kroków ogólny rachunek daje ∣p0−ph∣≤∑i=0h−1∣pi−pi+1∣|p_0-p_h|\le\sum_{i=0}^{h-1}|p_i-p_{i+1}|. Stała liczba zaniedbywalnych składników daje zaniedbywalną sumę. Przy rosnącym h(λ)h(\lambda) trzeba podać wspólne ograniczenie składników i wzrost liczby kroków. Wielomian razy funkcja zaniedbywalna pozostaje zaniedbywalny. Wykładnicza liczba kroków nie daje tej gwarancji.

Jeżeli zastępujemy wiele osobnych obiektów i redukcja losuje pozycję zastąpienia, strata rzędu hh może być uzasadniona. Nie przenosimy jej automatycznie do naszego przykładu z jedną wyrocznią. Przy losowaniu pozycji analizujemy różnice ze znakami i teleskopowanie, nie średnią wartości bezwzględnych, która może opisywać inny algorytm.

10. Kiedy argument przestaje działać

  • Przeciwnik ustawia identyfikator. Może wymusić powtórzenie i odzyskać maskę z szyfrowania zera. Losowa granica urodzinowa nie opisuje takiego modelu.
  • Pojawia się deszyfrowanie. Konstrukcja nie uwierzytelnia danych. Zmiana cc na c⊕Δc\oplus\Delta zmienia tekst na m⊕Δm\oplus\Delta. Twierdzenie CPA nie obejmuje modelu CCA.
  • Redukcja potrzebuje nieznanego klucza. W naszym dowodzie tego uniknęliśmy przez interfejs O(r)O(r). W innym schemacie odpowiedź „symulujemy” wymaga osobnego algorytmu.
  • Przerwanie znika z rachunku. Jeśli symulator po kolizji przerywa, trzeba zdefiniować wynik takiego przebiegu i ograniczyć jego wpływ. Nie wolno po prostu analizować tylko udanych symulacji.
  • Bad liczymy w wygodniejszej, ale innej grze. Trzeba uzasadnić przeniesienie oszacowania, np. osobną redukcją lub dodatkowym sprzężeniem. W naszym przykładzie liczymy kolizje niezależnych propozycji w G1G_1.
  • Pomiar zastępuje kwantyfikator. Test kilku przeciwników nie daje granicy dla każdego dozwolonego algorytmu. Numeryczny kalkulator sprawdza rachunek prawdopodobieństwa, nie założenie PRF.

11. Jak używać tej metody w dalszej części kursu

Miejsce w kursie Co wraca z tego rozdziału
ElGamal i Cramer–Shoup Redukcja dostaje instancję trudnego problemu i podstawia ją w widok przeciwnika
RSA-FDH Jedna spójna tabela, równość rozkładów odpowiedzi oraz jawne rozliczenie zgadywania i przerwania
Encrypt-then-MAC Zdarzenie nowej akceptacji pozwala zastąpić część obsługi deszyfrowania
Rewinding i forking Gry organizują analizę, ale samo cofanie i ekstrakcja wymagają własnego argumentu
Dowody AKE Kolejne zmiany muszą zachować reguły sesji i dopuszczalne ujawnienia
Uniwersalna kompozycyjność Samo porównanie dwóch światów nie wystarcza bez właściwych interfejsów i kwantyfikatorów
RSA-FDH
Rivest–Shamir–Adleman with Full Domain Hash. Podpis RSA z haszowaniem do pełnej dziedziny wyników.

Ćwiczenie z rozwiązaniem. Dla trzech szyfrowań z czterech identyfikatorów policz kolizję i granicę sumą. Czy ich równość jest wymagana? Następnie wskaż koszt każdej z trzech strzałek naszego dowodu.

Rozwiązanie i kontrola rozumowania

Brak kolizji ma prawdopodobieństwo (4⋅3⋅2)/43=3/8(4\cdot3\cdot2)/4^3=3/8. Kolizja ma więc prawdopodobieństwo 5/85/8, a granica sumą wynosi 3/43/4. Nie muszą być równe, bo przy trzech jednakowych identyfikatorach zliczamy kilka kolidujących par. Pierwsza strzałka kosztuje przewagę redukcji PRF, druga najwyżej 5/85/8, a trzecia zero. Dla tak małych parametrów nawet ta dokładna granica kolizji nie daje nietrywialnego ograniczenia przewagi zgadywania poniżej 1/21/2. Jest to informacja o słabości tego oszacowania dla wybranych parametrów, nie pomiar najlepszego ataku.

Dalszy rachunek: C3, redukcje i suma strat oraz L2, ponowne użycie losowości. W źródle: Shoup, pełny tekst. Dodatkowe tło do eksperymentów i szyfrowania z funkcją pseudolosową: Boneh–Shoup, A Graduate Course in Applied Cryptography, rozdziały 2, 4 i 5.