Która transformacja MD5? Matematyczny (od dowolnego łańcucha bitowego do 128 bitów) czy ten z dowolnego bajtu na 32-znakowy ciąg szesnastkowy (praktyczny)? Nie jest oczywiste, że odpowiedzi dla nich obu są takie same ...
Rafał Dowgird
4
Cóż, to ta sama odpowiedź, prawda? Wiemy, że nie istnieje non-128-bit-long x, dla której md5(x) == x, ponieważ md5(x)jest 128 bitów. Dlatego w md5 istnieje stały punkt dla danych wejściowych o dowolnych rozmiarach wtedy i tylko wtedy, gdy istnieje stały punkt w md5 w domenie 128-bitowej.
paul
1
Nie sądzę, że są one tą samą odpowiedzią, ponieważ w przypadku praktycznego 32-znakowego ciągu szesnastkowego jest to arbitralny wybór, czy cyfry szesnastkowe są reprezentowane wielkimi literami [AF], czy małymi literami [af]. Obie reprezentacje odpowiadają tej samej 128-bitowej liczbie, ale będą dawać różne skróty, gdy zostaną dostarczone jako dane wejściowe do MD5. Więc prawdopodobieństwo, że w którejkolwiek z reprezentacji istnieje stały punkt, jest w rzeczywistości1-(1/e)*(1/e) ≈ 86.47%
Dušan
Odpowiedzi:
138
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 1 / 2 128 .
Zatem, prawdopodobieństwo, że ma łańcuch 128 bitów jest ustalony punkt jest (1 - 1 / 2 128 ), 2 128 , zatem prawdopodobieństwo, że istnieje punkt stały jest 1 - (1 - 1 / 2 128 ) 2 128 .
Ponieważ granica n dochodzi do nieskończoności (1 - 1 / n ) n wynosi 1 / e , a 2 128 to z pewnością bardzo duża liczba, to prawdopodobieństwo wynosi prawie dokładnie 1 - 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).
Czy faktycznie możesz założyć, że suma MD5 dowolnego łańcucha jest równomiernie rozłożona na wszystkie możliwe sumy?
Ori Pessach
13
Tak. Duże liczby i modulacja tworzą z grubsza losowy rozkład. Jeśli tego nie zrobią, będziesz miał ciągłe kolizje. Natura md5 wymusza losową dystrybucję wyjścia.
Czy jesteś tego pewien: prefix 12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762 Użyłem md5sumpolecenia linux, otrzymałem inny wynik
ThunderPhoenix
Nie jestem pewien, czy używasz poprawnej sumy md5. Możesz to również potwierdzić online tutaj: onlinemd5.com
Thomas Egense
11
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.
To prawda, gdybyś musiał spróbować każdego . Ale musiałbyś tylko wypróbować wszystkie możliwe dane wejściowe, aby sprawdzić, czy nie ma stałego punktu. Jeśli istnieje stały punkt (a odpowiedź Adama Rosenfielda sugeruje, że może istnieć), wystarczy jedno szczęśliwe przypuszczenie.
Naaff
Funkcja jest nieodwracalna w tym sensie, że nie ma odwrotności matematycznej, ale oznacza to tylko, że dla danego wyjścia może być więcej niż jedno wejście. Ogólnie rzecz biorąc, przestrzeń wejściowa dla danego wyjścia byłaby nieskończona, ale jeśli wiesz, że zaczęło się jako wartość 128-bitowa, możesz zawęzić możliwości. Jest szansa na „pracę wstecz”, jeśli nie potraktujesz funkcji jako czarnej skrzynki, ale zamiast tego przeczytasz specyfikację i zastosujesz myślenie matematyczne.
rndmcnlly
2
@Naaff: „wystarczy wypróbować wszystkie możliwe dane wejściowe” - a to jest łatwiejsze niż wypróbowanie każdego skrótu, jak? Wręcz przeciwnie, ponieważ kilka możliwych wejść może haszować do tego samego wyjścia.
Piskvor opuścił budynek
1
@Piskvor: Źle zrozumiałeś, co miał na myśli Naaff (zajęło mi to również minutę). Jaśniejszym sposobem na powiedzenie byłoby „Tylko jeśli nie ma ustalonego punktu, spróbuj wypróbować wszystkie możliwe dane wejściowe (z przestrzeni 2 ^ 128)”. Innymi słowy, musisz tylko wypróbować każdą możliwość, jeśli żadna wcześniej nie zadziałała. Więc 1.08e28 lat, albo jedno szczęśliwe przypuszczenie!
P Daddy
„Jeśli obliczenie skrótu zajęło 1 milisekundę”. Nowoczesne układy GPU potrafią obliczyć miliardy skrótów na sekundę, znacznie szybciej niż to. Ale i tak zajmie to bardzo dużo czasu.
markasoftware
0
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!
Nie zostało złamane. Jedyne, co byli w stanie zrobić, to w rozsądnym czasie stworzyć 2 ciągi, które zrównują ten sam hash. Wciąż bardzo trudno jest stworzyć ciąg, który będzie równy konkretnemu hashu.
Kibbee
9
Nie jestem pewien, jak znalezienie jednego zagroziłoby md5, bardziej niż zagroziłoby algorytmowi, gdybym powiedział ci MD5 ("Szybki brązowy lis przeskakuje nad leniwym psem") = 9e107d9d372bb6826bd81d3542a419d6
Kip
5
Ustalony punkt prawdopodobnie dałby pewien wpływ na matematykę, co mogłoby prowadzić do bardziej kompleksowego naruszenia MD5. Nie jestem przekonany, że Glomek naprawdę potrafi uzasadnić „prawdopodobnie”; Przyjąłbym „prawdopodobnie” bez dwuznaczności.
Jonathan Leffler
-9
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?
Nie ma nic w algorytmie MD5, który implikuje hex - działa na bajtach i produkuje bajty - więc myślę, że ta druga interpretacja jest nieprawidłowa.
Nick Johnson
Niezależnie od tego, czy w interpretacji 1 istnieje stały punkt, czy nie, nadal może istnieć (lub nie) jeden z interpretacji 2. Jednak jeśli jesteś zainteresowany zbadaniem problemu, interpretacja 1 wydaje się znacznie lepszym miejscem do rozpoczęcia, ponieważ wygrałeś Nie trzeba podejmować wszelkiego rodzaju arbitralnych decyzji dotyczących wielkości liter i kodowania znaków. Co więcej, przypadek binarny ma mniej bitów!
rndmcnlly
4
Źle interpretujesz, czym naprawdę jest ten heks. Możesz przedstawić liczbę binarną w systemie szesnastkowym, tak jak możesz to przedstawić w postaci dziesiętnej, ósemkowej lub 3. Jest to liczba i ma różne reprezentacje. Zatem interpretacja 1 i 2 to to samo. Myślisz o reprezentacji ciągu znaków, który wcale nie jest tym samym szesnastkiem, ale jest zupełnie inną wartością binarną. W rzeczywistości możesz mieć wiele różnych ciągów szesnastkowych w różnych zestawach znaków. 128-bitową wartość skrótu można przedstawić jako ciąg „szesnastkowy”, ale nie jest równa ciągowi. Ciąg nie jest tymi samymi danymi binarnymi.
określa
Dustin, interpretacja 2 naprawdę oznacza MD5 wyświetlanego ciągu.
Joshua
4
Istnieje jednak ogromny problem z tym pomysłem, ponieważ jest bezpośrednio zależny od kodowania znaków. Różne schematy kodowania dadzą całkowicie różne zestawy wyników. Jest nawet cały projekt i artykuł obalający go w oparciu o to niezrozumienie sposobu działania MD5 acodingfool.typepad.com/blog/2009/05/the-kembler-identity.html
określa
-23
Ś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.
Dane wejściowe mogą mieć dowolny rozmiar. Jeśli dane wejściowe mają mniej niż 512 bajtów, są uzupełniane, ale małe dane wejściowe są nadal dopuszczalne. Z Wikipedii: „MD5 przetwarza wiadomość o zmiennej długości na 128-bitowe wyjście o stałej długości. Wiadomość wejściowa jest dzielona na fragmenty bloków 512-bitowych (szesnaście 32-bitowych liczb całkowitych little endian); wiadomość jest dopełniana tak, że jego długość jest podzielna przez 512 ”.
Naaff
Więc zakładasz, że, powiedzmy, 0000000001 = 1? Twierdziłbym wtedy, że pytanie to jest w najlepszym przypadku słabo określone.
Ori Pessach
11
Wejście MD5 może być 128 bitów. Jeśli MD5 chce uzupełnić to wejście, to cóż, szczerze mówiąc, to jest sprawa MD5. Dane wejściowe są nadal dobrze zdefiniowane. Podobnie, wyjście ma dobrze zdefiniowane 128 bitów. Jeśli (dobrze zdefiniowane) dane wejściowe i (dobrze zdefiniowane) dane wyjściowe są takie same, wówczas MD5 (x) = x.
Naaff
2
@Joshua MD5 pustego ciągu (tj. 0 bajtów) nawet istnieje
md5(x) == x, ponieważmd5(x)jest 128 bitów. Dlatego w md5 istnieje stały punkt dla danych wejściowych o dowolnych rozmiarach wtedy i tylko wtedy, gdy istnieje stały punkt w md5 w domenie 128-bitowej.1-(1/e)*(1/e) ≈ 86.47%Odpowiedzi:
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 1 / 2 128 .
Zatem, prawdopodobieństwo, że ma łańcuch 128 bitów jest ustalony punkt jest (1 - 1 / 2 128 ), 2 128 , zatem prawdopodobieństwo, że istnieje punkt stały jest 1 - (1 - 1 / 2 128 ) 2 128 .
Ponieważ granica n dochodzi do nieskończoności (1 - 1 / n ) n wynosi 1 / e , a 2 128 to z pewnością bardzo duża liczba, to prawdopodobieństwo wynosi prawie dokładnie 1 - 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).
źródło
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
źródło
md5sumpolecenia linux, otrzymałem inny wynikPonieważ 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.
źródło
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!
źródło
Prawdopodobnie, ale znalezienie tego zajmie więcej czasu niż mamy lub wymagałoby skompromitowania MD5.
źródło
Istnieją dwie interpretacje i jeśli wolno wybrać jedną z nich, prawdopodobieństwo znalezienia stałego punktu wzrasta do 81,5%.
źródło
Ś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.
źródło