Dlaczego wartości skrótu MD5 nie są odwracalne?

Question 1

Jedną z koncepcji, nad którą zawsze się zastanawiałem, jest użycie kryptograficznych funkcji skrótu i wartości. Rozumiem, że te funkcje mogą generować wartość skrótu, która jest unikalna i praktycznie niemożliwa do odwrócenia, ale oto, nad czym zawsze się zastanawiałem:

Jeśli na moim serwerze to w PHP produkuję:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Gdy uruchomisz ten sam ciąg za pomocą funkcji MD5, uzyskasz ten sam wynik po instalacji PHP. Proces jest używany do wytworzenia pewnej wartości z jakiejś wartości początkowej.

Czy to nie oznacza, że istnieje sposób na zdekonstruowanie tego, co się dzieje i odwrócenie wartości skrótu?

Co jest takiego w tych funkcjach, że nie można odtworzyć wynikowych łańcuchów?

Question 2

Materiał wejściowy może mieć nieskończoną długość, przy czym wyjście ma zawsze 128 bitów. Oznacza to, że nieskończona liczba ciągów wejściowych wygeneruje ten sam wynik.

Jeśli wybierzesz liczbę losową i podzielisz ją przez 2, ale zapiszesz tylko resztę, otrzymasz 0 lub 1 - odpowiednio parzyste lub nieparzyste. Czy można wziąć to 0 lub 1 i uzyskać oryginalny numer?

Question 3

Gdyby funkcje skrótu, takie jak MD5, były odwracalne, byłby to przełom w historii algorytmów kompresji danych! Łatwo zauważyć, że gdyby MD5 było odwracalne, to dowolne fragmenty danych o dowolnym rozmiarze mogłyby być reprezentowane przez zaledwie 128 bitów bez utraty informacji. W ten sposób byłbyś w stanie zrekonstruować oryginalną wiadomość z numeru 128-bitowego, niezależnie od rozmiaru oryginalnej wiadomości.

Question 4

W przeciwieństwie do tego, co podkreślają tutaj najczęściej popierane odpowiedzi, brak iniekcji (tj. Istnieje kilka ciągów haszujących z tą samą wartością) kryptograficznej funkcji skrótu spowodowanej różnicą między dużym (potencjalnie nieskończonym) rozmiarem wejściowym a stałym rozmiarem wyjściowym nie jest ważna kwestia - właściwie wolimy funkcje skrótu, w których takie kolizje występują tak rzadko, jak to tylko możliwe.

Rozważ tę funkcję (w notacji PHP jako pytanie):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Powoduje to dodanie spacji, jeśli ciąg jest zbyt krótki, a następnie zajmuje pierwsze 16 bajtów ciągu, a następnie koduje go jako szesnastkowy. Ma taki sam rozmiar wyjściowy jak hash MD5 (32 znaki szesnastkowe lub 16 bajtów, jeśli pominiemy część bin2hex).

print simple_hash("stackoverflow.com");

Spowoduje to wyświetlenie:

737461636b6f766572666c6f772e636f6d

Ta funkcja ma również tę samą właściwość braku iniekcji, co została podkreślona w odpowiedzi Cody'ego dla MD5: Możemy przekazywać ciągi dowolnego rozmiaru (o ile pasują do naszego komputera), a wypisze tylko 32 cyfry szesnastkowe. Oczywiście nie może być zastrzykiem.

Ale w tym przypadku znalezienie łańcucha, który odwzorowuje ten sam hash, jest trywialne (po prostu zastosuj hex2binswój hash i masz go). Jeśli Twój oryginalny ciąg miał długość 16 (jak w naszym przykładzie), otrzymasz nawet ten oryginalny ciąg. Nic takiego nie powinno być możliwe w przypadku MD5, nawet jeśli wiesz, że długość wejścia była dość krótka (poza wypróbowaniem wszystkich możliwych wejść, aż znajdziemy pasujący, np. Atak siłowy).

Ważnymi założeniami dla kryptograficznej funkcji skrótu są:

ciężko jest znaleźć ciąg produkujący dany hash (odporność na przedobraz)
trudno jest znaleźć inny ciąg produkujący taki sam hash jak dany ciąg (odporność na drugi przedobraz)
trudno znaleźć parę ciągów o tym samym skrócie (odporność na kolizje)

Oczywiście moja simple_hashfunkcja nie spełnia żadnego z tych warunków. (W rzeczywistości, jeśli ograniczymy przestrzeń wejściową do „ciągów 16-bajtowych”, wówczas moja funkcja stanie się iniekcyjna, a zatem będzie nawet możliwa do udowodnienia odporność na drugi obraz przed obrazem i kolizje).

Istnieją teraz ataki kolizyjne na MD5 (np. Możliwe jest utworzenie pary łańcuchów, nawet z danym prefiksem, które mają ten sam hash, co wymaga trochę pracy, ale nie jest to niemożliwe), więc nie powinieneś używać MD5 na wszystko, co krytyczne. Nie ma jeszcze ataku przedobrazowego, ale ataki będą lepsze.

Aby odpowiedzieć na rzeczywiste pytanie:

Co jest takiego w tych funkcjach, że nie można odtworzyć wynikowych łańcuchów?

To, co skutecznie MD5 (i inne funkcje skrótu zbudowane na konstrukcji Merkle-Damgarda) skutecznie robi, to zastosowanie algorytmu szyfrowania z wiadomością jako kluczem i pewną ustaloną wartością jako „zwykłym tekstem”, używając otrzymanego zaszyfrowanego tekstu jako skrótu. (Wcześniej wejście jest uzupełniane i dzielone na bloki, każdy z tych bloków jest używany do szyfrowania wyjścia poprzedniego bloku, XOR z jego wejściem, aby zapobiec odwrotnym obliczeniom).

