Kryptografia II stopień

W10a. Szyfrowanie asymetryczne: ElGamal i Cramer–Shoup

Nowa potrzeba: odbiorca udostępnił klucz publiczny i może być nieobecny. Nadawca chce zostawić mu poufną wiadomość bez wcześniejszego uzgodnienia wspólnego sekretu. To nie jest identyfikacja ani pełna wymiana AKE. Nadawca sam wykonuje Enc, a odbiorca później wykonuje Dec.

Z DH znamy już równość $(g^a)^r=(g^r)^a$. ElGamal wykorzysta ją do utworzenia i odtworzenia maski wiadomości. W tym zastosowaniu $A=g^a$ jest długoterminowym kluczem odbiorcy, a $g^r$ jednorazową częścią szyfrogramu. Najpierw zapiszmy interfejs. Dopiero potem podstawimy do niego ten rachunek.

Szyfrowanie publiczne: Setup, KeyGen, Enc, Dec

Schemat szyfrowania z kluczem publicznym zapisujemy jako krotkę:

Enc jest skrótem od encrypt, czyli szyfruj. Dec pochodzi od decrypt, czyli odszyfruj. Losowość jest wewnętrznym wejściem algorytmu probabilistycznego. Nie trzeba przekazywać sekretu odbiorcy ani losowych monet szyfrującego jako osobnego pola szyfrogramu. Kiedy analizujemy konkretny przebieg, jawnie nazwiemy jego losowość.

Poprawność wymaga, żeby odszyfrowanie uczciwie utworzonego szyfrogramu dawało wejściową wiadomość. Dla dopuszczalnych parametrów i pary kluczy wytworzonej przez KeyGen:

Prawdopodobieństwo uwzględnia losowania algorytmów. To wersja z doskonałą poprawnością, wystarczająca dla omawianych tu ElGamala i Cramera–Shoupa. Inne rodziny mogą dopuszczać jawnie ograniczone prawdopodobieństwo błędu. Poprawność nie mówi jeszcze nic o tym, czy przeciwnik potrafi odczytać wiadomość. To osobne wymaganie bezpieczeństwa.

Granica uprawnień: klucz publiczny pozwala każdemu zaszyfrować wiadomość do tego odbiorcy. Dlatego samo poprawne odszyfrowanie nie ustala nadawcy. Klucz tajny jest argumentem lokalnej procedury Dec i nie jest częścią przesyłanych danych. Wiarygodne pozyskanie $pk$ odbiorcy jest konieczne, aby nie zaszyfrować wiadomości do klucza podstawionego przez przeciwnika.

ElGamal

