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).