Nowoczesne algorytmy szyfrujące (w tym te używane w funkcjach skrótu) są wykonane w taki sposób, aby utrudnić odzyskanie klucza, nawet jeśli podano zarówno tekst jawny, jak i zaszyfrowany (lub nawet gdy przeciwnik wybierze jeden z nich). Robią to na ogół wykonując wiele operacji tasowania bitów w taki sposób, że każdy bit wyjściowy jest określony przez każdy bit klucza (kilka razy), a także każdy bit wejściowy. W ten sposób możesz łatwo odtworzyć to, co dzieje się w środku, tylko jeśli znasz pełny klucz i wejście lub wyjście.

W przypadku funkcji skrótu podobnych do MD5 i ataku typu preimage (z pojedynczym ciągiem mieszanym, aby ułatwić sprawę), masz tylko dane wejściowe i wyjściowe funkcji szyfrowania, ale nie masz klucza (właśnie tego szukasz).

Question 5

Odpowiedź Cody'ego Brociousa jest właściwa. Ściśle mówiąc, nie można „odwrócić” funkcji skrótu, ponieważ wiele ciągów jest odwzorowanych na ten sam skrót. Zauważ jednak, że albo znalezienie jednego ciągu, który jest mapowany na dany hash, albo znalezienie dwóch ciągów, które są mapowane na ten sam hash (tj. Kolizja ), byłoby dużym przełomem dla kryptoanalityka. Ogromna trudność obu tych problemów jest powodem, dla którego dobre funkcje skrótu są przydatne w kryptografii.

Question 6

MD5 nie tworzy unikalnej wartości skrótu; celem MD5 jest szybkie wytworzenie wartości, która zmienia się znacząco w zależności od niewielkiej zmiany źródła.

Na przykład,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Oczywiście to nie jest rzeczywiste szyfrowanie MD5)

Większość skrótów (jeśli nie wszystkie) również nie jest unikalna; są raczej wystarczająco wyjątkowe , więc zderzenie jest wysoce nieprawdopodobne, ale nadal możliwe.

Question 7

Dobrym sposobem na myślenie o algorytmie mieszania jest zmiana rozmiaru obrazu w Photoshopie ... powiedzmy, że masz obraz o wymiarach 5000x5000 pikseli, a następnie zmieniasz go do zaledwie 32x32. To, co masz, jest nadal reprezentacją oryginalnego obrazu, ale jest znacznie mniejsze i skutecznie „wyrzuciło” pewne części danych obrazu, aby zmieścić się w mniejszym rozmiarze. Więc gdybyś zmienił rozmiar tego obrazu 32x32 z powrotem do 5000x5000, wszystko, co otrzymasz, to rozmazany bałagan. Jednak ponieważ obraz 32x32 nie jest tak duży, teoretycznie można by sobie wyobrazić, że inny obraz mógłby zostać zmniejszony, aby uzyskać dokładnie te same piksele!

To tylko analogia, ale pomaga zrozumieć, co robi hasz.

Question 8

Kolizja hash jest znacznie bardziej prawdopodobna, niż mogłoby się wydawać. Przyjrzyj się paradoksowi urodzin, aby lepiej zrozumieć, dlaczego tak jest.

Question 9

Ponieważ liczba możliwych plików wejściowych jest większa niż liczba 128-bitowych wyjść, niemożliwe jest jednoznaczne przypisanie skrótu MD5 do każdego możliwego.

Kryptograficzne funkcje skrótu służą do sprawdzania integralności danych lub podpisów cyfrowych (skrót jest podpisywany w celu zwiększenia wydajności). Zmiana oryginalnego dokumentu powinna zatem oznaczać, że oryginalny hash nie pasuje do zmienionego dokumentu.

Te kryteria są czasami używane:

Odporność obrazu wstępnego: dla danej funkcji skrótu i danego skrótu powinno być trudno znaleźć dane wejściowe, które mają dany skrót dla tej funkcji.
Rezystancja drugiego obrazu wstępnego: dla danej funkcji skrótu i wejścia powinno być trudno znaleźć drugie, inne wejście z tym samym hashem.
Odporność na kolizje: dla danej funkcji powinno być trudno znaleźć dwa różne wejścia z tym samym hashem.

Kryteria te są wybrane tak, aby utrudnić znalezienie dokumentu pasującego do danego skrótu, w przeciwnym razie możliwe byłoby sfałszowanie dokumentów poprzez zastąpienie oryginału takim, który został dopasowany przez hash. (Nawet jeśli zamiana jest bełkotem, sama wymiana oryginału może spowodować zakłócenia).

Numer 3 implikuje numer 2.

W szczególności w przypadku MD5 wykazano, że jest on wadliwy: Jak złamać MD5 i inne funkcje skrótu .

Question 10

Ale tutaj pojawiają się tęczowe stoły. Zasadniczo jest to po prostu duża liczba wartości zaszyfrowanych osobno, a następnie wynik jest zapisywany na dysku. Wtedy bit cofania „tylko” służy do przeszukiwania bardzo dużej tabeli.

Oczywiście jest to możliwe tylko dla podzbioru wszystkich możliwych wartości wejściowych, ale jeśli znasz granice wartości wejściowej, może być możliwe jej obliczenie.

Question 11

Chiński naukowiec odkrył sposób zwany „kolizjami wybranego przedrostka”, który umożliwia konflikt między dwoma różnymi łańcuchami.

Oto przykład: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Kod źródłowy: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0. 5_source.zip

Question 12

