Jak działają jednokierunkowe funkcje skrótu?

Pomyśl o naprawdę podstawowym hash - dla ciągu wejściowego zwróć sumę wartości ASCII każdego znaku.

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

Teraz, biorąc pod uwagę wartość hash 294, możesz powiedzieć, jaki był oryginalny ciąg? Oczywiście nie, ponieważ ' abc ' i ' cba '(i niezliczone inne) dają tę samą wartość hash.

Kryptograficzne funkcje skrótu działają w ten sam sposób, z tym że oczywiście algorytm jest znacznie bardziej złożony. Zawsze będą kolizje, ale jeśli znasz string s hashes to h, wtedy powinno być bardzo trudno ("obliczeniowo niewykonalne") skonstruować inny łańcuch, który również hashuje do h.

Strzelanie do prostej analogii zamiast skomplikowanego wyjaśnienia.

Na początek, Podzielmy temat na dwie części, operacje jednokierunkowe i haszowanie. Co to jest operacja jednokierunkowa i dlaczego chcesz ją mieć?

Operacje są tak nazywane, ponieważ nie są odwracalne. Większość typowych operacji, takich jak dodawanie i mnożenie, może być odwrócona, podczas gdy dzielenie modulo nie może być odwrócone. Dlaczego to takie ważne? Ponieważ chcesz podać wartość wyjściową które 1) jest trudne do powielenia bez oryginalnych wejść i 2) nie zapewnia sposobu, aby dowiedzieć się wejścia z wyjścia.

Odwracalne

Dodanie :

4 + 3 = 7  

Można to odwrócić, pobierając sumę i odejmując jeden z dodatków

7 - 3 = 4  

Mnożenie :

4 * 5 = 20  

Można to odwrócić, biorąc produkt i dzieląc przez jeden z czynników

20 / 4 = 5

Nieodwracalne

Modulo Rejon :

22 % 7 = 1  

Nie można tego odwrócić, ponieważ nie ma operacji, którą można wykonać dla ilorazu i dywidendy, aby odtworzyć dzielnik (lub odwrotnie).

Można znaleźć operację, aby wypełnić gdzie'? jest?

1  ?  7 = 22  
1  ?  22 = 7

Z tym, że jest powiedziane, jednokierunkowe funkcje skrótu mają taką samą jakość matematyczną jak dzielenie modulo.

Dlaczego to jest ważne?

Powiedzmy, że dałem ci klucz do szafki w terminalu autobusowym, który ma jeden tysiąc szafek i poprosił, żebyś dostarczył je mojemu bankierowi. Będąc mądrym facetem, nie wspominając o podejrzanym, natychmiast spojrzysz na klucz, aby zobaczyć, jaki numer szafki jest napisany na kluczu. Wiedząc o tym, zrobiłem kilka przebiegłych rzeczy; najpierw znalazłem dwie liczby, które po podzieleniu za pomocą dzielenia modulo dają mi liczbę w zakresie od 1 do 1000, po drugie skasowałem oryginalny numer i napisałem na nim dzielnik z pary liczb, po drugie wybrałem terminal autobusowy, który ma strażnik chroni szafki przed przestępcami, pozwalając ludziom tylko próbować jedną szafkę dziennie z kluczem, po trzecie bankier zna już dywidendę, więc kiedy dostanie klucz, może zrobić matematykę i dowiedzieć się resztę i wiedzieć, którą szafkę otworzyć.

Jeśli wybieram operandy mądrze, mogę zbliżyć się do relacji jeden do jednego między ilorazem a dywidendą, która zmusza cię do wypróbowania każdej szafki, ponieważ odpowiedź rozprzestrzenia wyniki możliwych wejść w zakresie żądane numery, szafki dostępne w terminalu. Zasadniczo oznacza to, że nie możesz zdobyć żadnej wiedzy o pozostałej części, nawet jeśli znasz jeden z operandów.

Zobacz inne odpowiedzi na więcej szczegółów na temat różnych funkcji skrótu.

Oto bardzo prosty przykład. Załóżmy, że jestem początkującym kryptografem i tworzę funkcję haszującą, która wykonuje następujące czynności:

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

a teraz test. SimpleHash(specialFile) jest 0. jaki był mój oryginalny plik?

Oczywiście, nie ma sposobu, aby wiedzieć (chociaż prawdopodobnie można łatwo odkryć, że mój hash opiera się na długości pliku). Nie ma sposobu, aby "odtworzyć" mój plik w oparciu o hash, ponieważ hash nie zawiera wszystkiego, co zrobił mój plik.

Hash jest (bardzo) stratnym kodowaniem.

Aby dać ci prostszy przykład, wyobraź sobie fikcyjne 2-literowe kodowanie 5-literowego słowa zwanego kodowaniem X. Algorytm kodowania X jest prosty: weź pierwszą i ostatnią literę słowa.

Więc,

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

