Cześć!

W poprzednim wpisie wspominałem Wam, że jeśli używamy klucza tylko i wyłącznie jednorazowo to szyfr jest na tyle bezpieczny na ile nieprzewidywalne są liczby losowe użyte do szyfrowania. Może Was to nieco dziwić… Każdy z nas, od wczesnego dzieciństwa przyzwyczajony jest do losowych wyników poprzez rzut kością w grach planszowych czy przypadkowej kolejności kart w potasowanej talii (notabene do tematu gier karcianych wrócę nieco później) więc losowość do pewnego stopnia jest dla nas naturalna.

Niestety (albo stety) nie jest tak dla komputera, który ze swej natury jest deterministyczny. Podczas gdy my, rzucając kością wyzwalamy zdarzenia losowe, ponieważ nie jesteśmy w stanie rzucić kością zawsze dokładnie tak samo (chyba, że kość jest kantowana) to komputer nie ma takiej możliwości. Prawdziwa losowość może bazować na szumie sensorów albo zjawiskach fizycznych – może to być np. rozpad promieniotwórczy nie mówiąc już o innych zjawiskach elektromagnetycznych lub kwantowych.

Sensory jako źródło entropii

Spójrzcie na nagranie poniżej – prezentuje ono zapis odczytów akcelerometru, który jak widzicie tkwi w bezruchu… A odczyty szaleją!

Odczyty akcelerometru

Szum w odczytach czujników jest sporym problemem dla robotyków, którzy radzą sobie z nimi wykorzystując różnego rodzaju filtry, takie jak np. filtr Kalmana dla nas ma on jednak wielkie znaczenie. Pokazuje, że czujniki mogą stanowić źródło losowości (albo używając mądrzejszych słów entropii) dla komputera. Jeśli się zastanowimy, to upakowana jest w nim cała masa różnych komponentów elektronicznych, które często potrzebują ze względów bezpieczeństwa np. informację o temperaturze komponentu… System operacyjny zbiera te odczyty generując entropię dla generatorów liczb losowych.

Wykres poniżej przedstawia obciążenie procesora w czasie pracy komputera. Niektóre programy tj. na przykład VeraCrypt (służący do szyfrowania danych) wykorzystują w tym celu chaotyczne trajektorie ruchów myszy użytkownika w czasie instalacj oprogramowania.

Rysunek 1 Obciążenie procesora przy włączonym Wordzie i Netflix’ie

To podejście ma jednak drobną wadę – jest powolne. Dlatego informatycy wymyślili generatory liczb pseudolosowych. Algorytmy, które zainicjowane ziarnem, podają na wyjściu liczby, sprawiające wrażenie losowych.

Generatory liczb pseudolosowych

Jednym z przykładów takich algorytmów jest liniowy generator kongruentny (ang. linear congruential pseudorandom generator, LCRNG). Wiem, nazwa brzmi mądrze, gdyż wzięła się stąd, że wykorzystuje on reszty z dzielenia (stąd kongruentny). Działa on w następujący sposób:

1. Użytkownik inicjuje generator ziarnem, które oznaczamy jako X₀
2. Kolejne liczby są generowane wg. Następującej formuły

Zapis ten oznacza, że  ma wartość reszty z dzielenia  przez m, gdzie a, c oraz m są stałymi w czasie działania algorytmu.

Zróbmy drobny test, wykorzystajmy tę formułę w wyznaczenia przybliżonej wartości liczby π metodą Monte Carlo (tak na marginesie, została ona opisana i po raz pierwszy wykorzystana przez polskiego matematyka ze Lwowa, Stanisława Ulama). Działa ona w następujący sposób:

Losujemy punkty o współrzędnych z przedziału od -1 do 1 i zliczamy liczbę punktów, które znajdują się w kole o środku w punkcie (0, 0) i promieniu 1 – pole takiego koła wynosi… Niespodzianka, właśnie liczba π 😊. Punkty te należą do koła, jeśli spełniają nierówność .

Liczba π ma wtedy wartość  .

Rysunek 2 Rysunek poglądowy przygotowany z wykorzystaniem programu Wolfram Mathematica

