Зачем HashMap нужна криптографически безопасная функция хеширования?

Question

Я читаю книгу Rust о HashMap хеш-функциях , и я не могу понять эти два предложения.

По умолчанию HashMap использует криптографически безопасную функцию хеширования, которая может обеспечить устойчивость к атакам типа «отказ в обслуживании» (DoS). Это не самый быстрый из доступных алгоритмов хэширования, но компромисс между улучшением безопасности и снижением производительности того стоит.

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

• детерминированный (тот же объект имеет то же хеш-значение)
• будь ОЧЕНЬ быстрым,
• имеет равномерное распределение битов в хэш-значении (что означает уменьшение коллизии)

Другие свойства в криптографически защищенной хэш-функции на самом деле не имеют значения в 99% (возможно, даже в 99,99%) времени для хеш-таблиц.

Итак, мой вопрос: Что означает «устойчивость к DoS-атакам и лучшая безопасность» "даже означает в контексте HashMap?

Answer 1

Давайте начнем задом наперед: как вы делаете хэш-карту?

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

Затем вы просто внедряете этот набор в сайт, и для каждого (простого) запроса он выполняет непропорционально большой объем работы, поскольку для вставки N элементов требуется O (N ² ) операций.

---

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

Answer 2

Допустим, мы используем HashMap для хранения некоторых пользовательских данных в веб-приложении. Предположим, что пользователи могут каким-либо образом выбрать (часть) ключа - возможно, ключ - это имя пользователя или имя файла загруженного файла или что-то в этом роде.

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

Но когда происходит неестественно много столкновений, реализация хэш-карты может делать странные вещи. Например, поиск некоторых ключей может иметь время выполнения O (n) . Или хэш-карта может подумать, что она должна расти из-за всех столкновений; но увеличение не решит проблему, поэтому хэш-карта увеличивается до тех пор, пока не будет использована вся память . В любом случае это плохо. Хеш-карты просто предполагают, что статистически столкновения происходят редко.

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

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

---

не имеет значения в 99% (может быть, даже в 99,99%) времени для хеш-таблиц.

Да, , вероятно, . Но это трудно сбалансировать. Я предполагаю, что мы все согласимся с тем, что, если 20% пользователей будут иметь проблемы с безопасностью в своем приложении из-за небезопасной хэш-функции (в то время как 80% не заботятся), все равно будет хорошей идеей использовать подход «по умолчанию безопасный». Как насчет 5% / 95%? Как насчет 1% / 99%? Трудно сказать, где находится порог, верно?

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

Answer 3

Если серверное приложение хранит пользовательский ввод (например, данные публикации в веб-приложении) в хеш-таблице, злонамеренный пользователь может попытаться предоставить большое количество входных данных, которые имеют одинаковое хеш-значение, что приводит к большому числу хеш-коллизий и, таким образом, значительно замедляет операции на карте до такой степени, что ее можно использовать в качестве DoS-атаки (как описано, например, в этой статье ).

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