Oczywiście nie można zrekonstruować sosu z jego kodowania SE (zakładając, że zakres możliwych wejść to wszystkie 5-literowe słowa). Słowo to równie łatwo może być przestrzenią.

W prostych słowach, funkcja hash działa poprzez splątanie danych wejściowych.

Patrz MD5 na przykład. Przetwarza dane wejściowe za pomocą 512-bitowych bloków. Każdy blok jest podzielony na 16 32-bitowych słów. Istnieją 64 kroki, każdy krok za pomocą jednego z 16 słów wejściowych. Tak więc każde słowo jest używane cztery razy w ciągu algorytmu. Stąd bierze się jednokierunkowość: każdy bit wejściowy jest wprowadzany w kilku miejscach, a między dwoma takimi wejściami funkcja miesza cały prąd dane razem tak, że każdy bit wejściowy wpływa na większość 128-bitowego stanu pracy. Zapobiega to odwróceniu funkcji lub obliczeniu kolizji, patrząc tylko na Część danych. Trzeba spojrzeć na całe 128 bitów, a przestrzeń 128-bitowych bloków jest zbyt szeroka, aby można ją było sprawnie przechodzić.

Teraz MD5 nie robi na nim dobrej roboty, ponieważ można znaleźć kolizje dla tej funkcji. Z punktu widzenia kryptografa MD5 jest funkcją szyfrowania obrotowego. Przetwarzanie jeden blok wiadomości M (512 bitów) używa stanu wejściowego V (128-bitowa wartość) i oblicza nowy stan V' as V' = V + E (M, V), gdzie " + "jest słownym dodatkiem, A" E "jest symetryczną funkcją szyfrowania (aka "szyfr blokowy"), która używa m jako klucza i V jako Wiadomości do zaszyfrowania. Z bliższego spojrzenia wynika, że e can jest rodzajem "rozszerzonej sieci Feistela", podobnej do szyfru blokowego DES, z czterema ćwiartkami zamiast dwóch połówek. Szczegóły nie są tu ważne; chodzi mi o to, że to, co sprawia, że "dobra" funkcja hashowa, wśród funkcji hashowych, które używają tej struktury (zwanej" Merkle-Damgård"), jest podobna do tego, co sprawia, że szyfr blokowy jest "bezpieczny". Udane ataki kolizyjne na MD5 wykorzystują kryptoanalizę różnicową, narzędzie, które zostało zaprojektowane do atakowania szyfrów blokowych w pierwszej kolejności.

Od dobrego szyfru blokowego do dobrej funkcji hashowej, jest krok, którego nie można odrzucić. Dzięki strukturze Merkle-Damgård funkcja hash jest Bezpieczna, jeśli podstawowy szyfr blokowy jest odporna na "powiązane ataki kluczowe", dość niejasna właściwość, wobec której szyfry blokowe są rzadko wzmacniane, ponieważ w przypadku szyfrowania symetrycznego powiązane ataki kluczowe nie mają praktycznie żadnego wpływu. Na przykład, szyfrowanie AES okazało się nie być tak odporne na powiązane ataki kluczowe, jak można było sobie życzyć, a to nie wywołało ogólnej paniki. Opór ten nie był częścią właściwości, których poszukiwano podczas projektowania AES. Zapobiega tylko zamianie AES w hash funkcja. Istnieje funkcja hash o nazwie Whirlpool, która opiera się na pochodnej Rijndaela, "Rijndael" jest początkową nazwą tego, co stało się AES; ale Whirlpool dba o modyfikację części Rijndaela, które są słabe do powiązanych kluczowych ataków.

Istnieją również inne struktury, które można wykorzystać do budowy funkcji skrótu. Obecne standardowe funkcje (MD5, SHA-1 i rodzina" SHA-2", aka SHA-224, SHA-256, SHA-384 i SHA-512) to funkcje Merkle-Damgård, ale wiele z nich niedoszli następcy nie są. Trwa konkurs, organizowany przez NIST (amerykańską federal organization, która zajmuje się tego typu sprawami), aby wybrać nową standardową funkcję skrótu, nazwaną "SHA-3". Zobacz ta strona Po szczegóły. W tej chwili są do 14 kandydatów z początkowego 51 (nie licząc kilkunastu dodatkowych, które nie przeszły testu administracyjnego, polegającego na wysłaniu kompletnego zgłoszenia z kodem, który kompiluje i działa poprawnie).

