Kryptografia II stopień

UC 2. Zastąpienie idealnego klucza protokołem DH

Pierwszy przykład miał idealny zasób kluczowy. Teraz musimy go zrealizować. Robimy to w dwóch etapach: najpierw dowód dla samej wymiany klucza, potem użycie tego dowodu wewnątrz szyfrowania.

Krok 1. Zachowaj ten sam interfejs

Wymiana $\pi_{\mathrm{DH}}$ korzysta z dwóch osobnych uwierzytelnionych przesyłek:

1. Alicja losuje $a\overset{\$}{\leftarrow}\mathbb Z_q$ i wysyła $U=g^a$ do Boba.
2. Po dostarczeniu $U$ Bob losuje $b\overset{\$}{\leftarrow}\mathbb Z_q$, oblicza $K_B=U^b$ i przekazuje klucz swojej aplikacji.
3. Po sygnale gotowości aplikacji Bob wysyła $V=g^b$ do Alicji.
4. Po dostarczeniu $V$ Alicja przekazuje aplikacji $K_A=V^a$.

Obie strony otrzymują $g^{a\cdot b}$. Aplikacja Boba dostaje klucz wcześniej, dokładnie jak w $\mathcal F_{\mathrm{KE}}$. Kiedy aplikacją jest OTP z poprzedniego przykładu, „przekazanie aplikacji” oznacza wewnętrzne przekazanie do modułu szyfrowania, nie ujawnienie środowisku.

Krok 2. Zbuduj symulator wymiany klucza

Symulator $\mathcal S_{\mathrm{DH}}$ wybiera własne niezależne wykładniki $\widehat a,\widehat b$ i pokazuje $\widehat U=g^{\widehat a}$ oraz $\widehat V=g^{\widehat b}$ jako komunikaty uwierzytelnione. Każdą zgodę przeciwnika na dostarczenie odpowiedniego komunikatu przekłada na zgodę dla właściwej fazy $\mathcal F_{\mathrm{KE}}$.

Sama funkcjonalność losuje klucz $R\overset{\$}{\leftarrow}G$. Symulator nie zastępuje go wartością $g^{\widehat a\cdot\widehat b}$. Powstaje więc pozorna trudność: publiczna rozmowa sugeruje DH, lecz rzeczywisty idealny klucz jest od niej niezależny. Właśnie tę różnicę musi ukryć założenie DDH.

Krok 3. Wskaż dokładnie jedyną zmianę obliczeniową

Założenie Decisional Diffie–Hellman dotyczy nierozróżnialności:

Lewy rozkład ma algebraicznie powiązany trzeci element. W prawym trzeci element jest niezależny i jednostajny. Samo CDH nie wystarcza do tego kroku: potrzebujemy argumentu o rozróżnianiu, nie tylko o niemożności obliczenia klucza.

Dobór grupy jest częścią założenia. W grupie z efektywnie dostępnym symetrycznym pairingiem można testować relację DH przez porównanie $e(U,V)$ z $e(g,T)$. Nie przenosimy więc tego dowodu automatycznie do każdej grupy używanej w pozostałych demonstratorach.

Krok 4. Zbuduj redukcję, która nie zna wykładników

Przypuśćmy, że pewne środowisko $\mathcal Z$, współpracując z $\mathcal A$, zauważa różnicę między prawdziwym DH a idealnym kluczem z symulowaną rozmową. Redukcja $\mathcal B$ dostaje z eksperymentu DDH tylko trójkę $(U,V,T)$ i wykonuje:

1. Uruchamia programy $\mathcal Z$ i $\mathcal A$ wraz z pozostałym otoczeniem.
2. Jako pierwszą uwierzytelnioną przesyłkę pokazuje $U$. Na zgodę na jej dostarczenie zwraca aplikacji Boba klucz $T$.
3. Po gotowości Boba pokazuje drugą przesyłkę $V$. Na zgodę na jej dostarczenie zwraca aplikacji Alicji ten sam $T$.
4. Obsługuje resztę komunikacji bez zmiany. Nie oblicza logarytmów dyskretnych.
5. Zwraca bit, który zwróciło $\mathcal Z$.

Gdy $T=g^{a\cdot b}$, jest to rozkład rzeczywistej wymiany. Gdy $T=g^r$, jest to rozkład idealnego klucza i niezależnej publicznej rozmowy. Wylosowanie całej trójki wcześniej, zamiast losowania wykładników dopiero po kolejnych aktywacjach, nie zmienia widoku, bo niewykorzystane wartości pozostają ukryte i niezależne.

Redukcja i symulator mają różne role. Redukcja otrzymuje $T$ z zadania DDH, aby porównać dwa eksperymenty. Symulator w idealnym świecie nie otrzymuje sekretnego klucza z $\mathcal F_{\mathrm{KE}}$.

