Dziś krótka opowieść o tym, jak znaleźć kolizję 256-bitowej funkcji skrótu SHA2.
Jeżeli, Czytelniku, nie wiesz czym jest funkcja skrótu, albo wiesz ale masz w głębokim poważaniu szukanie kolizji, nie czytaj dalej. Będzie nudno.
Czytasz dalej?
W porządku. Zaczynamy.
Zaczniemy od tego, że żeby z prawdopodobieństwem 50% znaleźć kolizję n-bitowej funkcji skrótu, trzeba wypróbować około \(2^{\frac{n}{2}}\)skrótów. Nie będziemy tego teraz udowadniać - tak po prostu jest i już (wyliczenia są trochę podobne do tych przy paradoksie urodzin).
A więc żeby trafić na kolizję... Nie, wróć. Żeby mieć 50% szansy trafienia na kolizję 256-bitowej funkcji skrótu, wystarczy wygenerować \(2^{128}\) haszy.
Czy to dużo?
Spróbujmy ugryźć zagadnienie od strony stricte energetycznej. Dla uproszczenia policzymy sobie ile uda nam się przełączyć bitów za pomocą naszego sympatycznego Słońca. Pominiemy całkowicie kwestę zachowania stanu tych bitów, kwestie doprowadzenia energii, odprowadzenia nadmiaru ciepła czy nawet architektury komputera. Przyjmiemy też, że pojedynczy bit można zachować w jednym atomie (jak? nie mam pojęcia, ale pewnie kiedyś do tego dojdziemy).
Energia pojedynczego atomu w temperaturze K wynosi kT, gdzie k to stała Boltzmanna ( \(1.38064852×10^{−16}\) ergów na kelwin), a T - temperatura cząstki wyrażona w kelwinach.
Temperatura tła Kosmosu to 2.72548 kelwinów, a więc nasz "idealny komputer" powinien pracować w takiej właśnie temperaturze, ponieważ jakakolwiek temperatura wyższa lub niższa od niej wymagałaby dodatkowo chłodzenia (lub ogrzewania), co zwiększyłoby zapotrzebowanie "komputera" na energię.
Energia pojedynczego atomu w temperaturze 2.72548K wynosi więc (\(1.38064852×10^{−16}\) ergów na kelwin) * (2.72548 kelwinów) = \(3.762929928×10^{-16}\) ergów.
Możemy założyć (znów, upraszczamy, ale do tak abstrakcyjnych rozważań tego typu uproszczenia są jak najbardziej na miejscu), że przełączenie pojedynczego bitu w naszym "idealnym komputerze" wymaga dostarczenia takiej właśnie ilości energii. Niecałe cztery dziesięciobiliardowe części erga. Tyci-tyci.
Jak będziemy zasilać nasz komputer? Ekologicznie! Szkoda spalać ropę, szkoda budować elektrownie atomowe, weźmy sobie po prostu trochę energii naszej gwiazdy macierzystej.
Słońce emituje w ciągu roku około \(1.2*10^{34}\) dżuli energii. Ponieważ jeden dżul to dziesięć milionów ergów, Słońce przez rok emituje około \(1.2*10^{41}\) ergów energii.
Zakładając, że jakimś cudem uda nam się zużyć całą energię słoneczną przez okrągły rok, uda nam się przełączyć (\(1.2×10^{41}\) ergów) / (\(3.762929928×10^{-16}\) ergów na bit) = \(3.189004374×10^{56}\) bitów. Odpowiednio zmieniając podstawę z 10 na 2 okaże się, że przełączymy około \(2^{187}\) bitów, czyli wyliczymy około \(2^{179}\) skrótów (haszy).
To dużo więcej, niż wymagane \(2^{128}\). Doskonale - z bardzo dużym prawdopodobieństwem uda nam się w ten sposób znaleźć kolizję funkcji SHA2_256.
Pod warunkiem, rzecz jasna, że nauczymy się przechowywać i przetwarzać dane na poziomie pojedynczych atomów i w temperaturze tła Wszechświata, że uda nam się zachachmęcić całą energię emitowaną przez Słońce (nie tylko ten kawałek, który dolatuje do Ziemi - całą energię w każdy poprzek!) przez rok czasu, że nie będziemy musieli po drodze marnować energii na nic innego, że wydajność procesu będzie stuprocentowa, oraz że będziemy potrafili stwierdzić, że właśnie znaleźliśmy kolizję (co wymaga przecież w jakiś sposób zapamiętania wszystkich dotychczasowych kombinacji).
Kasza z mlekiem!
Ktoś mógłby zapytać: a po co właściwie szukać takich kolizji?
Głównie po to, żeby robić przekręty. Na przykład... kopać fałszywe bitcoiny. Albo podszywać się online pod pana Jacka spod dziewiątki.
Zupełnie nie wiem, o co chodzi, ale wchodzę w to!
W ogromnym uproszczeniu hasz (czyli skrót) pozwala zweryfikować, że między nadawcą wiadomości a jej odbiorcą wiadomość nie uległa zmianie. Nadawca wylicza hasz, odbiorca wylicza hasz, jeżeli obydwa dostaną to samo, to znaczy że obydwaj mają tą samą treść wiadomości. Wyliczenie hasza jest względnie proste, natomiast “wyliczenie” oryginalnej wiadomości z takiego hasza – praktycznie niewykonalne. Kolizja to sytuacja, w której dwie różne wiadomości generują na wyjściu ten sam hasz. “Starsze” funkcje haszujące, jak np MD4 czy MD5 zostały “złamane” – znane są praktyczne metody wyszukiwania kolizji. Dla funkcji haszującej SHA2_256 takiej metody jeszcze nie ma; nie są też znane żadne kolizje.
Skoro można kopać bitcoiny na Słońcu, to jakaś spółka węglowa by się przydała. Z kolei kolega zaglądając mi przez ramię zainteresował się bardzo słowem hasz, ale to inne pokolenie, coś mu się chyba wyliczenie haszu nie zgodziło – co innego odebrał, niż nadawca nadał.
W tym wpisie jest mnóstwo uproszczeń. Obstawiam, że końcowy wynik może się zgadzać z dokładnością do kilku rzędów wielkości…
A więc po to wymyślono sferę Dysona 😉