Почему std :: ha sh не гарантированно детерминировано c? - PullRequest
Новая
       29

Почему std :: ha sh не гарантированно детерминировано c?

28 голосов
/ 06 марта 2020

Здесь и далее мы используем N4140 (стандарт C ++ 14).

Согласно § 17.6.3.4 Ha sh требованиям ,

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

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

и § 20.9.12 Шаблон класса ha sh говорит

...

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

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

(1.2) - ...

Это означает, что значение ha sh, равное value (т.е. hash<decltype(value)>(value)), может принять другое значение при перезапуске программы.

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

Ответы [ 2 ]

17 голосов
/ 06 марта 2020

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

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

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

Если требования Hash указывают на то, что он определен c, то вы не сможете предоставить соленую га sh без нарушения требования.

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

7 голосов
/ 06 марта 2020

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

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

(из выпуск 2291. std :: ha sh уязвим для атаки DoS при столкновении )

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

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

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

(из Выпуск 2291. std :: ha sh уязвим для столкновения DoS-атаки )

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

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

PS

Я только что гуглил "ha sh table dos" и нашел информативную страницу: Момент, когда вы понимаете, что каждый сервер в мире уязвим .

...