Najlepszym sposobem, aby zrozumieć, co oznaczały wszystkie najczęściej głosowane odpowiedzi, jest faktycznie próba przywrócenia algorytmu MD5. Pamiętam, że kilka lat temu próbowałem przywrócić algorytm MD5crypt , aby nie odzyskać oryginalnej wiadomości, ponieważ jest to oczywiście niemożliwe, ale po prostu wygenerować wiadomość, która wygeneruje ten sam hash, co oryginalny hash. To, przynajmniej teoretycznie, dałoby mi sposób na zalogowanie się do urządzenia z Linuksem, które przechowuje użytkownika: hasło w pliku / etc / passwd przy użyciu wygenerowanej wiadomości (hasła) zamiast używania oryginalnego. Ponieważ obie wiadomości miałyby ten sam hash wynikowy, system rozpoznałby moje hasło (wygenerowane z oryginalnego skrótu) jako prawidłowe. To w ogóle nie zadziałało. Po kilku tygodniach, o ile dobrze pamiętam, stosowanie soliw pierwszej wiadomości mnie zabił. Musiałem przedstawić nie tylko prawidłową wiadomość początkową, ale także poprawną, ważną wiadomość początkową, czego nigdy nie byłem w stanie zrobić. Ale wiedza, którą uzyskałem z tego eksperymentu, była miła.

Question 13

Jak większość już powiedziała, MD5 została zaprojektowana do mieszania strumieni danych o zmiennej długości do fragmentów danych o stałej długości, dzięki czemu jeden skrót jest współdzielony przez wiele strumieni danych wejściowych.

Jeśli jednak kiedykolwiek musiałeś znaleźć oryginalne dane z sumy kontrolnej, na przykład jeśli masz skrót hasła i potrzebujesz znaleźć oryginalne hasło, często szybciej jest po prostu wygooglować (lub dowolną preferowaną wyszukiwarkę). dla odpowiedzi niż brutalnej siły. Udało mi się znaleźć kilka haseł za pomocą tej metody.

Question 14

z definicji funkcja Hash (kryptograficzna Hash): nie powinna być odwracalna; nie powinna mieć kolizji (najmniej możliwe).

regd twoje pytanie: jest to skrót jednokierunkowy. input (niezależnie od długości) wygeneruje wyjście o stałym rozmiarze (będzie wypełnione w oparciu o algorytm (granica 512 bitów dla MD5)). Informacje są kompresowane (tracone) i praktycznie nie można ich wygenerować z przekształceń odwrotnych.

dodatkowe informacje na temat MD5: jest podatny na kolizje. przejrzał ostatnio ten artykuł, http://www.win.tue.nl/hashclash/Nostradamus/

otwiera kod źródłowy dla implementacji skrótów kryptograficznych (MD5 i SHA) można znaleźć w kodzie Mozilli. (biblioteka freebl).

Question 15

Teraz dni hashe MD5 lub inne skróty w tym zakresie są wstępnie obliczane dla wszystkich możliwych ciągów i przechowywane w celu zapewnienia łatwego dostępu. Chociaż teoretycznie MD5 nie jest odwracalne, ale korzystając z takich baz danych, możesz dowiedzieć się, który tekst spowodował określoną wartość skrótu.

Na przykład wypróbuj następujący kod skrótu na http://gdataonline.com/seekhash.php, aby dowiedzieć się, jakiego tekstu użyłem do obliczenia skrótu

aea23489ce3aa9b6406ebb28e0cda430

Question 16

f (x) = 1 jest nieodwracalne. Funkcje skrótu nie są nieodwracalne.

W rzeczywistości jest to wymagane, aby mogli spełnić swoją funkcję polegającą na ustaleniu, czy ktoś posiada nieuszkodzoną kopię zaszyfrowanych danych. Stwarza to podatność na ataki brutalnej siły, które są obecnie dość potężne, szczególnie przeciwko MD5.

Istnieje również zamieszanie tutaj i gdzie indziej wśród ludzi, którzy mają wiedzę matematyczną, ale mało wiedzy na temat szyfrowania. Kilka szyfrów po prostu XORuje dane ze strumieniem klucza, więc można powiedzieć, że tekst zaszyfrowany odpowiada wszystkim tekstom jawnym o tej długości, ponieważ można było użyć dowolnego strumienia klucza.

Jednak to ignoruje fakt, że rozsądny tekst jawny utworzony z nasienia passwordjest znacznie bardziej prawdopodobny niż inny tekst utworzony przez nasienie Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6odo tego stopnia, że każdy, kto twierdzi, że drugi jest możliwy, byłby wyśmiewany.

W ten sam sposób, jeśli próbujesz wybrać między dwoma potencjalnymi hasłami passwordi Wsg5Nm^bkI4EgxUO, nie jest to tak trudne, jak sądzą niektórzy matematycy.

Question 17

Podobają mi się wszystkie argumenty. Jest oczywiste, że prawdziwą wartością zaszyfrowanych wartości jest po prostu zapewnienie nieczytelnych dla człowieka symboli zastępczych dla ciągów, takich jak hasła. Nie ma szczególnych korzyści w zakresie bezpieczeństwa. Zakładając, że atakujący uzyskał dostęp do tabeli z zaszyfrowanymi hasłami, może:

Skasuj wybrane przez siebie hasło i umieść wyniki w tabeli haseł, jeśli ma uprawnienia do zapisu / edycji tabeli.
Wygeneruj zaszyfrowane wartości typowych haseł i przetestuj istnienie podobnych zaszyfrowanych wartości w tabeli haseł.

W tym przypadku słabe hasła nie mogą być chronione przez sam fakt, że są zaszyfrowane.

Answer 1

Jedną z koncepcji, nad którą zawsze się zastanawiałem, jest użycie kryptograficznych funkcji skrótu i wartości. Rozumiem, że te funkcje mogą generować wartość skrótu, która jest unikalna i praktycznie niemożliwa do odwrócenia, ale oto, nad czym zawsze się zastanawiałem:

