Czy istnieje punkt stały MD5, w którym md5 (x) == x?

Czy istnieje stały punkt w transformacji MD5, tj. Czy istnieje x takie, że md5(x) == x?

Ponieważ suma MD5 ma długość 128 bitów, każdy stały punkt musiałby również mieć długość 128 bitów. Przy założeniu, że suma MD5 dowolnego łańcucha jest równomiernie rozprowadzany po wszystkich możliwych sumy, to prawdopodobieństwo, że dana 128-bitowy ciąg jest stały punkt jest ¹ / _{2 ¹²⁸} .

Zatem, prawdopodobieństwo, że ma łańcuch 128 bitów jest ustalony punkt jest (1 - ¹ / _{2 ¹²⁸} ), ^{2 128} , zatem prawdopodobieństwo, że istnieje punkt stały jest 1 - (1 - ¹ / _{2 ¹²⁸} ) ^{2 128} .

Ponieważ granica n dochodzi do nieskończoności (1 - ¹ / _n ) ⁿ wynosi ¹ / _e , a 2 ¹²⁸ to z pewnością bardzo duża liczba, to prawdopodobieństwo wynosi prawie dokładnie 1 - ¹ / _e ≈ 63,21%.

Oczywiście w rzeczywistości nie ma tu żadnej przypadkowości - albo istnieje stały punkt, albo go nie ma. Ale możemy być w 63,21% pewni, że istnieje stały punkt. (Zauważ też, że ta liczba nie zależy od rozmiaru przestrzeni kluczy - gdyby sumy MD5 były 32 lub 1024 bity, odpowiedź byłaby taka sama, o ile jest większa niż około 4 lub 5 bitów).

Moja próba brutalnej siły znalazła dopasowanie 12 przedrostków i 12 sufiksów.

prefiks 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762

przyrostek 12: df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78

Post na blogu: https://plus.google.com/103541237243849171137/posts/SRxXrTMdrFN

Ponieważ hasz jest nieodwracalny, byłoby to bardzo trudne do rozgryzienia. Jedynym sposobem rozwiązania tego problemu byłoby obliczenie skrótu na każdym możliwym wyjściu skrótu i ​​sprawdzenie, czy udało Ci się znaleźć dopasowanie.

Aby rozwinąć, w skrócie MD5 jest 16 bajtów. Oznacza to, że istnieje 2 ^ (16 * 8) = 3,4 * 10 ^ 38 kombinacji. Jeśli obliczenie skrótu na 16-bajtowej wartości zajęłoby 1 milisekundę, obliczenie wszystkich tych wartości zajęłoby 10790283070806014188970529154,99 lat.

Chociaż nie mam odpowiedzi tak / nie, przypuszczam, że jest "tak", a ponadto może być 2 ^ 32 takich stałych punktów (dla interpretacji ciągu bitów, a nie interpretacji ciągu znaków). Aktywnie nad tym pracuję, ponieważ wydaje się to niesamowitą, zwięzłą łamigłówką, która będzie wymagała dużo kreatywności (jeśli nie zadowoli się od razu brutalnym wyszukiwaniem).

Moje podejście jest następujące: potraktuj to jako problem matematyczny. Mamy 128 zmiennych boolowskich i 128 równań opisujących dane wyjściowe pod względem danych wejściowych (które mają być zgodne). Mam nadzieję, że poprzez podłączenie wszystkich stałych z tabel algorytmu i bitów dopełniających można znacznie uprościć równania, aby uzyskać algorytm zoptymalizowany do 128-bitowego przypadku wejściowego. Te uproszczone równania można następnie zaprogramować w jakimś ładnym języku do wydajnego wyszukiwania lub ponownie potraktować abstrakcyjnie, przypisując pojedyncze bity na raz, uważając na sprzeczności. Wystarczy zobaczyć kilka bitów wyjścia, aby wiedzieć, że nie pasuje do wejścia!

Prawdopodobnie, ale znalezienie tego zajmie więcej czasu niż mamy lub wymagałoby skompromitowania MD5.

Istnieją dwie interpretacje i jeśli wolno wybrać jedną z nich, prawdopodobieństwo znalezienia stałego punktu wzrasta do 81,5%.

• Interpretacja 1: czy MD5 wyjścia MD5 jest binarne odpowiada jego wejściu?
• Interpretacja 2: czy MD5 wyjścia MD5 w postaci szesnastkowej odpowiada jego wejściu?

Ściśle mówiąc, ponieważ wejście MD5 ma długość 512 bitów, a wyjście 128 bitów, powiedziałbym, że jest to niemożliwe z definicji.