2007.07_Jądro nieprzewidywalności_[Bezpieczenstwo].pdf

bezpieczeństwo

Jądro nieprzewidywalności

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, identyikatorów sesji, wektorów inicjalizacyjnych, tokenów, haseł jednorazowych

– to wszystko wymaga danych nieprzewidywalnych przez nikogo, w tym także potencjalnego napastnika.

nym mamy do dyspozycji funkcję, któ-

ra ma w nazwie „random”, co sugeruje,

że zwraca liczby losowe. W rzeczywisto-

ści jest to interfejs do algorytmu generującego liczby pseu-

dolosowe. Na początku zatem odpowiemy sobie na pyta-

nie: jak działają generatory liczb pseudolosowych i dlacze-

go nie zastąpią nam prawdziwej losowości?

Generator liczb pseudolosowych (GLP) musi być za-

inicjowany jakąś losową wartością (nazywa się ją zalążkiem,

ang. seed ). Następnie dla tej liczby generuje sekwencję liczb

pseudolosowych. Ta sekwencja jest jednak całkowicie deter-

ministyczna! Zatem jeśli tylko ktoś odgadnie, jaką wartością

zainicjowano algorytm, będzie w stanie przewidzieć wszyst-

kie kolejne wartości sekwencji.

Często stosowaną przez programistów techniką jest ini-

cjowanie generatora liczb pseudolosowych aktualnym cza-

sem systemowym i datą (tzn. timestampem). Do zastosowań

nie wymagających losowości wysokiej jakości (np. do wylo-

sowania pozycji gwiazd w grze komputerowej) z pewnością

to wystarczy. Jednak w zastosowaniach związanych z bez-

pieczeństwem już nie. Dość łatwo byłoby wykonać zorga-

nizowany brutalny atak na zalążki składające się z bardziej

prawdopodobnych timestampów. Drugim słabym punktem

GLP jest fakt, że generowana przez nie sekwencja jest okre-

sowa, a więc po jakimś czasie zacznie się powtarzać.

Do zastosowań wymagających większego bezpieczeń-

stwa stosuje się specjalny podzbiór algorytmów GLP – są

to kryptograicznie bezpieczne generatory liczb pseudolo-

sowych (KBGLP). Wymagania wobec nich są dużo surow-

sze i w sumie sprowadzają się do odporności wygenerowa-

nej sekwencji na jakiekolwiek ataki mające na celu odkrycie

przyszłych wartości sekwencji (co jest już podstawą do kom-

promitacji całego systemu, którego bezpieczeństwo zależy

od nieprzewidywalności tych wartości). Liczby losowe, w

odróżnieniu od pseudolosowych, nie są deterministyczne i

nie da się ich przewidzieć. Skąd je jednak wziąć w kompute-

rze, który jest deterministyczny aż do obrzydzenia? Do tego

problemu jeszcze wrócimy.

Czy jakość liczby losowej

można zmierzyć?

Jak najbardziej. Narzędzia do tego służące stworzył Claude

Shannon. Zacznijmy od kilku intuicji. Co zawiera więcej in-

lipiec 2007

Jądro

W każdym środowisku programistycz-

bezpieczeństwo

Jądro nieprzewidywalności

( ) =− = ∑

na do wstępnej obróbki danych (jako że dane z

różnych źródeł mają też różną jakość). Pierw-

sza pula w miarę potrzeb jest zasilana warto-

ściami z drugiej puli.

Kiedy za pośrednictwem urządzeń /dev/

random lub /dev/urandom użytkownik zażąda

liczby losowej, liczony jest skrót kryptograicz-

ny puli entropii algorytmem SHA i jego część

jest zwracana jako liczba losowa, a pozostała

część jest dołączana do puli entropii.

Dobra funkcja skrótu kryptograicznego

powinna zapewniać następujące cechy:

Co więcej, stan puli entropii jest zapisywa-

