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 |