Co to jest dobra funkcja skrótu?

Question 1

Co to jest dobra funkcja skrótu? Widziałem wiele funkcji skrótu i aplikacji na moich kursach dotyczących struktur danych na studiach, ale głównie dostałem, że dość trudno jest zrobić dobrą funkcję mieszającą. Z zasady, aby uniknąć kolizji, mój profesor powiedział, że:

function Hash(key)
  return key mod PrimeNumber
end

(mod jest operatorem% w C i podobnych językach)

gdzie liczba pierwsza jest rozmiarem tablicy skrótów. Rozumiem, że jest to dość dobra funkcja unikania kolizji i szybka, ale jak mogę zrobić lepszą? Czy są lepsze funkcje skrótu dla kluczy łańcuchowych i klawiszy numerycznych?

Question 2

Do "normalnego" przeszukiwania tabeli skrótów dla praktycznie każdego rodzaju danych - ten autorstwa Paula Hsieha jest najlepszy, jakiego kiedykolwiek używałem.

http://www.azillionmonkeys.com/qed/hash.html

Jeśli zależy Ci na bezpieczeństwie kryptograficznym lub czymkolwiek innym bardziej zaawansowanym, to YMMV. Jeśli potrzebujesz tylko funkcji skrótu ogólnego przeznaczenia do wyszukiwania tabeli skrótów, to jest to, czego szukasz.

Question 3

Nie ma czegoś takiego jak „dobra funkcja skrótu” dla uniwersalnych skrótów (red. Tak, wiem, że istnieje coś takiego jak „uniwersalne mieszanie”, ale nie o to mi chodziło). W zależności od kontekstu różne kryteria określają jakość skrótu. Dwie osoby wspomniały już o SHA. To jest kryptograficzny hash i wcale nie jest dobry dla tabel haszujących, co prawdopodobnie masz na myśli.

Tabele skrótów mają bardzo różne wymagania. Jednak znalezienie uniwersalnej dobrej funkcji skrótu jest trudne, ponieważ różne typy danych ujawniają różne informacje, które można zaszyfrować. Z reguły dobrze jest traktować wszystkie informacje, które zawiera dany typ. Nie zawsze jest to łatwe, a nawet możliwe. Ze względów statystycznych (a co za tym idzie kolizji) ważne jest również wygenerowanie dobrego rozrzutu w przestrzeni problemowej, czyli wszystkich możliwych obiektów. Oznacza to, że przy haszowaniu liczb z zakresu od 100 do 1050 nie jest dobrze, aby najbardziej znacząca cyfra odgrywała dużą rolę w haszowaniu, ponieważ dla ~ 90% obiektów ta cyfra będzie równa 0. O wiele ważniejsze jest, aby ostatnie trzy. cyfry określają skrót.

Podobnie, podczas mieszania ciągów ważne jest, aby wziąć pod uwagę wszystkie znaki - z wyjątkiem sytuacji, gdy z góry wiadomo, że pierwsze trzy znaki wszystkich łańcuchów będą takie same; rozważenie ich wtedy jest marnotrawstwem.

Jest to właściwie jeden z przypadków, w których radzę przeczytać, co Knuth ma do powiedzenia w The Art of Computer Programming , vol. 3. Kolejną dobrą lekturą jest The Art of Hashing Julienne Walker .

Question 4

Istnieją dwa główne cele funkcji mieszania:

aby równomiernie rozproszyć punkty danych na n bitów.
aby bezpiecznie zidentyfikować dane wejściowe.

Nie można polecić skrótu, nie wiedząc, do czego go używasz.

Jeśli tylko tworzysz tabelę skrótów w programie, nie musisz się martwić o to, jak odwracalny lub hakowalny jest algorytm ... SHA-1 lub AES są do tego całkowicie niepotrzebne, lepiej byłoby użyć odmianą FNV . FNV osiąga lepszą dyspersję (a tym samym mniej kolizji) niż prosty mod główny, o którym wspomniałeś, i jest bardziej dostosowany do różnych rozmiarów wejściowych.

Jeśli używasz skrótów do ukrywania i uwierzytelniania informacji publicznych (takich jak haszowanie hasła lub dokumentu), powinieneś użyć jednego z głównych algorytmów haszujących zweryfikowanych przez kontrolę publiczną. Hash Function Lounge to dobre miejsce na rozpoczęcie.

Question 5

To jest dobry przykład, a także przykład, dlaczego nigdy nie chciałbyś go napisać. Jest to skrót Fowler / Noll / Vo (FNV), który jest równy geniuszowi informatyki i czystemu voodoo:

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

Edytować:

Landon Curt Noll zaleca na swojej stronie algorytm FVN-1A zamiast oryginalnego algorytmu FVN-1: Ulepszony algorytm lepiej rozprasza ostatni bajt w hashu. Odpowiednio dostosowałem algorytm.

Question 6

Powiedziałbym, że główną zasadą jest nie toczyć własnego. Spróbuj użyć czegoś, co zostało dokładnie przetestowane, np. SHA-1 lub coś podobnego.

Question 7