Krok 5. Powiąż przewagi i czas pracy

Oznaczmy przez $\Delta_{\mathrm{KE}}$ różnicę prawdopodobieństw zwrócenia jedynki przez środowisko w obu światach. Dla zbudowanej redukcji:

Dla pojedynczej instancji nie zgadujemy sesji ani zapytania, więc nie pojawia się tutaj czynnik $1/Q$. Redukcja wykonuje $\mathcal Z$, $\mathcal A$ i wielomianową obsługę komunikatów. Jeżeli otoczenie działa w czasie wielomianowym, redukcja również. EasyUC, §5.4, podaje to jako „ke_security”. Osobno trzeba uzasadnić czas pracy, nie tylko przekształcić wzór na przewagę.

Krok 6. Złóż dwa już uzyskane wyniki

Niech $H_0$ oznacza cały rzeczywisty system DH + OTP. W $H_1$ zastępujemy tylko wymianę klucza przez $\mathcal F_{\mathrm{KE}}$ z symulatorem $\mathcal S_{\mathrm{DH}}$. W $H_2$ zastępujemy również OTP przez $\mathcal F_{\mathrm{SMT}}$ z odpowiednim symulatorem.

Środowiskiem dla dowodu DH jest teraz oryginalne środowisko razem z modułem OTP i pozostałymi częściami systemu. Ta obserwacja pozwala legalnie zastosować pierwszy wynik wewnątrz większego programu. Nie zakładamy, że aplikacja ignoruje klucz. Może wykonywać na nim obliczenia, które redukcja również wykonuje.

Pierwszy koszt pochodzi z DDH. Drugi składnik jest zerowy dzięki bijekcji OTP. Końcowy symulator uruchamia symulator OTP, wewnątrz niego symulator DH, a dopiero w nim przeciwnika. W notacji parametryzowanych programów źródła jest to $\mathcal S_{\mathrm{OTP}}(\mathcal S_{\mathrm{DH}}(\mathcal A))$.

Wniosek: DH + jednorazowe szyfrowanie grupowe, przy uwierzytelnionych przesyłkach, realizuje usługę tajnego przekazania jednej wiadomości w zadeklarowanym modelu. To jest odpowiednik końcowego lematu „smc_security” w §5.5 EasyUC. Nie jest to twierdzenie, że sam DH zapewnia uwierzytelnienie, że dowolny OTP można powtarzać ani że przeglądarkowa animacja stanowi formalną weryfikację.

UC 3. Jak samodzielnie zbudować i sprawdzić dowód

Siedem pól na kartce przed pierwszą redukcją

1. Cel: napisz wejścia i wyjścia idealnej funkcjonalności. Kto ma się czego dowiedzieć?
2. Uprawnienia: zapisz wycieki, możliwe przejęcia, opóźnienia, przerwania i dopuszczalne błędne wyjścia.
3. Zasoby: wymień uwierzytelnione kanały, klucze lub inne podusługi. CRS (common reference string) to wspólny ciąg referencyjny o określonym rozkładzie, dostępny uczestnikom, jeśli model go zakłada. Nie ukrywaj takich zasobów w słowie „bezpieczny”.
4. Algorytm symulatora: dla każdego komunikatu określ, co wie symulator i skąd bierze odpowiedź. Działaj online, bez zaglądania do przyszłych wejść środowiska.
5. Relacja stanów: po każdym zewnętrznie widocznym zdarzeniu wskaż, co musi się zgadzać między światami. Sprawdź także błędne i powtórzone komunikaty.
6. Koszt różnicy: podziel przejścia na dokładne równości rozkładów i redukcje do konkretnych założeń. Policz czas, liczbę instancji oraz ewentualną stratę.
7. Kompozycja: sprawdź, czy podmieniany moduł ma ten sam interfejs, model przejęć, wycieki i harmonogram wyjść. Kontroluj identyfikatory i dostęp do współdzielonego stanu.

Dlaczego nie wystarczy poprzedni rewinding

W dowodzie Schnorra symulator lub ekstraktor może cofnąć analizowany program do określonego stanu. W UC środowisko działa równolegle z innymi procesami i może w międzyczasie uzyskać zewnętrzne informacje. Symulator nie ma ogólnego prawa cofnąć całego środowiska wraz z nimi.

Nasze dwa symulatory są straight-line: odpowiadają w jednym przebiegu i nie cofają $\mathcal Z$. To nie jest definicja zakazująca każdego użycia rewindingu we wszystkich możliwych dowodach. Jest to ostrzeżenie, że symulacji pojedynczej rozmowy nie wolno bez dowodu przenieść do UC.