ElGamal szyfruje element grupy za pomocą wspólnej maski, którą nadawca wylicza z klucza publicznego odbiorcy i własnej losowości. Odbiorca odtwarza tę maskę za pomocą klucza tajnego. Zapiszmy cały schemat $\Pi_{\mathrm{EG}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$, zgodnie z definicją szyfrowania.

Małe $a$ jest sekretem. Duże $A$ jest publiczne. Litery nie są zamienne. Element grupy $A$ nie jest tym samym co jego wykładnik $a$.

Setup: parametry ElGamala

Wejście: $1^\lambda$. Wyjście: publiczne $pp=(G,q,g)$ z opisem kodowania i działań. Algorytm dobiera grupę cykliczną pierwszego rzędu $q$ oraz generator $g$. Do poniższego argumentu poufności potrzebujemy rodziny grup, w której DDH jest trudne. Sama możliwość wykonania potęgowania nie zapewnia tego założenia.

KeyGen: klucze odbiorcy

Wejście: $pp$. Odbiorca losuje $a\overset{\$}{\leftarrow}\mathbb Z_q$, oblicza $A=g^a$ i zwraca $(pk,sk)=(A,a)$. Klucz publiczny udostępnia w sposób, który pozwala przypisać go właściwemu odbiorcy. Klucz tajny zachowuje. Parametry $pp$ są dostępne przy obu kluczach.

Enc: szyfrowanie ElGamala

Wejście: $pp$, publiczny klucz $A\in G$ i wiadomość $m\in G$. Algorytm losuje świeże $r\overset{\$}{\leftarrow}\mathbb Z_q$ i oblicza:

Wyjście: $C\in G^2$. Nadawca przesyła dwa elementy grupy. Nie przesyła osobno $r$ ani maski $A^r$. Nie potrzebuje $a$. Wiadomość jest tu elementem grupy, a nie dowolnym plikiem. Kodowanie lub konstrukcję hybrydową trzeba określić osobno.

Dec: odszyfrowanie ElGamala

Wejście: $pp$, tajny klucz $a$ i szyfrogram $C$. Jeśli nie można odczytać kanonicznie zakodowanej pary $(u,v)\in G^2$, zwracamy $\bot$. W przeciwnym razie obliczamy:

Wyjście: odzyskany element $m'\in G$. Potęga $u^a$ odtwarza maskę. Odwrotność w grupie ją usuwa. Kontrola typu nie jest kontrolą autentyczności. W podstawowym ElGamalu każda poprawnie zakodowana para elementów grupy daje jakąś wiadomość.

Poprawność i przykład liczbowy

Podstawiamy wyniki Enc do wejścia Dec:

Do małego rachunku wybierzmy podgrupę rzędu $q=23$ modulo $47$, z generatorem $g=2$. Dla $a=7$ klucz publiczny to $A=34$. Szyfrujemy $m=9$ z $r=9$. Otrzymujemy $u=42$, maskę $A^r=36$ i $v=42$. Odbiorca oblicza $u^a=36$ oraz $36^{-1}=17\bmod47$. Stąd $m'=42\cdot17\bmod47=9$. Liczby są celowo małe, więc nie zapewniają bezpieczeństwa.

W tej wersji definicji skalary losujemy z całego $\mathbb Z_q$, także z możliwością wyniku 0. Zdarzenia $a=0$ lub $r=0$ są degeneracjami, każda o prawdopodobieństwie $1/q$. Profile wykluczające zero powinny określać to jawnie. Równanie poprawności działa również dla zera.

Bezpieczeństwo: od CPA do ataku CCA

Redukcja DDH dostaje $(g,A,U,T)$ i odpowiada na wyzwanie przez $(U,m_b\cdot T)$. Prawdziwe DH daje właściwy szyfrogram. Losowe $T$ ukrywa $m_b$ doskonale. Inne szyfrowania wykonujemy kluczem publicznym. To argument IND-CPA.

Nie jest to IND-CCA2. Zmieniamy wyzwanie na $(u,v\cdot\Delta)$ dla $\Delta\ne1$. Wyrocznia deszyfrowania nowego szyfrogramu zwraca $m_b\cdot\Delta$, skąd odzyskujemy $m_b$. Potrzebna jest konstrukcja z dowodem dla silniejszego modelu, nie samodzielnie dopisana suma kontrolna.

Ten sam szyfr, silniejszy przeciwnik

Rozpiszmy tę zmianę modelu. W CPA przeciwnik może uzyskiwać szyfrowania wybranych wiadomości. W szyfrowaniu publicznym i tak może je obliczać. W CCA otrzymuje dodatkowo dostęp do deszyfrowania innych szyfrogramów. W wersji adaptacyjnej CCA2 może pytać również po otrzymaniu wyzwania. Jedyny zakaz bezpośredni dotyczy jego deszyfrowania. Bez niego gra byłaby trywialna.

1. Przeciwnik wybiera różne wiadomości $m_0,m_1\in G$.
2. Otrzymuje wyzwanie $(u,v)$, będące szyfrowaniem jednej z nich.
3. Wybiera $\Delta\ne1_G$ i pyta o $(u,v\cdot\Delta)$. To inny szyfrogram, więc zakaz go nie obejmuje.
4. Dostaje $m_b\cdot\Delta$, mnoży przez $\Delta^{-1}$ i porównuje z wiadomościami.
5. Zgadnięty bit jest poprawny. Nie obliczył ani $a$, ani $r$.

Demonstrator ataku na ElGamala

Demonstrator losuje niezerowe $a$ i $r$, aby nie zaczynać od degeneracji. Rysunek przedstawia szyfrogram $(U,V)=(g^r,M\cdot A^r)$. Dla niejednostkowego $\Delta$ przeciwnik przesyła $(U,V\cdot\Delta)$, otrzymuje $M\cdot\Delta$ i odzyskuje $M$ przez pomnożenie przez $\Delta^{-1}$. Małą wiadomość liczbową kodujemy jako $M=g^m$. Wielkie $U,V,M$ oznaczają elementy grupy, a nie skalary.

Realizacja na krzywej. W zapisie addytywnym szyfrogram to $(U,V)=(r\cdot P_2,M+r\cdot A)$. Przeciwnik dodaje niezerowy punkt $\Delta$ do drugiego składnika. Wyrocznia zwraca $M+\Delta$, więc odjęcie znanego punktu odzyskuje $M$. Tylko wyrocznia ma dostęp do sekretu $a$. Obliczenie odzyskujące korzysta z jej odpowiedzi i publicznego $\Delta$.

Atak nie przeczy argumentowi DDH dla CPA. Używa usługi, której tamten argument nie obsługuje. W prawdziwym systemie taki dostęp może wynikać z interfejsu odszyfrowywania, przetwarzania zmodyfikowanych rekordów albo ujawniających informacji błędów. Nie każda aplikacja daje pełną wyrocznię deszyfrującą, ale model CCA celowo bada mocną gwarancję.

Rerandomizacja daje pokrewny przykład: $(u\cdot g^t,v\cdot A^t)$ szyfruje tę samą wiadomość. Jeżeli wynik jest inny niż wyzwanie, samo zakazanie identycznego szyfrogramu nie zamyka ataku. Poufność wobec aktywnego przetwarzania wymaga kontroli takich przekształceń.

Naprawa wymaga zmiany kontraktu, np. użycia sprawdzonej konstrukcji szyfrowania uwierzytelnionego lub hybrydowego z odpowiednim twierdzeniem. Zwykły publiczny hasz dołączony do szyfrogramu nie pomaga, bo przeciwnik przeliczy go po modyfikacji.

Cramer–Shoup

Nie każda przekształcalność jest błędem. W ElGamalu publiczna rerandomizacja pozwala zmienić wygląd szyfrogramu bez poznania wiadomości. Jest użyteczna np. w odpowiednio zabezpieczonych sieciach miksujących. Mnożenie dwóch szyfrogramów daje z kolei szyfrogram iloczynu ich wiadomości. Takie własności projektuje się świadomie wraz z ograniczeniami dostępu do deszyfrowania. Nie są zgodne z obietnicą IND-CCA2 dla tego samego, swobodnie przekształcalnego formatu.

Cramer–Shoup zmienia tę obietnicę. Nadal każdy może szyfrować kluczem publicznym, ale odbiorca najpierw sprawdza algebraiczne powiązanie wszystkich składników. Nie wydaje częściowo odszyfrowanej wiadomości po nieudanej kontroli. Opiszemy wersję CS1 z pracy Cramera i Shoupa Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack, §6.1. Używa ona dwóch skalarów maskujących. To wariant tej samej rodziny co pierwotny schemat z CRYPTO 1998. Publikacja i algorytmy.

CS1

Cramer–Shoup, construction 1. Oznaczenie pierwszej konstrukcji Cramera–Shoupa w omawianym źródle.

Formalnie $\Pi_{\mathrm{CS1}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$. Rozdzielamy przygotowanie publicznych parametrów od generowania sekretu. W źródle obie czynności znajdują się w algorytmie generowania kluczy. Ten podział służy opisowi i nie zmienia poniższych równań.

Setup: parametry Cramera–Shoupa

Wejście: $1^\lambda$. Wyjście: $pp=(G,q,g_1,g_2,\kappa)$ wraz z rodziną haszy, kodowaniem i działaniami grupy. Wszystkie te parametry są jawne.

Pracujemy w grupie $G$ pierwszego rzędu $q$, w której zakładamy trudność DDH. Wybieramy niezależne generatory $g_1,g_2\in G$, różne od elementu neutralnego. Ich indeksy numerują bazy tej samej grupy, nie dwie grupy pairingu. Przeciwnik nie dostaje logarytmu jednej bazy względem drugiej.

Publiczny parametr $\kappa$ wybiera funkcję haszującą $\mathcal H_\kappa:G^3\to\mathbb Z_q$. Haszowanie obejmuje jednoznaczne kodowanie uporządkowanej trójki. To hash do skalaru, a nie $\mathcal H_{G_1}$ mapujący do punktu. W twierdzeniu potrzebna jest odporność na kolizję z zadanym celem, określona w źródle jako TCR (target collision resistance). W definicji z §5 źródła cel jest jednostajną trójką z $G^3$, losowaną niezależnie od parametru $\kappa$. Przeciwnik dostaje cel i parametr. Ma znaleźć inną trójkę z tym samym haszem. Nie wybiera obu wejść. To konkretny wariant definicji, a nie wymóg dla każdego dowolnie wybranego celu. Pełna odporność na kolizje jest silniejszym wystarczającym wymaganiem. Nie zastępujemy tych własności samym stwierdzeniem „użyto funkcji hashującej”.

Parametr $\kappa$ jest losowany zgodnie z opisem rodziny haszy, niezależnie od skalarów klucza. Nie jest tajnym kluczem MAC. Zestaw parametrów dobieramy uczciwie, zgodnie z modelem konstrukcji.

KeyGen: sześć sekretów i klucz publiczny

Wejście: $pp$. Odbiorca losuje niezależnie sześć skalarów $x_1,x_2,y_1,y_2,z_1,z_2\overset{\$}{\leftarrow}\mathbb Z_q$ i oblicza:

Wyjście: para $(pk,sk)$, gdzie $pk=(c,d,h)$ i $sk=(x_1,x_2,y_1,y_2,z_1,z_2)$. Oba klucze są używane razem z $pp$. Pełny publiczny opis zawiera więc również grupę oraz $(g_1,g_2,\kappa)$. Składnik $h$ służy maskowaniu wiadomości. Składniki $c,d$ służą kontroli spójności. Klucz publiczny odbiorcy musi pochodzić z zaufanego źródła, podobnie jak w innych systemach szyfrowania publicznego.

Enc: szyfrowanie Cramera–Shoupa

Wejście: $pp$, klucz publiczny $pk=(c,d,h)$ i wiadomość $m\in G$. Nadawca losuje świeże $r\overset{\$}{\leftarrow}\mathbb Z_q$. Kolejność jest istotna:

1. Losowość w dwóch bazach: $u_1=g_1^r$, $u_2=g_2^r$. Oba elementy powstają z tego samego $r$.
2. Ukrycie wiadomości: $w=m\cdot h^r$.
3. Związanie zawartości: $\alpha=\mathcal H_\kappa(u_1,u_2,w)$.
4. Znacznik kontroli: $v=c^r\cdot d^{r\cdot\alpha}$.

Wyjście: szyfrogram $C=(u_1,u_2,w,v)\in G^4$. Zauważmy, że nadawca oblicza $v$ z klucza publicznego i własnego $r$. Nie potrzebuje sześciu sekretów odbiorcy.

Dec: kontrola i odszyfrowanie

Wejście: $pp$, klucz tajny $sk=(x_1,x_2,y_1,y_2,z_1,z_2)$ i szyfrogram $C$. Wyjście: element $m\in G$ albo $\bot$.

Odbiorca sprawdza format, kanoniczne kodowanie i przynależność elementów do właściwej grupy. Następnie sam oblicza $\alpha$ z odebranej trójki. Nie ufa haszowi dołączonemu przez nadawcę. Sprawdza:

Niezgodność oznacza $\bot$, czyli odrzucenie bez wiadomości. Dopiero po zgodności wolno obliczyć:

Poprawność i demonstrator

Dlaczego uczciwe szyfrowanie przechodzi kontrolę? Rozpiszmy prawą stronę, korzystając wyłącznie z praw działań w grupie:

Usuwamy więc dokładnie tę maskę, którą dodał nadawca. Jest to dowód poprawności, jeszcze nie dowód bezpieczeństwa.

Dlaczego modyfikacja z ataku na ElGamala już nie wystarcza

Zamieńmy tylko $w$ na $w'=w\cdot\Delta$, gdzie $\Delta\ne1_G$. Odbiorca wyznaczy nowy $\alpha'=\mathcal H_\kappa(u_1,u_2,w')$. Stary znacznik był związany z $\alpha$, więc z reguły nie spełni nowego równania. Samo przeliczenie publicznego hasza nie daje przeciwnikowi nowego znacznika.

Można próbować subtelniej: przemnożyć $u_1,u_2,w$ odpowiednio przez $g_1^t,g_2^t,h^t$ i obliczyć $\alpha'$ dla nowej trójki. Prosta aktualizacja znacznika do $v\cdot c^t\cdot d^{t\cdot\alpha'}$ nadal pomija czynnik:

Przeciwnik zna własne $t$, lecz nie zna losowości $r$ zaatakowanego szyfrogramu. To pomaga zrozumieć rolę hasza, ale nie jest samodzielnym dowodem odporności na wszystkie ataki. Szczególne przypadki i prawdopodobieństwa obsługuje redukcja.

Nowe, poprawne szyfrowanie innej wiadomości powinno natomiast przejść kontrolę. Akceptacja nie oznacza uwierzytelnienia nadawcy. Każdy zna klucz publiczny. Schemat nie wykrywa też samodzielnie ponownego przesłania identycznego szyfrogramu. To osobne cele protokołu.

Bezpieczeństwo: od DDH do IND-CCA2

W grze przeciwnik wybiera dwie wiadomości i dostaje szyfrogram jednej z nich. Może adaptacyjnie pytać o deszyfrowanie innych szyfrogramów, także po otrzymaniu wyzwania. Jego celem jest wskazanie zaszyfrowanej wiadomości z przewagą nad losowaniem. Dowód musi symulować również tę wyrocznię, nie tylko zamienić maskę na losowy element, jak w prostym argumencie CPA dla ElGamala.

• Zgodne wykładniki. W uczciwym szyfrogramie $u_1=g_1^r$ i $u_2=g_2^r$. To relacja DH. W analizie zastępujemy ją parą o niezależnych wykładnikach. Wykrycie takiej zmiany prowadzi do rozróżniacza DDH.
• Niespójne zapytania. Dwie ukryte współrzędne każdego składnika klucza pozostawiają swobodę algebraiczną, mimo znajomości klucza publicznego. Dla zapytań bez wspólnego wykładnika trafienie poprawnego znacznika wymaga spełnienia dodatkowego ukrytego warunku liniowego. Analiza ogranicza prawdopodobieństwo takiego zdarzenia także przy wielu zapytaniach.
• Próba zachowania hasza. Inna trójka z haszem trójki wyzwania stanowiłaby kolizję z zadanym celem. To miejsce użycia TCR. Nie zakładamy, że każdy zmieniony ciąg zawsze ma inny hasz.
• Ukryty bit. Po kontrolowanych zmianach reguł pozostały widok nie zależy od wybranej wiadomości. Różnice między grami rozliczamy przez DDH, TCR i małe prawdopodobieństwo wyjątków.

To mapa dowodu, nie jego pełny zapis. Dla wersji CS1 twierdzenie 1 źródła daje poniższe konkretne ograniczenie. Niech $Q_D$ oznacza maksymalną liczbę zapytań deszyfrujących, a przewaga CCA będzie zdefiniowana jako $|\Pr[b'=b]-1/2|$. Istnieją odpowiednie redukcje $\mathcal B,\mathcal C$ takie, że:

Przewaga DDH jest różnicą prawdopodobieństw odpowiedzi rozróżniacza w dwóch rozkładach, a składnik TCR jest prawdopodobieństwem znalezienia wymaganej kolizji. Wyraz $(Q_D+4)/q$ pochodzi z oszacowania zdarzeń wyjątkowych w dowodzie. Nie jest „siłą hasza” ani empirycznym wynikiem demonstracji. Zmiana definicji przewagi może zmienić stałe. Pełną kolejność gier i rachunek zawiera §6.2, twierdzenie 1.

Model standardowy: powyższe twierdzenie nie zastępuje hasza wyrocznią losową. Korzysta z jego konkretnej własności TCR oraz założenia DDH. Nie przenosi się automatycznie do każdej grupy z pairingiem. W demonstratorze wykorzystujemy działania w $G_1$ BLS12-381, ale nie pairing. Interpretacja bezpieczeństwa wymagałaby trudności DDH właśnie w tej grupie oraz odpowiedniego hasza. Nie publikujemy obrazów tych samych sekretów w $G_2$.

Granice demonstracji. Obliczenia punktów wykonuje MCL WebAssembly. Zapis potęgowy na rysunku oznacza w kodzie dodawanie punktów i mnożenie przez skalar, zgodnie z wcześniejszym słownikiem. Punkty $P,Q$ odpowiadają bazom $g_1,g_2$. Hasz skalarny to SHA-256 z separatorem domeny, publicznym parametrem $\kappa$ i kodowaniami trzech punktów, następnie redukcja modulo $q$. Nie jest to certyfikowana implementacja rodziny TCR ani gotowa ciphersuite. Wiadomości liczbowe są kodowane jako $m=\mu\cdot P$, a odczyt przeszukuje mały, jawny zakres. Dodanie $\Delta=\delta\cdot P$ oznacza w tym kodowaniu zmianę liczby o $\delta$. To odwracalne kodowanie demonstracyjne, nie hash-to-curve i nie szyfrowanie dowolnych plików. Demo przetwarza lokalnie utworzone punkty, nie pakiety odbierane z sieci. Klucze testowe i oba stany są dostępne na jednej stronie. Wyniki testów poprawności nie dowodzą IND-CCA2.

Gwarancja jest probabilistyczna. Na przykład losowanie $r=0$ z $\mathbb Z_q$ ma prawdopodobieństwo $1/q$. Wtedy $u_1=u_2=v=1_G$, a maska jest neutralna. Takie wyjątkowe wykonanie nie ukrywa wiadomości. Właśnie dlatego twierdzenie mówi o zaniedbywalnej przewadze w całym eksperymencie, a nie o bezwarunkowym odrzuceniu każdej modyfikacji w każdym możliwym wykonaniu.

Sprawdź rozumienie: co stałoby się, gdyby hasz pomijał $w$? Dlaczego tag nie jest podpisem nadawcy? Dlaczego nie wolno wydać $w\cdot B^{-1}$ przed sprawdzeniem równania? W wariancie bez wiązania $w$ atak $w\mapsto w\cdot\Delta$ znów przechodziłby kontrolę. Właśnie dlatego zestaw argumentów funkcji haszującej jest częścią schematu.

Dalszy krok: rerandomizacja i zmiana odbiorcy, sieci miksujące, C8. Źródła: Cramer–Shoup, CRYPTO 1998, rozszerzona analiza CS1.

Szyfrowanie hybrydowe: od elementu grupy do pliku

ElGamal powyżej przyjmuje element grupy, a nie dowolnie długi plik. Możemy rozdzielić zadanie: mechanizm asymetryczny dostarcza krótki sekret, a mechanizm symetryczny chroni właściwe dane. Interfejs całości nadal musi określać, co szyfrujemy i co przesyłamy.

Hybrydowe szyfrowanie pliku: KEM (key encapsulation mechanism) to mechanizm enkapsulacji klucza. Korzystając z klucza publicznego odbiorcy, nadawca uzyskuje tajny materiał kluczowy i kapsułkę do przesłania. Odbiorca dekapsułkuje ją swoim sekretem i odzyskuje ten sam materiał. Wyprowadzamy z niego klucz i szyfrujemy dane mechanizmem AEAD. Muszą zgadzać się długości, kodowania, identyfikator algorytmu i uwierzytelniany kontekst. Samo umieszczenie dwóch dobrych mechanizmów obok siebie nie zastępuje twierdzenia o kompozycji.

W formalnym interfejsie $\Pi_{\mathrm{KEM}}=(\mathsf{Setup},\mathsf{KeyGen},\mathsf{Encaps},\mathsf{Decaps})$ wywołanie $(c_K,z)\leftarrow\mathsf{Encaps}(pp,pk)$ zwraca publiczną kapsułkę $c_K$ oraz tajny materiał $z$. Nie przyjmuje wiadomości użytkownika. Wywołanie $z'\leftarrow\mathsf{Decaps}(pp,sk,c_K)$ odtwarza zgodny materiał dla uczciwej kapsułki. Obsługę nieprawidłowych kapsułek określa konkretny KEM, z jawnym odrzuceniem albo mechanizmem odrzucenia niejawnego. Następnie obie strony wyprowadzają klucz AEAD. Wiadomość użytkownika jest wejściem dopiero do tego symetrycznego szyfrowania.

Dalej: RSA zmieni rodzinę problemu matematycznego. Nadal będziemy jednak sprawdzać te same interfejsy Enc/Dec i Sign/Verify, zamiast nazywać pojedyncze potęgowanie gotowym systemem szyfrowania.

Powiązania: C8, Boneh–Shoup.

Needham–Schroeder: zaszyfrowane, lecz przypisane złej rozmowie

Niech $\operatorname{Enc}_B$ oznacza szyfrowanie do Boba. W historycznym protokole publicznym Alicja wysyła $\operatorname{Enc}_B(N_A,A)$, Bob odpowiada $\operatorname{Enc}_A(N_A,N_B)$, a Alicja odsyła $\operatorname{Enc}_B(N_B)$. Nonce $N_A,N_B$ mają wykazać świeżość. Ewa może jednak być legalnym uczestnikiem z własnym kluczem.

Szyfrowanie działało zgodnie z przeznaczeniem. Alicja nie potrafiła powiązać drugiej wiadomości z tożsamością odpowiadającego. Poprawka Lowe'a dodaje tę tożsamość: $\operatorname{Enc}_A(N_A,N_B,B)$. Lokalna sesja Alicji oczekuje Ewy, więc Alicja odrzuca odpowiedź oznaczoną jako pochodzącą od Boba. Jest to naprawa konkretnego przeplotu, nie uniwersalna zasada, że dopisanie nazwiska zawsze zabezpiecza protokół.

Źródło: Gavin Lowe, An Attack on the Needham–Schroeder Public-Key Authentication Protocol. Atak podkreśla, że uwierzytelnianie dotyczy relacji pomiędzy sesjami i uczestnikami, a nie tylko tajności pojedynczych szyfrogramów.