Jeśli na moim serwerze to w PHP produkuję:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

Gdy uruchomisz ten sam ciąg za pomocą funkcji MD5, uzyskasz ten sam wynik po instalacji PHP. Proces jest używany do wytworzenia pewnej wartości z jakiejś wartości początkowej.

Czy to nie oznacza, że istnieje sposób na zdekonstruowanie tego, co się dzieje i odwrócenie wartości skrótu?

Co jest takiego w tych funkcjach, że nie można odtworzyć wynikowych łańcuchów?

Answer 2

54

Prostym przykładem nieodwracalnej wartości jest na przykład modulo. Na przykład 10% 3 = 1, ale nie możesz odwrócić 1 do 10, ponieważ może to być również 4

Gab Royer,

Answer 3

57

Gdybyś mógł zrekonstruować dane, miałbyś najbardziej wydajny algorytm bezstratnej kompresji, jaki kiedykolwiek istniał :)

Dan Diplo,

Answer 4

206

Materiał wejściowy może mieć nieskończoną długość, przy czym wyjście ma zawsze 128 bitów. Oznacza to, że nieskończona liczba ciągów wejściowych wygeneruje ten sam wynik.

Jeśli wybierzesz liczbę losową i podzielisz ją przez 2, ale zapiszesz tylko resztę, otrzymasz 0 lub 1 - odpowiednio parzyste lub nieparzyste. Czy można wziąć to 0 lub 1 i uzyskać oryginalny numer?

Serafina Brocious
źródło

4

Oznacza to, że ani liczba -> reszta, ani ciąg znaków -> md5 nie są „funkcjami iniekcyjnymi”.

Federico A. Ramponi

Federico, na pewno masz na myśli, że żadne z nich nie są funkcjami bijektywnymi? Obie są iniekcyjne.

Mihai Limbășan

10

moocha: Injective oznacza 1 do 1. MD5 z pewnością nie jest 1 do 1, ponieważ domena jest większa niż zakres. Kolejną kwestią, na którą warto zwrócić uwagę, jest to, że biorąc pod uwagę sumę kontrolną MD5, bardzo trudno jest znaleźć choćby jeden ciąg, który jest z nią skrócony. Może warto dodać do odpowiedzi w celu wyjaśnienia.

biocynk

4

Niemożliwe jest posiadanie funkcji skrótu, która generuje unikalne wartości. Mapujesz nieskończoną liczbę wartości na skończoną liczbę wartości, co gwarantuje kolizje.

Serafina Brocious

4

Sugerowałbym, że twoja odpowiedź nie odnosi się do kluczowej kwestii. Jak wspomniał biozinc, ważne dla bezpiecznego skrótu hasła jest to, że nie można znaleźć żadnych danych wejściowych, które tworzą dane wyjściowe, a nie to, że nie można znaleźć oryginalnych danych wejściowych. W związku z tym MD5 niekoniecznie jest tak bezpieczne, jak mogłoby być ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).

Mike Pelley,

Answer 5

4

Oznacza to, że ani liczba -> reszta, ani ciąg znaków -> md5 nie są „funkcjami iniekcyjnymi”.

Federico A. Ramponi

Answer 6

Federico, na pewno masz na myśli, że żadne z nich nie są funkcjami bijektywnymi? Obie są iniekcyjne.

Mihai Limbășan

Answer 7

10

moocha: Injective oznacza 1 do 1. MD5 z pewnością nie jest 1 do 1, ponieważ domena jest większa niż zakres. Kolejną kwestią, na którą warto zwrócić uwagę, jest to, że biorąc pod uwagę sumę kontrolną MD5, bardzo trudno jest znaleźć choćby jeden ciąg, który jest z nią skrócony. Może warto dodać do odpowiedzi w celu wyjaśnienia.

biocynk

Answer 8

4

Niemożliwe jest posiadanie funkcji skrótu, która generuje unikalne wartości. Mapujesz nieskończoną liczbę wartości na skończoną liczbę wartości, co gwarantuje kolizje.

Serafina Brocious

Answer 9

4

Sugerowałbym, że twoja odpowiedź nie odnosi się do kluczowej kwestii. Jak wspomniał biozinc, ważne dla bezpiecznego skrótu hasła jest to, że nie można znaleźć żadnych danych wejściowych, które tworzą dane wyjściowe, a nie to, że nie można znaleźć oryginalnych danych wejściowych. W związku z tym MD5 niekoniecznie jest tak bezpieczne, jak mogłoby być ( en.wikipedia.org/wiki/MD5#Collision_vulnerabilities ).

Mike Pelley,

Answer 10

53

Gdyby funkcje skrótu, takie jak MD5, były odwracalne, byłby to przełom w historii algorytmów kompresji danych! Łatwo zauważyć, że gdyby MD5 było odwracalne, to dowolne fragmenty danych o dowolnym rozmiarze mogłyby być reprezentowane przez zaledwie 128 bitów bez utraty informacji. W ten sposób byłbyś w stanie zrekonstruować oryginalną wiadomość z numeru 128-bitowego, niezależnie od rozmiaru oryginalnej wiadomości.

Samouk
źródło

9

pomyśl, jak szybko byłoby pobieranie dystrybucji Linuksa, gdybyś zamiast tego mógł po prostu pobrać md5 :)

Colin Pickard,

16

@Colin Pickard: nie pobieralibyśmy już dystrybucji Linuksa, zapisywalibyśmy je . :)

tzot

Answer 11

9

pomyśl, jak szybko byłoby pobieranie dystrybucji Linuksa, gdybyś zamiast tego mógł po prostu pobrać md5 :)

Colin Pickard,

