Алгоритм шифрования ГОСТ 28147-89

Обзор криптоаналитических исследований отечественного стандарта шифрования ГОСТ 28147-89

Краткое описание алгоритма

Отечественный алгоритм шифрования ГОСТ 28147-89 определен в стандарте [14]. Алгоритм шифрует данные 64-битными блоками с использованием 256-битного ключа шифрования. Выполняется 32 раунда преобразований, в каждом из которых предусмотрены следующие операции (см. рис. 1):

Рис 1. Раунд алгоритма ГОСТ 28147-89.

1. Один из 32-битных субблоков данных складывается с 32-битным значением ключа раунда Ki по модулю 232.

2. Результат предыдущей операции разбивается на 8 фрагментов по 4 бита, которые параллельно «прогоняются» через 8 таблиц замен S1…S8. Таблицы замен в стандарте [14] не определены. Примеры возможных таблиц замен можно найти, например, в [17] или [18].

3. 4-битные фрагменты (после замен) объединяются обратно в 32-битный субблок, значение которого циклически сдвигается влево на 11 бит.

4. Обработанный предыдущими операциями субблок накладывается на необработанный с помощью побитовой логической операции «исключающее или» (XOR).

5. Субблоки меняются местами.

Процедура расширения ключа в алгоритме ГОСТ 28147-89, фактически, отсутствует: в раундах шифрования последовательно используются 32-битные фрагменты K1…K8 исходного 256-битного ключа шифрования в следующем порядке: K1, K2, K3, K4, K5, K6, K7, K8,
– за исключением последних 8 раундов – в раундах с 25-го по 31-й фрагменты используются в обратном порядке.

Расшифрование полностью аналогично зашифрованию, но с другим порядком использования фрагментов ключа:

в прямом порядке – в первых 8 раундах;

в остальных раундах – в обратном порядке.

Стандарт [14] также предусматривает и описывает различные режимы применения алгоритма:

описанный выше режим простой замены;

режимы гаммирования и гаммирования с обратной связью, предусматривающие вычисление с помощью описанных выше преобразований псевдослучайной последовательности – гаммы шифра – и ее наложение на шифруемый текст;

режим вычисления имитовставки – криптографической контрольной суммы, используемой для подтверждения целостности данных; в данном режиме выполняется 16 раундов преобразований вместо 32-х.

Алгоритм ГОСТ 28147-89 можно использовать и в различных общеупотребительных режимах шифрования (предусмотренных стандартом [4]). Кроме того, на основе данного алгоритма построен отечественный стандарт хэширования ГОСТ Р 34.11-94 [15].

Как видно из описания, алгоритм ГОСТ 28147-89 является весьма простым в реализации, что является его несомненным достоинством.

Криптоанализ алгоритма

В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на английский язык и опубликовано [11], именно после этого стали появляться результаты его анализа, выполненного зарубежными специалистами; однако, в течение значительного времени не было найдено каких-либо атак, приближающихся к практически осуществимым [1].

Анализ таблиц замен

Поскольку таблицы замен в стандарте [14] не приведены, в ряде работ (например, в [2]) высказывается предположение, что «компетентная организация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако, в [21] известнейший эксперт Брюс Шнайер (Bruce Schneier) называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен (пример таковой приведен в [18]), применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно привести два следующих факта из истории стандарта шифрования США DES (подробно см. [16]):

Атаки с помощью как линейного, так и дифференциального криптоанализа алгоритма DES используют конкретные особенности таблиц замен. При использовании других таблиц криптоанализ придется начинать сначала (различные методы криптоанализа описаны в статьях «Современные методы вскрытия алгоритмов шифрования» и «Криптоаналитические атаки на связанных ключах»).

Были попытки усилить DES против линейного и дифференциального криптоанализа путем использования более стойких таблиц замен. Такие таблицы, действительно более стойкие, были предложены, например, в алгоритме s5DES [7]. Но, увы, заменить DES на s5DES было невозможно, поскольку таблицы замен жестко определены в стандарте [3], соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.

В ряде работ (например, [2], [17] и [18]) ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом). Однако, в работе [12] доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически:

1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т.е. значения z = f(0), где f() – функция раунда алгоритма. Этот этап занимает порядка 232 операций шифрования.

2. С помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 211 операций.

Модификации алгоритма и их анализ

В работе [10] проведен криптоанализ модификаций алгоритма ГОСТ 28147-89:

алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно, в раундах с 25-го по 32-й подключи используются в прямом порядке, т.е. точно так же, как и в предыдущих раундах алгоритма;

20-раундового алгоритма GOSTA, в раунде которого для наложения ключа используется операция XOR вместо сложения по модулю 232.

По результатам анализа сделан вывод о том, что GOST-H и GOSTA слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Стоит отметить, что в части криптоанализа GOSTA работа [10] слово в слово повторяет раздел, посвященный криптоанализу данного алгоритма, вышедшей в 2000 г. известной работы [1] (без каких-либо ссылок на оригинал). Это ставит под сомнение профессионализм авторов работы [10] и остальные ее результаты.

Весьма интересная модификация алгоритма предложена в работе [13]: таблицы S1…S8 обязательно должны быть различными; в каждом раунде алгоритма должна выполняться их перестановка по определенному закону. Данная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т.е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.

И еще одна модификация, связанная с таблицами замен, приведена в работе [5], в которой анализируется один из возможных методов вычисления таблиц замен на основе ключа шифрования. Авторы работы сделали вывод, что подобная зависимость ослабляет алгоритм, поскольку приводит к наличию слабых ключей и к некоторым потенциальным уязвимостям алгоритма.

Анализ полнораундового алгоритма

Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма, – широко известная работа [6] – посвящена атакам, использующим слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако, сильные таблицы замен (например, приведенная в [21]) делают такую атаку абсолютно непрактичной.

Отечественные ученые А.Г. Ростовцев и Е.Б. Маховенко в 2001 г. в работе [19] предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ [20]) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе [20].

В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 бит секретного ключа [8]. Для атаки требуется 235 выбранных открытых текстов и 236 операций шифрования. Как видно, данная атака, практически, бесполезна для реального вскрытия алгоритма.

Заключение

Как видно, в открытой литературе можно найти достаточно мало работ, посвященных криптоанализу алгоритма ГОСТ 28147-89. Это особенно заметно по сравнению с огромным числом работ, посвященных криптоанализу стандартов шифрования США DES (обзор таких работ можно найти в [16]) и AES (см. статью «Алгоритм шифрования AES и его криптоанализ») или криптоанализу некоторых из широко используемых алгоритмов шифрования, например, IDEA [9] или SAFER (см. статью «Эволюция алгоритмов шифрования на примере семейства алгоритмов SAFER»). По результатам открытых работ можно сделать вывод о достаточно высокой криптостойкости отечественного стандарта шифрования.

Об авторе: Панасенко Сергей Петрович, нач. отдела разработки программного обеспечения фирмы АНКАД, кандидат технических наук.