plik

bezpieczeństwo

Jądro nieprzewidywalności

lipiec 2007

bezpieczeństwo

Jądro nieprzewidywalności

www.lpmagazine.org

lin

ftw

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

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

lipiec 2007

bezpieczeństwo

Jądro nieprzewidywalności

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: cerekwicki@tlen.pl

O autorze

H p p

, ,...,

log

(

)

= −

∑