Program montecarlo https://gitlab.com/sisiphus-on-code/cryptography/-/tree/main/random_number_generator/montecarlo zawiera implementację algorytmu LCRNG i wykorzystuje go do wyznaczenia wartości liczby Pi. Możecie sprawdzić, że im więcej punktów losujemy, tym bliżej otrzymana wartość bliska jest liczbie 3,14 zatem algorytm z dużym prawdopodobieństwem generuje liczby losowe. Pozostaje tylko pytanie, czy jest jakiś haczyk, tym bardziej, że jest on wykorzystywany w bibliotekach standardowych wielu różnych języków programowania – w tym glibc języka C, która jest swego rodzaju lingua franca świata komputerów. Tak na marginesie, z niej właśnie wziąłem parametry do generatora użytego w metodzie Monte Carlo.

Niestety, jak się za chwilę dowiecie algorytm ten w pewnych okolicznościach może być przewidywalny o czym boleśnie przekonały się swego czasu kasyna Las Vegas.

Historia o automatach do gry w pokera

Kilka lat temu czytałem książkę Kevina Mitnicka „Sztuka infiltracji”, obecnie szanowanego konsultanta do spraw bezpieczeństwa komputerowego, a kiedyś hakera znanego pod pseudonimem Condor (było to nawiązanie do filmu z „Trzy dni kondora” z roku 1975, w którym główną rolę grał Robert Redford).

Otóż Mitnick, przytoczył w niej historię grupki znajomych, którzy mieli przeprowadzić konsultacje w Nevadzie i pod wpływem ich piękniejszych, drugich połówek zdecydowali się by przy okazji znaleźć sposób na rozbicie puli w kasynach Vegas. Czego nie zrobią mężczyźni, gdy kobiety im wejdą na ambicje!

Grupa analizowała przede wszystkim dwie możliwości w jaki sposób można potencjalnie zaatakować kasyno albo mówiąc bardziej profesjonalnym językiem, wyznaczyli następujące wektory ataku:

1. Fizyczne włamanie do maszyn i “podmiana firmware’u”
   
   Umieszczenie własnego chipu, aby zastąpić oryginalne oprogramowanie wersją zapewniającą bardziej atrakcyjne wypłaty. Rozwiązanie to jest o tyle problematyczne, że wymaga współpracy z technikiem opiekującym się automatami – można byłoby je porównać z walnięciem staruszki po głowie i odebraniem jej torebki,
   
   
2. Atak zaczerpnięty z książki The Eudaemonic Pie Thomasa Bassa (Penguin, 1992).
   
   Grupa komputerowców i fizyków rozpracowywali w latach 80 system ruletki w kasynach. Opracowali komputerek, któremu jeden członek grupy podawał prędkość koła ruletki
   oraz obrotów kulki i próbował przewidzieć wynik gry. Nie wygrali tym sposobem tony złota, gdyż ich metoda była skażona tym, że dużą rolę odgrywało w niej zachowanie i stosunki międzyludzkie – nie mogli się wydać podejrzani innym uczestnikom gry.

Podejście, które zastosowała grupa bazowała na ataku 2, ale wybrali grę, która ograniczała stosunki między ludzkie do minimum – czyli automaty do gry w pokera.

Prace nad problemem rozpoczeli or pragmatycznego założenia związanego względami proceduralnymi. Maszyny zanim zostaną dopuszczone do użytku muszą przejść testy wymagane przez Komisję Gier Hazardowych Las Vegas. Testy te nie dość, że zabierają bardzo dużo czasu to do tego są jeszcze niezwykle kosztowne. Ich celem jest sprawdzenie czy z jednej strony automat zapewnia dostateczną losowość, z drugiej czy nie zapewnia nieuczciwej przewagi kasynu. Do pewnego stopnia musi być przewidywalne, jak często pada zwycięskie rozdanie, aby kontrolować maksymalną wartość puli. W związku z tym kasyna decydowały się dłużej eksploatować przestarzałe maszyny niż to było wskazane. Bezpieczeństwo poprzez wycinkę drzew i generowanie tony dokumentów jest elementem charakterystycznym dla branży automotive. Za pewne pożalę się na to w którymś z kolejnych artykułów.

Panowie koledzy pojechali więc do sąsiedniego stanu i.… zakupili w nieoficjalnym obiegu jedną ze starszych maszyn do pokera, gdyż założyli (jak się później okazało słusznie), że podobne są używane w Vegas. Stwierdzili też, że skoro planują atakować automaty o niskich wypłatach to za pewne generator nie jest zbyt silny i może być wadliwie zaimplementowany 😊. Maszyny po przewiezieniu do wynajętych przez nich apartamentów, zostały rozebrane na części pierwsze po czym zrzucili zawartość pamięci Flash z programem.