Answer 12

16

@Colin Pickard: nie pobieralibyśmy już dystrybucji Linuksa, zapisywalibyśmy je . :)

tzot

Answer 13

W przeciwieństwie do tego, co podkreślają tutaj najczęściej popierane odpowiedzi, brak iniekcji (tj. Istnieje kilka ciągów haszujących z tą samą wartością) kryptograficznej funkcji skrótu spowodowanej różnicą między dużym (potencjalnie nieskończonym) rozmiarem wejściowym a stałym rozmiarem wyjściowym nie jest ważna kwestia - właściwie wolimy funkcje skrótu, w których takie kolizje występują tak rzadko, jak to tylko możliwe.

Rozważ tę funkcję (w notacji PHP jako pytanie):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

Powoduje to dodanie spacji, jeśli ciąg jest zbyt krótki, a następnie zajmuje pierwsze 16 bajtów ciągu, a następnie koduje go jako szesnastkowy. Ma taki sam rozmiar wyjściowy jak hash MD5 (32 znaki szesnastkowe lub 16 bajtów, jeśli pominiemy część bin2hex).

print simple_hash("stackoverflow.com");

Spowoduje to wyświetlenie:

737461636b6f766572666c6f772e636f6d

Ta funkcja ma również tę samą właściwość braku iniekcji, co została podkreślona w odpowiedzi Cody'ego dla MD5: Możemy przekazywać ciągi dowolnego rozmiaru (o ile pasują do naszego komputera), a wypisze tylko 32 cyfry szesnastkowe. Oczywiście nie może być zastrzykiem.

Ale w tym przypadku znalezienie łańcucha, który odwzorowuje ten sam hash, jest trywialne (po prostu zastosuj hex2binswój hash i masz go). Jeśli Twój oryginalny ciąg miał długość 16 (jak w naszym przykładzie), otrzymasz nawet ten oryginalny ciąg. Nic takiego nie powinno być możliwe w przypadku MD5, nawet jeśli wiesz, że długość wejścia była dość krótka (poza wypróbowaniem wszystkich możliwych wejść, aż znajdziemy pasujący, np. Atak siłowy).

Ważnymi założeniami dla kryptograficznej funkcji skrótu są:

ciężko jest znaleźć ciąg produkujący dany hash (odporność na przedobraz)
trudno jest znaleźć inny ciąg produkujący taki sam hash jak dany ciąg (odporność na drugi przedobraz)
trudno znaleźć parę ciągów o tym samym skrócie (odporność na kolizje)

Oczywiście moja simple_hashfunkcja nie spełnia żadnego z tych warunków. (W rzeczywistości, jeśli ograniczymy przestrzeń wejściową do „ciągów 16-bajtowych”, wówczas moja funkcja stanie się iniekcyjna, a zatem będzie nawet możliwa do udowodnienia odporność na drugi obraz przed obrazem i kolizje).

Istnieją teraz ataki kolizyjne na MD5 (np. Możliwe jest utworzenie pary łańcuchów, nawet z danym prefiksem, które mają ten sam hash, co wymaga trochę pracy, ale nie jest to niemożliwe), więc nie powinieneś używać MD5 na wszystko, co krytyczne. Nie ma jeszcze ataku przedobrazowego, ale ataki będą lepsze.

Aby odpowiedzieć na rzeczywiste pytanie:

Co jest takiego w tych funkcjach, że nie można odtworzyć wynikowych łańcuchów?

To, co skutecznie MD5 (i inne funkcje skrótu zbudowane na konstrukcji Merkle-Damgarda) skutecznie robi, to zastosowanie algorytmu szyfrowania z wiadomością jako kluczem i pewną ustaloną wartością jako „zwykłym tekstem”, używając otrzymanego zaszyfrowanego tekstu jako skrótu. (Wcześniej wejście jest uzupełniane i dzielone na bloki, każdy z tych bloków jest używany do szyfrowania wyjścia poprzedniego bloku, XOR z jego wejściem, aby zapobiec odwrotnym obliczeniom).

Nowoczesne algorytmy szyfrujące (w tym te używane w funkcjach skrótu) są wykonane w taki sposób, aby utrudnić odzyskanie klucza, nawet jeśli podano zarówno tekst jawny, jak i zaszyfrowany (lub nawet gdy przeciwnik wybierze jeden z nich). Robią to na ogół wykonując wiele operacji tasowania bitów w taki sposób, że każdy bit wyjściowy jest określony przez każdy bit klucza (kilka razy), a także każdy bit wejściowy. W ten sposób możesz łatwo odtworzyć to, co dzieje się w środku, tylko jeśli znasz pełny klucz i wejście lub wyjście.

W przypadku funkcji skrótu podobnych do MD5 i ataku typu preimage (z pojedynczym ciągiem mieszanym, aby ułatwić sprawę), masz tylko dane wejściowe i wyjściowe funkcji szyfrowania, ale nie masz klucza (właśnie tego szukasz).

Answer 14

4

Tak, wiem, że jest to dość późna odpowiedź, ale zaakceptowanej odpowiedzi nie należy pozostawiać w ten sposób.

Paŭlo Ebermann

Answer 15

Myślę, że twoja krytyka ma jakąś wartość, ale nie udało ci się odpowiedzieć na rzeczywiste pytanie: „Co takiego jest w tych funkcjach, co uniemożliwia odtworzenie powstałych łańcuchów?”. Twoja odpowiedź koncentruje się na cechach, jakie kryptograficzny skrót powinien mieć, ale nie ma żadnego wyjaśnienia, w jaki sposób są one implementowane przez md5. Możesz tutaj podać dokładny algorytm obliczania sum MD5, aby pokazać, jak nie jest on odwracalny, ale inne odpowiedzi zapewniają prostsze wyjaśnienie bez wchodzenia w szczegóły.

