Kryptografia II stopień

W8. Identyfikacja i granica chronionego urządzenia

Identyfikacja sprawdza, czy aktualny rozmówca posiada sekret. Trzeba wskazać, jakie wcześniejsze rozmowy przeciwnik obserwuje lub sam prowadzi. Pasywna obserwacja i aktywny trening są różnymi modelami.

Trzy błędne poprawki: poprawność zostaje, bezpieczeństwo znika

Punktem odniesienia jest Schnorr. Celowo zmienimy jego odpowiedź i odpowiednie równanie sprawdzające. Uczciwe wykonania nadal będą akceptowane. Dla każdego wariantu podamy jednak strategię oszusta, który nie zna sekretu. To przykłady z analizy protokołów, nie alternatywne bezpieczne konstrukcje.

1. Odpowiedź afiniczna. Zastąpmy odpowiedź przez $s=u+a+c$, a weryfikację przez $g^s=X\cdot A\cdot g^c$. Z obserwowanego $(X_0,c_0,s_0)$ przeciwnik wybiera własne $r$ i tworzy nowe zobowiązanie $X_1=X_0\cdot g^r$. Gdy otrzyma nowe wyzwanie $c_1$, odpowiada:

Sprawdzenie przechodzi, bo $g^{s_1}=X_1\cdot A\cdot g^{c_1}$. Przeciwnik nie znał $u$ ani $a$. Wyeliminował stare wyzwanie i wstawił nowe. Pamięć poprzednich zobowiązań nie naprawia problemu, bo $X_1$ może być nowe.

2. Wyzwanie przed całym nawiasem. Niech $s=c\cdot(u+a)$, a weryfikacja sprawdza $g^s=(X\cdot A)^c$. Oszust losuje $t$ i przed wyzwaniem wysyła $X=g^t\cdot A^{-1}$. Potem odpowiada $s=c\cdot t$. Nie potrzebował nawet wcześniejszego transkryptu. Ułożył znany sobie logarytm całej podstawy, którą weryfikator podniesie do wyzwania.

3. Brak związania z tożsamością. Dowodzący miał wysyłać $W=g^{a\cdot u}$, a weryfikator sprawdzać $g^s=W^c$. Oszust po prostu wysyła $W=g^t$ dla własnego $t$ i odpowiada $s=t\cdot c$. Równanie niczego nie sprawdza względem klucza $A$. Sam udział tajnego $a$ w uczciwym algorytmie nie zmusza oszusta do jego użycia.

W każdym przypadku atak jest chronologicznie wykonalny. Pierwsza wiadomość nie zależy od przyszłego wyzwania. To ważny test poprawności analizy: „rozwiązanie” wymagające wcześniejszego poznania świeżej losowej wartości weryfikatora nie jest atakiem w tym modelu.

Relay to jeszcze inny cel ochrony

Oszust może także przekazywać w czasie rzeczywistym zobowiązanie uczciwej osoby, wyzwanie weryfikatora i odpowiedź. Nie poznaje wtedy klucza. Zwykły eksperyment podszycia po zakończeniu treningu wyklucza taki bieżący dostęp do dowodzącego. Jeśli rzeczywisty scenariusz go dopuszcza, trzeba osobno zapewnić właściwe powiązanie kanału, czynności lub fizycznej odległości. Nie naprawia tego większa grupa algebraiczna.

Okamoto: inny świadek i inny punkt osadzenia

Ten sam interfejs identyfikacji, inna konstrukcja. Pozostają Setup, KeyGen oraz interaktywne $\mathsf P$ i $\mathsf V$. Zmienia się postać sekretu, zobowiązania i odpowiedzi. Poniżej KeyGen tworzy parę skalarów. Commit używa dwóch świeżych skalarów, Respond zwraca parę odpowiedzi, a Check sprawdza jedno równanie. Oba generatory należą tutaj do tej samej grupy. To nie są grupy źródłowe pairingu.

