Coś dla miłośników podsłuchów, czyli backdoor in da crypto, yo!

Mamy nadzieję, że wypoczęliście w weekend, bo przy lekturze tego artykułu trzeba myśleć. Podobno nie boli, a przy okazji można się czegoś ciekawego nauczyć.  Polecamy opowieść Łukasza o tylnych furtkach w kryptografii.

Porozmawiajmy o kleptografii. Nie, nie mam dziwnej wady wymowy (wypisu?), która powoduje, że piszę „le” zamiast „ry”. Zanim dojdziemy do tego czym jest kleptografia, zacznijmy od, z pozoru bardzo prostego, problemu: jak wylosować liczbę? Losowanie liczb jest bardzo pożyteczne w kryptografii: korzystając z szyfrowania symetrycznego w połączeniach HTTPS losujemy nowy klucz. Gdy chcemy dodać sól do hasła to również ją losujemy. Dlatego potrzebujemy bardzo dobrej maszyny losującej. Niestety Ryszard Rembiszewski jest tylko jeden i jego maszyna losująca jest dosyć niewygodna w transporcie, nie mówiąc już o automatyzacji. Dowolna analogowa metoda losowania (np. rzut kostką) jest dosyć trudna w automatyzacji, a komputery mają tę niewygodną w tej sytuacji cechę, że są przewidywalne. Dlatego też trzeba znaleźć algorytm, który dostarczy liczby „wystarczająco” losowe do naszych zastosowań.

Reszta z dzielenia

Zacznijmy od bardzo prostego algorytmu. Algorytm zakłada, że mamy wybrane trzy liczby – m, g oraz s. Następnie pierwsza wartość losowa to:

s' = sg mod m

Już tłumaczę co ten dziwny zapis znaczy. Otóż mnożymy najpierw liczbę s przez g i następnie bierzemy resztę z dzielenia tego mnożenia przez m. Jeśli s = 6, g = 2, a m = 10 to sg = 6*2 = 12, a reszta z dzielenia 12 przez 10 to 2. Dosyć proste, łatwe w implementacji. Kolejne wartości losowe otrzymujemy podstawiając za s wartość s’. W ten sposób możemy losować liczby w nieskończoność. Dla naszego przykładu kolejną wartością losową będzie sg = 2 * 2 = 4 i reszta z dzielenia 4 przez 10 to wciąż 4.

Dosyć proste, prawda? W zasadzie tak proste, że można zaimplementować to sprzętowo i otrzymać ciąg liczb losowych potrzebnych do szyfrowania danych. Co więcej, g oraz m mogą być publiczne wiadome, natomiast pierwsza wartość s może być zapisana tylko w takim sprzęcie. W ten sposób nikt nie jest w stanie przewidzieć pierwszej wylosowanej wartości. A co z kolejnymi? Dla naszego przykładu powstanie następujący ciąg:

2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4, 8, 6, ...

Wygląd jakby nasze losowe wartości wcale nie były zbyt losowe. Dodatkowo bardziej spostrzegawczy czytelnicy zauważyli pewnie, że jeśli w ciągu pojawi się znowu pierwotna wartość s to kolejne wartości będą się powtarzać. Czyli mamy w sumie pięć, w miarę losowych liczb. Weźmy zatem inne wartości m oraz g. Niech g będzie równe 2 717 a m będzie równe 46 189. Przyjmijmy, podobnie jak poprzednio, s = 6. Wtedy nasz ciąg wygląda następująco:

16302, 43472, 8151, 21736, 27170, 10868, 13585, 5434, 29887, 2717, 38038, 24453, 19019, 35321, ...

„Na oko” liczby wyglądają dosyć losowo, nie ma żadnych powtórzeń, czyli implementujemy i wysyłamy podzespoły na cały świat.  Niestety po tym jak już nasze podzespoły znalazły się w każdym urządzeniu do szyfrowania na świecie okazało się, że liczby powtarzają się na szesnastej pozycji. Czyli otrzymujemy ciąg tylko 16 liczb w miarę losowych i, co za tym idzie, szesnaście różnych kluczy do szyfrowania. Czy można ulepszyć ten wynik? Oczywiście, że tak. Wystarczy wybrać jako m dowolną dużą liczbę pierwszą, a jako g dowolną liczbę różną od 0 i 1. Równie oczywiście możecie zadać sobie pytanie – czemu macie mi wierzyć?

Uważni czytelnicy zauważyli też kolejną niezbyt dobrą cechę tego generatora liczb losowych. Jeśli ktoś jest w stanie przechwycić jedną wylosowaną wartość to może też wyliczyć wszystkie następujące po niej wartości, ponieważ algorytm jak i g oraz m są publicznymi stałymi. Utajnienie g i m niewiele by pomogło – mając odpowiednio dużo liczb wyjściowych z takiego generatora można by je też wyliczyć. Utajnienie algorytmu jest złym pomysłem z innego powodu, ale o tym napiszę kolejny wpis. To co teraz?