Samouk

Answer 16

(cd…) 2. W tych wyjaśnieniach „matematyka” ukazuje podstawowy problem, w wyniku którego takie operacje tracą informacje i stają się nieodwracalne.

Samouk

Answer 17

1

@SandeepDatta Dodałem kilka akapitów na ten temat.

Paŭlo Ebermann

Answer 18

2

Podczas gdy inne odpowiedzi w tym wątku są bardziej poprawne technicznie, ta odpowiedź jest najbardziej przydatna. Funkcja nieinjekcyjna f (x) = 1 jest nieodwracalna, ale nieinteresująca. Użyteczność haszowania polega na rezystancji przedobrazu, gdzie trudno jest znaleźć jakiekolwiek dane wejściowe dające określone wyjście.

Justin J Stark

Answer 19

Odpowiedź Cody'ego Brociousa jest właściwa. Ściśle mówiąc, nie można „odwrócić” funkcji skrótu, ponieważ wiele ciągów jest odwzorowanych na ten sam skrót. Zauważ jednak, że albo znalezienie jednego ciągu, który jest mapowany na dany hash, albo znalezienie dwóch ciągów, które są mapowane na ten sam hash (tj. Kolizja ), byłoby dużym przełomem dla kryptoanalityka. Ogromna trudność obu tych problemów jest powodem, dla którego dobre funkcje skrótu są przydatne w kryptografii.

Answer 20

MD5 nie tworzy unikalnej wartości skrótu; celem MD5 jest szybkie wytworzenie wartości, która zmienia się znacząco w zależności od niewielkiej zmiany źródła.

Na przykład,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Oczywiście to nie jest rzeczywiste szyfrowanie MD5)

Większość skrótów (jeśli nie wszystkie) również nie jest unikalna; są raczej wystarczająco wyjątkowe , więc zderzenie jest wysoce nieprawdopodobne, ale nadal możliwe.

Answer 21

Dobrym sposobem na myślenie o algorytmie mieszania jest zmiana rozmiaru obrazu w Photoshopie ... powiedzmy, że masz obraz o wymiarach 5000x5000 pikseli, a następnie zmieniasz go do zaledwie 32x32. To, co masz, jest nadal reprezentacją oryginalnego obrazu, ale jest znacznie mniejsze i skutecznie „wyrzuciło” pewne części danych obrazu, aby zmieścić się w mniejszym rozmiarze. Więc gdybyś zmienił rozmiar tego obrazu 32x32 z powrotem do 5000x5000, wszystko, co otrzymasz, to rozmazany bałagan. Jednak ponieważ obraz 32x32 nie jest tak duży, teoretycznie można by sobie wyobrazić, że inny obraz mógłby zostać zmniejszony, aby uzyskać dokładnie te same piksele!

To tylko analogia, ale pomaga zrozumieć, co robi hasz.

Answer 22

3

Chociaż zmiana rozmiaru obrazu jest procesem stratnym, nadal dość łatwo jest wytworzyć obraz w oryginalnym rozmiarze 5000 × 5000, który (po ponownym zastosowaniu funkcji zmniejszania) zmniejszy się do tego samego obrazu 32 × 32. Znalezienie takiego obrazu wstępnego powinno być trudne dla dobrej funkcji skrótu.

Paŭlo Ebermann

Answer 23

4

Kolizja hash jest znacznie bardziej prawdopodobna, niż mogłoby się wydawać. Przyjrzyj się paradoksowi urodzin, aby lepiej zrozumieć, dlaczego tak jest.

Gamic
źródło

1

Istnieje 365 możliwych wartości urodzin, czyli między 2 ^ 8 a 2 ^ 9. 128-bitowy skrót ma 2 ^ 128 możliwych wartości - 2 ^ 120 razy więcej. Tak, zderzenia są bardziej prawdopodobne, niż mogłoby się wydawać, ale nadal są astronomicznie mało prawdopodobne.

Tim Keating

Będziesz potrzebować około 2 ^ 64 różnych wartości, aby mieć dużą szansę na zderzenie z hashem. Wciąż całkiem sporo.

Paŭlo Ebermann

Answer 24

1

Istnieje 365 możliwych wartości urodzin, czyli między 2 ^ 8 a 2 ^ 9. 128-bitowy skrót ma 2 ^ 128 możliwych wartości - 2 ^ 120 razy więcej. Tak, zderzenia są bardziej prawdopodobne, niż mogłoby się wydawać, ale nadal są astronomicznie mało prawdopodobne.

Tim Keating

Answer 25

Będziesz potrzebować około 2 ^ 64 różnych wartości, aby mieć dużą szansę na zderzenie z hashem. Wciąż całkiem sporo.

Paŭlo Ebermann

Answer 26

Ponieważ liczba możliwych plików wejściowych jest większa niż liczba 128-bitowych wyjść, niemożliwe jest jednoznaczne przypisanie skrótu MD5 do każdego możliwego.

Kryptograficzne funkcje skrótu służą do sprawdzania integralności danych lub podpisów cyfrowych (skrót jest podpisywany w celu zwiększenia wydajności). Zmiana oryginalnego dokumentu powinna zatem oznaczać, że oryginalny hash nie pasuje do zmienionego dokumentu.

Te kryteria są czasami używane:

Odporność obrazu wstępnego: dla danej funkcji skrótu i danego skrótu powinno być trudno znaleźć dane wejściowe, które mają dany skrót dla tej funkcji.
Rezystancja drugiego obrazu wstępnego: dla danej funkcji skrótu i wejścia powinno być trudno znaleźć drugie, inne wejście z tym samym hashem.
Odporność na kolizje: dla danej funkcji powinno być trudno znaleźć dwa różne wejścia z tym samym hashem.

