Na czym polegają funkcje skrótu

Gdy pobierasz oprogramowanie i porównujesz sumę kontrolną, logujesz się hasłem, podpisujesz dokument lub dodajesz blok do łańcucha Bitcoin, działa funkcja skrótu. Zamienia ona dowolną ilość danych w krótki odcisk palca o stałym rozmiarze, czyli skrót, w sposób, którego nie da się cofnąć ani podrobić. Pomysł jest prosty, ale wymagania wobec dobrej funkcji skrótu są surowe, a dwie z najpowszechniej używanych, MD5 i SHA-1, im nie sprostały.

Dwie wiadomości różniące się jedną literą trafiają do funkcji skrótu i wychodzą jako dwa zupełnie różne skróty SHA-256, z odwróconymi bitami zaznaczonymi na siatce
Dwie wiadomości różniące się jedną literą trafiają do funkcji skrótu i wychodzą jako dwa zupełnie różne skróty SHA-256, z odwróconymi bitami zaznaczonymi na siatce

Odcisk palca danych

Funkcja skrótu przyjmuje dane wejściowe dowolnej długości i zwraca skrót o stałej długości: 256 bitów w przypadku SHA-256, zapisanych jako 64 cyfry szesnastkowe. Te same dane zawsze dają ten sam skrót, więc skrót może reprezentować dane. Jeśli dwa pliki mają ten sam skrót SHA-256, możesz być pewien, że są identyczne, a jeśli choć jeden bit pobranego pliku uległ uszkodzeniu, jego skrót przestaje się zgadzać z tym, który podał wydawca. Ponieważ możliwych wejść jest znacznie więcej niż skrótów, każdy skrót musi odpowiadać wielu wejściom; dobra funkcja skrótu po prostu sprawia, że nie da się znaleźć żadnego z nich.

Trzy obietnice

Kryptograficzna funkcja skrótu składa trzy obietnice. Odporność na przeciwobraz: mając skrót, nie da się znaleźć wejścia, które go daje. Odporność na drugi przeciwobraz: mając wejście, nie da się znaleźć innego wejścia o tym samym skrócie. Odporność na kolizje: nie da się znaleźć żadnych dwóch wejść o tym samym skrócie. Dla idealnej funkcji skrótu o n bitach najlepszym atakiem jest zgadywanie: około 2ⁿ prób dla przeciwobrazu i około 2ⁿᐟ² dla kolizji. Funkcję skrótu nazywa się złamaną, gdy ktoś znajdzie sposób znacznie szybszy.

Efekt lawinowy

Zmień jeden bit wejścia, a każdy bit skrótu powinien odwrócić się z prawdopodobieństwem jednej drugiej, niezależnie od pozostałych. Wtedy drobna zmiana wiadomości daje skrót, który wygląda na zupełnie niezwiązany z poprzednim, a skrót nie zdradza niczego o tym, która część wejścia się zmieniła. SHA-256 osiąga to, wykonując 64 rundy, które rotują, dodają i łączą osiem 32-bitowych słów swojego stanu, tak że w ciągu kilku rund każdy bit wejścia wpływa na każde słowo. Prosta suma bajtów zmienia się natomiast dokładnie o tyle, o ile zmieniło się wejście, więc zdradza wszystko.

Wnętrze SHA-256

SHA-256 najpierw uzupełnia wiadomość: dopisuje bit 1, zera i długość wiadomości, aż całość będzie wielokrotnością 512 bitów. Następnie przetwarza wiadomość porcjami po 512 bitów. Każdy blok jest rozciągany do 64 słów, które są wmieszane w stan złożony z ośmiu 32-bitowych słów; jego wartości początkowe to stałe wzięte z pierwiastków kwadratowych pierwszych ośmiu liczb pierwszych. Stan po ostatnim bloku jest skrótem. Tę łańcuchową konstrukcję, nazwaną od nazwisk jej twórców (Ralph Merkle i Ivan Damgård), mają też MD5, SHA-1 i SHA-512; nowsza SHA-3, ustandaryzowana w 2015 roku, korzysta z innej konstrukcji, zwanej gąbką.

Ralph Merkle na Singularity Summit w 2007 roku. Łańcuchowa konstrukcja, której używa SHA-256, nosi jego imię i imię Ivana Damgårda.
Ralph Merkle na Singularity Summit w 2007 roku. Łańcuchowa konstrukcja, której używa SHA-256, nosi jego imię i imię Ivana Damgårda.

Atak urodzinowy

