Kryptografia II stopień

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

Pogłębienie C. Dowody AKE i ujawnienia stanu

Materiał do wyboru. Rozwija W10. Zgodność kluczy jest początkiem, nie końcem analizy.

Gra sesyjna

Sesja $\pi_U^i$ ma właściciela, partnera, rolę, transkrypt, stan i ewentualny klucz. Przeciwnik kontroluje sieć. Partnerowanie określa dwie lokalne sesje tej samej wymiany. Sam jednakowy nonce nie wystarcza.

Zapytanie	Znaczenie
$\operatorname{Send}(\pi,M)$	Dostarczenie wiadomości i kolejny krok
$\operatorname{KeyReveal}(\pi)$	Ujawnienie ustalonego klucza
$\operatorname{StaticReveal}(U)$	Ujawnienie sekretu długoterminowego
$\operatorname{EphemeralReveal}(\pi)$	Dokładnie wskazana losowość sesji
$\operatorname{Test}(\pi)$	Klucz rzeczywisty albo losowy

To interfejs dydaktyczny. Konkretne modele określają kolejność, rejestrację kluczy i dopuszczalne kompromitacje. Sesja testowa musi być zakończona i świeża, także wobec dopuszczalnej dalszej interakcji.

Świeżość w eCK

Nie wolno ujawnić klucza sesji testowej ani klucza jej sesji partnerskiej. Ujawnienie choćby jednego z nich pozbawia sesję świeżości. Gdy istnieje uczciwa sesja partnerska, nie wolno też łącznie poznać sekretu stałego i sekretu efemerycznego tego samego uczestnika z odpowiedniej sesji. Wolno natomiast rozważać niektóre ujawnienia dotyczące różnych uczestników, zgodnie z tabelą poniżej. Gdy nie ma uczciwej sesji partnerskiej, nie wolno znać sekretu stałego deklarowanego partnera. Nadal nie wolno poznać obu sekretów właściciela sesji testowej. Dokładne warunki, w tym kolejność ujawnień, ustala definicja analizowanego modelu.

W NAXOS ujawnienie efemeryczne dotyczy zalążka, nie całej pamięci ani gotowego wykładnika. Zastąpienie go pełnym odczytem stanu tworzy inny model. Nie należy utożsamiać go z wizualizacją chronionego urządzenia.

SIGMA: trzy bariery dowodu

Pochodzenie transkryptu. Nowy zaakceptowany podpis nieprzejętego partnera może prowadzić do fałszerstwa. Powtórzony uczciwy transkrypt nie jest nowym fałszerstwem, więc trzeba śledzić sesje i wkłady.
Związanie tożsamości. MAC wiąże tożsamość z wymianą. Symulator musi obsłużyć dozwolone zapytania i wskazać zdarzenie znacznika dla nieuprawnionego kontekstu.
Tajność. Po określeniu partnerowania zastępujemy źródło klucza lub wynik KDF przez losowość, pod dokładnym założeniem DH i wyprowadzania kluczy.

Granica zawiera straty przejść oraz wybór użytkownika i sesji. Samo zdanie „podpis, MAC i DH są bezpieczne” nie dowodzi kompozycji. SIGMA wyjaśnia motywację. Formalna analiza rodziny jest w Canetti–Krawczyk, Security Analysis of IKE's Signature-Based Key-Exchange Protocol.

Jeden kompletny krok tajności

Ograniczamy model do jednej uczciwej wymiany bez ujawnień i aktywnych modyfikacji. Redukcja otrzymuje DDH $(g,U,V,T)$ , publikuje $X=U,Y=V$ i używa $T$ jako sekretu wejściowego. Prawdziwe DH daje prawdziwy widok. Losowe $T$ daje niezależne źródło klucza. Potrzebne jest jeszcze założenie o KDF dla tego rozkładu. Zakodowany punkt nie musi być jednostajnym ciągiem bitów.

To algorytm jednego przejścia, nie cały dowód AKE. Aktywny przeciwnik wymaga symulacji innych sesji, uwierzytelniania i ekspozycji.

Trzy składniki NAXOS

Oznaczmy sekrety stałe przez $a,b$ , a wykładniki po haszowaniu przez $x,y$ . Dla partnerowanych sesji:

Ujawnione dane	Łatwo dostępny składnik	Kandydat na trudny składnik
$a,b$	$Y^a$ i $X^b$	$g^{x\cdot y}$
$a,r_B$	$Y^a$	m.in. $g^{b\cdot x}$
$r_A,b$	$X^b$	m.in. $g^{a\cdot y}$
$r_A,r_B$	Same zalążki nie dają wykładników	Zależy od osadzenia instancji

Tabela wybiera przypadek redukcji. Nie dowodzi niemożności policzenia pozostałych wartości.

Od rozróżniania do zapytania o klucz

Wyrocznia $\mathcal K$ daje losowy ciąg dla nowego wejścia. Dopóki przeciwnik nie zapyta o poprawną uporządkowaną krotkę trzech składników i tożsamości sesji testowej, klucz pozostaje od jego widoku niezależny. Sprzężenie gier ogranicza przewagę prawdopodobieństwem takiego zapytania oraz zdarzeń rozbieżności symulacji.

Redukcja osadza instancję DH w kluczach lub wkładach, zależnie od ekspozycji. Monitoruje zapytania $\mathcal K$ . W analizie Gap-DH wyrocznia decyzyjna pozwala rozpoznawać właściwe relacje bez znajomości poszukiwanych wykładników. Z odpowiedniego zapytania wydobywa rozwiązanie. Osobno analizuje zapytania $\mathcal H(r_A,a)$ z brakującym sekretem.

