Dlaczego nie można zagwarantować, że std :: hash jest deterministyczny?

28

Odtąd używamy N4140 (C ++ 14 Standard).

Zgodnie z § 17.6.3.4 Wymagania mieszania ,

Zwrócona wartość zależy tylko od argumentu k dotyczącego czasu trwania programu .

[Uwaga: Tak więc wszystkie oceny wyrażenia h(k)o tej samej wartości kdają ten sam wynik dla danego wykonania programu . - uwaga końcowa]

i § 20.9.12 Skrót szablonu klasy mówi

...

instancja hash<Key>:

(1.1) - spełniają wymagania Hash (17.6.3.4) ...

(1.2) - ...

Oznacza to, że wartość skrótu value(tj. hash<decltype(value)>(value)) Może przyjąć inną wartość po ponownym uruchomieniu programu.

Ale dlaczego? Ograniczenie to nie było w standardzie C ++ 11, ale w standardzie C ++ 14, C ++ 17 i C ++ 20. Jako użytkownik (nie programista STL) byłby bardzo użyteczny, gdyby std::hashbył deterministyczny. Czy są jakieś matematyczne trudności we wdrażaniu deterministycznej funkcji skrótu? Ale funkcje skrótu, których używamy na co dzień (np. Przestarzałe md5sumlub bezpieczniejsze sha256), są deterministyczne. Czy jest problem z wydajnością?

c++ hash language-lawyer std Ynn
źródło
7
„... Funkcje skrótu są wymagane tylko do uzyskania tego samego wyniku dla tych samych danych wejściowych w ramach pojedynczego wykonania programu; pozwala to na solenie skrótów, które zapobiegają atakom typu„ odmowa usługi ”. źródło: en.cppreference.com/w/cpp/utility/hash
Richard Critten
5
Umożliwia algorytmowi deterministycznemu przyjmowanie danych niedeterministycznych. Na przykład wartości wskaźnika. Niezmienna struktura danych może mieszać adresy wewnętrznych danych, co może być znacznie szybsze niż mieszanie zawartości.
John Kugelman
4
Ta odpowiedź zawiera kilka ciekawych linków do tego, dlaczego nie chcesz determinizmu.
NathanOliver
3
Nie zagrażaj temu jako ograniczeniu, ale zmniejszając standardowe ograniczenia.
Marek R
4
Oto pełne wyjaśnienie, dlaczego rozwiązano ograniczenia.
Marek R

Odpowiedzi:

17

Nie ma potrzeby, aby funkcja skrótu była deterministyczna między uruchomieniami, ale nadal możesz podać swój własny skrót, np. Dla nieuporządkowanych kontenerów, jeśli jest to zachowanie, na którym się opierasz.

Co do tego, dlaczego cppreference mówi:

Funkcje skrótu są wymagane tylko w celu uzyskania tego samego wyniku dla tych samych danych wejściowych w ramach pojedynczego wykonania programu; pozwala to na solenie skrótów, które zapobiegają atakom typu „odmowa usługi” w przypadku kolizji.

Jeśli Hashwymagania mówią, że jest deterministyczne, to nie byłbyś w stanie zapewnić solonego skrótu bez złamania wymagania.

Oto rzeczywiste wyjaśnienie, dlaczego

Geoffroy
źródło
7

Ta odpowiedź (i zawarte w niej linki) sugerowana przez @NathanOliver jest ostatecznie pomocna. Przytoczę ważne części.

W przypadku nieszyfrowej funkcji skrótu można wstępnie obliczyć masywne dane wejściowe o tej samej wartości skrótu, aby algorytmicznie spowolnić nieuporządkowane kontenery i doprowadzić do ataku typu „odmowa usługi”.

(z wydania 2291. std :: hash jest podatny na kolizję z atakiem DoS )

Z tego powodu projektanci języków migrują do losowego mieszania. W haszowaniu losowym wartość skrótu ciągu „a” może się zmieniać przy każdym uruchomieniu programu. Losowe hashowanie jest teraz domyślnym ustawieniem w Pythonie (od wersji 3.3), Ruby (od wersji 1.9) i Perlu (od wersji 5.18).

(od Czy zdajesz sobie sprawę, że używasz losowego mieszania? )

Przejdź do opcji Gotowe, a nie Natychmiastowe, ponieważ nawet pozwolenie było sporne w dyskusji na temat odbłyśników

(z wydania 2291. std :: hash jest podatny na kolizję z atakiem DoS )

W praktyce, o ile rozumiem, brak std::hashimplementacji losowego mieszania, ale możesz napisać własne my::secure_hash.

(z tej odpowiedzi )

PS

Właśnie przejrzałem „tablicę skrótów” i znalazłem stronę informacyjną: Moment, w którym zdasz sobie sprawę, że każdy serwer na świecie jest podatny na atak .

Ynn
źródło