bezpieczeństwo Jądro nieprzewidywalności Jądro nieprzewidywalności Cezary Cerkwicki W wielu problemach z zakresu bezpieczeństwa informatycznego pojawia się problem nieprzewidywalności. Generowanie kluczy dla algorytmów szyfrujących, zalążków dla generatorów liczb pseudolosowych, identyfikatorów sesji, wektorów inicjalizacyjnych, tokenów, haseł jednorazowych to wszystko wymaga danych nieprzewidywalnych przez nikogo, w tym także potencjalnego napastnika. każdym środowisku programistycz- nizowany brutalny atak na zalążki składające się z bardziej nym mamy do dyspozycji funkcję, któ- prawdopodobnych timestampów. Drugim słabym punktem ra ma w nazwie random , co sugeruje, GLP jest fakt, że generowana przez nie sekwencja jest okre- Wże zwraca liczby losowe. W rzeczywisto- sowa, a więc po jakimś czasie zacznie się powtarzać. ści jest to interfejs do algorytmu generującego liczby pseu- Do zastosowań wymagających większego bezpieczeń- dolosowe. Na początku zatem odpowiemy sobie na pyta- stwa stosuje się specjalny podzbiór algorytmów GLP są nie: jak działają generatory liczb pseudolosowych i dlacze- to kryptograficznie bezpieczne generatory liczb pseudolo- go nie zastąpią nam prawdziwej losowości? sowych (KBGLP). Wymagania wobec nich są dużo surow- Generator liczb pseudolosowych (GLP) musi być za- sze i w sumie sprowadzają się do odporności wygenerowa- inicjowany jakąś losową wartością (nazywa się ją zalążkiem, nej sekwencji na jakiekolwiek ataki mające na celu odkrycie ang. seed). Następnie dla tej liczby generuje sekwencję liczb przyszłych wartości sekwencji (co jest już podstawą do kom- pseudolosowych. Ta sekwencja jest jednak całkowicie deter- promitacji całego systemu, którego bezpieczeństwo zależy ministyczna! Zatem jeśli tylko ktoś odgadnie, jaką wartością od nieprzewidywalności tych wartości). Liczby losowe, w zainicjowano algorytm, będzie w stanie przewidzieć wszyst- odróżnieniu od pseudolosowych, nie są deterministyczne i kie kolejne wartości sekwencji. nie da się ich przewidzieć. Skąd je jednak wziąć w kompute- Często stosowaną przez programistów techniką jest ini- rze, który jest deterministyczny aż do obrzydzenia? Do tego cjowanie generatora liczb pseudolosowych aktualnym cza- problemu jeszcze wrócimy. sem systemowym i datą (tzn. timestampem). Do zastosowań nie wymagających losowości wysokiej jakości (np. do wylo- Czy jakość liczby losowej sowania pozycji gwiazd w grze komputerowej) z pewnością można zmierzyć? to wystarczy. Jednak w zastosowaniach związanych z bez- Jak najbardziej. Narzędzia do tego służące stworzył Claude pieczeństwem już nie. Dość łatwo byłoby wykonać zorga- Shannon. Zacznijmy od kilku intuicji. Co zawiera więcej in- 58 lipiec 2007 linux@software.com.pl bezpieczeństwo Jądro nieprzewidywalności n na do wstępnej obróbki danych (jako że dane z Co więcej, stan puli entropii jest zapisywa- Hn p1, p2,..., pn = - log2 pi ( ) różnych zródeł mają też różną jakość). Pierw- ny na dysku podczas wyłączania systemu i od- "p i i=1 sza pula w miarę potrzeb jest zasilana warto- czytywany przy starcie, dzięki czemu na stan Rysunek 1. Entriopia ściami z drugiej puli. generowanej przez niego losowości ma wpływ formacji: wiadomość o ataku terrorystycznym Kiedy za pośrednictwem urządzeń /dev/ nie tylko to, co się zdarzyło od ostatniego re- czy o dużej liczbie wypadków drogowych? In- random lub /dev/urandom użytkownik zażąda startu, ale także zdarzenia wcześniejsze. tuicyjnie czujemy, że raczej ta o terrorystach, liczby losowej, liczony jest skrót kryptograficz- ponieważ jest to zdarzenie dużo rzadsze niż ny puli entropii algorytmem SHA i jego część Podsumowanie wypadki drogowe. Idzmy dalej. jest zwracana jako liczba losowa, a pozostała Bezpieczeństwo implementacji tego rozwią- Im jakieś zdarzenie jest mniej prawdopo- część jest dołączana do puli entropii. zania w kernelu zbadał Thomas Biege. Udało dobne, tym więcej zawiera informacji. Dwa Dobra funkcja skrótu kryptograficznego mu się przeprowadzić kilka ciekawych ataków niepowiązane ze sobą zdarzenia zawiera- powinna zapewniać następujące cechy: cząstkowych na generator liczb losowych oraz ją łącznie więcej informacji niż dwa zdarze- wypunktować jego słabe strony. nia związane np. relacją implikacji albo rów- " Odwzorowywać zbiór o zmiennej długo- noważności. ści (w naszym przypadku pulę entropii) " Podczas instalacji systemu wiele zródeł lo- Na bazie tych intuicji Shannon stworzył w zbiór o stałej długości (zwany skrótem sowości używanych przez kernel jest dość pojęcie entropii. Entropia to miara autoin- kryptograficznym albo hashem). przewidywalnych. Konsekwencją tego fak- formacji stowarzyszonej z danym zbiorem. " Drobną zmianę wejścia (np. zmiana jedne- tu może być niska jakość wygenerowanych Im zbiór zawiera więcej informacji (czyli nie- go bitu), która powinna skutkować dużą kluczy dla SSH. przewidywalności), tym większą ma entro- zmianą wyjścia. " Możliwy jest atak lokalny polegający na pię. Entropia osiąga maksimum, kiedy praw- " Odtworzenie wejścia na podstawie wyj- podawaniu kernelowi danych losowych dopodobieństwa występowania wszystkich ścia (odwracalność) powinno być możli- o niskiej jakości. W konsekwencji prowa- znaków są takie same. Entropia osiąga mini- wie trudne (najlepiej niemożliwe). Nazy- dzi to do przeszacowania entropii w sys- mum, kiedy zbiór jest absolutnie przewidy- wamy tę cechę także odpornością na tzw. temie i w konsekwencji generowania bar- walny (np. składa się z samych zer). Entropię ataki przeciwdziedzinowe. dziej przewidywalnych liczb. przedstawiamy wzorem zawartym na Ry- " Kiedy moc przeciwdziedziny funkcji jest " Możliwy jest atak lokalny polegający na po- sunku 1. większa niż jej dziedzina, funkcja na pew- daniu kernelowi danych spreparowanych Zmienne p1, p2, ..., pn to prawdopodo- no nie będzie różnowartościowa, a więc tak, aby algorytm przetwarzający pulę en- bieństwa występowania odpowiednich zda- będą się w niej zdarzały kolizje. Dobra tropii zniszczył ją, generując na przykład rzeń (w naszym przypadku są to prawdo- funkcja skrótu kryptograficznego powin- ciąg zer w miejsce danych losowych. podobieństwa występowania wartości kolej- na mieć owe kolizje porozrzucane moż- " Możliwe jest zdalne zwiększenie konsump- nych wartości w ocenianej sekwencji). Muszą liwie losowo, aby nie dało się ich zbyt ła- cji liczb losowych, co może doprowadzić być nieujemne, a ich suma musi być równa 1. two znajdować. Nazywamy tę cechę także do zmniejszenia nieprzewidywalności sys- odpornością na tzw. ataki kolizyjne. temu. Jak to robi kernel? " Implementacja funkcji extract_entropy() Generator liczb losowych został wprowadzo- Gwoli ścisłości, są to tylko najważniejsze wy- pozwala na odgadnięcie części zawarto- ny w kernelu 1.3.30 i od tamtej pory jego im- magania, a nie wszystkie. Opisanie wszystkich ści puli entropii. Jak pamiętamy, użytkow- plementacja znajduje się w pliku drivers/char/ wykracza poza ramy tego artykułu. nik otrzymuje część skrótu kryptograficz- random.c w zródłach jądra. Dwie pierwsze cechy są dość proste do nego z puli entropii, a pozostała część jest Aby móc tworzyć liczby prawdziwie loso- uzyskania. Cecha trzecia jest kluczowa, ponie- dodawana do puli. Okazuje się, że tę część we, trzeba posłużyć się jakimiś zródłami niede- waż od niej zależy czy pula entropii pozosta- daje się przewidzieć w jedynie 229 krokach. terministycznych danych, np. odstępami czasu nie tajna. Idealnie byłoby, gdyby funkcje skró- między wywołaniami przerwań (m. in. klawia- tu gwarantowały nieodwracalność, ale na razie Pozostaje mieć nadzieję, że wyżej wymienio- tury), współrzędnymi myszki albo czasem po- istnienie funkcji z taką gwarancją nie zostało ne niedoskonałości zostaną naprawione w naj- trzebnym systemowi na wykonanie określonej udowodnione. Czwarta cecha jest bardzo trud- nowszych wersjach jądra. procedury systemowej (co zależy m. in. od ak- na do osiągnięcia, to właśnie na tym polu poja- tualnego obciążenia systemu, charakterystyki wia się najwięcej doniesień o złamaniu dane- sprzętowej komputera, stopnia defragmenta- go algorytmu haszującego . Jednak w zasto- O autorze cji pamięci dyskowej oraz RAM-u). Te wszyst- sowaniu, o którym akurat mówimy, ta cecha Cezary Cerekwicki jest z wykształcenia in- kie zródła generują losowość o różnej jakości nie jest aż tak istotna jak np. w podpisach cy- formatykiem i politologiem. Pracował jako (która dodatkowo może zmieniać się w cza- frowych. Urządzenie /dev/random udostępnia programista, administrator, konsultant, tłu- sie, np. im więcej interakcji człowieka z kom- liczby losowe, jeśli tylko w puli entropii bę- macz, koordynator międzynarodowych pro- puterem, tym więcej jakościowo dobrej loso- dzie jej dostatecznie dużo. Jeśli nie, /dev/random jektów, dziennikarz i publicysta. Pisał pro- wości w systemie). Dlatego same te wartości nic nie zwróci. Urządzenie /dev/urandom dzia- gramy w dziesięciu językach programowa- nie są udostępniane użytkownikowi jako licz- ła inaczej. Dopóki w systemie jest dość entro- nia (od asemblerów po języki skryptowe) by losowe, tylko zbierane w strukturze danych pii, zwraca dokładnie to samo co /dev/random, w czterech systemach operacyjnych, na zwanej pulą entropii. Gwoli ścisłości napraw- różnica pojawia się dopiero, gdy entropia się dwóch platformach sprzętowych. dę są dwie pule entropii jedna przeznaczo- wyczerpie. Wówczas /dev/urandom generuje se- Kontakt z autorem: cerekwicki@tlen.pl na do serwowania danych i druga przeznaczo- kwencję pseudolosową. www.lpmagazine.org 59