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

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

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

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

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

Используя свойства отражения, фиксированных точек и двумерной атаки встречи посредине (2DMITM) им удалось с использованием 2³² данных снизить затраты памяти с непрактичных 2⁶⁴ до практичных 2³⁶ без изменения времени исполнения 2²²⁴. Если использовать теоретическую возможность использования 2⁶⁴ данных (исчерпание кодовой книги, задаваемой размером блока шифра), то можно снизить время исполнения до 2¹⁹² и затраты памяти до 2³⁶.

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

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

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