Pytanie w sprawie cryptography, hash-function, hash – Jakie są ważne punkty dotyczące kryptograficznych funkcji skrótu?

11

czytałemto pytanie na wartościach mieszania MD5 i zaakceptowana odpowiedź wprowadza mnie w błąd. Jedną z głównych właściwości, jak rozumiem, kryptograficznej funkcji mieszającej jest to, że nie można znaleźć dwóch różnych komunikatów (wejść) o tej samej wartości mieszania.

Jednak zgoda na pytanieDlaczego wartości skrótu MD5 nie są odwracalne? jestPonieważ nieskończona liczba ciągów wejściowych wygeneruje to samo wyjście. Wydaje mi się to całkowicie sprzeczne.

Co mnie trochę wprawia w zakłopotanie, to fakt, że algorytmy są publiczne, ale wartości mieszania są wciąż nieodwracalne. Czy to dlatego, że w funkcji skrótu zawsze występuje utrata danych, więc nie ma sposobu na określenie, które dane zostały odrzucone?

Co się dzieje, gdy rozmiar danych wejściowych jest mniejszy niż ustalony rozmiar danych wyjściowych (np. Mieszanie hasła „abc”)?

EDYTOWAĆ:

OK, pozwól mi zobaczyć, czy mam to proste:

Naprawdę, naprawdę trudno jest wywnioskować dane wejściowe z hashaponieważ istnieje nieskończona ilość ciągów wejściowych, które wygenerują to samo wyjście (własność nieodwracalna).Jednak,odkrycie nawet pojedyncza instancja wielu ciągów wejściowych, które generują to samo wyjście, jest naprawdę, bardzo trudna (właściwość odporna na kolizje).
Powodem właściwości odwracalności nie jest „nieskończona ilość ciągów wejściowych”, powinna być również taka, gdy ograniczasz wejście do czegoś małego (jak na przykład rozmiar wyjściowy). Paŭlo Ebermann
Tak, „konsensus” w odpowiedziach napytanie, które powiązałeś jest całkowicie błędne. Właśnie dodałem kolejną odpowiedź, poprawiając to. Paŭlo Ebermann
Nie widziałem twojej edycji. Myślę, że podsumowałeś to w tych dwóch kulach. Alex Feinman

Twoja odpowiedź

6   odpowiedzi
18

Ostrzeżenie: Długa odpowiedź

Myślę, że wszystkie te odpowiedzi nie posiadają bardzo ważnej właściwości kryptograficznych funkcji skrótu: nie tylko nie jest możliwe obliczenie oryginalnej wiadomości, która została zmieszana w celu uzyskania danego skrótu, ale niemożliwe jest obliczeniekażdy komunikat, który będzie mieszał do danej wartości skrótu. To się nazywaopór przed obrazem.

(Przez „niemożliwe” - mam na myśli to, że nikt nie wie, jak to zrobić w krótszym czasie niż potrzeba do odgadnięcia każdej możliwej wiadomości, dopóki nie zgadniesz tego, który został zmieszany z hashem).

(Pomimo powszechnego przekonania o niepewności MD5, MD5 jest nadal odporny na obraz. Każdy, kto mi nie wierzy, może dać mi wszystko, co ma na celu2aaddf751bff2121cc51dc709e866f19. Co nie ma MD5odporność na kolizje, co jest czymś zupełnie innym.)

Teraz, jeśli jedynym powodem, dla którego nie możesz „pracować wstecz” w kryptograficznej funkcji mieszającej, było to, że funkcja mieszania odrzuca dane w celu utworzenia skrótu, to nie gwarantowałoby odporności na obraz przedwczesny: nadal możesz „pracować wstecz” i po prostu wstawić dane losowe wszędzie tam, gdzie funkcja skrótu odrzuca dane, i chociaż nie wymyśliłeś oryginalnej wiadomości, wciąż pojawiałby się komunikat, który miesza do żądanej wartości skrótu. Ale nie możesz.

Więc pytanie brzmi: dlaczego nie? (Lub, innymi słowy, jak sprawić, by funkcja była odporna na obrazowanie?)

Odpowiedź brzmi: kryptograficzne funkcje mieszające symulują chaotyczne systemy. Biorą twoją wiadomość, rozbijają ją na bloki, mieszają te bloki dookoła, niektóre bloki wchodzą ze sobą w interakcję, mieszają te bloki dookoła i powtarzają to wiele razy (cóż, jedna kryptograficzna funkcja mieszająca to robi; inni mają swoje własne metody). Ponieważ bloki wchodzą ze sobą w interakcję, blok C musi nie tylko współdziałać z blokiem D, aby wytworzyć blok A, ale musi oddziaływać z blokiem E, aby utworzyć blok B. Teraz, na pewno, można znaleźć wartości bloków C, D, E, które wytworzyłyby bloki A i B w wartości skrótu, ale gdy cofniesz się dalej, nagle potrzebujesz bloku F, który wchodzi w interakcję z C, aby zrobić D, a za pomocą E, aby uczynić B, i żaden taki blok nie może zrobić obu w o tym samym czasie! Musisz odgadnąć błędne wartości dla C, D i E.

