Kryptografia II stopień
Od definicji bezpieczeństwa do konstrukcji, redukcji i publikacji naukowych.
W1. Od szyfru do definicji bezpieczeństwa
Pytanie: co dokładnie ma pozostać tajne i przed kim? Tekst jawny to wiadomość przed zaszyfrowaniem, a szyfrogram to wynik szyfrowania. Zaczniemy od szyfrów historycznych. Pokażą nam, że zmiana wyglądu tekstu nie musi ukrywać jego struktury. Bezpieczeństwo nie powinno zależeć od ukrywania opisu algorytmu. Zakładamy, że przeciwnik zna ten opis, ale nie zna tajnego klucza.
Historyczna droga prowadzi od ukrywania samego sposobu szyfrowania do publicznego opisu algorytmu i precyzyjnego modelu przeciwnika. Szyfry podstawieniowe i przestawieniowe uczą rozpoznawania struktury. Analiza Shannona oddziela tajność informacyjną od ograniczeń obliczeniowych. Kryptografia z kluczem publicznym rozdziela prawo do szyfrowania lub sprawdzania od prawa do odszyfrowania lub podpisania. Każdy z tych kroków zmienia pytanie, które zadajemy o system.
Podstawianie, przestawianie i informacja, która pozostaje
Szyfr monoalfabetyczny. Klucz określa jedną tabelę zamiany liter. Jeżeli według tej tabeli literze A odpowiada Q, każde wystąpienie A w tekście jawnym zastępujemy literą Q w szyfrogramie, niezależnie od pozycji. Dopóki używamy tego samego klucza, przyporządkowanie się nie zmienia. Nie chodzi więc o pozostawienie litery bez zmiany, tylko o konsekwentne stosowanie tej samej tabeli.
W rozpatrywanym prostym podstawieniu różnym literom wejściowym odpowiadają różne litery wynikowe. Dzięki temu odbiorca znający tabelę może odwrócić każdą zamianę. Definicja dopuszcza też przyporządkowanie niektórej litery jej samej, np. B do B. Stałość tabeli nie oznacza jednak, że wszystkie litery pozostają bez zmiany.
Przykład: jeśli tabela zawiera zamiany A → Q i L → M, tekst ALA daje szyfrogram QMQ. Oba wystąpienia A przeszły w Q. Czytelnik szyfrogramu nadal widzi, że pierwsza i trzecia litera tekstu jawnego były jednakowe. Sama obserwacja tego powtórzenia nie mówi mu jeszcze, jakie to były litery. Liczba wystąpień danej litery przechodzi na jej zamiennik, np. liczba liter A staje się liczbą liter Q. Powtarzający się fragment tekstu jawnego daje powtarzający się fragment szyfrogramu.
Szyfr przestawieniowy. Nie zastępuje liter innymi literami, lecz zmienia ich kolejność zgodnie z kluczem. Na przykład przestawienie ALA w AAL pozostawia dwie litery A i jedną L. Zachowane są więc same znaki i liczba wystąpień każdego z nich, ale niekoniecznie ich sąsiedztwo. To inny rodzaj zachowanej informacji niż przy podstawianiu. Handbook of Applied Cryptography, §7.3.1–7.3.2.
Duża liczba możliwych kluczy sama nie wystarcza do zapewnienia bezpieczeństwa. Dla prostego podstawienia alfabetu 26-literowego istnieje tabel zamiany. Przeciwnik nie musi jednak sprawdzać ich wszystkich. Może wykorzystywać częstości liter, typowe połączenia liter i prawdopodobne słowa. Są to wskazówki, a nie pewne odpowiedzi, szczególnie przy krótkim tekście. Nie możemy też zakładać, że przeciwnik nie zna formatu, nagłówka lub części treści wiadomości.
Szyfr polialfabetyczny. Korzysta z więcej niż jednej tabeli podstawień. Wybór tabeli może zależeć od pozycji litery w wiadomości. Ta sama litera tekstu jawnego może więc dawać różne litery szyfrogramu na różnych pozycjach. Jeśli kolejność tabel powtarza się z krótkim okresem, można zebrać pozycje korzystające z tej samej tabeli i analizować je osobno. Za chwilę zobaczymy to w szyfrze Vigenère’a. Samo wrażenie, że szyfrogram wygląda losowo, nie jest zatem dowodem bezpieczeństwa.
Vigenère: gdzie dokładnie działa klucz
W popularnym wariancie szyfru Vigenère’a zapisujemy litery jako liczby od do . Klucz to słowo długości , powtarzane pod wiadomością. Numerujemy pozycje od zera. Liczba oznacza literę tekstu jawnego na pozycji , a literę szyfrogramu na tej pozycji. Wartość oznacza literę klucza na pozycji . Dla kolejnej pozycji wiadomości wybieramy , czyli wracamy do początku klucza po wykorzystaniu jego ostatniej litery. Szyfrowanie i odszyfrowanie mają postać:
Litera klucza określa przesunięcie w alfabecie. Dla litery wiadomości A i litery klucza K liczymy , czyli otrzymujemy K. Po przekroczeniu Z wracamy do A, co zapewnia działanie modulo 26. Zmiana jednej litery klucza zmienia przesunięcie na wszystkich pozycjach wiadomości, na których używamy tej litery klucza. Dwa przebiegi poniżej szyfrują tę samą wiadomość, ale różnymi kluczami.
Przebieg A
Wynik:
Przebieg B
Wynik:
Obrys wskazuje tę samą pozycję klucza w kolejnych okresach. Znany tekst i szyfrogram ujawniają wykorzystane przesunięcie. Krótkie próbki nie wystarczają do wiarygodnej analizy częstości.
Słabość: okres rozbija problem na prostsze części. Numerujemy pozycje od zera, jak we wzorze. Przy kluczu długości trzy pozycje 0, 3, 6, … korzystają z jednego przesunięcia, pozycje 1, 4, 7, … z drugiego, a pozycje 2, 5, 8, … z trzeciego. Przy dostatecznie długim tekście można analizować częstości w tych grupach. Odległości między powtarzającymi się fragmentami szyfrogramu pomagają proponować okres w metodzie Kasiskiego, ale pojedyncze powtórzenie może być przypadkowe. Krótki przykład ilustruje zależność, nie gwarantuje odzyskania klucza analizą częstości.
Gdy znamy fragment tekstu jawnego, obliczamy odpowiadający mu fragment klucza przez . Przy wybranym tekście AAAA… dostajemy bezpośrednio powtarzany klucz. To różne możliwości przeciwnika. Ich uporządkowanie za chwilę stanie się podstawą modelu bezpieczeństwa. Handbook of Applied Cryptography, §7.3.3 i §7.3.5.
Enigma: stan maszyny zmienia podstawienie
Enigma jest elektromechaniczną maszyną szyfrującą. Operator naciska klawisz z literą wiadomości, a maszyna zapala lampkę z literą szyfrogramu. Na przykład naciśnięcie A może zapalić B. O tym, która lampka się zapali, decydują połączenia elektryczne i aktualne nastawy maszyny. Klawisz służy do wprowadzania litery. Klucz kryptograficzny to uzgodniony zestaw nastaw, a nie naciskany klawisz.
Rozpatrujemy wojskową Enigmę z trzema ruchomymi wirnikami. W naszym przykładzie są to wirniki I, II i III, umieszczone w tej kolejności od lewej, oraz nieruchomy reflektor B. Oznaczenie B określa tutaj typ reflektora, nie literę wyniku. Inne wersje Enigmy mogły mieć inną budowę.
Najpierw części maszyny
- Klawiatura ma klawisze literowe. Naciśnięcie klawisza uruchamia mechanizm kroku wirników, a następnie zamyka obwód elektryczny odpowiadający wybranej literze.
- Łącznica wtyczkowa to panel gniazd oznaczonych literami. Kabel wpięty między
AiZzamienia te dwie litery: wejścieAprowadzi dalej jakoZ, a wejścieZjakoA. Litera bez kabla przechodzi bez zmiany. Łącznica nie obraca się. Te same połączenia działają także na drodze powrotnej. - Wirnik to obracany krążek z 26 stykami elektrycznymi po każdej stronie. Wewnątrz przewody łączą każdy styk jednej strony z jednym stykiem drugiej strony. Każdy typ wirnika realizuje własne przestawienie styków. Okablowanie jest ustalone, ale obrót całego krążka zmienia to, które styki spotykają się ze stykami sąsiednich części.
- Okienko i pierścień literowy pozwalają określić nastawy wirnika. Przez okienko w pokrywie widać jedną literę z pierścienia otaczającego wirnik. Sam pierścień można przestawić względem rdzenia z przewodami. Dlatego wskazanie okienka i nastawa pierścienia są dwiema osobnymi informacjami. W przykładach używamy liter A–Z, również gdy historyczna maszyna oznaczała pozycje liczbami 01–26.
- Reflektor łączy styki parami i kieruje sygnał z powrotem przez te same trzy wirniki. Nie jest lampą ani czwartym ruchomym wirnikiem.
- Panel lampek pokazuje wynik. Świeci litera, do której doprowadziła droga elektryczna. W tej maszynie wynik odczytuje i zapisuje operator, zamiast otrzymać wydruk.
Między łącznicą a prawym wirnikiem jest jeszcze nieruchoma tarcza wejściowa ETW. Doprowadza przewody do zestawu wirników. W wybranym wariancie zachowuje oznaczenia liter, więc w obliczeniach nie dodaje osobnej zamiany. Zasilanie zapewnia bateria. Budowa Enigmy I w Crypto Museum, A. Ray Miller, budowa i nastawy maszyny, s. 4–5.
- ETW
- Eintrittswalze. Niemiecka nazwa tarczy wejściowej Enigmy. Po angielsku entry wheel lub entry disc. Nie jest to skrót angielski.
Jeden klawisz, jedna droga do lampki
Na poniższym schemacie zachowujemy kolejność części: reflektor jest po lewej, a wirnik III po prawej. Początek drogi jest jednak po prawej stronie rysunku, przy klawiaturze. Górna droga prowadzi do reflektora, a dolna wraca do lampki. Pokazujemy tylko połączenia wykorzystane przy jednym naciśnięciu, nie wszystkie przewody maszyny.
- Przed naciśnięciem okienka pokazują
AAA. Używamy pierścieniAAAi łącznicy bez kabli. Każda z trzech liter opisuje kolejny wirnik, od lewej strony maszyny. - Naciskamy
A. Najpierw następuje ruch mechaniczny. Prawy wirnik III przesuwa się o jedną pozycję, więc okienka pokazująAAB. W tym kroku wirniki I i II pozostają nieruchome. - Dopiero po kroku płynie sygnał. Łącznica i ETW przekazują
Abez zmiany. Wirnik III przekształcaAwC, wirnik II przekształcaCwD, a wirnik I przekształcaDwF. - Reflektor zawraca drogę. W reflektorze B styk
Fjest połączony ze stykiemS. Sygnał wraca przez wirnik I jakoS, przez II jakoE, a przez III jakoB. Przejście przez ETW i łącznicę bez kabli pozostawiaB. - Zapala się lampka
B. Podczas tej drogi w obie strony wirniki już się nie obracają. Operator odczytuje wynik. Następne naciśnięcie ponownie rozpocznie się od kroku mechanizmu.
Litery wewnątrz rysunku są oznaczeniami torów elektrycznych. Maszyna nie wyświetla pośrednich C, D ani F. Widoczna jest dopiero lampka wyniku. Ruch i przepływ to dwa etapy jednego naciśnięcia, a nie obrót wirnika przy każdym przejściu sygnału. Droga sygnału i kolejność działania, okablowanie wirników i reflektora.
Gdzie jest klucz i co zmienia obrót
Nie dodajemy tu litery klucza do litery wiadomości jak w Vigenèrze. Operator przygotowuje maszynę według uzgodnionej konfiguracji. Te nastawy wybierają drogę elektryczną, a mechanizm zmienia ją podczas pisania.
| Nastawa | Co operator ustawia | Co to zmienia |
|---|---|---|
| Dobór i kolejność wirników | Wybiera wirniki i ich miejsca, tutaj I, II, III od lewej | Kolejność trzech różnych przekształceń |
| Położenia początkowe | Obraca wirniki do ustalonych wskazań okienek, tutaj AAA |
Stan, od którego zacznie się szyfrowanie wiadomości |
| Nastawy pierścieni | Ustawia pierścień literowy względem rdzenia z przewodami, tutaj AAA |
Dopasowanie okablowania do oznaczeń widocznych w okienku |
| Połączenia łącznicy | Wpina kable między wybrane pary liter | Zamiany przed wirnikami i po przejściu powrotnym |
Okienko i pierścień to nie to samo. Obrót całego wirnika zmienia literę widoczną w okienku. Przestawienie pierścienia zmienia jego ustawienie względem rdzenia. Po takiej zmianie można ponownie ustawić tę samą literę w okienku, ale przewody będą już dopasowane inaczej. W naszej demonstracji typ reflektora pozostaje stały. Odbiorca musi użyć zgodnej maszyny i odtworzyć nastawy do danej wiadomości, nie tylko trzy litery okienek.
Przy nastawach z rysunku dwa kolejne naciśnięcia A dają różne wyniki. Nie zmieniamy kabla ani okablowania wirników. Zmienia się ich położenie:
| Naciśnięcie | Litera wejściowa | Okienka przed krokiem | Okienka po kroku | Lampka |
|---|---|---|---|---|
| 1 | A |
AAA |
AAB |
B |
| 2 | A |
AAB |
AAC |
D |
| 3 | A |
AAC |
AAD |
Z |
To przykład, nie reguła zakazująca powtórzenia wyniku w całej wiadomości. Inne położenie wybiera inne podstawienie całego alfabetu, ale dla niektórych liter wyniki mogą się powtarzać. W pięcioliterowym przebiegu poniżej AAAAA daje BDZGO.
Przepływ rozłożony na pojedyncze operacje
Teraz te same trzy wirniki przedstawiamy jako kolejne kroki drogi sygnału. Oznaczenie „powrót” nie dodaje nowej części. To ponowne przejście przez wcześniej poznany wirnik, w przeciwnym kierunku. Przebieg A zachowuje nastawy ze schematu trzywirnikowej maszyny. Przebieg B służy do porównania po zmianie jednej nastawy. Okienka i pierścienie nadal zapisujemy od lewej, w kolejności I, II, III.
Wirniki I–II–III, reflektor B. Rzeczywiste okablowanie, krok przed szyfrowaniem i podwójny krok środkowego wirnika. To historyczny szyfr, nie metoda ochrony współczesnych danych.
Przebieg A
Okienka:
Szyfrogram:
Przebieg B
Okienka:
Szyfrogram:
| Litera | Wejście | Okienka A | Wynik A | Okienka B | Wynik B |
|---|
Obliczenia wirników: Hristijan Lubeski, enigma-emulator (MIT). Rysunek pokazuje kolejne operacje, nie rozmieszczenie części w obudowie. Podgląd pośrednich liter służy objaśnieniu i nie jest widokiem historycznego podsłuchującego.
- MIT
- Massachusetts Institute of Technology. Massachusettski Instytut Technologiczny, uczelnia w USA.
Dlaczego czasem porusza się więcej wirników
Zapadka to mechaniczny element, który przy naciśnięciu klawisza popycha wirnik o jeden krok. Wycięcie na pierścieniu pozwala w określonym położeniu zaangażować mechanizm przesuwający również sąsiedni wirnik. Prawy wirnik wykonuje krok zawsze. To, czy poruszą się pozostałe, zależy od położeń wycięć przed naciśnięciem.
Dla wirników I, II, III z pierścieniami AAA można to prześledzić od nastawy ADU:
| Okienka przed krokiem | Co uruchamia ruch | Wirniki wykonujące krok | Okienka po kroku |
|---|---|---|---|
ADU |
Zwykły krok prawego wirnika | III | ADV |
ADV |
Prawy III jest przy swoim wycięciu, widocznym jako V |
II i III | AEW |
AEW |
Środkowy II jest przy swoim wycięciu, widocznym jako E |
I, II i III | BFX |
Środkowy wirnik przeszedł kolejno z D do E, a zaraz potem z E do F. To podwójny krok, czyli dwa kroki podczas dwóch kolejnych naciśnięć, nie dwa kroki w jednym naciśnięciu. Dlatego Enigma nie zachowuje się dokładnie jak licznik, który przenosi pozycję dopiero po pełnym obrocie sąsiada. Wycięcie jest związane z pierścieniem literowym. Zmiana nastawy pierścienia nie zmienia litery okienka, przy której następuje przeniesienie, ale zmienia dopasowanie przewodów. D. Hamer, analiza mechanizmu podwójnego kroku.
Dopiero teraz zapis matematyczny
Przy nieruchomych wirnikach droga do reflektora jest permutacją, czyli odwracalnym przyporządkowaniem 26 liter. Oznaczmy ją przez . W uwzględniamy łącznicę, ETW i trzy wirniki na drodze do reflektora. Reflektor oznaczymy przez . Droga powrotna odwraca wcześniejsze połączenia, więc opisuje ją . Całe podstawienie ma postać:
Czytamy złożenie od prawej: najpierw , potem , na końcu . Reflektor łączy różne styki parami. Jego dwukrotne zastosowanie zwraca literę wejściową, a pojedyncze nigdy nie pozostawia jej bez zmiany. Stąd:
dla każdej litery i tego samego, ustalonego położenia wirników. Nie chodzi o dwa kolejne naciśnięcia, bo pomiędzy nimi następuje obrót. Aby odszyfrować całą wiadomość, odbiorca odtwarza nastawy początkowe i wpisuje szyfrogram. Maszyna przechodzi wtedy przez tę samą kolejność położeń. W naszym przykładzie po powrocie do AAA wpisanie BDZGO daje AAAAA.
Ograniczenie konstrukcji: brak szyfrowania litery na nią samą eliminuje pewne dopasowania przy zgadywaniu fragmentu wiadomości. Sam nie wystarcza do odzyskania klucza. Przewidywalny tekst i błędy procedur mogą jednak dostarczyć dalszych wskazówek. Liczba możliwych nastaw nie jest więc samodzielnym dowodem bezpieczeństwa.
Od szyfrowania do celów bezpieczeństwa
Trzy cele nie są zamienne. Poufność chroni treść. Integralność pozwala wykrywać nieuprawnioną zmianę. Uwierzytelnianie wiąże działanie z odpowiednią stroną lub kluczem. Szyfrowanie bez integralności może pozwalać na kontrolowaną modyfikację. Poprawny podpis nie ukrywa treści. Kanał z uzgodnionym kluczem nie musi jeszcze wiedzieć, kto jest partnerem.
Rozróżniamy generowanie klucza , szyfrowanie i deszyfrowanie . Dla klucza i wiadomości wymagamy poprawności:
Prawdopodobieństwo obejmuje losowość algorytmów. Jeżeli konstrukcja dopuszcza mały błąd poprawności, trzeba podać jego granicę. Poprawność nie mówi, czy podsłuchujący potrafi odzyskać wiadomość.
Bezpieczeństwo jako eksperyment
Przeciwnik otrzymuje określony widok i ma wygrać określone zadanie. W eksperymencie nierozróżnialności wybiera dwie dozwolone wiadomości jednakowej długości. Challenger generuje tajny klucz , losuje równomiernie bit i przekazuje przeciwnikowi szyfrogram wiadomości . Przeciwnik odpowiada bitem , czyli swoją oceną, którą wiadomość zaszyfrowano. Równa długość usuwa trywialne rozróżnianie przez rozmiar.
Na rysunku rozdzielamy wiedzę obu stron. Czytelnik widzi zapis losowania bitu po prawej, ale przeciwnik nie otrzymuje jego wartości. Widzi tylko dane przekazane strzałkami i własny stan. Szyfrogram nazywamy wyzwaniem tego eksperymentu. Nie jest to wyzwanie z protokołu identyfikacji. Rysunek pokazuje podstawowy wariant z jednym szyfrogramem. Za chwilę rozszerzymy dostęp przeciwnika do dodatkowych usług. Boneh–Shoup, eksperyment 2.4.
Obie strony znają opis algorytmów. Strzałki między stronami pokazują przekazywane dane. Pola po prawej pokazują czynności challengera. Czas płynie w dół.
Cały eksperyment. 6 kroków, dwa różne punkty widzenia.
Podstawowy eksperyment IND-EAV z jednym wyzwaniem dla szyfrowania symetrycznego. W modelach CPA i CCA dochodzą dozwolone zapytania opisane poniżej. Jedno trafienie nie jest dowodem złamania szyfru. Animacja przedstawia reguły eksperymentu, nie pomiar bezpieczeństwa konkretnego algorytmu.
W tym kursie przewaga zgadywania to:
Dwie wersje eksperymentu oznaczymy przez , a zdarzenia sukcesu w nich przez . Indeksy numerują eksperymenty, nie grupy algebraiczne. Różnica mówi, jak bardzo zmieniła się szansa sukcesu. To inna konwencja niż przewaga zgadywania. Przy przejściu między typowymi definicjami może pojawić się czynnik 2. Każde twierdzenie podaje swoją konwencję. Pełne wyjaśnienie zawiera rozdział o metodzie gier.
Zaniedbywalna oznacza tu więcej niż „mała w jednym pomiarze”. Funkcja jest zaniedbywalna, jeżeli dla każdego dodatniego wielomianu od pewnego zachodzi . Przykładem jest . Funkcja nie jest zaniedbywalna, choć dąży do zera.
Od podsłuchu do aktywnego przeciwnika
Najpierw oddzielmy dwie osie. Cel mówi, co przeciwnik ma osiągnąć, np. rozpoznać zaszyfrowaną wiadomość. Model dostępu mówi, jakie dane i usługi może wykorzystać. COA, KPA, CPA i CCA opisują możliwości ataku. Sam skrót nie ustala jeszcze formalnego zdarzenia wygranej. Angielskie rozwinięcia i polskie znaczenia są zebrane w słowniku modeli ataku.
| Dostęp | Co otrzymuje lub wybiera przeciwnik | Przykład rzeczywistej sytuacji |
|---|---|---|
| COA: tylko szyfrogramy | Przechwycone szyfrogramy, opis algorytmu i wiedzę o formacie danych | Obserwacja zaszyfrowanego ruchu |
| KPA: znany tekst jawny | Dodatkowo pary tekst–szyfrogram, których tekstu sam nie wybrał | Znany nagłówek przesłanego dokumentu |
| CPA: wybrany tekst jawny | Sam podaje teksty do zaszyfrowania pod atakowanym kluczem | Usługa szyfrująca dokumenty użytkowników |
| CCA: wybrany szyfrogram | Może podawać szyfrogramy do odszyfrowania, z ograniczeniami gry | Odbiorca przetwarzający dane kontrolowane przez napastnika |
Przy zgodnych ograniczeniach zasobów kolejne uprawnienia obejmują poprzednie. Usługa deszyfrująca w modelu zwraca tekst lub odrzucenie, oznaczane . W rzeczywistym ataku wystarcza czasem informacja pośrednia, np. rozróżnialny błąd odbiorcy. Nie utożsamiamy jednak każdego komunikatu błędu z pełną wyrocznią deszyfrującą. Goldwasser–Bellare, modele ataków na szyfrowanie.
Ta sama gra IND, coraz szerszy dostęp
Teraz ustalamy jeden cel: odgadnąć bit wyboru między dwiema wiadomościami tej samej długości. Zmieniamy tylko uprawnienia. Wyzwanie to szyfrogram otrzymany w tej grze, nie wyzwanie z protokołu identyfikacji.
| Model poufności | Przed otrzymaniem wyzwania | Po otrzymaniu wyzwania |
|---|---|---|
| IND-EAV, wariant jednego wyzwania | Brak dodatkowych wyroczni | Tylko obserwacja wyzwania |
| IND-CPA | Szyfrowanie wybranych wiadomości | Szyfrowanie wybranych wiadomości |
| IND-CCA1 | Szyfrowanie i deszyfrowanie wybranych danych | Szyfrowanie, bez deszyfrowania |
| IND-CCA2 | Szyfrowanie i deszyfrowanie wybranych danych | Szyfrowanie oraz deszyfrowanie innych szyfrogramów niż wyzwanie |
IND oznacza nierozróżnialność. W CCA1 dostęp do deszyfrowania kończy się przed wyzwaniem. W CCA2 napastnik może reagować na otrzymane wyzwanie i odpowiedzi na kolejne dozwolone zapytania. Nie wolno pytać o deszyfrowanie samego , bo wtedy gra natychmiast ujawniłaby . Wolno natomiast pytać o zmieniony szyfrogram. To właśnie taki dostęp musi przetrwać konstrukcja odporna na CCA2. Bellare, Desai, Pointcheval, Rogaway, Relations among Notions of Security for Public-Key Encryption Schemes.
Mapa reguł gry dla szyfrowania symetrycznego. Nie uruchamia konkretnego szyfru i nie stanowi testu jego bezpieczeństwa.
Zapytanie o wyzwanie jest zawsze niedopuszczalne po jego wydaniu. CCA2 dopuszcza pytania o inne, również celowo zmodyfikowane szyfrogramy. Zmiana modelu lub fazy zachowuje wcześniejsze próby w historii.
Zapytania przed wyzwaniem mogą zależeć od wcześniejszych odpowiedzi również w CCA1. Różnica między CCA1 i CCA2 dotyczy dostępu do deszyfrowania po wyzwaniu, a nie zakazu reagowania na wcześniejsze odpowiedzi.
Dlaczego silniejszy model daje mocniejszą gwarancję
Dla tej samej rodziny schematów, zgodnych reguł wyzwania i odpowiednio rozliczonych zasobów zachodzi:
Strzałki gwarancji biegną przeciwnie do rozszerzania uprawnień. Przeciwnik słabszego modelu jest szczególnym przypadkiem przeciwnika silniejszego: po prostu nie korzysta z części usług. Jeśli schemat wytrzymuje wszystkich dozwolonych przeciwników silniejszego modelu, wytrzymuje również tę podklasę. W drugą stronę taki argument nie działa.
Szyfrowanie publiczne jest szczególne. Mając klucz publiczny, napastnik sam szyfruje wybrane teksty. Dlatego dodatkowa wyrocznia szyfrująca nie daje mu nowej możliwości. Rozróżnienie EAV–CPA zyskuje znaczenie przede wszystkim dla szyfrowania symetrycznego. Trzeba też pilnować, czy definicja dotyczy jednej wiadomości, wielu wiadomości lub schematu ze stanem. Nie zamieniamy między sobą tych definicji bez argumentu.
Konkretny skok możliwości: jednorazowa maska bitowa ukrywa jeden bit. Jeśli jednak tę samą maskę wykorzystamy ponownie i pozwolimy przeciwnikowi zaszyfrować zero, pozna maskę. Nie łamie to twierdzenia o jednorazowej masce. Łamie warunek jej jednorazowości. W W3 policzymy to dokładnie. Z kolei klasyczny ElGamal może spełniać IND-CPA przy założeniu DDH, lecz pozwala modyfikować szyfrogram. Dostęp CCA2 zamienia tę modyfikację w odzyskanie wiadomości, co pokazujemy rachunkiem i demonstracją w W10a.
- DDH
- Decisional Diffie–Hellman. Decyzyjny problem Diffiego–Hellmana.
Silniejszy model nie naprawia algorytmu. Ujawnia dodatkowe wymaganie. Odpowiedzią może być konstrukcja z uwierzytelnianiem szyfrogramów i dowodem, a nie zwiększenie samej długości klucza. W W4 poznamy AEAD. Standardowa poufność IND-CCA nie oznacza automatycznie uwierzytelnienia nadawcy, ochrony metadanych, odporności na wycieki z urządzenia ani bezpieczeństwa po utracie tajnego klucza. To osobne cele i rozszerzenia modelu. Boneh–Shoup, rozdziały 2, 5, 9 i 12.
- IND-CCA
- indistinguishability under chosen-ciphertext attack. Nierozróżnialność przy ataku z wybranym szyfrogramem. Zakres dostępu ustala definicja.
Przykład. Deterministyczne szyfrowanie tej samej wiadomości daje ten sam szyfrogram. Przy dostępie do szyfrowania przeciwnik może zapamiętać szyfrogram i porównać go z wyzwaniem. Długi klucz nie usuwa tego problemu.
Powiązania: C1. Literatura: Goldwasser–Bellare, Handbook of Applied Cryptography.
W2. Generatory i funkcje pseudolosowe
Pytanie: czym zastąpić długi losowy ciąg, gdy mamy tylko krótki sekret? Najpierw zdefiniujemy generator i rodzinę funkcji. W W3 poznamy szyfrowanie z prawdziwie losową maską. Dopiero wtedy porównamy je z maską z generatora i przeprowadzimy pierwszą redukcję.
Dwa różne obiekty: generator i funkcja pseudolosowa
Generator pseudolosowy rozwija krótki, tajny zarodek w długi ciąg. Funkcja pseudolosowa odpowiada na wiele argumentów pod jednym tajnym kluczem. To nie są dwa zapisy tego samego założenia. Różnią się interfejsem przeciwnika i obiektem, który zastępujemy w dowodzie przez losowy.
PRG rozwijamy jako pseudorandom generator, czyli generator pseudolosowy. PRF oznacza pseudorandom function, czyli funkcję pseudolosową. W obu przypadkach „pseudolosowy” oznacza nierozróżnialny obliczeniowo od odpowiedniego obiektu losowego. Nie oznacza, że algorytm deterministyczny tworzy nową entropię.
Parametry i granice obietnicy
Parametr bezpieczeństwa określa rodzinę rozpatrywanych instancji. Długość zarodka oznaczamy przez , długość klucza PRF przez , długość publicznego argumentu przez , a długość wyniku przez . Wszystkie te długości są mierzone w bitach. Nie muszą być równe. Algorytmy i długości są publiczne.
Rozpatrywane długości są ograniczone wielomianowo w . Symbol oznacza losowanie jednostajne ze zbioru po prawej. Samo oznacza przypisanie obliczonej wartości. Nie utożsamiamy tych dwóch operacji.
Przeciwnik zna konstrukcję. Tajne jest konkretne wylosowane wejście kluczujące, nie opis algorytmu. Dopuszczamy przeciwnika probabilistycznego, którego czas działania jest wielomianowy w . Skrót PPT pochodzi od probabilistic polynomial time. Przeciwnik ma własne losowe monety. Jego liczba zapytań również musi mieścić się w przyjętym budżecie czasu.
Nieujemna funkcja jest znikoma, jeśli maleje szybciej niż odwrotność dowolnego wielomianu:
To definicja asymptotyczna. Dla konkretnego wdrożenia potrzebujemy także konkretnej granicy zależnej od czasu, liczby zapytań i długości parametrów. Zdanie „przewaga jest znikoma” nie zastępuje dobrania tych parametrów.
Dobry PRG: co dokładnie zakładamy
Niech będzie publicznym, deterministycznym algorytmem obliczalnym w czasie wielomianowym:
W świecie rzeczywistym losujemy tajny zarodek i przekazujemy przeciwnikowi . W świecie idealnym przekazujemy mu niezależny ciąg . W obu światach dostaje ciąg tej samej długości. Nie dostaje ani etykiety świata. Algorytm rozróżniający zwraca jeden bit.
Założenie PRG: dla każdego PPT ta przewaga jest znikoma. Prawdopodobieństwa obejmują losowanie lub oraz monety . Zapis udostępnia publiczny parametr bezpieczeństwa. Indeksowanie rodziny przez pomijamy w nazwie .
Diagram zestawia alternatywy. Jedno uruchomienie dostarcza tylko jeden ciąg , nie parę ciągów do porównania.
Co przeciwnik może robić? Może analizować wszystkie otrzymane bity, obliczać dowolne efektywne statystyki, uruchamiać publiczny dla własnych kandydatów na zarodek i próbować odtworzyć jego stan. Założenie ma wykluczać każdy taki efektywny rozróżniacz, nie tylko ustalony zestaw testów statystycznych.
Co oznacza dobry generator? Nie wystarcza równowaga zer i jedynek ani przejście testów częstości. Ciąg może mieć prawidłowe częstości, a jednocześnie dawać się przewidzieć. Przykładowo skopiowanie pierwszej połowy ciągu do drugiej pozostawia wiele pozornie poprawnych statystyk, ale test równości połówek natychmiast odróżnia go od losowego. Kryptograficzne wymaganie dotyczy całego rozkładu wyjść i wszystkich PPT, a nie wyglądu jednego ciągu.
Nie jest to bezwarunkowy dowód bezpieczeństwa konkretnej implementacji. Trzeba wskazać konstrukcję, założenie obliczeniowe lub podstawy zaufania do prymitywu, długości parametrów i sposób inicjalizacji. Biblioteczny generator do symulacji nie staje się generatorem kryptograficznym tylko dlatego, że zwraca bity.
Dłuższy ciąg nie oznacza większej entropii
Generator ma najwyżej różnych wyjść, podczas gdy ciąg jednostajny długości ma możliwych wartości. Dla obrazu zachodzi:
Odległość statystyczna, czyli największa różnica prawdopodobieństwa tego samego zdarzenia w dwóch rozkładach, spełnia więc:
Rozkłady mogą być bardzo odległe statystycznie, a mimo to nierozróżnialne obliczeniowo. Rozróżniacz bez ograniczeń może sprawdzić przynależność do obrazu przez wyliczenie wszystkich zarodków. Przy dużym nie jest to dozwolony efektywny atak. W naszym małym przykładzie dydaktycznym cała tablica będzie widoczna, więc takiej obietnicy bezpieczeństwa nie ma.
Czego samo założenie PRG nie zapewnia
- Nie pozwala ujawnić zarodka. Mając , każdy obliczy .
- Nie uzasadnia ponownego używania tych samych bitów strumienia jako maski dla różnych wiadomości.
- Nie daje automatycznie bezpieczeństwa po ujawnieniu stanu urządzenia, po jego cofnięciu ani dla słabego, przewidywalnego zarodka. To osobne modele.
- Nie mówi, że publiczna funkcja jest tajną wyrocznią losową. Porównujemy jedno wyjście dla ukrytego, losowego zarodka, a nie całe zachowanie publicznego algorytmu z dowolnymi wejściami.
- Nie zapewnia integralności szyfrogramu. To własność schematu uwierzytelniania, nie samego pseudolosowego strumienia.
Możemy zużyć rozłączne fragmenty dłuższego wyjścia, jeżeli założenie obejmuje cały wykorzystany strumień. Konstrukcja strumieniowa z aktualizacją stanu wymaga własnego, odpowiednio sformułowanego założenia. Nie wolno domyślnie wywnioskować go z bezpieczeństwa jednego krótkiego prefiksu.
Dobry PRF: nierozróżnialność całego interfejsu
Niech będzie publicznym, deterministycznym i efektywnym algorytmem:
Klucz wybieramy raz na cały eksperyment. Przeciwnik może wysyłać argumenty i otrzymywać . Nie zna . Kolejne pytania mogą zależeć od wcześniejszych odpowiedzi. To właśnie adaptacyjność. Może także powtarzać pytania.
W świecie idealnym wybieramy raz funkcję jednostajnie ze zbioru wszystkich funkcji o tej samej dziedzinie i przeciwdziedzinie. Dla różnych argumentów jej wartości są niezależnymi, jednostajnymi ciągami. Dla powtórzonego argumentu zwraca tę samą wartość.
Założenie PRF: dla każdego PPT , z wielomianową liczbą adaptacyjnych zapytań, ta przewaga jest znikoma. Prawdopodobieństwa obejmują wybór lub oraz losowe monety . Wykładnik przy oznacza dostęp do wyroczni, a nie potęgowanie. W obu światach dostępny interfejs jest identyczny. Wewnętrzna tablica, klucz i etykieta świata pozostają ukryte.
Symbol oznacza zbiór wszystkich funkcji o podanych długościach. Powtórzenie pytania odtwarza odpowiedź w obu światach.
Nie losujemy nowej funkcji przy każdym pytaniu. Gdyby dla tego samego losować nową odpowiedź, przeciwnik odróżniłby ją od deterministycznego dwoma powtórzonymi pytaniami. Idealnym odpowiednikiem PRF jest funkcja z pamięcią, a nie bezstanowe źródło nowych ciągów.
Jedno losowe wyjście nie wystarcza
Rozważmy wadliwą rodzinę z . Jedna odpowiedź jest jednostajna, bo klucz wylosowano jednostajnie. Jednak dla dwóch różnych argumentów odpowiedzi zawsze są identyczne. Rozróżniacz pyta o te dwa argumenty i zwraca wtedy, gdy odpowiedzi są równe. W świecie funkcji losowej równość zachodzi z prawdopodobieństwem :
Ten przykład pokazuje, dlaczego formalizujemy cały transkrypt pytań i odpowiedzi. Ani pojedynczy wynik, ani same częstości bitów nie wystarczają.
Funkcja losowa a model wyroczni losowej
Pamiętająca tablica funkcji losowej działa tak samo jak tablica wyroczni losowej o ustalonej długości odpowiedzi. Nie oznacza to jednak, że jest publiczną funkcją haszującą. W grze PRF dostaje dostęp do albo . W grze szyfrowania przeciwnik nie dostaje bezpośredniej wyroczni masek. Dostaje szyfrogramy. Rozróżniacz użyty w redukcji ma inne uprawnienia niż przeciwnik uruchomiony wewnątrz tej redukcji.
Nie wymagamy różnowartościowości ani . Nie zakładamy też odporności PRF na kolizje w znaczeniu używanym dla funkcji haszujących. Kolizje wartości dla różnych argumentów są dopuszczalne, ponieważ występują również w funkcji losowej. Pełne tablice, widoki przeciwnika i dowód redukcji do OTP pokażą dokładnie, kiedy powtórzenie jest problemem.
- OTP
- one-time pad. Szyfr z jednorazowym, losowym kluczem długości wiadomości.
Powiązania: C3: generatory i redukcje, L2: ataki na losowość, pogłębienie: dowody symetryczne.