id: Гость   вход   регистрация
текущее время 01:56 10/12/2018
Владелец: unknown (создано 10/02/2015 11:55), редакция от 10/02/2015 15:55 (автор: unknown) Печать
Категории: криптография, алгоритмы, хэширование
http://www.pgpru.com/Новости/2015/XOR-комбинированиеХэш-функцийСнижаетИхСтойкость
создать
просмотр
редакции
ссылки

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


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


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


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


Атака может быть распространена и на случаи wide-pipe хэшей при размере сообщения, которое меньше размера внутреннего состояния хэш-функции. Так, исследователями был получен результат 2199 при комбинировании 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


 
Много комментариев (17) [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3