W grupie 23 osób szansa, że dwie mają urodziny tego samego dnia, wynosi nieco ponad połowę, choć rok ma 365 dni, bo liczy się liczba par, która rośnie z kwadratem wielkości grupy. Kolizje funkcji skrótu podlegają tej samej regule. Wśród 2ᵏ możliwych skrótów kolizji można się spodziewać po około √(π/2 · 2ᵏ) losowych wejściach. Dla 32 bitów to około 82 000 wejść, kwestia chwili; dla 128 bitów to około 2⁶⁴, co jest w zasięgu dużych przedsięwzięć obliczeniowych. Dlatego 128 bitów MD5 nigdy nie było hojnym zapasem i dlatego SHA-256 podwaja długość, aby zapewnić bezpieczeństwo na poziomie 128 bitów.

MD5 i SHA-1: złamane

Ron Rivest zaprojektował MD5 w 1991 roku, a NSA zaprojektowała SHA-1, opublikowaną w 1995 roku. W 2004 roku Xiaoyun Wang i jej współpracownicy pokazali, jak szybko tworzyć kolizje MD5, a w 2008 roku badacze wykorzystali je do podrobienia certyfikatu, któremu ufały przeglądarki internetowe. Szpiegowskie oprogramowanie Flame z 2012 roku użyło kolizji MD5, aby podszyć się pod aktualizację firmy Microsoft. SHA-1 padła w 2017 roku, gdy Google i CWI Amsterdam opublikowały dwa różne pliki PDF o tym samym skrócie SHA-1, po około 2⁶³ obliczeniach. Obie nadal nadają się do wykrywania przypadkowych błędów, ale nie do niczego, co mógłby wziąć na cel atakujący.

Gdzie używa się funkcji skrótu

Podpisy cyfrowe podpisują skrót dokumentu, a nie sam dokument. Git nazywa każdy plik i każdy commit jego skrótem, a górnicy w sieci Bitcoin szukają nagłówków bloków, których podwójny skrót SHA-256 zaczyna się od długiego ciągu zer. Strony internetowe nigdy nie powinny przechowywać haseł, tylko ich skróty; ale ponieważ ludzie wybierają krótkie hasła, taki skrót musi być powolny i z solą, obliczany metodami takimi jak bcrypt, scrypt czy Argon2, aby zgadywanie stało się kosztowne. Sumy kontrolne takie jak CRC-32, używane w plikach ZIP, obrazach PNG i sieciach Ethernet, też są funkcjami skrótu, ale zbudowanymi do wykrywania zakłóceń, a nie atakujących.

Wypróbuj sam

Otwórz laboratorium funkcji skrótu, aby obliczyć skrót własnego tekstu za pomocą SHA-256, SHA-512, SHA-1, MD5, CRC-32 i zabawkowej sumy bajtów. Zmień jeden znak i policz odwrócone bity, przeprowadź test lawinowy na tysiącu zmian jednego bitu, aby zobaczyć krzywą w kształcie dzwonu wokół połowy skrótu, i znajdź prawdziwe kolizje na pierwszych 8–32 bitach skrótu, by zobaczyć atak urodzinowy w działaniu.

Często zadawane pytania

Czy haszowanie to to samo co szyfrowanie?

Nie. Szyfrowanie ma być cofane przez tego, kto ma klucz; funkcja skrótu nie ma klucza i nikt nie może jej cofnąć. Szyfrowanie utrzymuje wiadomość w tajemnicy, a skrót daje tylko odcisk palca, który pozwala sprawdzić wiadomość, którą już masz.

Ile trwałoby znalezienie kolizji SHA-256?

Atakiem urodzinowym potrzeba około 2¹²⁸ obliczeń skrótu, a to liczba 39-cyfrowa. Nawet gdyby każdy komputer na Ziemi nie robił nic innego, trwałoby to nieporównanie dłużej niż wiek Wszechświata. Nie jest znana żadna droga na skróty.

Dlaczego dwa skróty tego samego tekstu nigdy się nie różnią?

Funkcja skrótu jest deterministyczna: nie ma w niej losowości ani klucza, więc te same bajty zawsze dają ten sam skrót. Drobne różnice, których nie widać, takie jak spacja na końcu, inny znak końca wiersza czy inna postać Unicode litery ze znakiem diakrytycznym, dają jednak inny skrót.

Co to jest sól?

Losowa wartość przechowywana obok skrótu hasła i wmieszana w niego. Dwóch użytkowników z tym samym hasłem dostaje wtedy różne skróty, a atakujący nie może użyć jednej, z góry obliczonej tabeli popularnych haseł do wszystkich kont.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz laboratorium funkcji skrótu