Почему std :: hash не гарантированно является детерминированным?

28

Далее мы используем N4140 (C ++ 14 Standard).

В соответствии с § 17.6.3.4 Хеш-требованиями ,

Возвращаемое значение должно зависеть только от аргумента k для продолжительности программы .

[Примечание: Таким образом, все вычисления выражения h(k)с одинаковым значением kдают один и тот же результат для данного выполнения программы . - конец примечания]

и § 20.9.12 хэш шаблона класса говорит

...

экземпляр hash<Key>должен:

(1.1) - удовлетворить требования хеширования (17.6.3.4) ...

(1.2) - ...

Это означает, что хеш-значение value(то есть hash<decltype(value)>(value)) может принимать другое значение, если вы перезапустите программу.

Но почему? Это ограничение было не в Стандарте C ++ 11, а в Стандарте C ++ 14, C ++ 17 и C ++ 20. Как пользователь (не разработчик STL), было бы весьма полезно, если бы он std::hashбыл детерминированным. Есть ли математические трудности в реализации детерминированной хэш-функции? Но хэш-функции, которые мы ежедневно используем (например, устаревшие md5sumили более безопасные sha256), являются детерминированными. Есть ли проблема эффективности?

c++ hash language-lawyer std YNN
источник
7
«... Хеш-функции требуются только для получения одного и того же результата для одного и того же ввода в рамках одного выполнения программы; это позволяет использовать соленые хэши, которые предотвращают атаки типа« отказ в обслуживании »». источник: en.cppreference.com/w/cpp/utility/hash
Ричард Криттен
5
Это позволяет детерминированному алгоритму принимать недетерминированные входные данные. Значения указателя, например. Неизменная структура данных может хешировать адреса своих внутренних данных, что может быть намного быстрее, чем хеширование содержимого.
Джон Кугельман
4
Этот ответ имеет несколько хороших ссылок, объясняющих, почему вы не хотите детерминизма.
Натан Оливер
3
Не угрожайте этому как ограничению, но сделайте стандартные ограничения немного менее строгими.
Марек Р
4
Вот полное объяснение, почему ограничения были ослаблены.
Марек Р

Ответы:

17

Нет необходимости, чтобы хэш-функция была детерминированной между запусками, но вы все равно можете предоставить свой собственный хэш, например, для неупорядоченных контейнеров, если вы полагаетесь на такое поведение.

Что касается того, почему cppreference говорит:

Хеш-функции требуются только для получения одинакового результата для одного и того же ввода в рамках одного выполнения программы; это позволяет использовать соленые хэши, которые предотвращают атаки типа «отказ в обслуживании».

Если Hashтребования говорят о том, что он является детерминированным, вы не сможете предоставить соленый хеш, не нарушая требования.

Вот фактическое объяснение, почему

Жоффруа
источник
7

Этот ответ (и ссылки в нем), предложенные @NathanOliver, в конечном итоге полезны. Позвольте мне привести важные части.

Для не криптографической хеш-функции возможно предварительно рассчитать массивные входные данные с тем же хеш-значением, чтобы алгоритмически замедлить неупорядоченные контейнеры и привести к атаке типа «отказ в обслуживании».

(из выпуска 2291. std :: hash уязвим для коллизионной атаки DoS )

По этой причине разработчики языка переходят на случайное хеширование. При случайном хешировании значение хеш-функции строки «a» может меняться при каждом запуске вашей программы. Случайное хеширование теперь используется по умолчанию в Python (с версии 3.3), Ruby (с версии 1.9) и Perl (с версии 5.18).

( Вы понимаете, что используете случайное хеширование? )

Переместитесь на Готов, а не Немедленно, поскольку даже разрешение было спорным в обсуждении рефлектора

(из выпуска 2291. std :: hash уязвим для коллизионной атаки DoS )

На практике, насколько я понимаю, ни одна реализация не std::hashреализует случайное хэширование, но вы можете написать свой собственный my::secure_hash.

(из этого ответа )

PS

Я просто погуглил «хэш-таблицу dos» и нашел информативную страницу: момент, когда вы понимаете, что каждый сервер в мире уязвим .

YNN
источник