Dobra funkcja skrótu ma następujące właściwości:

Biorąc pod uwagę skrót wiadomości, atakujący nie może znaleźć innej wiadomości, której skróty są identyczne.
Biorąc pod uwagę parę wiadomości, m 'im', jest obliczeniowo niewykonalne znalezienie dwóch takich, że h (m) = h (m ')

Te dwa przypadki nie są takie same. W pierwszym przypadku istnieje wcześniej istniejący skrót, dla którego próbujesz znaleźć kolizję. W drugim przypadku, starasz się znaleźć jakiekolwiek dwie wiadomości kolidujących. Drugie zadanie jest znacznie łatwiejsze ze względu na urodzinowy „paradoks”.

Tam, gdzie wydajność nie jest tak wielkim problemem, należy zawsze używać bezpiecznej funkcji skrótu. Istnieją bardzo sprytne ataki, które można wykonać, wymuszając kolizje w hashu. Jeśli od samego początku użyjesz czegoś mocnego, zabezpieczasz się przed tym.

Nie używaj MD5 ani SHA-1 w nowych projektach. Większość kryptologów, łącznie ze mną, uznałaby je za zepsute. Głównym źródłem słabości obu tych projektów jest to, że druga właściwość, którą nakreśliłem powyżej, nie dotyczy tych konstrukcji. Jeśli osoba atakująca może wygenerować dwie wiadomości, m i m ', obie mają tę samą wartość, może użyć tych wiadomości przeciwko tobie. SHA-1 i MD5 również cierpią z powodu ataków rozszerzających wiadomości, które mogą fatalnie osłabić twoją aplikację, jeśli nie będziesz ostrożny.

Bardziej nowoczesny haszysz, taki jak Whirpool, to lepszy wybór. Nie cierpi z powodu tych ataków rozszerzających wiadomości i używa tej samej matematyki, której używa AES, aby udowodnić bezpieczeństwo przed różnymi atakami.

Mam nadzieję, że to pomoże!

Question 8

Mówisz tutaj, że chcesz mieć taki, który wykorzystuje odporność na kolizje. Spróbuj użyć SHA-2. Lub spróbuj użyć (dobrego) szyfru blokowego w funkcji jednokierunkowej kompresji (nigdy wcześniej tego nie próbowałem), jak AES w trybie Miyaguchi-Preenel. Problem polega na tym, że musisz:

1) mieć IV. Spróbuj użyć pierwszych 256 bitów ułamkowych części stałej Khinchina lub coś w tym rodzaju. 2) mają schemat wypełnienia. Łatwy. Wyciągnij to z haszyszu, takiego jak MD5 lub SHA-3 (Keccak [wymawiane „ket-chak”]). Jeśli nie dbasz o bezpieczeństwo (kilka innych to powiedziało), spójrz na FNV lub lookup2 autorstwa Boba Jenkinsa (właściwie to ja jestem pierwszym, który poleca lookup2). ).

Question 9

Dobra funkcja skrótu powinna

dążyć do tego, aby w miarę możliwości nie tracić informacji i mieć jak najmniej kolizji
kaskadować tak dużo i tak równomiernie, jak to możliwe, tj. każdy bit wejściowy powinien odwracać każdy bit wyjściowy z prawdopodobieństwem 0,5 i bez oczywistych wzorców.
jeśli jest używany w kontekście kryptograficznym, nie powinien istnieć skuteczny sposób na jego odwrócenie.

Moduł liczb pierwszych nie spełnia żadnego z tych punktów. To jest po prostu niewystarczające. Często jest to lepsze niż nic, ale nawet nie jest szybkie. Mnożenie przez liczbę całkowitą bez znaku i przyjmowanie modułu potęgi dwóch rozkłada wartości równie dobrze, czyli wcale nie jest dobrze, ale przy zaledwie około 2 cyklach procesora jest znacznie szybsze niż 15 do 40, jaki zajmie główny moduł ( tak, dzielenie liczb całkowitych jest naprawdę powolne).

Aby utworzyć funkcję skrótu, która jest szybka i dobrze rozprowadza wartości, najlepszą opcją jest komponowanie jej z szybkich permutacji o niższej jakości, tak jak w przypadku PCG do generowania liczb losowych.

Przydatne permutacje to między innymi:

mnożenie przez nieparzystą liczbę całkowitą
obroty binarne
xorshift

Zgodnie z tym przepisem możemy stworzyć własną funkcję haszującą lub wziąć splitmix, który jest przetestowany i dobrze przyjęty.

Jeśli potrzebne są cechy kryptograficzne, gorąco polecam użycie funkcji rodziny sha, która jest dobrze przetestowana i ustandaryzowana, ale do celów edukacyjnych można to zrobić w następujący sposób:

Najpierw bierzesz dobrą, niekryptograficzną funkcję mieszającą, a następnie stosujesz funkcję jednokierunkową, taką jak potęgowanie na polu głównym lub kwiele aplikacji (n*(n+1)/2) mod 2^kprzeplatanych przesunięciem xorshift, gdy kjest liczba bitów w wynikowym skrócie.