ny na dysku podczas wyłączania systemu i od-

czytywany przy starcie, dzięki czemu na stan

generowanej przez niego losowości ma wpływ

nie tylko to, co się zdarzyło od ostatniego re-

startu, ale także zdarzenia wcześniejsze.

H p p p p p

i i

Rysunek 1. Entriopia

formacji: wiadomość o ataku terrorystycznym

czy o dużej liczbie wypadków drogowych? In-

tuicyjnie czujemy, że raczej ta o terrorystach,

ponieważ jest to zdarzenie dużo rzadsze niż

wypadki drogowe. Idźmy dalej.

Im jakieś zdarzenie jest mniej prawdopo-

dobne, tym więcej zawiera informacji. Dwa

niepowiązane ze sobą zdarzenia zawiera-

ją łącznie więcej informacji niż dwa zdarze-

nia związane np. relacją implikacji albo rów-

noważności.

Na bazie tych intuicji Shannon stworzył

pojęcie entropii. Entropia to miara autoin-

formacji stowarzyszonej z danym zbiorem.

Im zbiór zawiera więcej informacji (czyli nie-

przewidywalności), tym większą ma entro-

pię. Entropia osiąga maksimum, kiedy praw-

dopodobieństwa występowania wszystkich

znaków są takie same. Entropia osiąga mini-

mum, kiedy zbiór jest absolutnie przewidy-

walny (np. składa się z samych zer). Entropię

przedstawiamy wzorem zawartym na Ry-

sunku 1.

Zmienne p1, p2, ..., pn to prawdopodo-

bieństwa występowania odpowiednich zda-

rzeń (w naszym przypadku są to prawdo-

podobieństwa występowania wartości kolej-

nych wartości w ocenianej sekwencji). Muszą

być nieujemne, a ich suma musi być równa 1.

Podsumowanie

Bezpieczeństwo implementacji tego rozwią-

zania w kernelu zbadał Thomas Biege. Udało

mu się przeprowadzić kilka ciekawych ataków

cząstkowych na generator liczb losowych oraz

wypunktować jego słabe strony.

• Odwzorowywać zbiór o zmiennej długo-

ści (w naszym przypadku pulę entropii)

w zbiór o stałej długości (zwany skrótem

kryptograicznym albo hashem).

• Drobną zmianę wejścia (np. zmiana jedne-

go bitu), która powinna skutkować dużą

zmianą wyjścia.

• Odtworzenie wejścia na podstawie wyj-

ścia (odwracalność) powinno być możli-

wie trudne (najlepiej niemożliwe). Nazy-

wamy tę cechę także odpornością na tzw.

ataki przeciwdziedzinowe.

• Kiedy moc przeciwdziedziny funkcji jest

większa niż jej dziedzina, funkcja na pew-

no nie będzie różnowartościowa, a więc

będą się w niej zdarzały kolizje. Dobra

funkcja skrótu kryptograicznego powin-

na mieć owe kolizje porozrzucane moż-

liwie losowo, aby nie dało się ich zbyt ła-

two znajdować. Nazywamy tę cechę także

odpornością na tzw. ataki kolizyjne.

• Podczas instalacji systemu wiele źródeł lo-

sowości używanych przez kernel jest dość

przewidywalnych. Konsekwencją tego fak-

tu może być niska jakość wygenerowanych

kluczy dla SSH.

• Możliwy jest atak lokalny polegający na

podawaniu kernelowi danych losowych

o niskiej jakości. W konsekwencji prowa-

dzi to do przeszacowania entropii w sys-

temie i w konsekwencji generowania bar-

dziej przewidywalnych liczb.

• Możliwy jest atak lokalny polegający na po-

daniu kernelowi danych spreparowanych

tak, aby algorytm przetwarzający pulę en-

tropii zniszczył ją, generując na przykład

ciąg zer w miejsce danych losowych.

• Możliwe jest zdalne zwiększenie konsump-