W Schnorrze świadkiem jest jeden wykładnik. W Okamoto jest nim para wykładników $(a_1,a_2)$ reprezentująca publiczny element $A$. Generatory $g_1,g_2$ należą do tej samej grupy $G$ pierwszego rzędu $q$. Ich indeksy odróżniają bazy. Nie oznaczają grup źródłowych pairingu $G_1,G_2$. Nie zakładamy znajomości logarytmu jednego generatora względem drugiego.

1. Klucz: losujemy parę $(a_1,a_2)\overset{\$}{\leftarrow}\mathbb Z_q^2$ i publikujemy $A=g_1^{a_1}\cdot g_2^{a_2}$, odrzucając $A=1_G$.
2. Zobowiązanie: dla nowej rozmowy losujemy niezależne $u_1,u_2\overset{\$}{\leftarrow}\mathbb Z_q$ i wysyłamy $X=g_1^{u_1}\cdot g_2^{u_2}$.
3. Wyzwanie: weryfikator losuje $c\overset{\$}{\leftarrow}\mathbb Z_q$ po otrzymaniu $X$.
4. Odpowiedź: dowodzący wysyła dwa skalary $s_1=u_1+c\cdot a_1$, $s_2=u_2+c\cdot a_2$.

Sprawdzenie ponownie opiera się na mnożeniu potęg:

Przejście do krzywej: oznaczmy te dwie bazy przez $P,Q\in G$. Wtedy $A=a_1\cdot P+a_2\cdot Q$, $X=u_1\cdot P+u_2\cdot Q$, a kontrola ma postać $s_1\cdot P+s_2\cdot Q=X+c\cdot A$. Odpowiedzi $s_1,s_2$ nadal są skalarami. Klasyczny Okamoto nie wymaga pairingu. Pairing pojawia się dopiero w osobno opisanej modyfikacji.

Ekstrakcja pary $(a_1,a_2)$ daje reprezentację. Aby zredukować atak do DL jednego generatora względem drugiego, trzeba porównać ją z reprezentacją zaszytą przez redukcję. Dwa równania same nie kończą tego dowodu.

Pełny dowód: aktywne sesje, nierozróżnialność świadków i rewinding. Zobacz, dlaczego redukcja zna jedną reprezentację, a potrzebuje drugiej, oraz skąd biorą się wszystkie czynniki w prawdopodobieństwie sukcesu.

Ujawnienie, ustawienie i reset

• Ujawnienie: przeciwnik poznaje $u$. Przy $c\ne0$ odzyskuje $a=(s-u)\cdot c^{-1}$.
• Ustawienie: narzuca znane $u$. Rachunek jest ten sam, lecz interfejs ataku inny.
• Reset: niekoniecznie znany nonce powtarza się. Dwie odpowiedzi eliminują go przez odejmowanie.

To wspólna algebra liniowa, ale różne uprawnienia. Przy resecie nonce może pozostać nieznany. Wystarczy jego powtórzenie. Przy ustawieniu przeciwnik zna narzuconą wartość. Przy ujawnieniu poznaje wartość wybraną przez urządzenie. Model powinien wskazać moment udostępnienia, możliwość wyboru wiadomości i liczbę przebiegów.

Rozszerzenie modelu może wymusić zmianę architektury. Jeżeli celem jest ochrona tożsamości mimo wycieku nonce, klasyczna skalarna odpowiedź Schnorra nie spełnia tego celu. Samo ponowne sformułowanie dowodu tego nie zmieni. Trzeba zmienić konstrukcję, ograniczyć interfejs urządzenia lub inaczej rozdzielić sekrety. Jeżeli przeciwnik dostaje cały klucz długoterminowy, model odporności tylko na nonce przestaje być właściwym opisem.

Odpowiedź jako element grupy