Potęgowanie

Podobnie jak mnożyliśmy liczby i braliśmy resztę z dzielenia, możemy też liczby potęgować. Przyjmując poprzednie założenia możemy zapisać (^ oznacza potęgowanie):

r = g^s mod m

Zanim przejdziemy do dalszego opisu generatora, zastanówmy się nad innym problemem: czy atakujący, mając dostęp do wartości m, g oraz r (czyli nie znając tylko wartości s) jest w stanie szybko odtworzyć s? Gdybyśmy nie brali reszty z dzielenia przez m to taka operacja byłaby dosyć prosta – jest to po prostu logarytm. Niestety, w przypadku brania reszty modulo m operacja ta staje się o wiele trudniejsza. Tak trudna, że jest podstawą algorytmów szyfrowania podobnie jak rozkład na czynniki pierwsze. Operacja „odzyskania s” nazywa się logarytmem dyskretnym i jest wykorzystywana na przykład w wymianie kluczy Diffie-Hellmana.

Mając tak obliczone r zdefiniujemy kolejną wartość naszego generatora:

t = p^r mod m

Musimy też zmienić wartość s na nową, żeby następnym razem generator zwrócił inną wartość:

s' = g^r mod m

W ten sposób „chronimy” wartość s przed łatwym odkryciem i obliczeniem kolejnej liczby w naszym losowym ciągu. Intuicyjnie, s zmienia się według swojego schematu i „przypadkiem” produkuje nową wartość losową. Żeby odzyskać s trzeba umieć rozwiązać problem logarytmu dyskretnego w szybkim czasie. Wydaje się, że rozwiązaliśmy problem „przewidywalności” naszego generatora. Jedyne co pozostało to wybór wartości p, g, oraz m. Zacznijmy od końca – m powinno być odpowiednio dużą liczbą pierwszą (po prostu zaufajcie mi w tej sprawie).

Co do wartości p i g to sprawa jest bardziej skomplikowana. Wydaje się, że dowolne, losowe wartości (oprócz 0 oraz 1) powinny być odpowiednie. Tutaj dochodzimy do pewnego problemu, który z angielskiego nazywa się „nic w rękawie”. Chodzi o to, że wartości stałych powinny być ustalone w sposób, który nie budzi wątpliwości. Metaforycznie – przez kogoś kto nie chowa nic w rękawach. A gdyby tak można było manipulować tymi wartościami, w taki sposób żeby nikt się nie zorientował? Dodatkowo miło by było gdyby można było się wyprzeć wszelkich oskarżeń, gdy ktoś odkryje naszą manipulację.

Kleptografia

Ustalmy wartości p i g w następujący sposób. Wybierzmy bardzo tajną, wylosowaną kostką i trzymaną w sejfie liczbę e. To będzie nasza tajemnica, którą się dzielimy tylko z krajami, które lubimy. Wylosujmy też p, które oczywiście będzie publiczne znane i obliczmy g na podstawie poniższego równania.

g = p^e mod m

Zarówno e jak i p zostały wybrane losowo, więc wynik potęgowania – g – też będzie losowy. Zatem nie ma wątpliwości co do losowości tych dwóch liczb, chociaż oczywiście jest między nimi związek, który znają tylko osoby, które wybrały te liczby. Gdyby ktoś chciał odzyskać wartość e musiałby rozwiązać problem logarytmu dyskretnego,  który, jak wspominałem, rozwiązuje się bardzo długo. Wyliczmy teraz pierwszą wartość losową (oznaczoną wcześniej jako t):

r = g^s mod m

t = p^r mod m

Na razie wszystko wygląda losowo. Jeszcze nie zapomnijmy zmienić wartości s naszego generatora, żeby następna wygenerowana liczba była inna.

s' = g^r mod m

Teraz spróbujmy na podstawie „losowej” wartości t przewidzieć przyszłe wartości zwrócone przez generator liczb losowych. W tym celu wyciągamy z naszego sejfu liczbę e, która jednocześnie zapewnia, że tylko my jesteśmy w stanie przewidzieć przyszłe wartości. Wykonujemy dosyć proste obliczenie:

t^e mod m = (p^r)^e mod m = p^(re) mod m = (p^e)^r mod m = g^r mod m

