Как быстрые хеш-функции ломаются на специально подобранных данных

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

Автор с помощью Claude Fable разобрал популярные функции из набора тестов SMHasher. У большинства нашлись входы с устойчивостью к коллизиям минимум на 20 бит хуже ожидаемой. Для CityHash64, FarmHash64 и MurmurHash3 удалось построить сколько угодно входов, которые сталкиваются при любом секретном ключе.

Интерактивное сравнение скорости и гарантий отделяет доказанные оценки от найденных контрпримеров. Практический вывод: если сервис принимает чужие данные, одной пропускной способности хеша недостаточно. Нужны доказанные гарантии, а ещё лучше проверенные в Lean.