openPGP в России

19.02 // Первая атака на функцию хэширования ГOСТ-Р 34.11-94

Сотрудники Института Прикладной Информатики, Вычислений и Коммуникаций^[link1]
Florian Mendel^[link2], Dr. Norbert Pramstaller^[link3] и Christian RECHBERGER^[link4]
представили работу Cryptanalysis of the GOST Hash Function^[link5] на конференции Fast Software Encryption^[link6].

На функцию хэширования ГОСТ, являющуюся стандартом Российской Федерации ГOСТ-Р 34.11-94 долгое время не было известно никаких атак. В отличие от MD5 и SHA-1 в функции хэширования ГОСТ кроме простой итеративной структуры применяется также вычисление контрольной суммы всех входящих блоков хэшируемых данных, что затрудняет проведение атак.

Исследователям удалось обойти эту трудность. Ими были использован метод как неоснованный на свойствах блочного шифра ГОСТ, положенного в основу хэш-функции, так и метод, основанной на слабости ГОСТ в отношении фиксированных точек. Из-за слабого ключевого расписания, фиксированные точки, найденые для 8 раундов, легко удалось использовать в полных 32 раундах шифра.

Функция хэширования ГОСТ оказалась теоретически неустойчивой к псевдоколлизиям, коллизиям, мультиколлизиям, нахождению первого и второго прообраза.

Атаки нахождения первого и второго прообраза независят от свойств шифра ГОСТ и имеют сложность 2²²⁵, что меньше чем 2²⁵⁶ и 2³⁸ байт памяти, используя особенности шифра ГОСТ, атаку на нахождения прообраза можно упростить до 2¹⁹² шагов и 2⁶⁹ байт памяти.

Атаки на нахождения коллизий имеют сложность 2¹⁰⁵ < 2¹²⁸ и 2⁶⁹ байт памяти.

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

Источник: 15th Fast Software Encryption 2008 WorkShop^[link7]