Российский стандарт шифрования: стойкость снижена

07.03.2018

На конференции FSE 2011 анонсирована работа, предлагающая нетривиальную атаку на российский стандарт шифрования ГОСТ 28147-89. Заявленная атака предполагает снижение стойкости стандарта.

Российский (на самом деле еще советский) стандарт шифрования ГОСТ 28147-89 (далее - ГОСТ) был принят в 1989 году в СССР, но по некоторым сведениям разработан еще в 70-х годах. Кроме Российской Федерации ГОСТ принят в качестве стандарта СНГ (ГОСТ Р 34.12-2015).

Учитывая темпы развития информационных технологий, нельзя не сказать, что (более чем тридцатилетний) ГОСТ является долгожителем. Но является ли он устаревшим? Плюсом такого «возраста» является большое количество исследований, направленных на оценку криптографических качеств шифра. В то же время, только по прошествии более 20 лет с момента принятия стандарта появились исследования, снижающие стойкость ГОСТа.

Алгоритм ГОСТ построен с использованием преобразования Фейстеля и состоит из 32-х однотипных итераций. Длина блока преобразуемой информации равняется 64 битам, а длина ключа – 256 битам. Преобразование на каждой итерации состоит из сложения с ключом итерации по модулю 2³², применения восьми S-блоков (каждый действует на 4-х битах) и циклического сдвига. Вообще говоря, значения S-блоков не определены стандартом, видимо, предполагается, что каждая реализация использует свой набор значений.

Нельзя сказать, что ГОСТ – сверхбыстрый программный шифр. Это даже естественно, учитывая время, когда он был разработан. Но вот с точки зрения аппаратной реализации, конструкция ГОСТа является очень удачной. Например, существуют его реализации с использованием всего 650 GE. Таким образом, ГОСТ может рассматриваться как «сверхлегкий» (ultra lightweight) блочный шифр, подходящий для использования в системах с ограниченными ресурсами, включая пассивные RFID и сенсорные элементы - sensor nodes.

За более чем 20 лет существования стандарта было предложено множество работ по его анализу. Разностная атака была предложена в 2000 году Seki и Kaneko, но она применялась только к 13 из 32-х итерациям ГОСТа. Также к шифру в 2000 году была применена слайд-атака, но и здесь рассматривалось только 30 итераций алгоритма ГОСТ. Затем, в 2007 году Kara представил так называемую рефлексивную (reflection) атаку на алгоритм ГОСТ, но опять состоящий только из 30 итераций.

В ряде работ, например, описаны классы слабых ключей. Несмотря на то, что общее число слабых ключей велико: 2¹²⁸ и 2²²⁴ соответственно, их доля среди всего ключевого множества пренебрежительно мала.

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

И вот, только в 2011 году появились исследования, действительно снижающие стойкость ГОСТа. Предложена новая атака на блочные шифры: «рефлексивная встреча посередине» (reflection-meet-in-the-middle). Отметим, что применение этой атаки к ГОСТу потребовало существенной модификации этапа встречи посередине путем использования эквивалентных ключей для четырех итераций. Параметры предложенной атаки составляют 2²²⁵ операций, 2³² известных пар блоков открытого/шифртекста и 2⁶⁴ ячеек памяти.

Каковы последствия появления данной атаки? Во-первых, стойкость ГОСТа снижена, пусть и не значительно: с 2²⁵⁶ до 2²²⁵. Но все же это говорит о том, что ГОСТ более слабый шифр, нежели предполагалось ранее. В то же время, предложенная атака имеет исключительно теоретическое значение, так как имеет высокую трудоемкость, требует большой объем памяти (десятки терабайт) и большое количество известных блоков открытого текста. Таким образом, с точки зрения практических аспектов использования ГОСТа не произошло ровным счетом ничего. А вот попытки стандартизации ГОСТа в ISO ожидаемо завершились неудачей.

В России рассматриваемый алгоритм вошел в стандарты 2013 и 2015 года на блочные шифры ГОСТ Р 34.12-2015. В этом стандарте Гост 28147-89, который мы рассматривали в этой статье, обозначен как шифр МАГМА, который отличается от исходного ГОСТ, только тем, что в МАГМЕ зафиксировали подстановки.