Kryteria te są wybrane tak, aby utrudnić znalezienie dokumentu pasującego do danego skrótu, w przeciwnym razie możliwe byłoby sfałszowanie dokumentów poprzez zastąpienie oryginału takim, który został dopasowany przez hash. (Nawet jeśli zamiana jest bełkotem, sama wymiana oryginału może spowodować zakłócenia).

Numer 3 implikuje numer 2.

W szczególności w przypadku MD5 wykazano, że jest on wadliwy: Jak złamać MD5 i inne funkcje skrótu .

Answer 27

Ale tutaj pojawiają się tęczowe stoły. Zasadniczo jest to po prostu duża liczba wartości zaszyfrowanych osobno, a następnie wynik jest zapisywany na dysku. Wtedy bit cofania „tylko” służy do przeszukiwania bardzo dużej tabeli.

Oczywiście jest to możliwe tylko dla podzbioru wszystkich możliwych wartości wejściowych, ale jeśli znasz granice wartości wejściowej, może być możliwe jej obliczenie.

Answer 28

Ach tak. Z przyjemnością przeczytałem post Jeffa w Hash Tables ( codinghorror.com/blog/archives/000949.html ), a ten wątek pomógł w zrozumieniu koncepcji.

barfoon

Answer 29

Chiński naukowiec odkrył sposób zwany „kolizjami wybranego przedrostka”, który umożliwia konflikt między dwoma różnymi łańcuchami.

Oto przykład: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
Kod źródłowy: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0. 5_source.zip

Answer 30

Najlepszym sposobem, aby zrozumieć, co oznaczały wszystkie najczęściej głosowane odpowiedzi, jest faktycznie próba przywrócenia algorytmu MD5. Pamiętam, że kilka lat temu próbowałem przywrócić algorytm MD5crypt , aby nie odzyskać oryginalnej wiadomości, ponieważ jest to oczywiście niemożliwe, ale po prostu wygenerować wiadomość, która wygeneruje ten sam hash, co oryginalny hash. To, przynajmniej teoretycznie, dałoby mi sposób na zalogowanie się do urządzenia z Linuksem, które przechowuje użytkownika: hasło w pliku / etc / passwd przy użyciu wygenerowanej wiadomości (hasła) zamiast używania oryginalnego. Ponieważ obie wiadomości miałyby ten sam hash wynikowy, system rozpoznałby moje hasło (wygenerowane z oryginalnego skrótu) jako prawidłowe. To w ogóle nie zadziałało. Po kilku tygodniach, o ile dobrze pamiętam, stosowanie soliw pierwszej wiadomości mnie zabił. Musiałem przedstawić nie tylko prawidłową wiadomość początkową, ale także poprawną, ważną wiadomość początkową, czego nigdy nie byłem w stanie zrobić. Ale wiedza, którą uzyskałem z tego eksperymentu, była miła.

Answer 31

Gdybyś był w stanie wygenerować dane wejściowe, które wygenerowałyby daną wartość skrótu MD5 w jakikolwiek rozsądnie efektywny sposób, byłaby to wielka sprawa dla społeczności kryptograficznej i powinna zostać opublikowana. Jest to całkowicie niezależne od tego, czy dany wkład był solony.

Dave L.

Answer 32

Jak większość już powiedziała, MD5 została zaprojektowana do mieszania strumieni danych o zmiennej długości do fragmentów danych o stałej długości, dzięki czemu jeden skrót jest współdzielony przez wiele strumieni danych wejściowych.

Jeśli jednak kiedykolwiek musiałeś znaleźć oryginalne dane z sumy kontrolnej, na przykład jeśli masz skrót hasła i potrzebujesz znaleźć oryginalne hasło, często szybciej jest po prostu wygooglować (lub dowolną preferowaną wyszukiwarkę). dla odpowiedzi niż brutalnej siły. Udało mi się znaleźć kilka haseł za pomocą tej metody.

Answer 33

z definicji funkcja Hash (kryptograficzna Hash): nie powinna być odwracalna; nie powinna mieć kolizji (najmniej możliwe).

regd twoje pytanie: jest to skrót jednokierunkowy. input (niezależnie od długości) wygeneruje wyjście o stałym rozmiarze (będzie wypełnione w oparciu o algorytm (granica 512 bitów dla MD5)). Informacje są kompresowane (tracone) i praktycznie nie można ich wygenerować z przekształceń odwrotnych.

dodatkowe informacje na temat MD5: jest podatny na kolizje. przejrzał ostatnio ten artykuł, http://www.win.tue.nl/hashclash/Nostradamus/

otwiera kod źródłowy dla implementacji skrótów kryptograficznych (MD5 i SHA) można znaleźć w kodzie Mozilli. (biblioteka freebl).

Answer 34

0

Teraz dni hashe MD5 lub inne skróty w tym zakresie są wstępnie obliczane dla wszystkich możliwych ciągów i przechowywane w celu zapewnienia łatwego dostępu. Chociaż teoretycznie MD5 nie jest odwracalne, ale korzystając z takich baz danych, możesz dowiedzieć się, który tekst spowodował określoną wartość skrótu.

Na przykład wypróbuj następujący kod skrótu na http://gdataonline.com/seekhash.php, aby dowiedzieć się, jakiego tekstu użyłem do obliczenia skrótu

aea23489ce3aa9b6406ebb28e0cda430

Babar
źródło

Ach, tak, skrót pospolitego siedmioliterowego słowa. Teraz użyj go, aby znaleźć ten 11-wyrazowy tekst piosenki z białymi spacjami i interpunkcją: 9f2c08d4e6158bd4854b15be50c8daa8. Do zobaczenia za kilka tysiącleci.