Podobnie model wyroczni losowej i UC rozwiązują inne problemy. ROM idealizuje konkretną usługę haszującą. UC opisuje bezpieczeństwo protokołu w otoczeniu innych procesów. Jeżeli dowód UC potrzebuje wyroczni, trzeba określić jej interfejs, dostęp i możliwość programowania. Sam skrót „ROM” nie daje twierdzenia o kompozycji.

Cztery kontrprzykłady, które ujawniają pominięte założenie

• Usuń uwierzytelnienie szyfrogramu. Przeciwnik zastępuje $C$ przez $C\cdot\Delta$, gdzie $\Delta\neq1_G$. Bob otrzymuje $M\cdot\Delta$. Idealna usługa nie dopuszcza takiej zmiany, więc można rozróżnić światy. OTP chroni tajność, ale sam nie zapewnia integralności.
• Użyj ponownie klucza. Z $C_1=M_1\cdot K$ i $C_2=M_2\cdot K$ otrzymujemy $C_1\cdot C_2^{-1}=M_1\cdot M_2^{-1}$. Nie ma już dwóch niezależnych jednostajnych szyfrogramów.
• Pozwól na adaptacyjne przejęcie. Po wcześniejszej symulacji sieci trzeba ujawnić spójną pamięć urządzenia. Nasz symulator nie konstruuje takiego otwarcia. To nowe zobowiązanie dowodowe, a nie automatyczny wniosek z przypadku bez przejęć.
• Ukryj w specyfikacji możliwość opóźnienia. Jeśli idealna usługa musi natychmiast zwrócić wynik, a rzeczywista sieć może go zatrzymać, samo oczekiwanie pozwala odróżnić światy.

Co naprawdę pozwala podmieniać twierdzenie o kompozycji

Schematycznie, dla zgodnych interfejsów i dopuszczonych protokołów:

Relacja $\succeq_{\mathrm{UC}}$ oznacza „UC-realizuje”. Symbol $\rho^{\mathcal F}$ oznacza program korzystający z idealnej podusługi, a $\rho^\pi$ ten sam program z jej implementacją. Twierdzenie nie mówi, że dowolne dwa osobno bezpieczne programy są bezpieczne po sklejeniu.

Przy wielu osobnych sesjach podmieniamy kolejne instancje i sumujemy ich błędy hybrydowe. Wielomianowa liczba zaniedbywalnych błędów pozostaje zaniedbywalna. Jeżeli sesje współdzielą klucz, wspólną bazę albo globalną wyrocznię, zwykłe rozumowanie o niezależnych kopiach może nie wystarczyć. Należy modelować ten zasób i zastosować właściwe twierdzenie o współdzielonym stanie lub ustawieniu globalnym.

UC stawia silne wymagania. Dla pewnych zadań nie istnieje realizacja w modelu bez dodatkowego zaufania. Przykładem są dwustronne zobowiązania UC w modelu plain, przy możliwości złośliwego przejęcia jednej ze stron. CRS, czyli wspólny ciąg referencyjny, jest jednym z rozważanych dodatkowych zasobów. Jego rozkład i sposób udostępnienia należą do modelu, nie do szczegółów implementacyjnych.

Sprawdź zrozumienie

1. W dowodzie OTP środowisko zna $M$, ale symulator nie zna $M$. Dlaczego nie ma sprzeczności? Wskaż, kto przekazuje wynik Bobowi.
2. Opisz stan obu światów, gdy przeciwnik zatrzyma pierwszą, drugą albo ostatnią przesyłkę. Które wyjścia już nastąpiły, a które jeszcze nie?
3. Zbuduj środowisko rozróżniające po usunięciu uwierzytelnienia. Nie odzyskuj klucza. Wystarczy sprawdzić wynik Boba.
4. Dlaczego redukcja DDH może przekazać $T$ aplikacji, chociaż nie zna $a$ ani $b$? Dlaczego tego samego dostępu nie przypisujemy symulatorowi?
5. Przenieś konstrukcję do dwóch sesji. Podaj oddzielne identyfikatory i losowania. Następnie wskaż dokładnie, który krok psuje współdzielenie jednej maski OTP.

Źródła: Canetti, Universally Composable Security, Canetti–Stoughton–Varia, EasyUC, §5.1–5.5, wykłady Canettiego w MIT, definicja i kompozycja. Materiał EasyUC jest dostępny na licencji CC BY. Rysunki i polskie objaśnienia są autorskim opracowaniem dydaktycznym. Wynik mechanicznej weryfikacji cytujemy za publikacją. Zamieszczone tutaj interakcje ilustrują stany i rachunek, nie zastępują proof assistanta.

CC BY

Creative Commons Attribution. Licencja Creative Commons z warunkiem uznania autorstwa.