openPGP в России

14.06 // Показан первый концептуальный взлом ГОСТ 28147-89 путём дифференциального криптоанализа

Исследователи Николя Куртуа^[link1] (Университетский Колледж Лондона, кафедра компьютерных наук^[link2]) и Мичал Мижтал (Военный Университет Технологий, Варшава^[link3]) опубликовали новую атаку на российский стандарт блочного шифрования — ГОСТ 28147-89. Также как и предыдущие работы по взлому полнораундовой версии ГОСТ, атака не имеет практического значения, но показывает некоторые очевидные, по мнению авторов, вещи:

• ГОСТ не удовлетворяет требованиям стойкого шифра с точки зрения современного сертификационного криптоанализа.
• Десятилетиями поддерживаемое ведущими криптографами мнение о стойкости ГОСТа к диффереренциальному криптоанализу оказалось ошибочным.

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

Лучшая из опубликованных в данной работе атак состоит из одиннадцати пунктов и включает в себя такие абсолютно непрактичные трюки, как угадывание 160 бит ключа из 256 и наличие 2⁶⁴ известных открытых текстов (это все возможные варианты открытых текстов в пределах блока). Стойкость ГОСТа снижается с 2²⁵⁶ до 2²²⁸ — именно столько шагов в сумме требует атака для нахождения ключа с вероятностью 50%. В отличие от ранее опубликованных алгебраических атак, которые требуют 2²²⁵ шагов, в данной атаке затраты памяти сокращены с 2¹²⁸ до 2⁶⁴.

Противнику в сценарии таких атак необходимы не только недостижимые вычислительные ресурсы, но и невыполнимые (и в практическом смысле абсурдные) требования, которые он должен получить по доступу к нужным объёмам информации с атакуемой системы. Однако, с теоретической точки зрения, если работа достоверна, можно сказать, что полнораундовый шифр ГОСТ впервые взломан дифференциальным криптоанализом. Чтобы привлечь внимание специалистов на фоне попыток стандартизации ГОСТ в международном стандарте ISO 18033, авторы особо подчёркивают что шифр ГОСТ помимо уже известных рефлективных атак, атак с "двойным отражением" и ряда специфических атак, нестоек даже к ДК.

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

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