W tym tekście opisuję generator liczb losowych w Linuxie oraz cele do jakich może zostać wykorzystany. Generator ten jest dość skomplikowany, dlatego uznałem, że warto przedstawić najpierw przyczyny, dla których jest w ogóle potrzebny oraz pewne techniki stosowane nie tylko w jego kodzie. Tak więc strona ta dzieli się na dwie części: ogólną, dotyczącą kryptografii i jej związku z generatorami liczb losowych, oraz bardziej szczegółową, dotyczącą budowy podprogramu obsługi urządzenia random.c.
Obecnie technik kryptograficznych używa się głównie do dwóch celów:
Mówiąc o szyfrowaniu mamy na myśli parę funkcji: f i g, przy czym f będzie szyfrować, a g odszyfrowywać. Nadawca komunikatu K przekazuje odbiorcy f(K), odbiorca zaś obliczy g(f(K))=K. Jeżeli by się używało zawsze tych samych funkcji f i g, to groziłoby, że ktoś wreszcie złamie nasz szyfr. Co więcej, nie wiadomo, jak przekazać sobie opis tych funkcji. Pamiętajmy, że coś takiego, jak np. "zamiast litery 'a' wstaw 'b', zamiast 'b' wstaw 'c'..." jest banalne do złamania. Zachodzi więc potrzeba jakiegoś sparametryzowania funkcji f i g. Wtedy nadawca, mając komunikat K i parametr KLn, wysyła odbiorcy f(K, KLn). Natomiast odbiorca posiada swój parametr KLo i oblicza K=g(f(K, KLn), KLo). Parametry KLn i KLo nazywa się kluczami.
Powyższe postępowanie ma sens wtedy, gdy wielkość KLn i KLo nie jest przesadna - nadawca i odbiorca muszą się bowiem jakoś umówić co do wartości tych parametrów. Zwykle też funkcje f i g nie są utrzymywane w tajemnicy: ich kod jest dostępny publicznie. Natomiast klucze są zwykle sekretne. Typowy jest przypadek, gdy KLn=KLo jest liczbą o długości kilkudziesięciu (lub kilkuset) bitów. Jeżeli KLn=KLo, to odbiorca i nadawca muszą się jakoś umówić, jaki klucz wybrać. Nie mogą też nigdy zdradzić tego klucza, gdyż każdy mógłby wtedy mieć dostęp do ich tajemnic. Taka metoda szyfrowania nazywa się szyfrowaniem z kluczem tajnym. Kłopot, jaki powstaje przy używaniu tej metody, to konieczność uzgodnienia klucza przez obie strony "na boku", co często nie jest możliwe.
Inaczej jest przy tak zwanym szyfrowaniu z kluczem publicznym. Wówczas KLn!=KLo, co pozwala na to, by klucz KLn był ogólnie znany. Klucz KLo musi oczywiście być tajny niezależnie od przyjętej metody szyfrowania. W takiej sytuacji KLn nazywa się kluczem publicznym, a KLo kluczem prywatnym.
Jeżeli Prosiaczek chce nadać komunikat K do Puchatka, to korzysta jedynie z kluczy Puchatka (a nie ze swoich). Po prostu odczytuje z jakiegoś miejsca publiczny klucz Puchatka (KLn) i oblicza SZ=f(K, KLn). Następnie wysyła do Puchatka komunikat SZ. Puchatek po otrzymaniu komunikatu SZ bierze swój klucz tajny (KLo) i oblicza g(SZ, KLo)=K. Widzimy zatem, że Prosiaczek zdołał poinformować Puchatka o czymś, o czym Kłapouchy nigdy się nie dowie (o ile nie zgadnie prywatnego klucza Puchatka).
Metoda kluczy publicznych w prosty sposób rozwiązuje też drugi poważny problem kryptograficzny - problem weryfikacji tożsamości. O tym jednak napiszę nieco dalej.
Oczywiście zasadniczym problem implementacji szyfrowania z kluczem publicznym jest zapewnienie, że, znając funkcje f i g oraz wartość klucza publicznego KLn, nie da się obliczyć w rozsądnym czasie wartości klucza prywatnego KLo. A przecież jest to tylko problem rozwiązania pewnego równania: g(f(K, KLn), X)=K dla każdego K. Wystarczy z tego równania obliczyć X, by nic już nie było dla nas tajemnicą.
Z tej właśnie przyczyny funkcje f i g nie mogą być całkiem dowolne - muszą mieć specjalne własności kryptograficzne. Stąd pochodzi dodatkowy kłopot z szyfrowaniem kluczem publicznym - jest ono dużo wolniejsze niż szyfrowanie z kluczem tajnym. Dlatego często łączy się obie metody, szyfrując komunikat losowym kluczem tajnym, który to klucz szyfruje się następnie kluczem publicznym odbiorcy. Odbiorca najpierw odszyfrowuje klucz tajny za pomocą swojego klucza prywatnego, a następnie odszyfrowuje wiadomość za pomocą odzyskanego klucza tajnego. Tak utworzone komunikaty nazywamy kopertami cyfrowymi (digital envelopes).
Nazwa RSA pochodzi od twórców szyfru: Rivest, Shamir, Adleman. Jest to metoda z kluczem publicznym. Metoda ta działa następująco:
Dlaczego odszyfrowany przez Puchatka komunikat jest tym samym komunikatem, które nadał Prosiaczek? W tym celu rozumujemy następująco:
Udowodniliśmy, że RSA jest poprawny. Ale dlaczego jest to algorytm zapewniający bezpieczeństwo? Innymi słowy, dlaczego z klucza publicznego (n, e) nie da się obliczyć klucza prywatnego (n, d)? Zakłada się, że takie obliczenie byłoby zbyt kosztowne, ale tego nie udowodniono. W rzeczywistości nie udowodniono istnienia żadnej bezpiecznej metody szyfrowania z kluczem publicznym. Zauważmy, że gdybyśmy znali rozkład n na czynniki pierwsze, to nie mielibyśmy kłopotu z odnalezieniem klucza prywatnego. Również umiejętność liczenia pierwiastków w arytmetyce modularnej pozwoliłaby złamać RSA.
Jaka jest pożądana wielkość liczby n w algorytmie RSA? Obecnie używa się zwykle liczb o 128 lub 512 bitach. Można przeczytać, że koszt złamania klucza 512-bitowego to około $1,000,000 i osiem miesięcy pracy. W związku z tym uważa się, że za jakiś czas będzie trzeba przejść do kluczy większych rozmiarów.Liczby p i q zwykle się losuje, sprawdzając następnie, czy są pierwsze. Często nie wykonuje się dokładnego sprawdzenia, a jedynie zapewnia się, że są one pierwsze z bardzo dużym prawdopodobieństwem.
Inaczej niż RSA wygląda metoda zaproponowana przez Diffiego i Hellmana. Służy ona do uzgodnienia wspólnego tajnego klucza. Opiera się ona na tym, że obliczenie dyskretnego logarytmu jest zapewne bardzo trudne. Wygląda to następująco:
Ponieważ RSA i inne szyfry z kluczem publicznym nie są wystarczająco szybkie, więc zwykle korzysta się z klucza tajnego do szyfrowania komunikatu, by następnie klucz tajny zaszyfrować kluczem publicznym. Jak dotychczas przedstawione algortymy szyfrowały liczby. Powstaje problem, jak szyfrować dużo dłuższe komunikaty. Ten problem dotyczy sytuacji, gdy mamy już dany klucz (tajny), i chcemy zaszyfrować długą wiadomość tak, żeby analiza kryptograficzna nie pozwoliła z szyfrogramu uzyskać tekst oryginalny nie posiadając klucza. Będziemy rozpatrywać przypadki, gdy klucz odbiorcy jest równy kluczowi nadawcy.
Zakładamy, że wiadomość do zaszyfrowania jest podzielona na bloki ustalonej długości (np. 64 bity). Długość tych bloków będzie zależała od rodzaju szyfru. Najprostsza metoda polega na szyfrowaniu każdego bloku z osobna (szyfr prosty). Bardziej skomplikowana metoda polega na wykonaniu szyfrowania w paru kolejkach (szyfr iterowany). Najpierw szyfrujemy tekst kluczem K1, następnie kluczem K2, it. Często klucze następne pochodzą w jakiś sposób od klucza pierwszego.
Przykładem szyfru iterowanego jest tzw. szyfr Feistela. W tym szyfrze najpierw dzielimy tekst na połowy. Następnie szyfrujemy lewą połowę za pomocą K1. Nową lewą połową będzie stara prawa połowa, natomiast nową prawą połową będzie wykonanie operacji XOR na starej prawej połowie oraz zaszyfrowanej starej lewej połowie. W następnej kolejce robimy to samo używają innego klucza K2, itd. Zaletą tego systemu jest fakt, że do odkodowania wiadomości używa się tego samego algorytmu, tylko klucze trzeba brać w odwrotnej kolejności.
Zanim opiszę bardziej szczegółowo metody szyfrowania z kluczem tajnym, przedstawię możliwe rodzaje ataków na te szyfry. Im lepszy szyfr, tym trudniej będzie wykonać na niego atak i osiągnąć sukces. Ataki mogą być m.in. następujących rodzajów:
Najpopularniejszym szyfrem stosowanym obecnie jest szyfr DES (Data Encryption Standard), który jest oficjalnym standardem szyfrowania przyjętym przez rząd USA. Jest to szyfr z kluczem tajnym (klucz nadawcy=klucz odbiorcy), który łączy się często z RSA (tzn. klucz przekazuje się za pomocą RSA).
DES jest szyfrem typu Feistela. Wykonuje się w 16 kolejkach, korzystając z 56-bitowego klucza. W każdej kolejce używa się innego 48-bitowego klucza wyliczonego z głównego klucza 56-bitowego. Oryginał jest dzielony na bloki wielkości 64 bitów. Jak dotychczas jedyna udana próba złamania DES polegała na "nakarmieniu" go 243 oryginałami i analizie pochodzących stąd szyfrogramów. Kosztowało to 50 dni pracy 12 stacji roboczych HP 9735. Wykonanie takiego ataku w praktyce wydaje się niemożliwe. DES jest powszechnie uważany za bezpieczny, choć dużo mówi się o konieczności zwiększenia rozmiaru klucza (w obawie przed atakiem "na chama").
Istnieje kilka trybów działania DES:
Kryptograficzną funkcją mieszającą nazywamy taką funkcję H, że:
Kryptograficzne funkcje mieszające znajdują zastosowanie m.in. w tworzeniu elektronicznych podpisów oraz w generatorach liczb losowych. Również jeżeli chcemy uzyskać stempel czasowy, tzn. dać komuś tekst i uzyskać u niego potwierdzenie, że danego dnia ten tekst daliśmy, to funkcje mieszające się przydają. Jeżeli bowiem nie chcemy ujawnić tego tekstu, to stemplujemy tylko wartość otrzymaną z funkcji mieszającej. Zauważmy tu, że istota funkcji mieszającej polega na dwóch rzeczach:
Funkcje mieszające wraz z szyframi typu RSA pozwalają na elektronicznę kontrolę tożsamości nadawcy komunikatu. Przypuśćmy, że Puchatek chce wysłać do Prosiaczka komunikat K (niezaszyfrowany), ale nie jest pewien, czy Prosiaczek uwierzy, że to on napisał. Żeby udowodnić swoją tożsamość skorzysta z wersji RSA. Zachowujemy wszystkie oznaczenia z opisu algorytmu RSA - (n, e) to klucz publiczny, (n, d) to klucz prywatny (oba należą do Prosiaczka). Kontrola tożsamości wygląda następująco:
Istnieją jeszcze nieco inne metody weryfikacji tożsamości, ale wszystkie działają według podobnego schematu (użycie tu funkcji mieszającej jest związane z efektywnością - kodowanie całego komunikatu byłoby zbyt kosztowne).
Funkcje mieszające buduje się zwykle na fundamencie tzw. funkcji kompresujących. Funkcja kompresująca pobiera dane ustalonej długości i jakoś je skraca. Funkcję mieszającą tworzy się przez iterowane obliczanie funkcji kompresujących, tzn. H(a1,...,an)=C(C(..(C(s,a1),a2)..),an), gdzie C jest funkcją kompresującą dwukrotnie, a s jest wektorem startowym. Jeżeli funkcja C ma kolizje, to nazywamy je pseudokolizjami. Istnienie pseudokolizji nie jest uważane za dowód bezużyteczności funkcji, np. funkcja MD5 (opisana dalej), ma odkryte pseudokolizje, a mimo to jest uważana za bezpieczną.
Najpopularniejsze obecnie funkcje mieszające to MD4, MD5 oraz SHA i SHA-1. Spośród nich MD4 nie jest uważana za bezpieczną, a SHA-1, która jest modyfikacją SHA (Secure Hash Algorithm), jest uważana za najbezpieczniejszą z nich (choć jest nieco wolniejsza niż MD5).
Problematyka generatorów liczb losowych jest dość skomplikowana - trudno tu nawet o dokładną definicję. Często mówi się, że ciąg bitów jest losowy, jeżeli na podstawie wszystkich poza jednym nie da się przewidzieć wartości tego jednego (tzn. są one niezależne). Liczby losowe są potrzebne m.in. do generowania kluczy w kryptografii, ale przydają się też do symulacji, do randomizowanych algrytmów itp. Sławny Donald E. Knuth pisze: There are reports that many executives make their decisions by flipping a coin or by throwing darts, etc. It is also rumored that some college professors prepare their grades on such a basis. Jak widzimy, istnieje konieczność znalezienia dobrej metody obliczania liczb losowych. Ponieważ "wyliczanie liczb losowych" brzmi brzydko dla niektórych uszu, więc takie liczby nazywa się pseudolosowymi.
John von Neumann zaproponował jako pierwszy metodę uzyskiwania liczb pseudolosowych - tzw. middle-square method. Była ona bardzo prosta - brało się liczbę 10-cyfrową, liczyło jej kwadrat i następnie brało 10 jego środkowych cyfr w zapisie dziesiętnym. W ten sposób otrzymywało się kolejne liczby "losowe". Niestety okazało się, że liczby tak uzyskane nie są tak bardzo losowe, jak można by się było spodziewać. Okazuje się niestety, że liczby losowe trudno uzyskać za pomocą tworzenia przypadkowych i skomplikowanych algorytmów - bardzo często takie algorytmy szybko się degenerują i przechodzą w ciąg o krótkim okresie.
Jest oczywiste, że jeżeli stosujemy deterministyczny algorytm i mamy ograniczoną ilość pamięci, to nasz ciąg musi być okresowy. Jedną z cech dobrego generatora jest długi okres w porównaniu z zajętością pamięci. Inną cechą powinien być rozkład możliwie bliski jednostajnemu.
Bardzo popularnym generatorem liczb pseudolosowych jest tzw. generator liniowy. Kolejna liczba zależy tam tylko od poprzedniej, zgodnie ze wzorem:Generatory liczb losowych, a nie tylko pseudolosowych, próbuje się tworzyć korzystając z losowych zdarzeń w komputerze. Zdarzenia losowe w komputerze pochodzą z jego urządzeń zewnętrznych, w szczególności z klawiatury, myszy itp. Idea jest taka, żeby te losowe zdarzenia jakoś gromadzić, uzyskując coraz więcej losowych bitów. Jest istotne, że tylko bardzo mała część otrzymanych od urządzeń danych można uznać za losową. Np. naciśnięcie klawisza o danym kodzie jest bardzo mało losowym zdarzeniem: zwykle są to kody ASCII małych liter, a korelacja między nimi jest bardzo duża. Tworząc generator liczb losowych buduje się go tak, żeby dodanie całkowicie deterministycznych ciągów, np. 1000000 bajtów o tej samej wartości, nie zmniejszyło losowości zawartej w generatorze (choć oczywiście nie zwiększy się też ona specjalnie).
Generator liczb losowych może utrzymywać specjalny licznik, który liczyłby, ile jest jeszcze losowych bitów w generatorze. Implementacja takiego licznika jest bardzo trudna, dlatego stosuje się raczej liczenie "na oko" i trudno powiedzieć, czy z tych obliczeń otrzymuje się sensowne wyniki.
Dodatkową cechą generatora służącego do celów kryptogrficznych powinno być, że nawet znając kod generatora i odczytując z niego kolejne tworzone przez niego liczby losowe, nawet jeżeli nie dostaje on żadnych kolejnych losowych bitów, nie powinno się dać przewidzieć, jaka jest następna liczba (ta cecha odnosi się również do generatorów pseudolosowych).
Działanie generatora liczb losowych w Linuxie jest następujące:
Generator utrzymuje
512 bajtowy "pojemnik losowości". Początkowo pojemnik jest inicjalizowany wartościami
opisującymi system, czas itp. Istnieje procedura, która umieszcza w pojemniku nową
wartość losową. Teoretycznie procedura ta powinna zapewniać, że "losowość" pojemnika
się nie zmniejszy, nawet jeśli otrzymana liczba nie będzie zbyt losowa. Głównym źródłem
losowości dla generatora jest wartość zmiennej jiffies w momencie wystąpienia
jakiegoś zdarzenia (np. przerwania, ruchu myszą...). Poza tym wszystkie te sytuacje
dostarczają jeszcze dodatkowych informacji, np. kod naciśniętego klawisza. Generator
próbuje obliczać, ile bitów prawdziwie losowych jeszcze jest w jego pojemniku. Kody klawiszy,
numery wywołanych przerwań itp. są dodawana do pojemnika, ale entropii (tak w kodzie
generatora nazywa się liczba losowych bitów) nie zwiększają. Jedynie umieszczenie
wartości jiffies może zmienić entropię (można jeszcze ręcznie zwiększyć
entropię za pomocą ioctl). Jeżeli ktoś chce otrzymać nową liczbę losową, to
generator oblicza wartość mieszającą całego pojemnika za pomocą funkcji mieszającej
MD5 lub SHA. Ta wartość jest zwracana, a generator dokonuje jeszcze pewnych
zmian w pojemniku, żeby następna liczba nie była taka sama jak poprzednio.
Użytkowanie generatora
Z punktu widzenia użytkownika generator są to dwa urządzenia znakowe: /dev/random i /dev/urandom. Różnią się one jedynie tym, że /dev/random blokuje proces do momentu znalezienia przynajmniej bajtu entropii i zwraca mu tylko bajty naprawdę losowe, natomiast /dev/urandom zawsze daje tyle "losowych" bajtów, ile żąda proces. Urządzenia te korzystają z jednego pojemnika i różnią się jedynie implementacją funkcji read oraz brakiem dla /dev/urandom funkcji select.
Na obu urządzeniach można wykonywać następujące operacje:
Implementacja generatora
Implementacja podprogramu obsługi to sprawa dość skomplikowana. Wydaje się, że najgorsza w niej jest funkcja dodawania słowa (32-bitowego) do pojemnika. Wygląda to następująco:
Dla każdego źródła losowości w systemie urządzenie utrzymuje specjalną strukturę informacyjną. Źródłami losowości są mysz, klawiatura, linie przerwań IRQ oznaczone flagą SA_SAMPLE_RANDOM, urządzenia blokowe (wysyłają coś w związku z obsługą żądania zapisu/odczytu) oraz sam generator liczb losowych, który uważa wywołanie swoich funkcji przez kogoś z zewnątrz za wydarzenie losowe. Po otrzymaniu losowego słowa z jakiegoś z tych źródeł losowości, dzieje się co następuje:
Jeżeli ktoś pobiera losowy bajt z pojemnika, to nie dajemy mu bezpośrednio bajtów z pojemnika, tylko bajty przekształcone przez SHA lub MD5. Dzięki temu nie zgadnie, co my mamy w pojemniku, a poza tym wynik będzie może jeszcze bardziej losowy. Po wydaniu takiego bajtu mieszamy w pojemniku jeszcze raz za pomocą MD5 lub SHA, żeby następnym razem nie dać tej samej liczby (można więc powiedzieć, że w istocie jest to generator pseudolosowy opraty o MD5 lub SHA).
Na koniec chciałbym mniej więcej opisać działanie funkcji mieszającej MD5. Jej kod można znaleźć w random.c oraz w dokumencie RFC1321 (napisanym przez autora algorytmu - Ronalda Rivesta). Opiszę tę funkcję w przybliżeniu, gdyż wydaje się, że szczegóły nic a nic nie wyjaśniają.
Algorytm MD5 pobiera komunikat dowolnej długości i zwraca pewną wartość 128-bitową. Zakłada się, że MD5 jest kryptograficzną funkcją mieszającą (patrz).
Pierwszy krok algorytmu polega na dopisaniu bitów do komunikatu, by miał on długość 448 bitów modulo 512. W wypadku gdy jego długość w bitach dzieli się przez 512 z resztą 448 dodaje się jeszcze 512 bitów (tzn. zawsze się coś dodaje). Najpierw dodajemy bit 1, następnie same zera.
Następnie dodajemy długość komunikatu, zapisaną jako liczba 64-bitowa. Od tego momentu nasz komunikat ma długość w słowach (32-bitowych) podzielną przez 16.
Będziemy korzystać z czterech specjalnych funkcji (X, Y, Z - słowa 32-bitowe):
Będziemy korzystać z rejestrów A, B, C, D i tablicy T, w której pod indeksem i znajduje się część całkowita liczby 4294967296*abs(sin(i)) (???). Rejestry A, B, C, D inicjalizujemy tajemniczymi liczbami, a następnie dla każdego 16-słowowego bloku wykonujemy:
Jak widać istotnie trudno jest coś sensownego wykombinować z tego algorytmu. Wygląda na to, że jego wyniki muszą być losowe, że aż strach.