Chociaż nie wszystkie kryptograficzne funkcje mieszające są dokładnie takie, jak opisano powyżej z interakcją blokową, mają ten sam pomysł: że jeśli spróbujesz „pracować wstecz”, skończysz z całą masą ślepych zaułków, a czas to wymaga wypróbowania wystarczającej liczby wartości, aby wygenerować preimage od setek do milionów lat (w zależności od funkcji skrótu), niewiele lepiej niż czas potrzebny na wypróbowanie wiadomości, aż znajdziesz taki, który działa.

2

Są to właściwości ogólnie funkcji skrótu.

Należy jednak pamiętać, że MD5 nie powinien być już używany ze względu na znalezione w nim luki. Sprawdź sekcję „Luki w zabezpieczeniach” i linki zewnętrzne opisujące te ataki.http://en.wikipedia.org/wiki/Md5 Możesz dokonać kolizji MD5, zmieniając tylko 128 bitów w wiadomości.

SHA-1 jest bezpieczny do prostego mieszania, chociaż istnieją pewne ataki, które osłabiłyby go przeciwko dobrze finansowanym podmiotom (rządy, duże korporacje)

SHA-256 jest bezpiecznym punktem wyjścia dla technologii na najbliższe dziesięciolecia.

@ vg1890: właściwościkryptograficzny funkcje mieszające. H (x) = x mod 2 nie jest funkcją kryptograficzną. (Może to być dobre dla tabeli mieszania z 2 wpisami.) Paŭlo Ebermann
Niekoniecznie. Przyjęta odpowiedź w pytaniu, które łączyłem, używa przykładu funkcji mieszającej H (x) = x mod 2. Ta funkcja skrótu wykazuje właściwość trudną do odwrócenia, ale nie właściwość niskiej kolizji. Rob Sobers
6

Możesz być zdezorientowany, ponieważ odpowiedź na topytanie, które cytujesz jest mylące. Jednym z wymogów dla funkcji skrótu kryptograficznego jest to, że powinna ona być odporna na przedwczesne działanie. Oznacza to, że jeśli znasz MD5 (x), ale nie komunikat x, trudno jest znaleźć dowolny x '(równy x lub inny niż x), tak że MD5 (x') = MD5 (x).

Odporność na przedwczesność jest inną właściwością niż odwracalność. Funkcja jest odwracalna, jeśli podano y = f (x) jest dokładnie jeden x, który pasuje (czy jest to łatwe, czy nie). Na przykład zdefiniuj f (x) = x mod 10. Wtedy f nie jest odwracalne. Z f (x) = 7 nie można określić, czy x wynosi 17, 27 czy coś innego. Ale f nie jest odporny na przedwczesność, ponieważ wartości x 'takie, że f (x) = 7 są łatwe do znalezienia. x '= 17, 27, 12341237 itd. wszystko działa.

Podczas wykonywania kryptografii zazwyczaj potrzebujesz funkcji, które są odporne na przedwczesne działanie (i innych właściwości, takich jak odporność na kolizje), a nie tylko czegoś, co nie jest odwracalne.

1

Jednak zgodna odpowiedź na pytanie „dlaczego wartości skrótu MD5 nie są odwracalne?” jest tak, ponieważ „nieskończona liczba ciągów wejściowych wygeneruje to samo wyjście”.

Dotyczy to każdej funkcji mieszającej, ale nie jest istotą kryptograficznej funkcji mieszającej.

W przypadku krótkich ciągów wejściowych, takich jak hasła, teoretycznie możliwe jest odwrócenie kryptograficznej funkcji mieszającej, ale powinno to być niemożliwe do obliczenia. To znaczy. Twoje obliczenia przebiegałyby zbyt długo, aby były przydatne.

Przyczyną tej niemożności jest to, że dane wejściowe są tak dokładnie „zmieszane” w wartości mieszania, że ​​niemożliwe staje się ich rozplątanie przy mniejszym wysiłku niż atak brutalnej siły obliczania wartości skrótu dla wszystkich danych wejściowych

12

1: Głównym celem skrótu jest mapowanie bardzo, bardzo dużej przestrzeni na mniejszą, ale wciąż bardzo dużą przestrzeń (np. MD5, która zajmie „wszystko” i przekształci ją w przestrzeń o rozmiarze 2 ^ 128 - duża , ale nie tak duży jak aleph-0.)

Oprócz innych funkcjidobry hashe jednorodnie wypełniają przestrzeń docelową. Złe hasze wypełniają przestrzeń w niezgrabny sposób, wymyślając ten sam skrót dla wielu wspólnych wejść.

Wyobraź sobie idiotyczną funkcję skrótu sum (), która po prostu dodaje wszystkie cyfry numeru wejścia: udaje się go odwzorować, ale jest kilka kolizji (dane wejściowe o tym samym wyjściu, jak 3 i 12 i 21) na niskim poziomie koniec przestrzeni wyjściowej i górny koniec przestrzeni jest prawie pusty. W rezultacie bardzo źle wykorzystuje przestrzeń, jest łatwa do złamania itp.

Tak więc dobry hash, który wykorzystuje nawet przestrzeń docelową, utrudni znalezienie dwóch wejść o tym samym wyjściu, po prostu przez szanse: jeśli MD5 byłby doskonały, prawdopodobieństwo, że dwa wejścia będą miały ten sam wynik, wynosiłoby 2 ^ - 128. To całkiem przyzwoity kurs: najlepsze, co możesz zrobić bez uciekania się do większej przestrzeni wyjściowej. (W rzeczywistości MD5 nie jest doskonały, co jest jedną z rzeczy, które sprawiają, że jest podatny na ataki).

Ale nadal będzie prawdą, że ogromna liczba danych wejściowych będzie mapować na dowolny dany skrót, ponieważ przestrzeń wejściowa jest „nieskończona”, a dzielenie nieskończoności przez 2 ^ 128 wciąż daje nieskończoność.

2: Tak, skróty zawsze powodują utratę danych, z wyjątkiem przypadku, gdy przestrzeń wyjściowa jest taka sama lub większa niż przestrzeń wejściowa - iw takim przypadku prawdopodobnie nie trzeba było mieszać!

3: W przypadku mniejszych nakładów najlepszą praktyką jest zasolenie danych wejściowych. Właściwie jest to dobra praktyka dla każdego kryptograficznego mieszania, ponieważ w przeciwnym razie atakujący może podać ci konkretne dane wejściowe i spróbować dowiedzieć się, którego skrótu używasz. „Sól” to tylko zbiór dodatkowych informacji, które dołączasz (lub wstawiasz) do swojego wejścia; wtedy osiągniesz wynik.

edytować: W kryptografii ważne jest również, aby funkcja hash była odporna na ataki preimage, intuicyjnie, trudno jest odgadnąć dane wejściowe dla danego wyjścia, nawet znając wiele innych par wejścia / wyjścia. Funkcję „sumy” można raczej odgadnąć dość łatwo (ale ponieważ niszczy ona dane, nadal może nie być łatwo odwrócić).

@ Paŭlo Ebermann, jeśli masz zmiany sugerowane, chętnie je uwzględnię. Trudno jest jednak poruszyć głosowanie nad odpowiedziami na stare pytania, więc możesz nie mieć szczęścia, jeśli chodzi o zmianę innego pytania. Alex Feinman
Mówi się o funkcjach skrótu, które mogą być używane w tabelach mieszania, ale pomijają punkt kryptograficznych funkcji skrótu (np. Odporność na preimage). Paŭlo Ebermann
Twój zły hash jest jak mój idiotyczny hash: ma słabą jednorodność i straszną strategię kolizji. Myślę, że edytuję go, aby wskazać, że funkcje, o których wspomniałem, są konieczne, ale niewystarczające dla kryptograficznie silnej funkcji mieszającej, ponieważ ma kilka punktów wyjaśniających, że odpowiedź Zarela się błyszczy. Alex Feinman
Przepraszam, nie chciałem sugerować, że funkcja liniowo dystrybuuje funkcję, tylko że rozkład liczb powinien być płynny na dużą skalę. Alex Feinman
0

„dlaczego wartości skrótu MD5 nie są odwracalne?” jest tak, ponieważ „nieskończona liczba ciągów wejściowych> wygeneruje to samo wyjście”

to jest powód, dla którego nie można odwrócić funkcji skrótu (uzyskać to samo wejście). kryptograficzne funkcje mieszające są odporne na kolizje, co oznacza, że ​​trudno jest znaleźć inną wartość wejściową, która odwzorowuje to samo wyjście (jeśli funkcją skrótu był mod 2: 134 mod 2 = 0; teraz nie można odzyskać 134 z wynik, ale możemy znaleźć numer 2 o tej samej wartości wyjściowej (zderzamy się z 134 i 2)).

Gdy wejście jest mniejsze niż rozmiar bloku,wyściółka służy do dopasowania do rozmiaru bloku.

cofanie funkcji jest czymś innym niż znalezienie kolizji. Idealnie jedynym sposobem znalezienia kolizji byłoby wypróbowanie jednego wejścia za drugim i porównanie ouptut funkcji mieszającej z wartością, którą chcesz odwrócić / znaleźć kolizję (to jest trudne). Ale nawet gdybyś to zrobił, nie wiedziałbyś, czy znaleziona kolizja była oryginalna, czy właśnie znalazłeś nowy ciąg o tej samej wartości mieszania. cube
Nadal nie ma sensu, trudno jest znaleźć dwa wejścia, które wytwarzają ten sam sygnał wyjściowy, ale fakt, że wiele wejść ma to samo wyjście, jest przyczyną nieodwracalnego mieszania. Jak to nie jest sprzeczność? Rob Sobers

Powiązane pytania