openPGP в России

10.02 // XOR-комбинирование хэш-функций снижает их стойкость

Проблемы со стойкостью хэш-функций часто приводят к перестраховкам, основанным на комбинировании разных алгоритмов. Наиболее простым и надёжным является объединение выходов двух разных хэшей путём простого присоединения: H₁(M) ║ H₂(M). Это оказывается неудобным для некоторых протоколов, т.к. приводит к увеличению размера выхода. Долгое время оптимальным и простым решением представлялось XOR-комбинирование: H₁(M) ⊕ H₂(M). При некоторых оговорках стойкость такого решения была частично доказана. Сами алгоритмы функций при этом должны быть разными и несвязанными, иначе это привело бы к тривиальной атаке: H₂(M) := H₁(M) ⊕ const. Даже если обе функции идеально безопасны, но связаны через константу, то их XOR-комбинирование привело бы к результату: H₁(M) ⊕ H₂(M) = const для любого M.

Исследователи Gatan Leurent (государственный институт исследований в информатике и автоматике, Франция) и Lei Wang (Наньянский технологический университет, Сингапур) показали существенные изъяны в стойкости XOR-комбинирования. Большинство n-битовых хэш-функций структуры Дамгарда-Меркла или Хайфа при XOR-комбинировании теряют свою стойкость до 2^5n/6. Так, для 512-битной комбинации SHA512 ⊕ Whirlpool стойкость будет порядка 426 бит, т.е. стойкость XOR-комбинации двух функций слабее стойкости этих функций по отдельности. Нестойкость к коллизиям для XOR-объединения была известна и раньше, но авторы распространили результат на все хэш-функции структуры narrow pipe, даже заведомо стойкие или те, против которых не известно методов взлома по отдельности.

Расходы памяти на атаку зависят от длины сообщения: при длине n / 2 · 2^2t расходы памяти описываются этой же формулой, что позволяет вывести оптимальную длину сообщения для проведения атаки.

Атака может быть распространена и на случаи wide-pipe хэшей при размере сообщения, которое меньше размера внутреннего состояния хэш-функции. Так, исследователями был получен результат 2¹⁹⁹ при комбинировании SHA-224 ⊕ BLAKE-224 с этим условием.

Исследователям удалось атаковать и более сложную комбинирующую функцию Cryptophia, предложенную Миттельбахом и усовершенствованную Менником и Пренелом. Эта функция использует оптимизированное укороченное сочетание присоединения и XOR. Даже такое комбинирование оказалось слабее исходных функций при комбинации SHA-512 и Whirlpool.

Следует ещё раз подчеркнуть, что исследователи рассматривали функции сжатия внутри хэшей как идеальные в модели случайного оракула, а сами хэши — как стойкие. Даже при таких ограничениях им удалось добиться заметных результатов. В случае обнаружения в какой-либо из функций уязвимости результат такого перестраховочного комбинирования может оказаться ещё более слабым, чем использование хэш-функций по отдельности. Также результат атаки может быть распространён и на попытки XOR-комбинирования более двух хэш-функций.

В работе отмечается, что многие хэш-функции относятся к классу narrow pipe (SHA-1, SHA-256, SHA-512, Whirlpool, RIPEMD, GOST, BLAKE, Skein) и комбинирование их посредством XOR приводит к снижению стойкости. Также отмечается, что XOR-комбинирование всё ещё встречается в протоколах TLS, SSL и алгоритмах KDF (функция получения производных ключей).

Источник: Cryptology ePrint Archive^[link1]