Groźne skróty i kolizje

Słabości odkryte w popularnych funkcjach skrótu mogą w długim okresie zagrozić bezpieczeństwu poufności informacji w Internecie. Powodów do paniki nie ma, ale ostrożność jest wskazana. Niedawne informacje o nowych słabościach w najpopularniejszych algorytmach skrótu wiadomości - MD5 i SHA -wywołały spore zamieszanie w środowisku kryptologicznym.

Niepokój jest jak najbardziej uzasadniony - algorytmy te leżą u podstaw podpisu elektronicznego. Ale nie tylko - funkcje MD5 i SHA są podstawowymi "klockami" służącymi do budowania mechanizmów ochrony integralności danych w sieciach czy systemach operacyjnych. Radykalne podważenie zaufania pokładanego w tych algorytmach mogłoby mieć poważne konsekwencje dla wszystkich systemów kryptograficznych będących w powszechnym użyciu, jak PGP, SSL czy IPsec.

Niebezpieczne kolizje

Ubiegły tydzień był dla funkcji skrótu pechowy z kilku powodów. Pierwszą złą wiadomością był e-mail francuskiego badacza Antoine Joux na lokalną listę dyskusyjną poświęconą kryptografii, dotyczący kolizji w funkcji SHA-0. Joux przedstawił po prostu dwa całkiem różne ciągi bitów, które po "przepuszczeniu" przez funkcję SHA-0 dały identyczny skrót. Nic dodać, nic ująć - jest to bezdyskusyjna kolizja.

Mówiąc obrazowo, Francuz mógłby pokazać dwie różne wersje umowy biznesowej spisanej w formacie elektronicznym różniące się w detalach, takich jak cena czy termin. Fakt istnienia kolizji w funkcji skrótu umożliwiałby nieuczciwemu partnerowi przedstawienie przed sądem korzystnej dla siebie wersji umowy i dochodzenie swoich rzekomych praw na podstawie podpisu cyfrowego. W sytuacji, gdy poprawny podpis figuruje pod każdą z wersji umowy, rozstrzygnięcie tego, która jest prawdziwa, byłoby co najmniej trudne.

Wkrótce po tej informacji pojawił się artykuł czterech chińskich kryptologów, opisujący kolizje w innych popularnych funkcjach skrótu - MD5, MD4, HAVAL-128 i RIPEMD-160. Jeszcze później, na prestiżowej konferencji Crypto 2004 poświęconej nowym trendom w kryptografii dwóch izraelskich badaczy przedstawiło swoje prace nad słabościami w algorytmie SHA-0, omawiające szczegółowo to, co Joux pokazał w praktyce.

Nazwisko jednego z nich, Eli Bihama, nigdy nie wróżyło niczego dobrego szyfrom, które miały pecha pojawić się w tytule prezentacji razem ze słowem "słabości". Biham jest m.in. współodkrywcą dziur w szyfrowaniu GSM czy PkZip oraz współautorem tak zaawansowanych technik łamania szyfrów, jak kryptoanaliza różnicowa. Równocześnie Biham opowiedział też pokrótce o wstępnych wynikach prac nad kryptoanalizą algorytmu SHA-1, będącego nowszą wersją SHA-0. Ta informacja wzbudziła największe zaniepokojenie....

***

Wiecej w artykule Pawła Krawczyka - "Bezpieczeństwo na skróty" w tygodniku Computerworld nr 34/2004