Kryptografia II stopień

Pogłębienie D. UC: bezpieczeństwo wewnątrz większego systemu

W dowodzie niepodrabialności pytaliśmy, czy przeciwnik potrafi wytworzyć nowy podpis. Teraz pytanie jest szersze: czy gotowy protokół można wstawić do większego systemu tak, aby otoczenie nie uzyskało możliwości, których nie dopuszcza specyfikacja? Otoczenie może prowadzić inne rozmowy, wybierać następne wejścia na podstawie wcześniejszych wyników i współpracować z przeciwnikiem.

Odpowiedź porządkuje Universal Composability (UC), czyli framework uniwersalnej kompozycyjności Rana Canettiego. Najpierw opisujemy idealną usługę. Potem pokazujemy, że rzeczywisty protokół można nią zastąpić bez zauważalnej zmiany zachowania całego otoczenia. „Idealna” nie znaczy „zapewniająca wszystko”. Usługa może jawnie ujawniać długość wiadomości i pozwalać przeciwnikowi opóźniać jej dostarczenie.

Podstawą tej ścieżki są definicja i twierdzenie Canettiego oraz Canetti, Stoughton, Varia, EasyUC, §5. W drugim źródle udowodniono w EasyCrypt bezpieczeństwo jednorazowej komunikacji z kluczem idealnym, bezpieczeństwo wymiany Diffiego–Hellmana i ich złożenia. Poniżej rozwijamy ten przykład we własnym zapisie dydaktycznym. Nie przepisujemy składni modułów EasyCrypt.

Cztery role, których nie należy utożsamiać

Środowisko nie jest kolejnym użytkownikiem protokołu. Jest zewnętrznym obserwatorem i sterownikiem eksperymentu. Może znać wiadomość, którą samo podało Alicji. To nie znaczy, że wiadomość została ujawniona symulatorowi. Symulator ma odtworzyć widok także wtedy, gdy środowisko zachowuje swoje wejście dla siebie.

Jedno zdanie zapisane kwantyfikatorami

Zapis $1^\lambda$ oznacza ciąg $\lambda$ jedynek, czyli podanie parametru bezpieczeństwa w zapisie unarnym. Nie jest potęgą liczby jeden. PPT oznacza algorytmy probabilistyczne działające w czasie wielomianowym. Symbole $\forall$ i $\exists$ znaczą „dla każdego” oraz „istnieje”. Kolejność tych słów w definicji jest istotna.

Parametr $\lambda$ określa poziom bezpieczeństwa, a $z$ oznacza dodatkową informację środowiska. Symbol $\operatorname{EXEC}$ oznacza bit zwrócony przez środowisko po całej interakcji. Strony idealne tylko przekazują wejścia i wyjścia między środowiskiem a $\mathcal F$. Dla obliczeniowego UC wymagamy:

PPT oznacza probabilistyczny czas wielomianowy. Granica obowiązuje dla dopuszczonych wejść pomocniczych $z$. Funkcja zaniedbywalna maleje szybciej niż odwrotność dowolnego wielomianu.

1. Wybierz dowolnego rzeczywistego przeciwnika. Nie analizujemy tylko jednej przygotowanej strategii.
2. Zbuduj dla niego jeden symulator. Ten symulator ma działać wobec wszystkich dopuszczonych środowisk, nie być dopasowany do ukrytej wiadomości wybranego środowiska.
3. Porównaj całe interakcje. Nie wystarczy sprawdzić, że pojedynczy szyfrogram wygląda losowo.
4. Uwzględnij kolejność i brak odpowiedzi. Jeżeli sieć może zatrzymać komunikat w świecie rzeczywistym, idealny świat musi pozwalać odtworzyć to zachowanie.

Nie wymagamy identycznych wartości w dwóch niezależnie uruchomionych eksperymentach. Porównujemy rozkłady obserwacji. W dowodzie doskonałym są one równe. W dowodzie obliczeniowym skuteczny test ich rozróżnienia prowadzi do złamania określonego założenia.

Umowa modelu dla dwóch przykładów

