Раундовая функция ГОСТ 28147-89

" Сложение по модулю 2³² с раундовым ключом.

" Замена с использованием 8 четырехразрядных таблиц замены.

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

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

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

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

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

Считается,^[8]что ГОСТ устойчив к таким широко применяемым методам, как линейный и дифференциальный крипто анализ. Обратный порядок использования ключей в последних восьми раундах обеспечивает защиту от атак скольжения (slide attack) и отражения (reflection attack). Ростовцев А. Г., Маховенко Е. Б., Филиппов А. С., Чечулин А. А. в своей работе^[9]описали вид криптоанализа, который сводится к построению алгебраической целевой функции и нахождению ее экстремума. Были выделены классы слабых ключей, в частности, показано, что разреженные ключи (со значительным преобладанием 0 или 1) являются слабыми. По мнению авторов, их метод в любом случае лучше, чем полный перебор, однако без численных оценок.

В мае 2011 года известный криптоаналитик Николя Куртуадоказал существование атаки на данный шифр, имеющей сложность в 2⁸(256) раз меньше сложности прямого перебора ключей при условии наличия 2⁶⁴пар открытый текст/закрытый текст.^[10][11]Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности. Более того, знание 2⁶⁴пар открытый текст/закрытый текст, очевидно, позволяет читать зашифрованные тексты, даже не вычисляя ключа. В большинстве других работ также описываются атаки, применимые только при некоторых предположениях, таких как определенный вид ключей или таблиц замен, некоторая модификация исходного алгоритма, или же требующие все еще недостижимых объемов памяти или вычислений. Вопрос о наличии применимых на практике атак без использования слабости отдельных ключей или таблиц замены остается открытым.