Cel modyfikacji: zachować trzy wiadomości identyfikacji, ale nie wydawać skalarnej odpowiedzi, z której przy znanym nonce można wyliczyć klucz. Odpowiedź będzie elementem grupy, a kontrola użyje pairingu. To zmiana konstrukcji i modelu urządzenia, nie tylko sposobu zapisu.

Najpierw zachowajmy notację potęgową. Niech $g_2\in G_2$, $A=g_2^a$ i $X=g_2^u$. Hash $B=\mathcal H_{G_1}(\operatorname{enc}(X,c))$ daje element $G_1$. Zamiast ujawniać skalar $s=u+a\cdot c$, wysyłamy jego obraz:

Lewą stronę równania można przepisać jako $e(B,g_2)^{u+a\cdot c}$. Prawa strona jest tym samym elementem przez dwuliniowość. Chroniona operacja zwraca $B^a$, a część robocza łączy ten wynik z własnym $B^u$. Nie potrzebuje do tego odczytu $a$. To opis rachunku przy założonym podziale urządzenia, nie dowód bezpieczeństwa tego podziału.

Realizacja na krzywej: zapis addytywny tej samej konstrukcji. Rysunek zachowuje powyższe potęgi. Poniższe równanie wyjaśnia operacje wykonywane przez MCL:

Niech $P_2\in G_2$, $A=a\cdot P_2$, $X=u\cdot P_2$ i $e:G_1\times G_2\to G_T$. Wyznaczamy $B=\mathcal H_{G_1}(\operatorname{enc}(X,c))$ oraz $S=(u+a\cdot c)\cdot B$. Sprawdzamy:

Przy znanym $u$ i $c\ne0$ można obliczyć punkt $c^{-1}\cdot(S-u\cdot B)=a\cdot B$, ale nie otrzymuje się wprost $a$. Znaczenie punktu zależy od powiązania bazy z kontekstem i modelu zapytań. Ta obserwacja nie dowodzi odporności na wszystkie wycieki.

Granica zaufania: moduł przechowuje $a$ i zwraca $Z=B^a$. Zwykły kod liczy $S=B^u\cdot Z^c$. W realizacji na krzywej są to odpowiednio $Z=a\cdot B$ i $S=u\cdot B+c\cdot Z$. To dydaktyczne rozłożenie równania i założony interfejs urządzenia, nie fizyczny HSM w przeglądarce. Ujawnienie $a$ łamie założenie. Inne użycia sekretu, np. w AKE, wymagają osobnej analizy.

Porównania i źródła publikacyjne: Schnorr, Okamoto.

W8a. Identyfikacja, transkrypt i zaprzeczalność

Identyfikacja ma przekonać rozmówcę teraz. Podpis ma dać dokument sprawdzalny również później i przez inne osoby. Nie są to zamienne cele. Pytamy więc nie tylko, czy weryfikacja przyjmuje, ale także, kto mógł wytworzyć jej zapis i komu ten zapis coś udowadnia.

Przyjmijmy grupę rzędu $q$, gdzie $q$ jest liczbą pierwszą, generator $g$, sekret $a$ i uwierzytelniony klucz publiczny $A=g^a$. Opis i diagramy zachowują ten zapis potęgowy. Operacje na skalarach wykonujemy w $\mathbb Z_q$. W tym rozdziale $\mathcal H$ zwraca skalar. Osobny skrót $\mathcal D_\ell$ zwraca $\ell$ bitów i haszuje kanoniczny zapis elementu grupy, a nie mapuje do grupy.

Schnorr: kolejność, która oddziela symulację od ataku

Weryfikator nie wybiera pierwszego komunikatu. Najpierw dowodzący ustala zobowiązanie, dopiero potem otrzymuje wyzwanie:

1. Dowodzący losuje $u\overset{\$}{\leftarrow}\mathbb Z_q$ i wysyła $X=g^u$.
2. Weryfikator losuje $c\overset{\$}{\leftarrow}\mathbb Z_q$ i wysyła $c$.
3. Dowodzący odsyła $s=u+a\cdot c$. Weryfikator sprawdza $g^s=X\cdot A^c$.