Wybieramy celowo mały, kompletny przypadek. Alicja i Bob są uczciwi i nie są przejmowani. Przeciwnik sieciowy jest dowolny, może komunikować się ze środowiskiem, obserwować jawne przesyłki i opóźniać je bez ograniczenia. Nie może zmienić treści przesyłki dostarczanej przez założony kanał uwierzytelniony.

• Sesja: $\mathit{sid}$ jednoznacznie wskazuje rozmowę oraz role Alicji i Boba. Podusługi mają osobne identyfikatory, np. $(\mathit{sid},\text{key})$ i $(\mathit{sid},\text{data})$.
• Wiadomość: jeden element $M$ publicznie ustalonej grupy $G$. Grupa ma pierwszy rząd $q$, generator $g$ i zapis multiplikatywny. Wszystkie wiadomości mają ten sam publiczny format.
• Kanał $\mathcal F_{\mathrm{auth}}$: po wysłaniu zapisuje nadawcę, odbiorcę i treść. Ujawnia je przeciwnikowi. Na zgodę na dostarczenie przekazuje dokładnie zapisaną treść, najwyżej raz. Może czekać bez końca.
• Granica dostępu: środowisko nie może wywoływać prywatnych portów podusług, podszywać się pod ich wyjścia ani czytać ich pamięci. Przejęcia urządzeń nie są ukrytym dodatkowym uprawnieniem.

Jest to profil odpowiadający przykładowi komunikacji z EasyUC. Nie jest to dowód pełnego AKE z kompromitacją kluczy ani dowód bezpieczeństwa surowego DH w Internecie. Uwierzytelnienie jest tutaj zasobem, nie wnioskiem z równania Diffiego–Hellmana.

UC 1. Jednorazowe szyfrowanie z idealnym kluczem

Zaczynamy od pytania: jeśli Alicja i Bob otrzymują naprawdę tajny, jednostajny klucz, czy potrafimy już całkowicie opisać symulator komunikacji? Tak. Ten pierwszy dowód nie potrzebuje założenia o trudności obliczeń.

Krok 1. Opisz usługę, a nie jej implementację

Funkcjonalność $\mathcal F_{\mathrm{SMT}}$ ma przekazać jedną tajną wiadomość:

1. Na poprawne wejście $(\mathsf{send},\mathit{sid},A,B,M)$ od Alicji zapisuje $M$.
2. Wysyła symulatorowi wyłącznie $(\mathsf{pending},\mathit{sid},A,B)$. Nie wysyła $M$. Format jest stały. Dla wiadomości o zmiennej długości należałoby dopisać jawny wyciek długości.
3. Po poprawnym poleceniu $(\mathsf{deliver},\mathit{sid})$ od symulatora przekazuje Bobowi $(\mathit{sid},A,M)$ i oznacza sesję jako zakończoną.
4. Powtórzenia, zły identyfikator i nieprawidłowa kolejność nie powodują kolejnego wyjścia. Bez polecenia dostarczenia nie ma wyjścia Boba.

Ta specyfikacja gwarantuje poufność i autentyczność dostarczonej wiadomości, ale nie gwarantuje dostarczenia. Odmowa usługi jest dopuszczonym zachowaniem sieci.

Krok 2. Nazwij zasób kluczowy

Idealna usługa $\mathcal F_{\mathrm{KE}}$ uzgadnia jeden klucz $K\overset{\$}{\leftarrow}G$ dla określonej sesji i pary stron. Jej harmonogram jest istotny:

1. Po rozpoczęciu przez Alicję ogłasza przeciwnikowi rozpoczęcie sesji, bez klucza.
2. Po pierwszej zgodzie sieci losuje $K$ i przekazuje go prywatnie Bobowi.
3. Bob zgłasza gotowość do drugiej fazy. Usługa ogłasza tę fazę przeciwnikowi.
4. Po drugiej zgodzie przekazuje ten sam $K$ prywatnie Alicji.

To kolejność zgodna z późniejszym dwukomunikatowym DH. Wewnątrz protokołu szyfrowania Bob automatycznie zgłasza gotowość po odebraniu klucza. Żadna ze stron nie eksportuje klucza do aplikacji. Ta granica jest potrzebna: poufność OTP znika, jeżeli aplikacja otrzyma maskę wraz z szyfrogramem.