Gap-DH: Gap Diffie–Hellman / Gap Computational Diffie–Hellman. Obliczeniowy problem Diffiego–Hellmana z dostępem do wyroczni rozstrzygającej jego wersję decyzyjną. Słowo gap wskazuje różnicę między obliczeniem a rozpoznaniem wyniku.

To nie jest samo forking lemma. Istotne są wydobycie elementu grupy z zapytania, dobór ekspozycji i spójna tabela. Pełna analiza obejmuje brak partnera, rejestrację kluczy, wszystkie dozwolone ujawnienia oraz straty. NAXOS, §3–4 stanowi źródło modelu i twierdzenia.

Plan samodzielnego dowodu: wypisz stan stron, tabelę zapytań i wiedzę redukcji. Dla każdej gry wskaż założenie, algorytm symulacji, przerwania i stratę. Dopiero potem sumuj granice.

Przykład redukcji NAXOS: ujawnione oba sekrety stałe

Pogłębienie. Rozpatrujemy tylko jedną uczciwą, pasywnie obserwowaną wymianę. Stałe sekrety $a,b$ są znane przeciwnikowi i różne. Zalążki sesji mają po $\kappa$ bitów, są niezależne i nie są ujawniane. Nie udostępniamy innych sesji ani aktywnego interfejsu sieciowego. To szczególny eksperyment pomagający zrozumieć jedno osadzenie instancji, nie pełne twierdzenie eCK.

Redukcja $\mathcal B$ dostaje instancję Gap-CDH $(g,U,V)$ , gdzie $U=g^x$ , $V=g^y$ , ale $x,y$ są nieznane. Może sprawdzać relację DH wyrocznią decyzyjną. Ma obliczyć $g^{x\cdot y}$ . Publikuje wkłady $X=U$ , $Y=V$ . Zna $a,b$ , więc oblicza dwa składniki:

Z_1=V^a,\qquad Z_2=U^b.

Nie zna trzeciego $Z_3=g^{x\cdot y}$ . Wybiera ukryte zalążki $r_A,r_B$ . W modelowym sprzężeniu wyrocznia skalarna ma przy tych dwóch wejściach wartości $x,y$ . Redukcja nie zna tych wartości. Dlatego przerywa, jeżeli przeciwnik zapyta o $\mathcal H(\operatorname{enc}(r_A,a))$ albo $\mathcal H(\operatorname{enc}(r_B,b))$ . Dla pozostałych wejść prowadzi zwykłą, spójną tabelę losowych odpowiedzi.

Ten krok nie zakłada zdolności obliczenia nieznanego wykładnika. Dopóki ukryte wejście nie zostało trafione, widoczne wartości $U,V$ mają właściwy rozkład losowych wkładów. Przy najwyżej $Q_1$ zapytaniach do wyroczni skalarnej prawdopodobieństwo trafienia któregoś zalążka ograniczamy przez $2Q_1/2^\kappa$ . Suma uwzględnia dwie strony. Przyjmujemy granicę obciętą do 1.

Wyrocznia klucza $\mathcal K$ jest niezależna od wyroczni skalarnej. Dla każdego nowego zapytania redukcja:

Sprawdza tożsamości i kolejność pól.
Porównuje dwa pierwsze składniki z obliczonymi $Z_1,Z_2$ .
Dla kandydata $T$ z trzeciego pola pyta wyrocznię decyzyjną, czy $(g,U,V,T)$ jest krotką DH.
Przy odpowiedzi twierdzącej zwraca $T$ jako rozwiązanie CDH.

Pozostałe zapytania $\mathcal K$ otrzymują niezależne losowe klucze, ze spójnym powtarzaniem odpowiedzi. Dopóki nie wystąpi trafienie dokładnego wejścia do $\mathcal K$ , klucz sesji testowej można sprzęgnąć z niezależnym losowym kluczem. Przeciwnik nie ma wtedy informacji o bicie testowym.

Oznaczmy przewagę zgadywania przez $\epsilon$ . Konserwatywna granica tego ograniczonego eksperymentu ma postać:

\epsilon\le \Pr[\mathcal B\text{ rozwiązuje Gap-CDH}] +\min\{1,2Q_1/2^\kappa\}.

Wyrocznia decyzyjna eliminuje potrzebę zgadywania, które zapytanie do $\mathcal K$ jest właściwe. To właśnie rola słowa „Gap”. Bez takiego interfejsu potrzebowalibyśmy innej redukcji lub dodatkowej straty za wybór kandydata.

Pełny dowód NAXOS musi ponadto obsłużyć inne ekspozycje, niepartnerowane sesje, rejestrację kluczy i symulację całej sieci. Powyższy rachunek pokazuje jeden konkretny element tej drogi. Nie uprawnia do przypisania implementacji HKDF wszystkich własności wyroczni losowej.

Publikacje prowadzącego: dalsza ścieżka SIGMA

Do porównania służą Deniable Version of SIGMA Key Exchange Protocol Resilient to Ephemeral Key Leakage oraz Privacy-Oriented Dependency via Deniable SIGMA Protocol. Czytaj je po podstawowym SIGMA i modelach z tego rozdziału.

Przygotuj tabelę z pięcioma kolumnami: stan długoterminowy, stan efemeryczny, dozwolone ujawnienia, uwierzytelnianie i cel zaprzeczalności. Przepisz te elementy z definicji konkretnej pracy. Następnie zaznacz, który krok dowodu zmienia się względem protokołu bazowego. Odporności opisanej w jednym modelu nie przenosimy automatycznie do eCK ani do pełnego odczytu pamięci. To zadanie przygotowuje do lektury naukowej i możliwej pracy magisterskiej, bez zakładania nowego nieopublikowanego wyniku.

Powiązania: C7, L5.