Stosując narzędzia inżynierii wstecznej (czyli odzyskiwaniu informacji jak on działa na podstawie analizy istniejącego produktu), odkryli, w jaki sposób generowane są wartości kart oraz to,
że losowość zapewniana jest przez znany nam już algorytm LCG. Dało im to zdolność do przewidzenia, za ile rozdań pojawi się zwycięskie rozdanie. W jaki sposób możemy przewidzieć kolejne liczby generatora?

Hakowanie glibc’a?

Spójrzcie na zamieszczony poniżej fragment linuksowego manual’a dotyczącego funkcji random().

Rysunek 3 Fragment linuksowego manuala dotyczącego funkcji random()

Kluczowe jest pierwsze zdanie: “The random() function uses a nonlinear additive feedback random number generator”, które jest nie do końca prawdziwe. Dlaczego?

Jeśli zerkniecie https://github.com/lattera/glibc/blob/master/stdlib/random_r.c znajdziecie tam kod, który na pierwszy rzut oka (i nawet na drugi 😉) wydaje się całkiem skomplikowany jednak Peter Selinger z Uniwersytetu Dalhousie na stronie https://www.mathstat.dal.ca/~selinger/random/ zaprezentował algorytm, który produkuje dokładnie te same wartości co funkcja random() (oczywiście dla tego samego ziarna).

Na stronie mojego repozytorium https://gitlab.com/sisiphus-on-code/cryptography/-/tree/main/random_number_generator/glibc_randomness znajdziecie trzy programy:

• GlibcGenerator – oczekuje podania ziarna generatora, informację ile liczb losowych ominąć i ile liczb wydrukować na ekranie. Liczby są wygenerowane używając funkcji random().
• AlternativeGenerator – oczekuje na podobne parametry wejściowe jak program powyżej jednak liczby generowane są z wykorzystaniem algorytmu Selingera, który nieco zrefaktoryzowałem,
• GlibcNextPredictor – oczekuje na 31 liczb podanych poprzez standardowe wejście i na ich podstawie generuje jaka będzie następna liczba dostarczona poprzez generator glibc’a.

Zajmiemy się teraz przez moment analizą programu AlternativeGenerator. Co możemy zaobserwować przy pierwszym czytaniu kodu

1. W funkcji main nie ma żadnego bezpośredniego odwołania do struktury state (typu randomness_state).

Struktura ta jest wewnętrznym stanem generatora, gdyby wyciągnąć funkcje init_randomness() oraz get_random() do osobnego pliku, programista nie miałby do niej w ogóle dostępu.

• Przed użyciem funkcji get_random() wywołujemy funkcję init_randomness() zatem sekwencja jest podobna do użycia funkcji srand() i random().
• Algorytm LCG jest używany TYLKO I WYŁĄCZNIE na początku inicjowania tablicy stanów, później używane są już proste sumy lub podstawienia.
• Funkcja random() nie zwraca nam dokładnej wartości przechowywanej w wewnętrznym stanie tylko obciętą o najmniej znaczący bit.

Kluczowe dla nas będą obserwacje 3 i 4. Możemy zauważyć, że jeśli dostaliśmy 31 liczb z generatora to kolejna jest sumą liczb o indeksach 0 oraz 28. Jednak musimy sobie przypomnieć, że liczby które widzieliśmy na ekranie są obcięte o jeden bit względem wewnętrznego stanu generatora zatem kolejna liczba może być mieć jedną z następujących wartości:

• 2 * buffer[0] + 2 * buffer[28] – brakującym bitem obu liczb jest zero
• 2 * buffer[0] + 2 * buffer[28] + 1 – brakującym bitem jednej z liczb jest 1 (najbardziej prawdopodobna).
• 2 * buffer[0] + 2 * buffer[28] + 2 – brakującym bitem obu liczb jest jeden

Jak widzicie udało nam się z pewnym prawdopodobieństwem określić jakie będzie kolejna liczba pochodząca z generatora.

Na ile dobry jest los?

Skoro już wiemy, że generator generatorowi nie jest równy, warto zastanowić się nad tym czy da się to w jakiś sposób sprawdzić.

Możemy tego dokonać z wykorzystaniem narzędzi takich jak:

• Dieharder,
• TestU01.

