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
Ten sam tajny klucz dostarczono już obu stronom.
Sprawdź długość. Nie używaj k dla drugiej wiadomości.
Odrzuć błędną długość szyfrogramu.
Szyfr z kluczem jednorazowym
Nadawca:
Odbiorca:
- Nadawca, Enc:
- Nadawca → Odbiorca: Przekazywany jest tylko szyfrogram
- Odbiorca, Dec:
Jak działa jednorazowa maska
Setup ustala długość . Wiadomość, klucz i szyfrogram mają po 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 .
Poprawność: . 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 oznacza losową wiadomość, a odpowiadający jej szyfrogram. Małe litery są ich konkretnymi wartościami. W tajności doskonałej obserwacja szyfrogramu nie zmienia rozkładu wiadomości:
dla każdego o dodatnim prawdopodobieństwie. W one-time pad wiadomość i klucz mają długość , klucz jest jednostajny, niezależny od wiadomości i użyty raz. Szyfrowanie to . Dla ustalonych dokładnie jeden klucz daje ten szyfrogram. Stąd niezależnie od . Również , bo uśredniamy tę samą wartość po wszystkich wiadomościach. Podstawiamy do wzoru Bayesa, który zamienia kierunek warunkowania:
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:
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.
Lokalny rachunek na bajtach. Dwa wejścia szesnastkowe muszą mieć tę samą długość.
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.
oznacza wersję wyjściową. 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 . 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.
Redukcja jest algorytmem wykorzystującym atak
Przyjmujemy hipotetyczny skuteczny atak na konstrukcję. Budujemy program , który dostaje trudne zadanie, uruchamia , 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ść 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 | Wysyłany szyfrogram | Długość szyfrogramu |
|---|---|---|---|---|
| OTP | świeży | |||
| PRG | tajny | |||
| PRF | tajny |
W ostatnim wierszu jest publicznym argumentem długości . Będziemy go losować niezależnie dla każdego szyfrowania albo zapewniać jego niepowtarzalność. Długość klucza , długość argumentu i długość maski pełnią różne role. Publiczny 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ść / maska | 00 | 01 | 10 | 11 |
|---|---|---|---|---|
00 | 00 | 01 | 10 | 11 |
01 | 01 | 00 | 11 | 10 |
10 | 10 | 11 | 00 | 01 |
11 | 11 | 10 | 01 | 00 |
W każdym wierszu każdy szyfrogram pojawia się dokładnie raz. Dla ustalonej wiadomości i szyfrogramu istnieje dokładnie jedna maska . Jeśli maska jest jednostajna i niezależna od wiadomości, to:
Nie zakładamy, że wiadomości są równie prawdopodobne. Niech będzie dowolnym rozkładem wiadomości. Wówczas:
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 zastępujemy przez .
Co oznacza ukrycie kolumny z kluczem
Pełny zapis doświadczenia zawiera . Przeciwnik otrzymuje tylko . Przejście do jego widoku jest projekcją pełnego stanu, a obliczenie rozkładu widoku wymaga zsumowania prawdopodobieństw po wszystkich ukrytych wartościach:
Symbol ma wartość , gdy warunek zachodzi, i 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 . To jest matematyczny powód tajności.
PRG: sekret wybiera jeden wiersz
Teraz , , a wiadomością jest . Publiczny generator jest określony przez całą poniższą tablicę. Tajny jest tylko wybór .
000 | 011010 | 110110 |
|---|---|---|
001 | 110001 | 011101 |
010 | 001111 | 100011 |
011 | 100100 | 001000 |
100 | 111000 | 010100 |
101 | 010110 | 111010 |
110 | 000101 | 101001 |
111 | 101011 | 000111 |
Prześledźmy jeden wiersz. Zarodek wybiera maskę . Dla naszej wiadomości otrzymujemy:
Odbiorca, znając ten sam zarodek, oblicza . Przeciwnik widzi , ale nie dostaje oznaczenia wybranego wiersza.
Znając , odbiorca odtwarza maskę i oblicza . Formalna składnia tej jednorazowej konstrukcji to:
Parametry są publiczne, a jest kluczem tajnym. Dziedzina wiadomości to . 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 . Ich prawdopodobieństwa wynoszą , a pozostałych masek . Odległość statystyczna od rozkładu jednostajnego wynosi . 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 . Nie ukrywamy przed nim definicji funkcji. Założenie PRG mówi, że przy losowym, ukrytym nie znajdzie efektywnego testu rozpoznającego rozkład z niezaniedbywalną przewagą. Nie mówi, że wszystkie maski są możliwe albo równie prawdopodobne.
Ukrycie kolumny na rysunku samo niczego nie dowodzi. Rozkład widoku nadal jest rozkładem wynikającym z . 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 , , . Wypiszmy całą małą rodzinę. Każda kolumna jest jedną deterministyczną funkcją. Klucz wybieramy raz, a kolejne publiczne argumenty wybierają wiersze tej samej kolumny.
000 | 000110 | 101001 | 011010 | 111100 |
|---|---|---|---|---|
001 | 110011 | 001101 | 101101 | 010010 |
010 | 011101 | 110000 | 000110 | 100011 |
011 | 101000 | 011110 | 111100 | 001011 |
100 | 010111 | 100101 | 010011 | 110110 |
101 | 111010 | 000100 | 101101 | 011000 |
110 | 001001 | 111111 | 110000 | 101010 |
111 | 100100 | 010001 | 001011 | 000101 |
Przy , i otrzymujemy , więc wysyłamy:
Zauważmy, że . 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 ma jedną odpowiedź dla każdego z argumentów. Jej pełną tablicę można wyobrazić sobie jako niezależnych losowań po bitów. Oto jeden możliwy wynik takiego doświadczenia:
000 | 010101 |
|---|---|
001 | 101100 |
010 | 111000 |
011 | 010101 |
100 | 000011 |
101 | 110010 |
110 | 100001 |
111 | 011110 |
Wartości dla i 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 , a liczba funkcji:
Dla , są to bitów i funkcji. Rodzina kluczowana dwubitowym kluczem zawiera najwyżej cztery różne funkcje. Ogólnie klucz o długości może wybrać najwyżej 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ę 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.
Pierwsze pytanie o tworzy wpis. Każde kolejne pytanie o ten sam odczytuje istniejący wpis. Dla nowego argumentu losowanie jest jednostajne z całego , także z wartości już użytych w innych wierszach. Zabronienie powtarzania odpowiedzi dałoby inny obiekt, a nie funkcję losową.
| Pochodzenie |
|---|
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ę i publiczny szyfrogramu wyzwania, zapytałby o i odczytał wiadomość.
Dlaczego wyrocznia świeżych masek jest inna
Procedura przy każdym wywołaniu losuje nowy, niezależny . Jej lista jest indeksowana numerem wywołania . Tablica funkcji losowej jest indeksowana argumentem . Jeśli 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 wybiera pary wiadomości tej samej długości . Challenger, czyli strona prowadząca eksperyment, losuje jeden ukryty bit na cały przebieg. Za każdym razem szyfruje wiadomość . 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 daje szyfrowanie tej samej, znanej przeciwnikowi wiadomości niezależnie od . 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 zapytań. Na końcu zwraca bit . Zakończenie jest momentem zgłoszenia decyzji, nie zakazem wcześniejszego wnioskowania.
W tej konwencji największa przewaga wynosi . Inne źródła czasem mnożą tę definicję przez . Wtedy przez trzeba pomnożyć także odpowiednie prawe strony naszych granic. Nie można przenosić stałych między tymi konwencjami bez sprawdzenia definicji.
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 , klucz, maski i oba światy porównania | ta wszechwiedza nie jest interfejsem przeciwnika |
| Przeciwnik szyfrowania | publiczne parametry, własne monety, wybrane pary, odpowiedzi | klucza, masek, bitu , prywatnej tablicy i etykiety świata |
| Rozróżniacz PRF w redukcji | własny bit , pary zadawane przez , odpowiedzi swojej wyroczni | tego, czy , czy , oraz ukrytego klucza wyroczni |
Przeciwnik zna własne losowe monety . Jego widok po odpowiedziach możemy zapisać jako:
Publiczne parametry oznaczono przez . Wewnętrzne zmienne challengera nie występują w . Przeciwnik może jednak wyciągać z 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 , 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 można ukryć obie maski w tabeli, ale przeciwnik nadal widzi powtórzenie i oblicza . Ukrycie kolumny nie usuwa tej zależności.
Jednorazowe szyfrowanie z PRG: pełna redukcja
Przeciwnik wybiera jedną parę i otrzymuje szyfrogram jednej z nich. W świecie maską jest . W świecie maską jest . Pozostałe reguły nie zmieniają się.
| Gra | Maska | Odpowiedź dla przeciwnika |
|---|---|---|
| dla tajnego losowego | ||
| świeże |
Rozróżniacz otrzymuje ciąg o długości , który jest albo , albo jednostajnym . Uruchamia , odbiera parę wiadomości, sam losuje , przekazuje , odbiera i zwraca dokładnie wtedy, gdy . Nie musi znać zarodka .
Jeśli , obsługa jest dokładnie światem . Jeśli , jest dokładnie światem . W drugim świecie OTP daje szansę sukcesu . Dlatego dla tak skonstruowanego :
Zatem ograniczenie przewagi PRG ogranicza przewagę ataku na szyfr. Narzut redukcji to jedno XOR długości i prosta obsługa gry. Nie ma tu zdarzenia kolizji publicznych argumentów, bo nie ma publicznego ani wielu użyć maski.
Granica tej konstrukcji
Jeżeli użyjemy tego samego do dwóch pełnych wiadomości, otrzymamy:
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 . Każde szyfrowanie losuje własny publiczny argument długości . Klucz jest wspólny dla wszystkich szyfrowań:
Odbiorca nie musi zgadywać , 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 . W każdym świecie przeciwnik ma ten sam interfejs i ten sam limit . Losowania publicznych argumentów są niezależne i jednostajne.
| Świat | Źródło maski w wywołaniu | Co zachowujemy |
|---|---|---|
| jeden klucz na cały przebieg | ||
| jedną funkcję losową i tablicę na cały przebieg | ||
| świeże | nowe niezależne losowanie przy każdym wywołaniu |
W każdym wierszu odpowiedzią jest . Świat jest eksperymentem porównawczym, nie implementacją deszyfrowania z tego samego i . 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 dostaje wyrocznię , która jest albo , albo . Sam losuje i uruchamia . Na pytanie losuje , pyta i odpowiada . Na końcu zwraca wtedy i tylko wtedy, gdy .
Ta obsługa odtwarza dokładnie albo . Powtórzone argumenty nie są przeszkodą. Obie wyrocznie zwracają wtedy wcześniejszy wynik. Dlatego:
Nie mnożymy tej przewagi dodatkowo przez . Założenie PRF już obejmuje cały interfejs z wieloma adaptacyjnymi zapytaniami. Rozróżniacz wykonuje najwyżej zapytań i ma czas , 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:
Indeks „in” oznacza wejście funkcji. Sprzęgamy gry tak, aby dla nowego argumentu świeża maska świata była jednocześnie wpisana jako w świecie . To prawidłowe losowanie niezależnego wpisu. Dopóki argument jest nowy, szyfrogramy i cała historia przeciwnika są identyczne.
Przy powtórzonym argumencie musi użyć wcześniejszego . Świat nadal losuje nowe . Oba światy zachowują swój prawidłowy rozkład, ale mogą się rozejść. Nawet wtedy nowe 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.
| i | ||||||
|---|---|---|---|---|---|---|
| 1 | 001 | 110010ukryte | 101100ukryte | 101100ukryte | 011110 | 011110 |
| 2 | 100 | 001101ukryte | 000011ukryte | 000011ukryte | 001110 | 001110 |
| 3 | 011 | 111000ukryte | 010101ukryte | 010101ukryte | 101101 | 101101 |
| 4 | 000 | 000111ukryte | 010101ukryte | 010101ukryte | 010010 | 010010 |
| 5 | 001 | 010101ukryte | 111001ukryte | 101100ukryte | 111001 | 101100 |
| 6 | 101 | 101010ukryte | 110010ukryte | 110010ukryte | 011000 | 011000 |
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 . Funkcja losowa odczytuje wcześniejsze , natomiast nowa maska OTP wynosi . Dla wiadomości powstają odpowiednio szyfrogramy i . 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:
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 należą do nowego, czterogrowego porównania. W szczególności tamtego nie należy utożsamiać z tutejszym . 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 pozostaje jednostajna i niezależna. XOR z dowolnym z dwóch wybranych ciągów daje jednostajny szyfrogram. Publiczne również jest niezależne od .
Indukcyjnie cały widok, łącznie z adaptacyjnie wybranymi kolejnymi pytaniami, ma taki sam rozkład dla i . Zatem . Z nierówności trójkąta:
Które kolizje liczymy i od jakiej długości zależą
Dla dokładnie niezależnych, jednostajnych argumentów z prawdopodobieństwo braku kolizji wynosi:
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:
Par jest . Ich zdarzenia nie muszą być niezależne. Nierówność sumy działa także wtedy, gdy kilka par zderzy się w jednym przebiegu. Dlatego:
Gdy , kolizja jest pewna. Gdy przeciwnik może zakończyć przed limitem , wyrażenie dla 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ę:
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 . Stały, zbyt krótki argument nie spełni tego wymagania przy rosnącej liczbie szyfrowań.
Dokładne prawdopodobieństwo
Górna granica
151/256. Granica: 3/4. Założenie PRF nie jest mierzone tym kalkulatorem.
Przykład mały: dla i dokładny wynik to , czyli około . Oszacowanie sumą po parach daje , czyli . Granica może być luźna i nie jest równością.
Przykład dużych parametrów: przy i granica jest mniejsza niż . Przy tej samej liczbie szyfrowań i jest mniejsza niż . W mianowniku występuje długość argumentu , a nie długość maski ani długość klucza . Wydłużenie samej maski nie zmniejsza ryzyka powtórzenia .
Równe wyjścia nie są tym samym złym zdarzeniem
Dla dwóch ustalonych, różnych argumentów funkcji losowej mamy, dla dowolnych wartości :
Obejmuje to także przypadek . Prawdopodobieństwo równości dwóch odpowiedzi wynosi . 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 oraz dowolnych części szyfrogramów możemy zobaczyć to bezpośrednio:
Wynik nie zależy od . 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 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, , 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 bitów, dłuższą wiadomość dzielimy na bloki. Wprowadzamy osobną, poprawnie typowaną rodzinę:
Argument składa się z -bitowego nonce i -bitowego kodowania numeru bloku. Dla :
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ć bitów do funkcji zdefiniowanej wcześniej dla bitów.
Rozróżniacz PRF ma teraz budżet , czyli łączną liczbę bloków, a nie liczbę wiadomości. Jeżeli każda wiadomość losuje własny -bitowy nonce, oszacowanie powtórzeń nonce nadal liczy 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 bitach do losowej funkcji na bitach, dla obserwatora z najwyżej zapytaniami w przód, standardowa granica przełączania wynosi:
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ć |
|---|---|---|
| → jednostajny ciąg | założenie PRG | tajny, jednostajny zarodek i jednorazowe użycie maski |
| → | założenie PRF | cały adaptacyjny interfejs i jego budżet |
| → niezależne | identyczność do | powtórzenia argumentów długości |
| losowa permutacja → losowa funkcja | lemat przełączania PRP/PRF | kolizje wyjść długości w tym osobnym porównaniu |
Co zostało założone, a czego nie otrzymaliśmy
- i 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 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 , bez dodatkowego mnożnika .
Poufność to nie integralność. Przy XOR przeciwnik może zmienić na . Odbiorca otrzyma wtedy . Nie musi to ujawnić , 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ę , a nie .
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 . Numer oznacza wersję eksperymentu , a zdarzenie jego sukcesu. Zapisujemy . W tym rozdziale sukces zawsze oznacza , 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 | |
| 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 |
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 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 . Difference Lemma, lemat 1.
Odtwórzmy rachunek, aby zrozumieć, dlaczego nie pojawia się dodatkowy czynnik 2. Rozdzielamy sukces na część wewnątrz i poza :
Pierwsza część jest taka sama w obu grach i znika przy odejmowaniu. Pozostaje:
Obie odejmowane liczby należą do przedziału od zera do . 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 . Klucz jest tajny. Wiadomość ma dokładnie bitów, a identyfikator ma bitów. Każde szyfrowanie losuje go niezależnie i jednostajnie. Reguły są następujące:
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 i może pytać o szyfrowanie przed nim oraz po nim. Wszystkie teksty mają długość . Nie ma wyroczni deszyfrującej, odczytu klucza ani możliwości ustawiania . To eksperyment IND-CPA z jednym wyzwaniem. Łączna liczba szyfrowań, wraz z wyzwaniem, nie przekracza .
Twierdzenie. Dla każdego takiego przeciwnika istnieje redukcja wykonująca najwyżej zapytań do swojej wyroczni, dla której:
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.
We wszystkich grach sukces oznacza odgadnięcie tego samego rodzaju ukrytego bitu. Ostatnia gra ma szansę sukcesu .
5. Pierwsza strzałka: redukcja zastępuje funkcję
W działa rzeczywiste . W używamy jednej losowej funkcji 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 dostaje wyrocznię . Nie wie, czy jest to dla losowego klucza, czy . Nie dostaje klucza, kodu wybranej funkcji ani jej całej tabeli. Otrzymuje tylko odpowiedzi na własne pytania.
Strzałki pokazują interfejsy. Przeciwnik nie ma bezpośredniego dostępu do . Redukcja zna bit , ponieważ sama przygotowuje wyzwanie.
- Uruchamia i samodzielnie obsługuje jego pytania o szyfrowanie. Losuje , pyta o i oddaje .
- Po otrzymaniu losuje ukryty bit i tak samo szyfruje . Obsługuje również dalsze pytania.
- Odbiera i zwraca 1 dokładnie wtedy, gdy . Potrafi to sprawdzić, bo to ona wylosowała .
Gdy , widok jest dokładnie widokiem . Gdy , widok jest dokładnie widokiem . W obu przypadkach obejmuje również adaptacyjnie wybrane pytania. Dlatego, w konwencji różnicy prawdopodobieństw:
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 . Jej czas to czas oraz obsługa najwyżej szyfrowań i komunikatów. Gdy operację wyroczni liczymy jako jedno zapytanie, narzut bitowy poza nią wynosi . W rzeczywistym pomiarze trzeba doliczyć koszt wykonania samej funkcji.
6. Druga strzałka: porównujemy losowania identyfikatorów
W identyfikatory losujemy z powtórzeniami. W wybieramy je jednostajnie spośród dotąd nieużytych. To inny algorytm obsługi gry, a nie przemilczany warunek narzucony na .
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 oznacza zbiór identyfikatorów użytych w , a .
- Losujemy wspólną propozycję jednostajnie z możliwości. Gra zawsze ją przyjmuje.
- Jeżeli , gra również ją przyjmuje. W przeciwnym razie losuje zamiennik jednostajnie z wolnych identyfikatorów.
- 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 identyfikatorów, każdy ustalony wolny identyfikator zostanie przyjęty bezpośrednio z prawdopodobieństwem . Może też zostać zamiennikiem po trafieniu jednej z zajętych pozycji. Łącznie:
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 jest numerem szyfrowania, przyjętym identyfikatorem, wiadomością, maską, a częścią szyfrogramu. Wiersze są historią szyfrowań, nie osobnymi wpisami funkcji. Jeśli w identyfikator wraca, odczytujemy istniejący wpis .
· z powtórzeniami
| 1 | – | – | – | – |
|---|---|---|---|---|
| 2 | – | – | – | – |
| 3 | – | – | – | – |
| 4 | – | – | – | – |
· bez powtórzeń
| 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 mamy niezależne propozycje z 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 szyfrowań.
Dla ustalonej pary szansa wynosi . Par jest . 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.
Dla dokładnie 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:
Iloczyn wynika z kolejnych prawdopodobieństw warunkowych. Nie zakładamy niezależności zdarzeń „dotąd nie było kolizji”. Dla i mamy . Granica sumą to . Większa liczba jest ograniczeniem, nie błędem w dokładnym rachunku.
- 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 . 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 nigdy nie pytamy 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ę . Tak otrzymujemy . 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 mamy dla każdego ustalonego i każdego dokładnie jedną maskę, która daje ten wynik. Zatem 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 cały widok jest niezależny od , więc .
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:
Po wstawieniu granicy z punktu 7 dostajemy twierdzenie. Możemy użyć dokładnego iloczynu zamiast granicy sumą. Wynik wolno dodatkowo ograniczyć przez , ponieważ tyle maksymalnie wynosi przyjęta przewaga zgadywania.
Czynnik 2 zależy od definicji przewagi. Tutaj przewagą jest odległość szansy trafienia od . Jeśli inne źródło definiuje ją jako , 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 kroków ogólny rachunek daje . Stała liczba zaniedbywalnych składników daje zaniedbywalną sumę. Przy rosnącym 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 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 na zmienia tekst na . Twierdzenie CPA nie obejmuje modelu CCA.
- Redukcja potrzebuje nieznanego klucza. W naszym dowodzie tego uniknęliśmy przez interfejs . 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 .
- 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 . Kolizja ma więc prawdopodobieństwo , a granica sumą wynosi . 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 , a trzecia zero. Dla tak małych parametrów nawet ta dokładna granica kolizji nie daje nietrywialnego ograniczenia przewagi zgadywania poniżej . 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.