To wygląda dokładnie tak samo jak nowa wartość s. Skoro zatem mamy s możemy wyliczać dowolną liczbę wartości wprzód. Właśnie taką (lub podobną) sytuację rozumiemy pod pojęciem „kleptografii”. Jest to umieszczenie w algorytmie kryptograficznym (w tym przypadku generatorze liczb losowych) takich wartości bądź kroków, które wyglądają na zupełnie losowe i wydają się nie osłabiać algorytmu, nawet przy weryfikacji. Jak to napisali twórcy pojęcia „kleptografii” jest to zwrócenie kryptografii przeciwko sobie. Zauważmy, że cała operacja polegała na tym, że znamy wartość e – nikt nie jest w stanie nam tego udowodnić. Dlatego nikt nie jest w stanie jednoznacznie stwierdzić, że wartości p i g zostały wybrane nieprzypadkowo i cały algorytm zawiera tylną furtkę. No chyba, że ktoś wyniesie z naszego sejfu wartość e i ogłosi całemu światu, że ją znamy. Wtedy każda osoba jest w stanie złamać tę implementację algorytmu.

Jedyny komentarz

Od ochrony do podsłuchów

Mogłoby się wydawać, że cała historia jest miłą, chociaż trochę skomplikowaną, teorią matematyczną. Niestety wydarzyło się to naprawdę. Pomimo, że nie mamy jednoznacznego potwierdzenia, jest prawie pewne, że NSA – za pomocą standardu NIST – wybrała odpowiednie punkty krzywej eliptycznej P i Q tak, żeby umieć przewidywać przyszłe wartości losowe. Uważny czytelnik zauważył, że mówimy tu o punktach krzywych eliptycznych, a nie wspominałem nic o nich. Otóż algorytm, w którym NSA umieściła swoją kleptograficzną furtkę był trochę bardziej złożony, jednak koncept pozostaje ten sam. Dla bardziej ciekawskich i matematycznie uzdolnionych czytelników szybki skrót pomijający szczegóły: zamiast używać ciała Z_p, użyto ciała skończonego zbudowanego nad krzywą eliptyczną, a zamiast potęgowania używano mnożenia i wszystkie wartości, gdzie to konieczne, rzutowano na liczby.

Wracając do historii. W przeszłości bardzo wiele algorytmów wymagało wybrania pewnych wartości stałych – czy były to funkcje skrótu czy szyfrowanie. Najbardziej znanym przypadkiem jest algorytm DES używany do blokowego szyfrowania danych. Wtedy NSA – znowu za pomocą standardu NIST – również nie ustaliło stałych zgodnie z zasadą „niczego w rękawie”. NSA wiedziało o pewnej słabości tego algorytmu i wybrało takie wartości stałych, żeby utrudnić jego złamanie. Dopiero po latach, gdy odkryto metodą łamania DES, okazało się, że ona nie do końca działa ze względu właśnie na wartości stałych. Jak widać przez te lata zmieniła też się misja NSA.

Co ciekawe, naukowcy zaproponowali też podobną, teoretyczną, kleptograficzną metodę wprowadzenia tylnej furtki w algorytmie Diffie-Hellmana, który jest powszechnie używany do wymiany kluczy symetrycznych bez możliwości podsłuchu. W tym przypadku przyszłe wymiany kluczy pozwalały odzyskać klucz z poprzedniej wymiany. Podobnie jak powyżej, możliwości sprawdzenia czy taka tylna furtka jest wbudowana w konkretną implementację algorytmu są niewielkie. Szczególnie jeśli taka implementacja jest sprzętowa i nie mamy dostępu do jej kodu.

Możecie teraz spytać czy istnieje jakiś algorytm albo sposób tworzenia stałych, który zapewni, że nie będzie tylnej furtki. Tutaj pojawia się pewien problem. Standardy wprowadzone przez NIST czy inne instytucje były wprowadzone właśnie po to, żeby wybrać jak najlepsze algorytmy i wartości, które uchronią przed przyszłymi atakami, tak jak to się stało w przypadku DES. Niestety, akceptując wartości i algorytmy stworzone przez dane instytucje akceptujemy również fakt, że taka instytucja mogła wbudować tylną furtkę. Odkrycie jej może być, jak zauważyliście, bardzo trudne a udowodnienie celowości wręcz niemożliwe. Tworzenie samemu tych losowych wartości pociąga za sobą również pewnego rodzaju niebezpieczeństwo. Jak pokazałem na początku wpisu mogą istnieć wartości lepsze i gorsze – takie łatwiejsze do złamania i takie, na których w zasadzie opiera się cała siła naszego szyfrowania. Jedyna nadzieja pozostaje zatem w otwartości algorytmów, ich implementacji oraz użytych wartości i wierzeniu w to, że, przynajmniej część kryptologów jest po stronie naszego bezpieczeństwa.

P.S. Jeśli szukacie ciekawej historii o tylnych furtkach kryptograficznych umieszczonej w realiach Zimnej Wojny to polecamy ten artykuł, niestety po angielsku.