Próbują one znaleźć korelację pomiędzy kolejnymi liczbami losowymi implementując różne testy statystyczne (np. bazujące na paradoksie urodzinowym). Przykładowo, mogą one zliczać długość sekwencji rosnących i malejących wygenerowanych liczb i sprawdzać ich rozkład (żeby potencjalny adwersarz nie mógł określić prawdopodobieństwa czy kolejna liczba będzie większa czy mniejsza).
Do zastosowań kryptograficznych ważne jest aby rozkład generowanych liczb był jednostajny.
W rozkładzie jednostajnym, każdy bajt jest tak samo prawdopodobny, podczas gdy w rozkładzie normalnym wartości środkowe występują znacznie częściej niż skrajne.

Rysunek 4 Przykładowy rozkład zbliżony do normalnego

Rysunek 5 Przykładowy rozkład zbliżony do jednostajnego

Swego czasu, zdarzyło mi się eksperymentować ze sprzętowym generatorem liczb losowych dostępnego na płytce Nucleo L552ZE-Q. Test dieharder jest to aplikacja, która przyjmuje testowane liczby na standardowe wejście (tj. wejście na konsolę terminala) lub z pliku tekstowego. TestU01 jest natomiast dostarczany jako biblioteka, gdzie bateriom testowym przekazujemy funkcję generującą (czy w moim przypadku dostarczającą pobrane poprzez UART) liczby losowe. Wykonałem te testy na generatorze RC4, linuksowym pseudourządzeniu /dev/urandom (w systemach uniksowych każde urządzenie konceptualnie jest reprezentowane jako plik, generator liczb pseudolosowych nie jest prawdziwym urządzeniem, a sztucznie utworzonym przez jądro systemu, stąd prefiks pseudo) oraz sprzętowym z mikrokontrolera. Jakie były wyniki? Pierwsze dwa generatory okazały się bezpieczne podczas gdy STM’owy okazał się być wadliwy – prawie żaden nie przechodził. Wydało mi się to dziwne, gdyż znalazłem informację, że przechodzą na nim testy sugerowane przez NIST (bardzo ważną organizację wytyczających normy cyberbezpieczeństwa dla firm prywatnych). Myślałbym, że to wina sprzętu, jednak testy dostarczone przez producenta przechodzą właściwie (a niespodziewałbym się, że firma taka jak STMicro kłamie), stąd podejrzewam raczej, że źródło problemów znajdowało się między klawiaturą a krzesłem 😉. Później pojawiły mi się pilniejsze rzeczy do zrobienia więc nie inwestygowałem tego dalej.

Kończąc, sprzedam Wam anegdotkę, że pisząc ten test dość boleśnie przekonałem jak wiele daje buforowanie. Wczytując po jednej linii z UART’u duża bateria testowa TestU01 wykonywała się 3h i końca nie było widać podczas gdy zaimplementowałem wczytywanie bufora po 256 znaków czas skrócił się do… o ile mnie pamięć nie myli pół godziny. W tym momencie przypomniałem sobie cytat twórcy jądra systemu Linux, Linusa Torvaldsa, który słynie z dość „obrazowego” języka:

„Chciałbym również zasugerować, że należałoby wstecznie zaabortować każdego geniusza, który pomyślał, że czytanie danych przy pomocy JEDNEGO J*BANEGO BAJTU NA RAZ przez wywołania systemowe to dobry pomysł. Kto, do cholery, robi tak debilne rzeczy? Jak to się stało, że nie umarł jako dziecko – mając na uwadze, że prawdopodobnie był za głupi na znalezienie cycka, którego miał ssać.”

Całe szczęście on tego nie widział i to było tylko na chwilę 😉! Tymczasem chciałbym się z Wami pożegnać, a w kolejnym artykule pokażę Wam małe matematyczne czary mary – zajmiemy się tak zwanymi dowodami o wiedzy zerowej.

Pozdrawiam,
Paweł

UWAGA KOŃCOWA 1 – Jak tutaj się prezentuje algorytm RC4? Pewne sekwencje bajtów pojawiają się nieco częściej niż inne co zostało wykorzystane w ataku Fluhrera-Mantina-Shamira. Analizując dużą liczbę wiadomości zaszyfrowanych tym samym kluczem, można odzyskać klucz co pozwoliło złamać standard szyfrowania WiFi WEP (co przyśpieszyło rozwój standardu WPA). Istnieje jednak możliwość obrony przed tym atakiem – należy odrzucić początkową (co najmniej pierwsze 1024 bajty) porcję danych ze strumienia szyfrującego.