Uczciwy transkrypt da się wygenerować bez $a$. Symulator losuje niezależnie $\widehat c,\widehat s\overset{\$}{\leftarrow}\mathbb Z_q$ i oblicza $\widehat X=g^{\widehat s}\cdot A^{-\widehat c}$. Równanie weryfikacji zachodzi z definicji. Dla każdego ustalonego $c$ przekształcenie $u\mapsto s=u+a\cdot c$ jest bijekcją. Dlatego symulowane trójki mają dokładnie taki rozkład jak trójki z uczciwej rozmowy. To argument honest-verifier zero knowledge, czyli wiedzy zerowej względem uczciwego weryfikatora.

Nie oznacza to jednak umiejętności podszycia się w czasie rzeczywistym. Symulator konstruuje zobowiązanie po wyborze wyzwania i odpowiedzi. Atakujący w protokole musi wysłać zobowiązanie przed poznaniem wyzwania. Gdybyśmy odwrócili te dwa komunikaty bez innych zmian, symulator stałby się rzeczywistym algorytmem podszycia. Ten błąd porównaj z atakami na identyfikację.

Stinson–Wu: dlaczego weryfikator może zacząć

Wariant Stinsona–Wu z wcześniejszych wykładów nie polega na przestawieniu strzałek Schnorra. Pierwszy komunikat zawiera element grupy Diffiego–Hellmana i skrót oczekiwanej odpowiedzi. Weryfikator zna tę odpowiedź jeszcze przed rozmową, ale osoba podsłuchująca nie zna jego wykładnika.

1. Weryfikator losuje tajne $r\overset{\$}{\leftarrow}\mathbb Z_q^*$, oblicza $C=g^r$ i $h=\mathcal D_\ell(A^r)$, po czym wysyła parę $(C,h)$.
2. Dowodzący sprawdza poprawność punktu $C$ i oblicza $Z=C^a$. Najpierw sprawdza $\mathcal D_\ell(Z)=h$. Przy niezgodności przerywa bez wysyłania $Z$.
3. Przy zgodności dowodzący odsyła $Z$. Weryfikator akceptuje wtedy i tylko wtedy, gdy $Z=A^r$.

W grupie krzywej jest to dokładnie $C=r\cdot P_2$ oraz $Z=a\cdot C=r\cdot A$. Nie potrzebujemy pairingu. Dwa komunikaty nie oznaczają dwóch prostych operacji, bo przed odpowiedzią trzeba wykonać kontrolę skrótu. Pominięcie kontroli oddawałoby przeciwnikowi usługę obliczania $C^a$ dla dowolnego podanego $C$.

To operacyjny wariant z protokołu 2.2 Stinsona–Wu. Używamy niezerowych sekretów i niejednostkowych punktów, zgodnie z przykładem ze slajdów. W oryginalnym opisie $r$ jest losowane z całego $\mathbb Z_q$. Przy porównywaniu rozkładów symulatora i protokołu trzeba zachować tę samą dziedzinę losowania. Implementacja odbierająca cudze punkty musi sprawdzić ich przynależność do właściwej podgrupy przed mnożeniem przez sekret. Demonstrator wytwarza wszystkie punkty lokalnie z generatora tej podgrupy. Nie implementuje przyjmowania komunikatów z sieci.

Zaprzeczalność: symulator bez klucza tajnego

„Weryfikator może sam wygenerować całość” oznacza istnienie konkretnego algorytmu. Nazywamy go symulatorem, czyli generatorem zapisu rozmowy, który nie potrzebuje udziału dowodzącego. Nie wystarczy, że zapis spełnia równania weryfikacji. Musi także mieć odpowiedni rozkład, aby obserwator nie mógł odróżnić go od prawdziwego zapisu. Tutaj uzyskamy dokładnie ten sam rozkład.

