Ciekawe, przydatne, zabawne

Łamiemy SHA2_256

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.


Powiązane

5
Dodaj komentarz

avatar
2 Comment threads
3 Thread replies
3 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Butterxpil40i6 Recent comment authors
  Subscribe  
Powiadom o
40i6
Gość

Zupełnie nie wiem, o co chodzi, ale wchodzę w to!

Butter
Gość
Butter

A więc po to wymyślono sferę Dysona 😉

Back to top button
Close
%d bloggers like this: