Регистрация19.02 // Первая атака на функцию хэширования ГOСТ-Р 34.11-94
Сотрудники Института Прикладной Информатики, Вычислений и Коммуникаций
Florian Mendel, Dr. Norbert Pramstaller и Christian RECHBERGER
представили работу 
Cryptanalysis of the GOST Hash Function на конференции Fast Software Encryption.
На функцию хэширования ГОСТ, являющуюся стандартом Российской Федерации ГOСТ-Р 34.11-94 долгое время не было известно никаких атак. В отличие от MD5 и SHA-1 в функции хэширования ГОСТ кроме простой итеративной структуры применяется также вычисление контрольной суммы всех входящих блоков хэшируемых данных, что затрудняет проведение атак.
Исследователям удалось обойти эту трудность. Ими были использован метод как неоснованный на свойствах блочного шифра ГОСТ, положенного в основу хэш-функции, так и метод, основанной на слабости ГОСТ в отношении фиксированных точек. Из-за слабого ключевого расписания, фиксированные точки, найденые для 8 раундов, легко удалось использовать в полных 32 раундах шифра.
Функция хэширования ГОСТ оказалась теоретически неустойчивой к псевдоколлизиям, коллизиям, мультиколлизиям, нахождению первого и второго прообраза.
Атаки нахождения первого и второго прообраза независят от свойств шифра ГОСТ и имеют сложность 2225, что меньше чем 2256 и 238 байт памяти, используя особенности шифра ГОСТ, атаку на нахождения прообраза можно упростить до 2192 шагов и 269 байт памяти.
Атаки на нахождения коллизий имеют сложность 2105 < 2128 и 269 байт памяти.
Таким образом, атаки пока не имеют практического значения, но являются первым серьёзным теоретическим результатом в исследовании функции хэширования ГОСТ.
Источник: 15th Fast Software Encryption 2008 WorkShop
комментариев: 510 документов: 110 редакций: 75
который в начале этого года был на главной странице форума. И жаль, что мнение многих пользователей, ориентированное на не лучший прогноз, подтвердилось. Тем более жаль, что этой коснулось отечественной разработки. Хотя наша хеш-функция конечно еще не взломана, но эти результаты все-же не приятны.
комментариев: 11558 документов: 1036 редакций: 4118
комментариев: 9796 документов: 488 редакций: 5664
ГОСТ 34.11-94 определяет алгоритм и процедуру вычисления хэш-функции, используемой в России при реализации электронно-цифровой подписи (ЭЦП) и в других криптографических приложениях.
Хэш-функция h – детерминированная функция, отображающая строку битов произвольной длины в строку битов фиксированной длины. Хэш-функции должны обеспечивать неразрешимость задачи вычисления входной строки x по h(x). Кроме того, они должны быть устойчивы к коллизиям, то есть успешному поиску величин x и y, удовлетворяющих условиям "x не равно y" и "h(x) равна h(y)".
Исследователи из Университета Граца и Варшавского института математики и криптологии показали уязвимость российского стандарта ГОСТ 34.11-94 к атакам, направленным на писк коллизий и на вычисление как первого, так и второго прообраза, то есть соответственно двух или трех значений входной строки, для которых выходная строка совпадает.
http://online.tu-graz.ac.at/tu.....=80200&pCurrPk=36649
Предложенная модель атаки основана на уязвимости блочного шифра хэш-функции, позволяющей находить для некоторых видов открытого текста фиксированные точки, для которых можно предсказывать значение функции сжатия.
В результате коллизионный поиск мог быть существенно сокращен. Сложность успешной атаки, направленной на поиск коллизий, составил 2105 операций, на поиск второго прообраза – 2193 операций (последний показатель в 233 раз сокращает время аналогичной атаки, показанной в этом же году Флорианом Менделем (Florian Mendel) с коллегами).
Источник: http://www.cnews.ru/news/top/index.shtml?2008/08/29/315265
комментариев: 9796 документов: 488 редакций: 5664
По данным работы очередной версии исследования таблица наиболее важных предыдущих и текущих значений выглядит таким образом (работа представлена летом на CRYPTO 2008):
Сравниваем это с текстом опубликованной новости, где такие же цифры уже были приведены в феврале со слайдов и не исправлялись.
Видимо на FSE 2008 была подана заявка на старую версию работы, а слайды были представлены от будущей работы и к моменту FSE 2008 в начале года уже были известны, просто окончательная версия работы не была опубликована и была готова только к CRYPTO 2008.