Wejście publiczne: parametry $pp=(G,q,g,\mathcal D_\ell)$ oraz poprawny, niejednostkowy klucz $A\in G$. Sekret niebędący wejściem: wykładnik $a$, dla którego $A=g^a$. Wyjście: transkrypt $\tau$, czyli uporządkowany zapis dwóch komunikatów:

Symulator jest efektywnym algorytmem probabilistycznym. Ma własną losowość, ale nie dostaje cudzego sekretu ani dostępu do urządzenia dowodzącego. Losowany przez niego $r$ nie jest odzyskanym sekretem rzeczywistej sesji. Jest nową, niezależną wartością, która służy do zbudowania nowego zapisu. Tak jak w omawianym profilu protokołu, losowanie jest jednostajne z $\mathbb Z_q^*$.

Dlaczego nie da się rozpoznać pochodzenia zapisu

Ustalmy poprawne $pp,A$ oraz odpowiadający sekret $a$. Niech $\mathsf{Real}(pp,A,a)$ oznacza transkrypt pełnej, uczciwej rozmowy z poprzedniego diagramu. W tym eksperymencie dowodzący rzeczywiście używa $a$. Natomiast $\mathsf{Sim}(pp,A)$ oznacza wynik algorytmu powyżej. Porównujemy rozkłady wyników, nie zakładamy, że dwa niezależne uruchomienia dadzą identyczne bajty.

Dowód w trzech krokach:

1. W obu eksperymentach $r$ jest losowane jednostajnie z tego samego zbioru $\mathbb Z_q^*$. Możemy więc porównać wyniki dla każdego ustalonego $r$.
2. Pierwszy punkt jest w obu przypadkach równy $C=g^r$. Odpowiedź prawdziwego dowodzącego oraz odpowiedź utworzona przez symulator są równe:

3. Ta sama funkcja $\mathcal D_\ell$ zastosowana do tego samego elementu daje ten sam $h$. Dla każdego $r$ otrzymujemy więc ten sam transkrypt, z tym samym prawdopodobieństwem. Stąd:

Symbol $\equiv$ oznacza tutaj równość rozkładów. Formalnie, dla dowolnego testu $\mathcal T$, który otrzymuje tylko $pp,A,\tau$ i zwraca bit, zachodzi:

Prawdopodobieństwa obejmują losowość tworzenia transkryptu i ewentualną losowość testu. To równość dokładna, a nie tylko nierozróżnialność dla testów o ograniczonym czasie działania. Ten konkretny argument nie wymaga trudności logarytmu dyskretnego ani modelu wyroczni losowej. Wynika z równości grupowej i identycznego sposobu losowania. Założenia bezpieczeństwa są potrzebne do innych twierdzeń, w szczególności do analizy podszywania.

Co to daje dla zaprzeczalności

Sam transkrypt uczciwej rozmowy nie jest przenośnym dowodem udziału właściciela klucza. Weryfikator mógł stworzyć taki zapis bez niego. Osoba trzecia, która zna tylko dane publiczne i ten zapis, nie ma testu pozwalającego ustalić jego pochodzenie. To właśnie uzasadnienie zaprzeczalności takiego transkryptu. Nie twierdzimy, że symulator usuwa nagrania, poświadczenia urządzenia lub inne dowody pochodzące spoza protokołu.

Nie jest to algorytm podszywania się w żywej rozmowie. Symulator sam wybiera $r$, więc może obliczyć $A^r$. Atakujący, który otrzymał od uczciwego weryfikatora cudze $(C,h)$, nie może zastąpić go własnym wyzwaniem. Musi odpowiedzieć dla otrzymanego $C$, nie znając ani $a$, ani wykładnika $r$ tego wyzwania. Równość rozkładów nie daje mu takiej umiejętności. Zaprzeczalność zapisu i odporność na podszywanie odpowiadają na różne pytania.

