Tag Archives: kolizja

Kolizja hashy

Czym jest hash?

Hash (inaczej funkcja skrótu) jest kryptograficzną funkcją, która pobiera określone dane na wejściu i generuje z nich zaszyfrowaną wersję, zwykle podawaną w postaci znaków heksadecymalnych. Hashe nie są tym samym czym są checksum’y, checksum jest kodem sprawdzającym poprawność i integralność plików, przez sprawdzenie jej sumy kontrolnej na przesyłanym pliku. Dla tego pliku, suma integralności md5 to:

md5sum mdk3-v6.tar.bz2
 67705a814ded2a2e6f70522ca0dc6da9 mdk3-v6.tar.bz2

Czym jest kolizja hashy?

Z kolizją hashy mamy do czynienia gdy różne dane wejściowe przeprowadzane przez szereg operacji matematyczno-logicznych na wyjściu podają ten sam string jako hash.

Zapisując matematycznie:

A!=B

f(A)==f(B)

Im dłuższy jest ciąg f(A) tym mniejsze prawdopodobieństwo, że nastąpi kolizja z innym wyrazem B.

Skrót wersji MySQL64 składa się z 16 znaków heksadecymalnych, czyli ilość permutacji jaką można na nim stworzyć to:

16^16 = 18446744073709551616

czyli dość ograniczona ilość biorąc pod uwagę, że obecnie karty graficzne obliczają ponad Speed.GPU*: 5948.8M/s nie jest to wygórowana liczba. Łatwo jest wywołać kolizję ponieważ gdy karta graficzna ma za zadanie wytworzyć wszystkie permutacje z alfabetu: 1234567890abcdefghijklmnopqrstuwvxyz, który składa się z 26 znaków to dla długości haseł do 10 znaków mamy:

10^37 + 9^37 + 8^37 + 7^37 + … + 1^37 = dużo ( 10205370368408968258096392090176938105 )

Dla funkcji skrótu MD5 jest o wiele trudniej znaleźć kolizję gdyż liczba możliwych hashy jest równa

16^32=340282366920938463463374607431768211456

Długość hasha ułatwiła sprawę znalezienia kolizji w funkcji skrótu MySQL64 Rosjanom zajmującym się właśnie udowadnianiem, że obecnie używane metody kryptograficzne są niedoskonałe.

Na pewnym forum całkiem przypadkowo znaleziono kolizję dla hasha:

745d019f415d9513

który jest generowany z tych dwóch “słów”

корольbXBKkEHxi,i

Jest to pierwsza w historii praktycznie potwierdzona kolizja funkcji skrótu, o następne nie było trudno gdy ludzie sami zaczęli ich szukać, bardzo szubko znaleziono następne:

6acd60c427b48b95
Super-Pass!!!
f3uAI3 >DsZ

Pierwszą w historii i jak dotąd jedyną potrójną kolizją jaka miała miejsce jest zestawienie haseł:

QuantumCollision
bcSeW’!Tzu
fxO5H23g,]

Gdzie każde nich generuje

2f5b521d1ea3e566

Jak widać powyższe hasła nie dość, teoretycznie uznawane za mocne (np. fxO5H23g,]), są krótkie i generują za małą ilość. Jaki z tego wniosek? Jeśli nadal do szyfrowania danych używasz MySQL64 szybko to zmień ;)

Źródło.