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.
Komentarze
A gdybyśmy zaszyfrowali dane po kolei kilkoma algorytmami różnego autorstwa, żeby pojedynczy podmiot nie mógł samodzielnie złamać całości?
Nie wiem czy dobrze rozumiem, ale coś takiego jest w powszechnym użyciu xD
Pomysł wydaje się dobry. Niestety, tak dobrze to nie działa. Już dawno ktoś udowodnił, że identycznie „mocne” algorytmy i wielokrotne złożenie – mogą być nawet słabsze niż pojedynczy. No i czas!
> Już dawno ktoś udowodnił, że identycznie „mocne” algorytmy
> i wielokrotne złożenie – mogą być nawet słabsze niż pojedynczy.
Można prosić o więcej informacji na temat tego dowodu?
Not quite, mówisz chyba o hashowaniu, a nie szyfrowaniu.
Zapewne byłby dużo trudniej łamalny, natomiast na samym końcu zależy nam przecież równiez na wydajności. Zarówno szyfry symetryczne jak i asymetryczne muszą dać się implementować, nie tylko na super mocnych prockach, ale również na układach typu ASIC czy FPGA, gdzie mocy z pojedyńczego chipsetu jest mało, a co za tym idzie i złożoność szyfrów nie może być zbyt duża.
Poza tym, zakładam że skoro najlepszy hash to nie jest wcale SHA2(SHA1(cokolwiek(X))) to również enkapsulacja szyfrów nie jest dobrym pomysłem, ale to już pewnie ktoś mocny z kryptografii musiałby się wypowiedzieć.
Odpada – takie rozwiazajie mialo by koszmarna wydajnosc.
Może tak być, ale niekoniecznie. Podam prosty przykład:
3 xor 5 = 6
6 xor 7 = 1
1 xor 2 = 3
Swego czasu jak wchodziły pierwsze ZX Spectrum to dzieciaki sie tak bawiły że rozwiązanie pierwszego ogniwa układanki dawało kluch do drugiego ogniwa , drugie do trzeciego i tak dalej. czyli ze skoro dzieciaki wiedza o tym „od wczoraj” to służby wiedzą o tym „od zawsze” i pewnie jeszcze zaq czasów nieboszczki Enigmy było cos na rzeczy.
Nie ma obawy, enkapsulacja nigdy nie pogorszy algorytmu. Co innego manipulowanie w pojedynczych algorytmach. Tylko enkapsulacja zmniejszy wydajność, a czasem to jest problem.
Zabrakło mi tego obrazka :
https://www.random.org/analysis/dilbert.jpg
Należy dodać, że Dual_EC_DRBG, bo domyślam się, że o tym jest mowa w artykule, został usunięty przez NIST z rekomendowanych implementacji DRBG w kwietniu 2014 r.
https://en.wikipedia.org/wiki/Dual_EC_DRBG
z3s, idź tą drogą
slaby jestem w te klocki przyznaje sie Adam robilem scroll down :( mea pulpa
I co teraz?!
Scroll up? :)
Czemu do generowania liczb losowych nie wykorzystuje się zjawisk fizycznych, np. szumu termicznego rezystora? Czy teoria spiskowa będzie właściwą odpowiedzią?
Są fizyczne generatory, ten od Intela masz prawdopodobnie na plycie glownej. Ufamy Intelowi, prawda?
Fizyczne generatory tez da sie atakowac przez side channel, na przyklad zmiana temperatury zmienia zazwyczaj przebieg zjawisa fizycznego na ktorym jest oparty generator. Z tym, ze trzeba miec fizyczny dostęp do chipa.
Zmiana warunków zjawiska fizycznego zmienia odczytywane wartości, ale raczej nie uczyni ich całkowicie deterministycznymi; zmieni się wartość średnia, parametry i może rodzaj rozkładu prawdopodobieństwa, ale losowość raczej zostanie. Mając side channel, prościej będzie ustawić „specjalny” tryb pracy przetwornika analogowo-cyfrowego albo w ogóle całego generatora – choćby tak, żeby zamiast odczytywać element fizyczny, wysyłał liczby według algorytmu opisanego w artykule. Jeśli chodzi o RDRAND, który jest zaszyty w chipie Intela, to przyjąłbym, że Intel DEKLARUJE wykorzystanie sprzętowego źródła entropii, a co się tam dzieje naprawdę, to wie nieliczne grono wtajemniczonych.
A czy nie ma jakiegoś otwartego projektu stworzenia źródła entropii, które byłoby wykonane z powszechnie dostępnych elementów i otwartego kodu? Powiedzmy pendrive, który próbkowałby szumy rezystora, sygnał z fotodiody i sygnały indukowane w kilku antenkach? I żeby wynik był wykorzystywany w funkcjach systemu operacyjnego (/dev/random itp.)?
https://anonscm.debian.org/cgit/gnuk/gnuk/neug.git/tree/README
Super artykuł!
Chwila wytchnienia od artykułów sponsorowanych i nowych scamów.
Z tego art. płynie jeden wniosek…
Szyfrowanie jest trochę jak zakładanie drzwi antywłamaniowych do domu z wielkimi drzwiami balkonowymi…
Do momentu kiedy złodziej nie obejdzie domu jesteśmy bezpieczni.
W artykule brakło najważniejszego: praktycznego związku (potrzeby) losowych wartości z kryptografią. Ktoś może pomyśleć, że potrzebne to do generowania losowego hasła.
Jeśli ktoś jeszcze nie zna:
https://arstechnica.com/security/2013/09/fatal-crypto-flaw-in-some-government-certified-smartcards-makes-forgery-a-snap/
„The team of scientists uncovered what their paper called a „fatal flaw” in the hardware random number generator (RNG) used to ensure the numbers that form the raw materials of crypto keys aren’t based on discernible patterns. Randomness is a crucial ingredient in ensuring adversaries can’t break the cryptographic keys underpinning the smartcards issued to Taiwanese citizens.”
„Jeśli szukacie ciekawej historii o tylnych furtkach kryptograficznych umieszczonej w realiach Zimnej Wojny to polecamy ten artykuł, niestety po angielsku.”
Artykuł zaczyna się tak: „The story of the German Enigma machine is well-known – a device built to provide secure communications but which British code-breakers managed to crack at Bletchley Park”
Nie wiem czy po takim wstępie jest sens czytać dalej.
Dla tych, którzy uczą się historii z amerykańskich filmów: Enigmę początkowo złamali Polacy dzięki materiałom francuskiego wywiadu i błędom niemieckich operatorów. Enigma była ciągle rozbudowywana a procedury uszczelniane, i gdy w obliczu wojny dalsze prace w Polsce nie były możliwe, Polacy przekazali materiały Francuzom i Anglikom. W Anglii dokonano wielu postępów w łamaniu kolejnych wersji Enigmy, ale w końcu i Anglikom zabrakło środków. Wtedy wiedzę i maszyny („Bomby”) przekazali Amerykanom, którzy łamali kody do końca wojny.
może uaktualnisz wiki?
To teraz poproszę link do oryginału angielskiego, bo tego „tłumaczenia” po prostu nie da się czytać :P Widać, że ktoś tu nie za bardzo miał pojęcie o tym, co tłumaczy, a czego nie mógł zrozumieć, to przeskoczył machając rękami w powietrzu.
Trollujesz? 3/10 bo odpowiedziałem.
Gamma jednokrotna i klucz będący zapisem jednobitowym białego szumu radiowego (klucz o długości komunikatu). Brakuje mi jeszcze tylko pomysłu na bezpieczne przekazanie kluczy ;) no chyba że przez teleportację kwantową – ale jak będzie w zasięgu to po co szyfrować :)
Potrzebuje odzyskac hasło do Facebooka, czy ktoś może pomoc w tym temacie?