bezpieczeństwo

Jądro nieprzewidywalności

58

lipiec 2007

bezpieczeństwo

Jądro nieprzewidywalności

59

www.lpmagazine.org

lin

ux

@

so

ftw

ar

e.

co

m

.p

l

Jądro

nieprzewidywalności

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.

Cezary Cerkwicki

W

każdym środowisku programistycz-
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 kryptograficznie 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-

bezpieczeństwo

Jądro nieprzewidywalności

58

lipiec 2007

bezpieczeństwo

Jądro nieprzewidywalności

59

www.lpmagazine.org

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.

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-

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 kryptograficz-
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 kryptograficznego

powinna zapewniać następujące cechy:

• 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
kryptograficznym 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 kryptograficznego 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.

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ą.

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.

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.

• 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 kryptograficz-
nego z puli entropii, a pozostała część jest
dodawana do puli. Okazuje się, że tę część
daje się przewidzieć w jedynie 229 krokach.

Pozostaje mieć nadzieję, że wyżej wymienio-
ne niedoskonałości zostaną naprawione w naj-
nowszych wersjach jądra.

Rysunek 1.

Entriopia

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: [e-mail]

O autorze

H p p

p

p

p

n

n

i

i

i

n

1

2

2

1

, ,...,

log

(

)

= −

=

∑