Zakres argumentu: porównaliśmy pełne, uczciwe rozmowy. Dla złośliwego weryfikatora trzeba zdefiniować jego cały widok, obejmujący również własny stan, i zbudować odpowiedni symulator. To mocniejsze wymaganie. W analizie Stinsona–Wu pełniejszy wynik o wiedzy zerowej korzysta z modelu wyroczni losowej i założenia wiedzy o wykładniku, KEA. Analiza podszywania wykorzystuje również CDH. Nie wyprowadzamy tych twierdzeń wyłącznie z powyższej równości. Poprawny skrót nie jest też bezwarunkowym dowodem znajomości $r$ przez nadawcę, bo całe wyzwanie można przekopiować.

KEA

knowledge-of-exponent assumption. Założenie wiedzy wykładnika.

W demonstratorze MCL poniżej weryfikator liczy oczekiwaną odpowiedź $A^r$ bez sekretu $a$, a dowodzący oblicza $C^a$. Na rysunku zachowujemy potęgi. Realizacja na krzywej wykonuje odpowiednio $r\cdot A$ i $a\cdot C$. Porównanie wyników pokazuje krok algebraiczny dowodu. Sam test numeryczny nie zastępuje argumentu o całym rozkładzie.

Fiat–Shamir zmienia rolę wyzwania

W Schnorrze zamiast niezależnego $c$ możemy związać wyzwanie z wiadomością $m$, kluczem, zobowiązaniem i opisem grupy. Dla $A=g^a$ i $X=g^u$ zapisujemy najpierw:

Odbiorca wylicza hasz ponownie i sprawdza $g^s=X\cdot A^c$. W addytywnym profilu demonstratora $g$ reprezentuje punkt $P_2$, $A=a\cdot P_2$ i $X=u\cdot P_2$. Hasz otrzymuje kanoniczne kodowania tych punktów:

Teraz odbiorca podpisu sam odtwarza $c$. Trójka wygenerowana przez zwykły symulator Schnorra spełnia równanie grupowe, ale jej niezależnie wylosowane $\widehat c$ zazwyczaj nie jest haszem otrzymanego $\widehat X$. W idealnym modelu przy niezależnym świeżym zapytaniu szansa zgodności wynosi $1/q$. Tak powstaje istotna różnica między symulacją rozmowy a podrobieniem podpisu.

Złośliwy interaktywny weryfikator może wybrać wyzwanie właśnie jako taki hasz. Jeżeli kodowania, klucze i dziedziny protokołów na to pozwalają, otrzyma odpowiedź o postaci podpisu. Dlatego samo HVZK nie uzasadnia zaprzeczalności wobec dowolnego weryfikatora. Programowanie wyroczni losowej w dowodzie Fiata–Shamira nie daje zwykłemu użytkownikowi możliwości zmieniania rzeczywistej funkcji haszującej.

Stinson–Wu nie jest protokołem public-coin o tej samej strukturze. Naiwne ustalenie $r=\mathcal H(m)$ nie tworzy analogicznego podpisu. Upublicznia $r$, więc każdy może obliczyć $A^r$ i wygenerować odpowiedź. Sekret weryfikatora jest tu częścią mechanizmu, a nie zbędnym źródłem losowości.

Wspólna granica: żaden z tych przepływów sam nie mierzy odległości ani nie uniemożliwia przezroczystego przekazywania komunikatów. Ochrona przed relay, ujawnieniem stanu i błędnymi punktami wymaga jawnego modelu. Pytaj kolejno: co przyjmuje weryfikator, kto może stworzyć zapis, kto może odpowiedzieć na bieżąco i co wolno ujawnić?

Powiązania: zadania o zaprzeczalności, laboratorium porównawcze, dowód transformaty. Źródła: Schnorr, Fiat–Shamir, Stinson–Wu.