Krok 3. Wykonaj protokół rzeczywisty

Protokół $\rho$ używa podusług $\mathcal F_{\mathrm{KE}}$ i $\mathcal F_{\mathrm{auth}}$. Alicja czeka na swój klucz, oblicza $C=M\cdot K$ i wysyła $C$ przez kanał uwierzytelniony. Bob po odebraniu oblicza:

Jest to OTP w grupie. Działanie grupowe zastępuje XOR. Nie należy zastępować go przez XOR tekstowego kodowania dowolnego punktu DH i ogłaszać tajności doskonałej. Dla tekstów można wprowadzić jawne odwracalne kodowanie do grupy. W tym przykładzie wiadomości od razu są elementami $G$.

Krok 4. Skonstruuj symulator bez wiadomości

Symulator $\mathcal S_{\mathrm{OTP}}$ uruchamia wewnątrz kopię danego $\mathcal A$. Przekazuje jej komunikację ze środowiskiem bez zmiany. Gdy $\mathcal F_{\mathrm{SMT}}$ zgłasza oczekującą sesję:

1. Odtwarza powiadomienie pierwszej fazy usługi kluczowej.
2. Czeka na zgodę $\mathcal A$, a następnie odtwarza powiadomienie drugiej fazy.
3. Po drugiej zgodzie losuje sam szyfrogram $\widehat C\overset{\$}{\leftarrow}G$. Nie potrzebuje ani $M$, ani klucza.
4. Pokazuje $\mathcal A$ uwierzytelnioną przesyłkę z $\widehat C$ i właściwymi metadanymi.
5. Gdy $\mathcal A$ pozwala ją dostarczyć, wysyła polecenie dostarczenia do $\mathcal F_{\mathrm{SMT}}$.
6. Wiadomość Bobowi przekazuje sama $\mathcal F_{\mathrm{SMT}}$. Symulator nie musi jej poznać ani odszyfrować $\widehat C$.

Najważniejszy moment: symulator odtwarza to, co widać w sieci. Nie odtwarza tajnej pamięci uczciwych urządzeń. Idealna funkcjonalność odpowiada za poprawne wyjście.

Krok 5. Udowodnij równość rozkładów

Ustal dowolną wiadomość $m\in G$. Dla każdego możliwego szyfrogramu $c\in G$ istnieje dokładnie jeden klucz, który go tworzy:

Mapa $k\mapsto m\cdot k$ jest bijekcją grupy. Dlatego $C$ jest jednostajny także wtedy, gdy środowisko zna $m$. Taki sam rozkład ma $\widehat C$ losowany przez symulator.

To dopiero część dowodu. Niezmiennik interakcji mówi dodatkowo, że po każdym kroku oba światy mają ten sam rozkład dotychczasowej publicznej historii, tę samą fazę oczekiwania i tę samą liczbę wyjść Boba.

Indukcja po aktywacjach zachowuje ten niezmiennik. Można sprzęgnąć publiczne losowania tak, aby historie były identyczne. To narzędzie dowodowe, a nie dodatkowy kanał wiedzy symulatora. Nie musimy zakładać, że przeciwnik w końcu dostarczy przesyłkę.

Krok 6. Zapisz dokładny wniosek

Górne oznaczenie $\rho^{\mathcal F_{\mathrm{KE}},\mathcal F_{\mathrm{auth}}}$ wymienia usługi idealne, do których protokół $\rho$ ma dostęp. To nie potęga. Jawnie wskazuje, że twierdzenie zakłada idealne dostarczenie klucza i uwierzytelnianie, zamiast dowodzić ich od podstaw w tym samym kroku.

W powyższym modelu, przy świeżym kluczu dla jednej wiadomości, protokół $\rho^{\mathcal F_{\mathrm{KE}},\mathcal F_{\mathrm{auth}}}$ doskonale realizuje $\mathcal F_{\mathrm{SMT}}$. Błąd rozróżniania wynosi zero. Ten wynik nie obejmuje przejęcia urządzenia, powtórnego użycia klucza ani sieci bez uwierzytelnienia. W EasyUC odpowiada mu równość eksperymentów w §5.5, lemat nazwany w kodzie „smc_security2”.