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

Одна и та же пара 32-байтовых сообщений даёт 9, 12, 11 и 11 коллизий на каждые 2^30 ключей в wyhash, rapidhash v1, rapidhash v3 и XXH3-64. Такие пары искал Claude Fable по широкой выборке популярных хешей из SMhasher, и разбор в блоге Thomasahle показывает, что у большинства функций слабые входы находятся.

Коротко

• У большинства проверенных функций из SMhasher нашлись входы, на которых гарантия проседает минимум на 20 бит ниже ожидаемой, а часть пар сталкивается при любом секретном ключе.
• Собственный хеш авторов ChainHash выдаёт 28,31 байта за такт на сообщениях 256 КиБ на Intel Xeon и 26,26 на Apple M2 Pro при машинно проверенной гарантии 63,0 бита из 64 случайных байтов ключа.
• Автор предупреждает, что приложение с поштучным разбором содержит «AI slop», ручается только за конкретно найденные и измеренные примеры, а часть найденных пробелов потребовала правок кода.

Если вы не следили: качество быстрых хешей проверяли и раньше. По данным репозитория SMhasher на GitHub, набор меряет и скорость, и качество и прямо помечает проблемы, например у crc32 стоит «insecure, 8590x collisions, distrib». Список подозрительных функций существовал и до этого разбора, не хватало конкретных входов, на которых они ломаются, найденных и измеренных.

Большинство хешей из подборки проседают минимум на 20 бит

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

У выбранной для XXH3-64 пары измеренная частота другая: примерно 527 событий на 2^36 ключей, оценка по выборке, 527 событий пулом. Кроме пар, для многих функций нашлись и массовые коллизии уровня флудинга, подобранные без знания ключа.

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

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

ChainHash выдаёт 28,31 байта за такт на Intel Xeon

ChainHash, 64-битная функция авторов разбора, построена на их работе с Якобом Тейсом о быстром вычислении многочленов. Одна и та же реализация даёт 28,31 байта за такт на Xeon и 26,26 на Apple M2 Pro при машинно проверенной гарантии 63,0 бита из 64 равномерно случайных байтов ключа. По пропускной способности она первая среди всех проверенных хешей на Xeon и вторая на M2 Pro.

Есть и 128-битный вариант. ChainHash-128 идёт 14,43 байта за такт на Xeon и 10,26 на M2 при машинно проверенной гарантии 127 бит из 128 случайных байтов ключа, и на обоих хостах мерили одну и ту же функцию.

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

Обе заявленные границы UMASH доказаны, а 24-байтовый HalftimeHash опровергнут

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

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

SipHash-1-3 и SipHash-2-4 остались неподтверждёнными заявками на 64 битах выхода: аудит не дал ни доказательства, ни контрпримера. Цитируемый анализ 2014 года (Dobraunig, Mendel, Schläffer) даёт 2^-167 для SipHash-1-x и 2^-236,3 для SipHash-2-4, а собственный поиск авторов не увидел ничего выше 2^-26,4 на пару.

Как хеш вообще может что-то гарантировать?

Хеш сжимает данные любой длины в значение фиксированного размера, и вся польза в том, что разные входы почти никогда не дают одно значение. Хеш-таблица работает как гардероб с ящиками: при коллизии в один ящик сваливается всё подряд, и поиск деградирует. Функцию называют b-битно универсальной, если входы длины L сталкиваются с вероятностью не выше L · 2^-b; зависимость от L иногда хуже, но доказуемо никогда не лучше.

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

Скорость обычно покупают за качество: xxHash заявляет 60 ГБ/с, а komihash, a5hash, HighwayHash, SpookyHash, aHash и t1ha2 сознательно жертвуют стойкостью против враждебных входов ради темпа. Раньше такой размен был оправдан: многие сценарии низкорисковые, и дорогой криптоанализ ради коллизий не окупался.

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

Куда двинутся быстрые доказуемые хеши

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