Let ' s now have a more conceptual spójrz. Bezpieczna funkcja hash powinna wyglądać jak random oracle: oracle jest czarną skrzynką, która po podaniu wiadomości M jako wejście, wysyła odpowiedź h(M), która jest wybierana losowo, jednolicie, w przestrzeni wyjściowej (tj. wszystkie n-ciągi bitowe, jeśli długość wyjściowa funkcji hash wynosi n). Jeśli jako wejście podano tę samą wiadomość M, oracle wyświetli tę samą wartość niż poprzednio. Oprócz tego ograniczenia, wyjście wyroczni na nieużywane wcześniej wejście M jest nieprzewidywalne. Można sobie wyobrazić wyrocznię jako kontener dla gnoma, który rzuca kośćmi i starannie zapisuje wiadomości wejściowe i odpowiadające im wyniki w dużej książce, aby uszanować swój kontrakt wyroczni. Nie da się przewidzieć, jakie będzie następne wyjście, ponieważ sam gnome o tym nie wie.

Jeśli istnieje losowa oracle, to odwrócenie funkcji hash ma koszt 2^N: aby mieć dane wyjście, nie ma lepsza strategia niż używanie odrębnych komunikatów wejściowych, dopóki nie uzyska się wartości oczekiwanej. Ze względu na jednorodny dobór losowy prawdopodobieństwo sukcesu wynosi 1/(2^N) przy każdej próbie, a średnia liczba zapytań do gnome rzucającego kośćmi wyniesie 2^N. W przypadku kolizji (znalezienie dwóch różnych wejść dających tę samą wartość skrótu) koszt wynosi około *1.4 * 2^(n/2)* (z grubsza rzecz biorąc, z wyjściami *1.4*2^(n/2)*, możemy zebrać około 2^N pary wyjść, z których każda ma prawdopodobieństwo 1/(2^n) dopasowania, tzn. posiadanie dwóch różnych wejść, które mają to samo wyjście). To najlepsze, co można zrobić z losową wyrocznią.

Dlatego szukamy funkcji hashowych, które są tak dobre jak losowa oracle: muszą mieszać dane wejściowe w taki sposób, że nie możemy znaleźć kolizji bardziej efektywnie niż kosztowałoby wywołanie funkcji 2^(n/2) razy. Zmorą funkcji hash jest struktura matematyczna, czyli skróty które pozwalają atakującemu zobaczyć stan wewnętrzny funkcji hash (który jest duży, co najmniej N bitów) jako wariację na temat obiektu matematycznego, który żyje w znacznie krótszej przestrzeni. 30 lat publicznych badań nad symetrycznymi systemami szyfrowania zaowocowało całą gamą pojęć i narzędzi (dyfuzja, lawina, różnice, liniowość...), które można zastosować. Najważniejsze jest jednak to, że nie mamy dowodów na to, że losowa wyrocznia może rzeczywiście istnieć. We want {[16] } a hash funkcja, której nie można zaatakować. To, co mamy , to kandydaci do funkcji hash, dla których obecnie nie jest znany żaden atak , a nieco lepiej, mamy pewne funkcje, dla których {15]} niektóre rodzaje ataków mogą być udowodnione, że nie działają.

Jest jeszcze kilka badań do zrobienia.

Array
Przy niektórych mrużeniu oka tablice asocjacyjne wyglądają bardzo podobnie do hashów. Główną różnicą był brak symbolu % na nazwach skrótów, który można było przypisać tylko jednemu kluczowi na raz. Można więc powiedzieć $foo{'key'} = 1;, ale tylko @keys = keys(foo);. Znane funkcje, takie jak each, klucze i wartości, działały tak, jak teraz (a delete zostało dodane w Perlu 2).

Perl 3 miał trzy pełne typy danych: miał symbol % na nazwach skrótów, pozwalał na przypisanie całego skrótu jednocześnie i dodawał dbmopen (obecnie wycofany na rzecz tie). Perl 4 używał oddzielonych przecinkami kluczy hashowych do emulowania wielowymiarowych tablic (które są teraz lepiej obsługiwane przez odniesienia do tablic).

Perl 5 zrobił ogromny skok, odwołując się do tablic asocjacyjnych jako hashów. (O ile mi wiadomo, jest to pierwszy język, który odwołał się do struktury danych, a nie do "tabeli hashowej" lub czegoś podobnego.) Nieco ironicznie, przeniósł również odpowiedni kod z hasha.c w hv.c.

Nomenklatura
Słowniki, jak wyjaśniono wcześniej, są nieuporządkowanymi zbiorami wartości indeksowanymi przez unikalne klucze. Czasami nazywane są tablicami asocjacyjnymi lub mapami. Można je zaimplementować na kilka sposobów, z których jednym jest użycie struktury danych znanej jako tablica skrótów (i to jest to, co Perl określa jako hash).

Użycie przez Perla terminu "hash" jest źródłem pewnego potencjalnego zamieszania, ponieważ wyjście funkcji hashującej jest również czasami nazywane skrótem (szczególnie w kontekstach kryptograficznych), a także dlatego, że tabele hashowe nie są zwykle nazywane hashami nigdzie indziej.

Aby zachować bezpieczeństwo, odwołaj się do struktury danych jako tabeli skrótów i używaj terminu "hash" tylko w oczywistych, specyficznych dla Perla kontekstach.