cji liczb losowych, co może doprowadzić

do zmniejszenia nieprzewidywalności sys-

temu.

• Implementacja funkcji extract_entropy()

pozwala na odgadnięcie części zawarto-

ści puli entropii. Jak pamiętamy, użytkow-

nik otrzymuje część skrótu kryptograicz-

nego z puli entropii, a pozostała część jest

dodawana do puli. Okazuje się, że tę część

daje się przewidzieć w jedynie 229 krokach.

Jak to robi kernel?

Generator liczb losowych został wprowadzo-

ny w kernelu 1.3.30 i od tamtej pory jego im-

plementacja znajduje się w pliku drivers/char/

random.c w źródłach jądra.

Aby móc tworzyć liczby prawdziwie loso-

we, trzeba posłużyć się jakimiś źródłami niede-

terministycznych danych, np. odstępami czasu

między wywołaniami przerwań (m. in. klawia-

tury), współrzędnymi myszki albo czasem po-

trzebnym systemowi na wykonanie określonej

procedury systemowej (co zależy m. in. od ak-

tualnego obciążenia systemu, charakterystyki

sprzętowej komputera, stopnia defragmenta-

cji pamięci dyskowej oraz RAM-u). Te wszyst-

kie źródła generują losowość o różnej jakości

(która dodatkowo może zmieniać się w cza-

sie, np. im więcej interakcji człowieka z kom-

puterem, tym więcej jakościowo dobrej loso-

wości w systemie). Dlatego same te wartości

nie są udostępniane użytkownikowi jako licz-

by losowe, tylko zbierane w strukturze danych

zwanej pulą entropii. Gwoli ścisłości – napraw-

dę są dwie pule entropii – jedna przeznaczo-

na do serwowania danych i druga przeznaczo-

Gwoli ścisłości, są to tylko najważniejsze wy-

magania, a nie wszystkie. Opisanie wszystkich

wykracza poza ramy tego artykułu.

Dwie pierwsze cechy są dość proste do

uzyskania. Cecha trzecia jest kluczowa, ponie-

waż od niej zależy czy pula entropii pozosta-

nie tajna. Idealnie byłoby, gdyby funkcje skró-

tu gwarantowały nieodwracalność, ale na razie

istnienie funkcji z taką gwarancją nie zostało

udowodnione. Czwarta cecha jest bardzo trud-

na do osiągnięcia, to właśnie na tym polu poja-

wia się najwięcej doniesień o złamaniu dane-

go algorytmu „haszującego”. Jednak w zasto-

sowaniu, o którym akurat mówimy, ta cecha

nie jest aż tak istotna jak np. w podpisach cy-

frowych. Urządzenie /dev/random udostępnia

liczby losowe, jeśli tylko w puli entropii bę-

dzie jej dostatecznie dużo. Jeśli nie, /dev/random

nic nie zwróci. Urządzenie /dev/urandom dzia-

ła inaczej. Dopóki w systemie jest dość entro-

pii, zwraca dokładnie to samo co /dev/random ,

różnica pojawia się dopiero, gdy entropia się

wyczerpie. Wówczas /dev/urandom generuje se-

kwencję pseudolosową.

Pozostaje mieć nadzieję, że wyżej wymienio-

ne niedoskonałości zostaną naprawione w naj-

nowszych wersjach jądra.

O autorze

Cezary Cerekwicki jest z wykształcenia in-

formatykiem i politologiem. Pracował jako

programista, administrator, konsultant, tłu-

macz, koordynator międzynarodowych pro-

jektów, dziennikarz i publicysta. Pisał pro-

gramy w dziesięciu językach programowa-

nia (od asemblerów po języki skryptowe)

w czterech systemach operacyjnych, na

dwóch platformach sprzętowych.

Kontakt z autorem: cerekwicki@tlen.pl

www.lpmagazine.org

, ,..., log

1 2

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: