Co sprawia, że ​​algorytm mieszający jest „bezpieczny”?

Po przeczytaniu tego interesującego pytania poczułem, że mam dobry pomysł, który niepewny algorytm mieszający użyłbym, gdybym go potrzebował, ale nie mam pojęcia, dlaczego zamiast tego mogę użyć bezpiecznego algorytmu.

Jakie jest zatem rozróżnienie? Czy wynik nie jest tylko liczbą losową reprezentującą zaszyfrowaną rzecz? Co sprawia, że ​​niektóre algorytmy mieszające są bezpieczne?

Istnieją trzy właściwości, których oczekujemy od każdej funkcji skrótu kryptograficznego H:

• preimage odporność : Biorąc pod uwagę h, powinno być trudno znaleźć jakąkolwiek wartość xz h = H(x).

• Drugi opór preimage : Biorąc pod uwagę x1, powinno być trudno znaleźć x2 != x1z H(x1) = H(x2).

• Odporność na zderzenie : To powinno być trudno znaleźć dwie wartości x1 != x2z H(x1) = H(x2).

W przypadku funkcji skrótu używanych w popularnych językach programowania dla tabel skrótów (ciągów znaków) zwykle nie podano żadnej z nich, zapewniają one tylko:

• słaba odporność na kolizję : w przypadku losowo (lub „typowo”) wybranych wartości domeny szansa na kolizję jest niewielka. Nie mówi to nic o atakującym, który celowo próbuje tworzyć kolizje lub próbuje znaleźć preimages.

Trzy powyższe właściwości są (wśród) celami projektowania dla każdej funkcji skrótu kryptograficznego. W przypadku niektórych funkcji (takich jak MD4, SHA-0, MD5) wiadomo, że to się nie udało (przynajmniej częściowo). Zakłada się, że obecna generacja (SHA-2) jest bezpieczna, a następna („Bezpieczny algorytm mieszania 3”) jest obecnie w trakcie standaryzacji , po zakończeniu konkursu .

W przypadku niektórych zastosowań (takich jak haszowanie haseł i wyprowadzanie kluczy z haseł) dziedzina faktycznie używanych wartości xjest tak mała, że ​​brutalne wymuszanie tej przestrzeni staje się możliwe dzięki normalnym (szybkim) bezpiecznym funkcjom hashującym i wtedy też chcemy:

• powolne wykonywanie : Biorąc pod uwagę x, do obliczenia wartości potrzeba minimalnej (najlepiej konfigurowalnej) ilości zasobów H(x).

Ale dla większości innych zastosowań nie jest to pożądane, zamiast tego chce się:

• szybkie wykonanie : Biorąc pod uwagę x, obliczenie wartości H(x)jest tak szybkie, jak to możliwe (przy jednoczesnym zachowaniu bezpieczeństwa).

Istnieją pewne konstrukcje (takie jak PBKDF2 i scrypt), aby utworzyć powolną funkcję skrótu z szybkiej poprzez częste iterowanie.

Aby uzyskać więcej informacji, spójrz na tag hash na naszej siostrzanej stronie Cryptography Stack Exchange.

Bezpieczny oznacza, że ​​ktoś, kto chce wprowadzić cię w błąd przy użyciu kolizji (tj. Fakt, że dwa źródła są połączone tą samą wartością) będzie miał trudności.

Niektóre cechy:

• znając skrót, zbudowanie pliku, który ma skrót do tej wartości, jest trudne (wariant, część nowego pliku jest podana, a także pożądany skrót)

• budowanie dwóch różnych plików, których skrót do tej samej wartości jest trudny (podano wariant, część plików)

Podstawowa różnica jest dość prosta: normalny skrót ma na celu zminimalizowanie liczby przypadkowych kolizji, o ile jest to możliwe bez spowalniania całego procesu.

Bezpieczny skrót miał zapobiegać kolizjom, nawet jeśli ktoś robi wszystko, aby je wywołać. Zasadniczo nie chcesz wymieniać żadnej możliwości kolizji w celu szybszego działania. W rzeczywistości celowe spowalnianie operacji ma pewne zalety bezpieczeństwa, nawet jeśli nie utrudnia znajdowania kolizji.

Na przykład: jeśli obliczenie skrótu zajmuje 50 ms, nie będzie to miało istotnego wpływu na zwykłe logowanie użytkownika (tzn. Większość użytkowników nie zauważy różnicy 50 ms podczas logowania). Jednocześnie, jeśli atakujący chce wykonać atak słownikowy, możliwość wygenerowania tylko 20 skrótów sekund jest poważnym utrudnieniem. Innymi słowy, z jakiegoś powodu, dla bezpiecznego skrótu, wolniejsze jest lepsze.

Przeczytaj ten http://www.codinghorror.com/blog/2012/04/speed-hashing.html , a wszystko wyjaśni znacznie lepiej, niż mógłbym to wyjaśnić. Oto dwa najważniejsze nagłówki w artykule, które bezpośrednio dotyczą twojego pytania:

• Bezpieczne skróty są zaprojektowane tak, aby były odporne na manipulacje
  • radykalnie zmienia swój wynik za pomocą drobnych zmian bitów w danych wejściowych
• Bezpieczne skróty mają działać wolno

Jego sekcja TL; DR na końcu:

Jeśli jesteś użytkownikiem:

Upewnij się, że wszystkie hasła mają 12 lub więcej znaków, a najlepiej o wiele więcej. Zalecam stosowanie fraz hasła, które są nie tylko łatwiejsze do zapamiętania niż hasła (jeśli nie są typowe), ale także śmiesznie zabezpieczają się przed brutalnym wymuszaniem wyłącznie ze względu na ich długość.

Jeśli jesteś programistą:

Używaj bcrypt lub PBKDF2 wyłącznie do mieszania wszystkiego, czego potrzebujesz, aby być bezpiecznym. Te nowe skróty zostały specjalnie zaprojektowane, aby były trudne do wdrożenia w procesorach graficznych. Nie używaj żadnej innej formy skrótu. Niemal każdy inny popularny schemat mieszania jest podatny na brutalne wymuszanie przez układy GPU towarowych, które stają się szybsze i bardziej równoległe i łatwiejsze do zaprogramowania na każdy rok.

„Bezpieczny” skrót to skrót, który uważa się za trudny do „sfałszowania” w formalny, powtarzalny sposób bez uprzedniej wiedzy o komunikacie użytym do utworzenia skrótu. Ponieważ informacje te są ogólnie tajne, stąd potrzeba skrótu, jest to dobra właściwość funkcji skrótu przeznaczonej do użycia w uwierzytelnianiu.

Hash jest ogólnie uważany za „bezpieczny”, jeśli biorąc pod uwagę komunikat M, hash funkcji hash () i wartość skrótu H wytworzoną przez hash (M) o długości w bitach L, żadna z poniższych czynności nie może być wykonana w mniej niż Czas O (2 ^L ):

• Biorąc pod uwagę hash () i H, produkujemy M. (odporność na preimage)
• Biorąc pod uwagę hash () i M, produkujemy inny M _2, taki że hash (M ₂ ) == H. (słaby opór zderzenia)
• Biorąc pod uwagę hash (), produkuj dowolne M ₁ i M _2, tak aby hash (M ₁ ) == hash (M ₂ ). (duża odporność na zderzenia)

Dodatkowo „bezpieczny” skrót musi mieć długość skrótu L taką, że 2 ^Lnie jest wykonalną liczbą kroków, aby komputer mógł wykonać dany bieżący sprzęt. 32-bitowa liczba całkowita może mieć tylko 2,1 miliarda wartości; podczas gdy atak preimage (znalezienie wiadomości, która generuje określony skrót H) zająłby trochę czasu, nie jest to niemożliwe dla wielu komputerów, szczególnie tych znajdujących się w rękach agencji rządowych, które mają za zadanie łamanie kodów. Ponadto algorytm, który tworzy i przechowuje losowe wiadomości i ich skróty, według prawdopodobieństwa, miałby 50% szans na znalezienie duplikatu każdej nowej wiadomości po wypróbowaniu tylko 77 000 wiadomości i miałby 75% szansy na trafienie zduplikowane już po 110 000. Nawet skróty 64-bitowe nadal mają 50% szans na zderzenie po wypróbowaniu zaledwie około 5 miliardów wartości. Taka jest siła urodzinowego ataku na małe hasze. Natomiastliczby decylionowe (1,5 * 10 ³⁴ ).

Większość zademonstrowanych ataków na kryptograficzne skróty to ataki kolizyjne, które wykazały zdolność do generowania kolidujących wiadomości w czasie krótszym niż 2 ^l (większość nadal była czasem wykładniczym, ale zmniejszenie wykładnika o połowę jest znaczącym zmniejszeniem złożoności, ponieważ powoduje 256-bitowy skrót tak łatwy do rozwiązania jak 128-bitowy, 128-bitowy tak łatwy do rozwiązania jak 64-bitowy itp.).

Oprócz małego rozmiaru skrótu, innymi czynnikami, które mogą sprawić, że skrót jest wyraźnie niepewny, są:

Niska praca - skrót zaprojektowany do użycia przez tablicę skrótów lub do innych celów typu „suma kontrolna” jest zwykle zaprojektowany tak, aby był niedrogi obliczeniowo. To znacznie ułatwia atak z użyciem siły.

„Sticky State” - Funkcja skrótu jest podatna na wzorce danych wejściowych, w których bieżąca wartość skrótu wszystkich dotychczasowych danych nie zmienia się, gdy otrzyma się określony dodatkowy bajt danych wejściowych. Posiadanie „stanu lepkiego” ułatwia znajdowanie kolizji, ponieważ po zidentyfikowaniu wiadomości, która generuje skrót „stanu lepkiego”, generowanie innych wiadomości o tym samym haszu jest trywialne przez dołączanie bajtów wejściowych, które utrzymują skrót w jego „lepkim stanie” „.

Dyfuzja - każdy bajt wejściowy wiadomości powinien być rozdzielony między bajty wartości skrótu w równie złożony sposób. Niektóre funkcje skrótu powodują przewidywalne zmiany w niektórych bitach skrótu. To znowu sprawia, że ​​tworzenie kolizji jest trywialne; biorąc pod uwagę komunikat, który tworzy skrót, można łatwo utworzyć kolizje, wprowadzając do komunikatu nowe wartości, które wpływają tylko na bity zmieniające się w przewidywalny sposób.

Użyj właściwego algorytmu dla danego zadania.

CRC są używane do wykrywania / korekcji błędów.

Skrypty wiadomości kryptograficznych, takie jak SHA2, są wykorzystywane jako element konstrukcyjny dla konstrukcji kryptograficznych (podpisy cyfrowe, adresy MAC, funkcje wyprowadzania kluczy / haszowania haseł) oraz protokołów bezpieczeństwa.

W tablicach skrótów / słownikach / mapach używaj SipHash .

To, co nazywacie niezabezpieczonymi algorytmami mieszania, nie powinno być używane w tabelach skrótów , co potwierdzają następujące wpisy CVE: CVE-2003-0364, CVE-2011-4461, CVE-2011-4838, CVE-2011-4885, CVE-2011- 4462, CVE-2011-4815, CVE-2012-0840, CVE-2012-5371 , CVE-2012-5374, CVE-2012-5375