id: Гость   вход   регистрация
текущее время 14:17 19/03/2024
Владелец: unknown (создано 12/10/2011 11:11), редакция от 12/10/2011 20:31 (автор: unknown) Печать
Категории: криптография, криптоанализ, алгоритмы, симметричное шифрование, атаки
https://www.pgpru.com/Новости/2011/УлучшеннаяАтакаНаПолнораундовыйГОСТ28147-89
создать
просмотр
редакции
ссылки

12.10 // Улучшенная атака на полнораундовый ГОСТ 28147-89


Алгоритм блочного шифрования GOST (ГОСТ 28147-89) был создан в Советском Союзе как альтернатива американскому стандарту шифрования DES. DES изначально имел небольшой запас прочности по размеру ключа и количеству раундов, поэтому был взломан как теоретически, так и за счёт тривиальных атак перебора ключевого пространства ещё в 90-е годы. Однако сообщения о взломе шифра ГОСТ появились лишь относительно недавно.


Если не считать атак на связанных ключах, которые известны достаточно давно, то первую одноключевую атаку на полнораундовый ГОСТ представил Таканори Изобе на конференции FSE'11 (февраль 2011 года). Он использовал удивительное свойство отражения, которое впервые отметил Орхан Кара: каждый раз, когда левая и правая половина блока оказываются одинаковыми после 24 раундов (что может произойти с вероятностью 2-32), то последние раунды становятся тождественным отображением и таким образом можно снизить эффективное число раундов с 32 до 16-ти. Изобе разработал новый алгоритм выделения ключа от оставшихся 16 раундов ГОСТа, который требует затрат в количестве 2192 шагов по времени и 264 памяти. Для того, чтобы получить все 256 бит ключа требуется 232 данных, 264 памяти и 2224 времени. Это значительно быстрее, чем полный перебор по всем параметрам, хотя и непрактично.


Вскоре новую атаку на ГОСТ опубликовал Николя Куртуа. Она была основана на совершенно иных, алгебраических подходах, но имела даже худшие показатели в плане сложности: 264 данных, 264 памяти и 2248 шагов времени исполнения. Позднее Куртуа и Мижтал описали дифференциальную атаку, которая опять использовала 264 данных и памяти, но сокращала затраты времени до 2226.


Израильские исследователи Итаи Динур, Ади Шамир (кафедра компьютерных наук Института Вейцмана, Реховот), Орр Данкельман (кафедра компьютерных наук Университета Хайфы) продолжили исследования свойств алгоритма ГОСТ и представили новые, улучшенные методики криптоанализа.


Используя свойства отражения, фиксированных точек и двумерной атаки встречи посредине (2DMITM) им удалось с использованием 232 данных снизить затраты памяти с непрактичных 264 до практичных 236 без изменения времени исполнения 2224. Если использовать теоретическую возможность использования 264 данных (исчерпание кодовой книги, задаваемой размером блока шифра), то можно снизить время исполнения до 2192 и затраты памяти до 236.


Интересно отметить и другие усовершенствования. Атака Изобе основана на предположении об использовании только инвертируемых S-блоков. Поскольку S-блоки не описаны в стандарте, то в структуре шифра, основанной на сети Фейстеля, использование именно инвертируемых S-блоков, в принципе, не является обязательным. Схожая проблема есть и в атаках Куртуа — их сложность оценивается только для наиболее известного набора S-блоков, применявшихся в реализациях для банковских операций. Нет оснований считать, что какой-либо другой реально использующийся набор S-блоков в рамках такой атаки не окажется имеющим другой уровень стойкости.


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


Источник: Cryptology ePrint Archive
См. также:
Показан первый концептуальный взлом ГОСТ 28147-89 путём дифференциального криптоанализа
Сообщения о взломе блочного шифра ГОСТ 28147-89 в разгар усилий по его международной стандартизации
Первая атака на функцию хэширования ГOСТ-Р 34.11-94, Рефлективные атаки понижают стойкость шифра ГОСТ


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