Tim Keating

6fba2bbab8a8366309bf67c7df12c622? Wskazówka: może to być wersja OEM określonej wersji systemu Mac OS X!

scherand

@Tim Keating, @scherand: Zwracam tylko uwagę na słabość algorytmów mieszania, ponieważ hash ciągu jest zawsze taki sam, nie musimy koniecznie łamać algorytmu, aby znaleźć rzeczywisty ciąg.

Babar

2

Ale nie to powiedziałeś. Powiedziałeś, że skróty są „obliczane wstępnie dla wszystkich możliwych ciągów i przechowywane dla łatwego dostępu”, co jest ewidentnie fałszywe (zbiór „wszystkich możliwych ciągów” jest nieskończony… a nawet zbiór „wszystkich możliwych ciągów” jest naprawdę, bardzo duży ). IMHO to błędnie przedstawia, jak łatwo jest przeprowadzić atak słownikowy na rozsądne hasło.

Tim Keating

Answer 35

Ach, tak, skrót pospolitego siedmioliterowego słowa. Teraz użyj go, aby znaleźć ten 11-wyrazowy tekst piosenki z białymi spacjami i interpunkcją: 9f2c08d4e6158bd4854b15be50c8daa8. Do zobaczenia za kilka tysiącleci.

Tim Keating

Answer 36

6fba2bbab8a8366309bf67c7df12c622? Wskazówka: może to być wersja OEM określonej wersji systemu Mac OS X!

scherand

Answer 37

@Tim Keating, @scherand: Zwracam tylko uwagę na słabość algorytmów mieszania, ponieważ hash ciągu jest zawsze taki sam, nie musimy koniecznie łamać algorytmu, aby znaleźć rzeczywisty ciąg.

Babar

Answer 38

2

Ale nie to powiedziałeś. Powiedziałeś, że skróty są „obliczane wstępnie dla wszystkich możliwych ciągów i przechowywane dla łatwego dostępu”, co jest ewidentnie fałszywe (zbiór „wszystkich możliwych ciągów” jest nieskończony… a nawet zbiór „wszystkich możliwych ciągów” jest naprawdę, bardzo duży ). IMHO to błędnie przedstawia, jak łatwo jest przeprowadzić atak słownikowy na rozsądne hasło.

Tim Keating

Answer 39

f (x) = 1 jest nieodwracalne. Funkcje skrótu nie są nieodwracalne.

W rzeczywistości jest to wymagane, aby mogli spełnić swoją funkcję polegającą na ustaleniu, czy ktoś posiada nieuszkodzoną kopię zaszyfrowanych danych. Stwarza to podatność na ataki brutalnej siły, które są obecnie dość potężne, szczególnie przeciwko MD5.

Istnieje również zamieszanie tutaj i gdzie indziej wśród ludzi, którzy mają wiedzę matematyczną, ale mało wiedzy na temat szyfrowania. Kilka szyfrów po prostu XORuje dane ze strumieniem klucza, więc można powiedzieć, że tekst zaszyfrowany odpowiada wszystkim tekstom jawnym o tej długości, ponieważ można było użyć dowolnego strumienia klucza.

Jednak to ignoruje fakt, że rozsądny tekst jawny utworzony z nasienia passwordjest znacznie bardziej prawdopodobny niż inny tekst utworzony przez nasienie Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6odo tego stopnia, że każdy, kto twierdzi, że drugi jest możliwy, byłby wyśmiewany.

W ten sam sposób, jeśli próbujesz wybrać między dwoma potencjalnymi hasłami passwordi Wsg5Nm^bkI4EgxUO, nie jest to tak trudne, jak sądzą niektórzy matematycy.

Answer 40

Skąd masz większość szyfrów po prostu XOR danych z wiedzą o strumieniu kluczy ? Dotyczy to szyfrów strumieniowych, ale są też szyfry blokowe i nie działają w ten sposób.

Paŭlo Ebermann

Answer 41

Podobają mi się wszystkie argumenty. Jest oczywiste, że prawdziwą wartością zaszyfrowanych wartości jest po prostu zapewnienie nieczytelnych dla człowieka symboli zastępczych dla ciągów, takich jak hasła. Nie ma szczególnych korzyści w zakresie bezpieczeństwa. Zakładając, że atakujący uzyskał dostęp do tabeli z zaszyfrowanymi hasłami, może:

Skasuj wybrane przez siebie hasło i umieść wyniki w tabeli haseł, jeśli ma uprawnienia do zapisu / edycji tabeli.
Wygeneruj zaszyfrowane wartości typowych haseł i przetestuj istnienie podobnych zaszyfrowanych wartości w tabeli haseł.

W tym przypadku słabe hasła nie mogą być chronione przez sam fakt, że są zaszyfrowane.

Answer 42

Prawdziwa wartość „zaszyfrowanych wartości” nie polega na zapewnieniu nieczytelnych dla człowieka symboli zastępczych. Jeśli „hasło1” jest hashowane do „newval”, czy to nadal nie powoduje ukrycia wartości w podobny sposób, chociaż skrót jest czytelny i ma znaczenie? Ponadto hasła są złym przykładem, ponieważ NIGDY nie powinny być haszowane. Zakładając, że atakujący miał dostęp do zapisu we wspomnianej bazie danych, jest to zdecydowanie możliwe. Jednak wydaje się, że po prostu odrzucasz właściwe użycie takich funkcji haszujących, jeden przykład jest nakreślony w wielu odpowiedziach powyżej - integralność wiadomości. Właściwie to jest powód, dla którego jestem dzisiaj w tym wątku.

Shane

Dlaczego wartości skrótu MD5 nie są odwracalne?

Odpowiedzi: