Odcisk palca dowolnych danych
Funkcja skrótu to przepis, który z dowolnych danych wylicza krótki ciąg znaków, nazywany skrótem. Danymi może być jedno słowo, cała książka albo plik z filmem, a skrót zawsze ma tę samą długość. W funkcji SHA-256 to 256 bitów, czyli pojedynczych zer i jedynek. Taki ciąg trudno czytać, więc każde cztery bity zapisuje się jednym znakiem szesnastkowym: cyfrą od 0 do 9 albo literą od a do f. Stąd zapis z 64 znaków.
Te same dane zawsze dają ten sam skrót. Dlatego skrót działa jak odcisk palca. Pozwala sprawdzić, czy dwie rzeczy są identyczne, bez porównywania ich w całości.
Żeby jednak skrót mógł chronić dane, potrzebna jest kryptograficzna funkcja skrótu, czyli taka, która spełnia trzy warunki:
- Jednokierunkowość. Ze skrótu nie da się w praktyce odtworzyć danych. Nie znamy sposobu lepszego niż zgadywanie.
- Odporność na kolizje. O kolizji mówimy wtedy, gdy dwa różne zestawy danych dają ten sam skrót. Dla SHA-256 nikt nie zna sposobu, żeby znaleźć taką parę.
- Efekt lawiny. Po najmniejszej zmianie w danych zmienia się średnio około połowy bitów skrótu, i to w nieprzewidywalnych miejscach.
Efekt lawiny najłatwiej zobaczyć samemu. Wpisz dwa teksty, na przykład różniące się jedną literą, i porównaj ich skróty bit po bicie:
Efekt lawiny w SHA-256
SHA-256(A)
SHA-256(B)
Zmieniło się 0 z 256 bitów (0%). Skróty nie zdradzają, jak podobne były teksty.
Dlaczego połowa?
Skąd bierze się ta połowa? Wyobraź sobie, że skrót to ciąg zupełnie losowych bitów. Wtedy na każdej pozycji nowy bit zgadzałby się ze starym z prawdopodobieństwem pół na pół, jak przy rzucie monetą. Zmienionych bitów byłoby więc tyle, ile orłów w 256 rzutach. Średnio wychodziłoby ich 128, a zwykle od 112 do 144.
Dokładnie to widać w demonstracji powyżej. Przycisk pod porównaniem powtarza eksperyment 1 000 razy, za każdym razem zmieniając jeden znak tekstu. Potem rysuje histogram, czyli wykres, który pokazuje, jak często wypadała każda liczba zmienionych bitów. Wychodzi ten sam dzwon co na desce Galtona. Zmiana jednej litery miesza więc bity skrótu tak, jakby je wylosować od nowa. Skróty podobnych tekstów nie są do siebie ani trochę podobne, dlatego skrót nie zdradza niczego o danych.
Ile trwa zgadywanie?
Skoro skrótu nie da się odwrócić, zostaje zgadywanie. Wszystkich możliwych skrótów SHA-256 jest 2²⁵⁶. Ta liczba ma 78 cyfr. Wyobraźmy sobie komputer, który sprawdza miliard miliardów (10¹⁸) skrótów na sekundę. Żeby trafić jeden konkretny skrót, potrzebowałby średnio około 10⁵¹ lat. Wszechświat istnieje niecałe 1,4 · 10¹⁰ lat, czyli niecałe 14 miliardów lat. Dlatego dane ukryte za skrótem są bezpieczne nawet wtedy, gdy wszyscy znają sam skrót.
Uwaga: skrót to nie szyfrowanie. Nie ma tu klucza, więc nie da się niczego „odszyfrować”. Krótkie i przewidywalne dane, na przykład słabe hasło, można jednak odgadnąć, bo kandydatów jest niewiele. Wystarczy liczyć skróty kolejnych kandydatów i porównywać je ze znanym skrótem. Dlatego do przechowywania haseł używa się specjalnych funkcji, które celowo działają wolno.
SHA-256 w losowaniach na losowaliczba.pl
Skróty przydają się wszędzie tam, gdzie losowość ma być sprawdzalna. Tak wygląda droga od rundy drand, czyli losowej wartości publikowanej przez publiczną sieć, do liczby w weryfikowalnym losowaniu:
- Podpis rundySieć drand podpisuje numer rundy (podpis BLS)
- SHA-256Skrót podpisu to 256 bitów losowości rundy
- StrumieńSHA-256(nazwa ‖ losowość ‖ licznik) daje kolejne bloki
- LiczbaBlok zamieniony na zakres metodą odrzucania
- DowódKażdy przeliczy wynik na stronie weryfikacji
SHA-256 pojawia się też w innych miejscach serwisu:
- W kole fortuny program zapisuje w dowodzie losowania skrót listy pól. Gdyby ktoś po losowaniu zmienił listę, skrót przestałby się zgadzać, więc zmiana nie przejdzie niepostrzeżenie.
- Generator haseł korzysta z kilku źródeł nieprzewidywalnych danych, nazywanych entropią. Program łączy je funkcją HKDF, czyli przepisem opartym na SHA-256. Bity zebrane z ruchów myszy także przechodzą przez SHA-256. Więcej o tym piszemy w artykule skąd komputer bierze losowość.
- Skrót pozwala też pokazać, że stałe liczby w normie kryptograficznej nie zostały dobrane ręcznie. Jak działa ta metoda i gdzie są jej granice, widać na przykładzie krzywych eliptycznych NIST.
- Każdy skrót możesz policzyć sam, na przykład poleceniem
sha256sumw terminalu, czyli tekstowym oknie poleceń systemu. Nie musisz wierzyć stronie na słowo.