Claude Fable нашёл коллизии в большинстве быстрых хешей

Автор блога Thomasahle 20 сентября опубликовал разбор: с помощью Claude Fable он проверил широкую выборку популярных хеш-функций из SMhasher и у большинства нашёл входы, на которых гарантия от коллизий проседает минимум на 20 бит ниже ожидаемого. Часть найденных пар сталкивается при любом секретном ключе.

К посту приложены интерактивная диаграмма «скорость против гарантий» и подробное приложение по каждой функции, от CityHash64, MurmurHash3 и XXH3 до Go maphash, Abseil Hash, .NET Marvin и foldhash. Там же автор показывает собственный хеш ChainHash. Его гарантия проверена машиной, а по скорости он не уступает эвристическим хешам.

Что значит «на 20 бит хуже»

Хеш для таблиц берёт секретный ключ (сид), и два разных входа должны совпадать на выходе лишь с крошечной вероятностью, которая зависит от случайного выбора этого ключа. Только так элементы не сваливаются в одну корзину. Автор формализует требование так: хеш b-битно универсален, если два входа длины L сталкиваются с вероятностью не выше L·2^-b при любом L. Число b и есть оценка в битах на диаграмме. Для 64-битной функции идеал около 64, и каждый потерянный бит вдвое повышает шанс коллизии.

Такую границу доказывают немногие хеши. Остальные полагаются на эвристику и статистические тесты. SMhasher, откуда взят список, проверяет распределение, коллизии и скорость некриптографических хешей, а колонка «Quality problems» в его таблице фиксирует статистику, не стойкость к атакующему. Автор прямо называет komihash, a5hash, HighwayHash, SpookyHash, aHash и t1ha2 хешами, которые готовы пожертвовать качеством на враждебных входах ради скорости. Раньше так можно было жить: большинство применений хешей несут мало риска, и дорогой криптоанализ ради входов, которые сталкиваются чаще среднего, атакующему не окупался.

Скорость у таких функций действительно высокая: xxHash заявляет 60 ГБ/с, практически скорость чтения памяти.

Пары, которым не нужен ключ

Все входы в разборе подобраны без знания секретного ключа. Найденные слабости автор делит на четыре категории и к каждой приписывает, где она бьёт сильнее всего:

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

Среди примеров в посте есть историческая 32-байтная «пара A». На каждые 2^30 ключей она дала 9 коллизий в wyhash, 12 в rapidhash v1 и по 11 в rapidhash v3 и XXH3-64. Для XXH3-64 на диаграмме взята другая пара: по выборочному замеру она сталкивается примерно в 527 случаях на каждые 2^36 ключей.

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

Анализ по каждой функции писал Claude Fable. Автор предупреждает, что приложение содержит «AI slop», что он не может гарантировать правильность всего и доверяет только конкретным найденным и измеренным примерам. Протокол замеров и инструкции по воспроизведению выложены отдельно. Главный вывод автор формулирует так: «ИИ меняет модель угроз: софт, который был защищён в основном непрозрачностью, теперь легко ломается».

Ошибки нашлись и в доказательствах

У нескольких хешей есть опубликованные доказательства. В части из них Fable нашёл ошибки, другие проверил в Lean, системе, где корректность доказательства проверяет машина. Часть пробелов удалось закрыть исправлением рассуждения, для других пришлось менять код.

У UMASH доказаны обе заявленные границы, причём разными путями: через реализованный аккумулятор по модулю 8p и через два независимых множителя в C-версии отпечатка. На диаграмме это 56,18 и 83,99 бита (около 84 при L ≤ 246 слов) для идеальных полных ключей, фиксированного сида и полного вывода C-реализации. Вывод ключей, сиды на каждый вызов и маскированный вывод в теоремы не входят, а шаг проекции 162/q из статьи остаётся непроверенным.

У HalftimeHash исправленное доказательство даёт четырём 64-битным вариантам границу в 63 бита при оговорённых условиях исполнения и ограничениях на длину. Исходную продвинутую 24-байтную функцию опровергли, исправленная версия стоит на диаграмме отдельно.

SipHash-1-3 и SipHash-2-4 остались неразрешёнными: аудит не дал для них ни доказательства, ни контрпримера. Анализ Добрауниг, Менделя и Шлеффера 2014 года указывает характеристики коллизий 2^-167 для SipHash-1-x и 2^-236,3 для SipHash-2-4. Собственный поиск автора не нашёл ни одной пары с вероятностью выше 2^-26,4.

Вывод автора о доказательствах: обычные хороши, проверенные в Lean лучше, потому что не всё опубликованное проверено одинаково тщательно.

ChainHash и цена гарантий

ChainHash вырос из работы автора с Якобом Тейсом (Jakob Tejs) о быстром вычислении многочленов. На обеих платформах это одна и та же 64-битная функция: 28,31 байта за такт на Intel Xeon и 26,26 на Apple M2, с машинно проверенной гарантией 63,0 бита при 64 равномерно случайных байтах ключа. По пропускной способности это первое место среди всех проверенных хешей на Xeon и второе на M2 Pro, так что за доказанную гарантию здесь не пришлось платить скоростью. 128-битный ChainHash-128 выдаёт 14,43 байта за такт на Xeon и 10,26 на M2 с гарантией в 127 бит при 128 случайных байтах ключа.

Скорость мерили на сообщениях по 256 КиБ независимо от длины сталкивающейся пары. Таймеры M2 и Xeon считают такты по-разному, так что сравнивать хеши стоит только в пределах одной машины. Отдельно замерены короткие входы длиной 1-31 байт, а GHASH измеряли через интерфейс GMAC в OpenSSL вместе с затратами на настройку.

Автор надеется, что в ответ на находки никто не станет рефлекторно переводить всё на «криптографически стойкие» SHA или аппаратные инструкции AES. По его словам, доказуемо надёжных хешей много, и они быстрые, поэтому совет простой: «если можете получить доказуемо корректный софт, берите его».

Что ответили мейнтейнеры

Все находки отправили мейнтейнерам до публикации, их ответы лежат в обсуждениях xxHash, komihash, MuseAir и foldhash. По словам автора, мейнтейнеры сошлись в том, что исправлять стоит только настоящие атаки мультиколлизиями, когда большой набор входов сталкивается с высокой вероятностью. Автор называет эту позицию справедливой, тем более что поменять хеш с сохранением обратной совместимости трудно. При этом найденные пары, по его словам, доказывают, что эвристические хеши нельзя считать универсальными функциями, которые просто пока не доказаны.

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