Czy program md5 ma gwarancję wyjątkowości dla krótkich łańcuchów (skończona liczba ciągów znaków)?

Rozumiem, że istnieje dowód na to, że MD5 nie może gwarantować wyjątkowości, ponieważ we wszechświecie jest więcej ciągów niż sześciennych skrótów MD5, ale czy istnieje jakiś odwrotny dowód na skończoną liczbę łańcuchów?Czy program md5 ma gwarancję wyjątkowości dla krótkich łańcuchów (skończona liczba ciągów znaków)?

Zasadniczo, jeśli mam ciągi o maksymalnej długości X, czy istnieje X, dla którego MD5 ma być unikalny? jeśli tak, to co to jest X? a jeśli jest więcej niż jedna wartość dla X, jaka jest maksymalna wartość X?

lub czy istnieje taki X dla dowolnego innego algorytmu mieszającego, SHA-1 itp.?

Źródło

2012-05-15 xtrahelp.com

x = 1024 bitów zgodnie z następującą odpowiedzią http://stackoverflow.com/questions/1999824/whats-the-shortest-pair-of-strings-that-causes-an-md5-collision – Oli

@ Oli- That odpowiedź mówi, że najkrótsza * znana * kolizja hash wymaga 1024 bitów. Ponieważ MD5 wysyła wartości 128-bitowe, gwarantuje to, że najkrótsza kolizja hash musi być znacznie krótsza niż 1024 bity. – templatetypedef

, więc udowodniono, że jest ** nietypowy ** dla 1024 bitów, ale czy udowodniono, że jest ** unikalny ** dla mniej niż 1024 bitów? –

Odpowiedź na twoje pytanie brzmi: tak. Dla każdej funkcji skrótu jest maksymalna długość X, z której otrzymasz unikalne ciągi. Znalezienie X może być jednak bardzo trudne. Chodzi o to, aby uruchomić ten program:

X= 0; 
For i = 0 onward 
    For all strings of length i 
     Compute the hash code of that string. 
     If a collision is found, return X. 
    X = i

pomysł jest tylko lista coraz dłuższe ciągi aż znajdziesz kolizji hash. W końcu będziesz musiał, ponieważ w końcu wygenerujesz więcej ciągów niż możliwych wyjść mieszających.

Na oczekiwaniem, przy założeniu, że funkcja skrótu jest faktycznie dość przypadkowy, trzeba wygenerować O (√ U) różne ciągi Zanim znajdziesz kolizji, gdzie U jest wielkość przestrzeni, do której mapy funkcji mieszającej . W przypadku 256-bitowych skrótów jest to 2 . Oznacza to, że w praktyce powyższy program nigdy się nie kończy, chyba że funkcja hash została całkiem uszkodzona, ale teoretycznie oznacza to, że twoja liczba X istnieje.

Mam nadzieję, że to pomoże!

Źródło

2012-05-15 03:47:39 templatetypedef

Cóż, tak, czy ktoś już znalazł X? –

@templatetypedef, że twierdzenie tak naprawdę nie zachodzi - istnieje wiele znanych kolizji, a co za tym idzie, ataki wykorzystujące je na algorytmach hashowych uważanych za silne. –

@ CharlesDuffy - Tak, masz rację (przepraszam!).Moim zamierzonym twierdzeniem było to, że znalezienie tej wartości X prawdopodobnie sugerowałoby, że ktoś znalazł najkrótszą kolizję hashową, i rozumiem, że dla większości funkcji skrótu to jeszcze nie zostało zrobione (po prostu wiemy o krótkich zderzeń hashowych, a nie najkrótszych) . – templatetypedef

Podsumowując doskonałe odpowiedzi tutaj: What's the shortest pair of strings that causes an MD5 collision?

Najkrótsza znany atak na MD5 wymaga 2 bloków wejściowych, czyli 128 bajtów lub 1024 bitów.

Dla każdego algorytmu mieszającego, który wysyła N bitów, zakładając, że dzieli dane wejściowe w przybliżeniu losowo, można założyć, że kolizja jest większa niż 50% prawdopodobnych wartości na około sqrt(2^N) danych wejściowych. Na przykład, MD5 haszy do 128 bitów, więc możesz spodziewać się kolizji między wszystkimi wejściami 64-bitowymi. Zakłada to równomiernie losowy hash. Wszelkie uchybienia zmniejszyłyby liczbę wejść, zanim można spodziewać się kolizji.

Źródło

2012-05-15 03:50:58 Clueless

Wcześniejsze pytanie dotyczy najmniejszej * znanej * kolizji hasha. Wartość 1024 bitów jest o wiele większa niż rozmiar wyjściowy funkcji skrótu 128 bitów, więc odpowiedź jest bez znaczenia w tym pytaniu. – templatetypedef

Cóż, można się spodziewać jednego na ~ 64 bity, ale wiemy tylko, jak je niezawodnie generować w 1024 bitach. Nie wiem, czy ktokolwiek przetestował wszystkie ~ 2^64 krótkie wejścia do kolizji. To dużo pracy, wiele lat na jednym komputerze, ale nie niemożliwe. – Clueless

@ Clueless: Dostaję 11 000 lat na 8-rdzeniową maszynę 4 GHz, używając 600 cykli na hasz (przy użyciu http://cr.yp.to/talks/2008.06.05/slides.pdf jako odniesienia dla 600 cykli). – Charles

Czy program md5 ma gwarancję wyjątkowości dla krótkich łańcuchów (skończona liczba ciągów znaków)?

Odpowiedz

Powiązane problemy