Podpis do kosza?

Z szyfrowania bazującego na funkcjach MD5 i SHA-1 korzystamy niemal codziennie, przeglądając na przykład zabezpieczone strony WWW. Czy odkrycie luk w tych algorytmach oznacza, że nasze elektroniczne bezpieczeństwo jest zagrożone?

Wciągu ostatnich kilku miesięcy świat obiegły informacje o złamaniu popularnych w kryptografii algorytmów SHA-0, MD5 i SHA-1. Wydarzenia te nie nastąpiły co prawda po sobie lawinowo, ale i tak pokazują pewną niepokojącą tendencję do znajdowania luk w metodach uznawanych do tej pory za bezpieczne. Czy to oznacza, że przeciętny użytkownik komputera powinien zacząć się obawiać korzystania z bankowości elektronicznej lub poufnej poczty? Na szczęście nie jest aż tak źle, ale przyjrzyjmy się sprawie bliżej.

Odcisk palca

MD5 i SHA-1 to popularne algorytmy kryptograficzne, używane m.in. do tworzenia powszechnie stosowanych w Sieci podpisów cyfrowych. Korzystamy z nich na co dzień, na przykład podczas przeglądania stron zabezpieczonych protokołem SSL (Secure Sockets Layer) czy odczytywania e-maili kodowanych za pomocą PGP (Pretty Good Privacy). Zwykle jednak nie zdajemy sobie sprawy z istnienia tych funkcji ani też z istotnej roli, jaką pełnią one przy potwierdzaniu autentyczności informacji (patrz: $(LC134496: Funkcja hashująca a podpis cyfrowy)$). Wartości przez nie obliczane stanowią rodzaj cyfrowego odcisku palca i powinny być unikatowe dla dowolnych danych (np. plików).

Podpisując cyfrowo dokument czy też nawiązując bezpieczne połączenie SSL, korzystamy zatem z tzw. funkcji hashujących (nazywanych też często funkcjami skrótu), które obliczają wartość cyfrowego odcisku palca dla naszego dokumentu lub dla danych stwierdzających naszą tożsamość. Ostatecznie to właśnie na przykład 20-bajtowy ciąg danych decyduje o tym, czy dokument przesyłany przez Sieć jest autentyczny. O ile sprawa dotyczy rzeczy błahych, nie ma o co kruszyć kopii. Wyobraźmy sobie jednak, że mówimy o autentyczności umowy kupna-sprzedaży, gdzie w grę wchodzą prawdziwe pieniądze. Oczywiście powyższy tok rozumowania jest dość uproszczony, ale pokazuje kluczową rolę algorytmów takich jak SHA-1 w weryfikowaniu autentyczności informacji.

Jak szóstkę w totka

Jeśli przyjmiemy, że dane wejściowe mogą być dowolnie długie, a obliczona wartość funkcji hashującej ma wielkość 160 bitów (czyli 20 bajtów, jak w przypadku SHA-1), to wynika z tego, że – przynajmniej w teorii – zawsze będą istnieć różne informacje, które po przetworzeniu przez algorytm zwrócą tę samą wartość. Wynika to wprost z faktu, że liczba wszystkich możliwych kombinacji 160-bitowego odcisku palca jest skończona w odróżnieniu od otwartegozbioru podpisywanych plików. Nie ma w tym nic złego, dopóki prawdopodobieństwo znalezienia dwóch różnych danych wejściowych, które zwrócą tę samą wartość funkcji skrótu, jest bardzo niskie. W przypadku SHA-1 powinno ono wynosić 2-80, czyli tyle samo co szansa trafienia szóstki w Dużego Lotka 80 trylionów razy z rzędu (1 trylion to milion miliardów). Według specjalistów takie ryzyko można bez obaw zaakceptować i uznać algorytm za bezpieczny.

Kryptografia okazuje się jednak dziedziną płatającą figle i taką właśnie niespodziankę zafundował ostatnio światu zespół chińskich naukowców (Xiaoyun Wang, Yiqun Lisa Yin oraz Hongbo Yu) z Shandong University. Przedstawili oni sposób na uzyskanie dwóch wiadomości, które dadzą tę samą wartość funkcji SHA-1, ale w znacznie łatwiejszy sposób. Wymaga to wykonania „tylko” 2

69

operacji. Tym samym, jeśli mamy dokument podpisany cyfrowo, to musimy się liczyć z ryzykiem, że ktoś, stosując opracowaną przez nich metodę i dysponując odpowiednią mocą obliczeniową, może nasz podpis po prostu sfałszować. Sfałszować, a więc spreparować inny dokument, który wygeneruje tę samą wartość funkcji hashującej SHA-1 i zostanie przez odbiorcę uznany za autentyczny.

Zastosowania funkcji skrótu
Funkcja Zastosowanie
MD5 PGP, GPG, TLS/SSL, Kerberos, podpisy cyfrowe
SHA-1 PGP, SSL, HMAC, S/MIME, IPSec, SSH, TCPA, podpisy cyfrowe1)
1) oficjalny standard w USA