Алгоритм ГОСТ 28147-89 и шифр «Магма» (ГОСТ Р 34. 12-2015)

Общая схема алгоритма. Алгоритм, описанный ГОСТ 28 147–89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования», является отечественным стандартом симметричного шифрования (до 1 января 2016 г.) и обязателен для реализации в сертифицированных средствах криптографической защиты информации, применяемых в государственных информационных системах и, в некоторых случаях, в коммерческих системах. Сертификация средств криптографической защиты информации требуется для защиты сведений, составляющих государственную тайну РФ, и сведений, конфиденциальность которых требуется обеспечить согласно действующему законодательству. Также в Российской Федерации применение алгоритма ГОСТ 28 147–89 рекомендовано для защиты банковских информационных систем.

Алгоритм ГОСТ 28 147–89 (рис. 2.21) базируется на схеме Фейстеля и шифрует информацию блоками по 64 бит, которые разбиваются на два подблока по 32 бита (I, и R). Подблок R, обрабатывается функцией раундового преобразования, после чего его значение складывается со значением подблока Lj, затем подблоки меняются местами. Алгоритм имеет 16 или 32 раунда в зависимости от режима шифрования (вычисление имитовставки или другие режимы шифрования).

Рис. 2.21. Схема раунда алгоритма ГОСТ 28 147–89

В каждом раунде алгоритма выполняются следующие преобразования.

1. Наложение ключа. Содержание подблока R_i складывается по модулю 2³² с ключом раунда К. Kj — это 32-битовая часть исходного ключа, используемая в качестве раундового. Алгоритм ГОСТ 28 147–89 нс использует процедуру расширения ключа, исходный 256-битный ключ шифрования представляется в виде конкатенации (сцепления) восьми 32-битовых подключей (рис. 2.22): К₀, К_{, К_т К, К_А, К₅, К₆, К₇.

В процессе шифрования используется один из этих подключей К•

• с 1-го по 24-й раунд — в прямой последовательности:

• с 25-го, но 32-й раунд — в обратной последовательности:

Рис. 2.22. Строение ключа шифрования алгоритма ГОСТ 28 147–89.

2. Табличная замена. После наложения ключа подблок R_i разбивается на восемь частей, но 4 бита, значение каждой из которых по отдельности заменяется в соответствии со своей таблицей замены (S-блоком). Всего используется восемь S-блоков — S₀, S, S₂, S₃, S₄, S₅, S₆, S₇. Каждый S-блок алгоритма ГОСТ 28 147–89 представляет собой вектор (одномерный массив) с^{элементами,} пронумерованными от 0 до 15. Значениями S-блока являются 4-битовые числа, т. е. целые числа от 0 до 15.

Из таблицы S-блока берется элемент, порядковый номер которого совпадает со значением, пришедшим на вход подстановки.

Пример 2.6.

Пусть имеется S-блок следующего вида:

Пусть на вход этого S-блока подано значение 0100₂ = 4. Выходом S-блока будет 4-й элемент таблицы замен, т. е. 15 = 1111₂ (нумерация элементов начинается с нуля).^[1]

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

К сожалению, алгоритм ГОСТ 28 147–89 имеет «слабые» таблицы замен, при использовании которых алгоритм может быть достаточно легко раскрыт криптоаналитическими методами. К числу «слабых» относится, например, тривиальная таблица замен, в которой вход равен выходу (табл. 2.16).

Таблица 2.16

Пример слабого S-блока.

Считается, что конкретные значения таблиц замен должны храниться в секрете и являются долговременным ключевым элементом, т. е. действуют в течение гораздо более длительного срока, чем отдельные ключи. Однако секретные значения таблиц замен не являются частью ключа и не могут увеличить его эффективную длину.

Действительно, секретные таблицы замен могут быть вычислены с помощью следующей атаки, которую возможно применять на практике:

• • устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т. е. значения z = F (0), где F — функция раундового преобразования алгоритма. Это требует порядка 2³² тестовых операций шифрования;
• • с помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2¹¹ операций.

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

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

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

В современных алгоритмах S-блоки обычно представляют собой вектор (одномерный массив), содержащий 2″ т-битовых элементов. Вход блока определяет номер элемента, значение которого служит выходом S-блока.

Для проектирования S-блоков был выдвинут целый ряд критериев. Таблица замен должна удовлетворять:

• • строгому лавинному критерию;
• • критерию независимости битов;
• • требованию нелинейности от входных значений.

Для выполнения последнего требования было предложено задавать линейную комбинацию i битов (i = 1, …, т) значений таблицы замен бентфункциями (англ, bent — отклоняющийся, в данном случае — от линейных функций). Бент-функции образуют специальный класс булевых функций, характеризующихся высшим классом нелинейности и соответствием строгому лавинному критерию.

В некоторых работах для S-блоков предлагается проверка выполнения гарантированного лавинного эффекта порядка у — при изменении одного входного бита меняется, по крайней мере, у выходных бит S-блока. Свойство гарантированного лавинного эффекта порядка у от 2 до 5 обеспечивает достаточно хорошие диффузионные характеристики S-блоков для любого алгоритма шифрования.

При проектировании достаточно больших таблиц замен могут быть использованы следующие подходы:

• • случайный выбор (для S-блоков небольшого размера может привести к созданию слабых таблиц замен);
• • случайный выбор с последующей проверкой на соответствие различным критериям и отбраковкой слабых S-блоков;
• • ручной выбор (для S-блоков больших размеров слишком трудоемок);
• • математический подход, например генерация с использованием бентфункций (этот подход применен в алгоритме CAST).

Можно предложить следующий порядок^[2] проектирования отдельных Sблоков алгоритма ГОСТ 28 147–89:

• • каждый S-блок может быть описан четверкой логических функций, каждая из функций должна иметь четыре логических аргумента;
• • необходимо, чтобы эти функции были достаточно сложными. Это требование сложности невозможно выразить формально, однако в качестве необходимого условия можно потребовать, чтобы соответствующие логические функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) с использованием основных логических операций, не были короче некоторого необходимого значения;
• • отдельные функции, даже используемые в разных таблицах замен, должны различаться между собой в достаточной степени.

Описаны и другие алгоритмы^[3] построения S-блоков для шифра ГОСТ 28 147–89. На практике обычно достаточно получить узлы замен как независимые случайные перестановки чисел от 0 до 15.

Не требуется, чтобы S-блоки были простыми перестановками чисел от О до 15, т. е. допускаются повторение элементов, а также необратимые замены, однако в этом случае снижается стойкость шифра.

Попытки проектирования S-блоков как функции от ключа шифрования показали, что использование зависящих от ключа S-блоков обычно ослабляет шифр (как для DES, так и для ГОСТ 28 147–89).

Режимы работы алгоритма ГОСТ 28 147–89. Алгоритм ГОСТ 28 147–89 имеет четыре режима работы, которые отличаются от общепринятых:

• • простой замены;
• • гаммирования;
• • гаммирования с обратной связью;
• • выработки имитовставки.

Режим простой замены. В режиме простой замены производится независимое шифрование 64-битных блоков текста одним и тем же ключом с выполнением 32 раундов алгоритма ГОСТ 28 147–89. Аналогично режиму электронной кодовой книги ЕСВ, по причине раздельного шифрования режим простой замены не рекомендуется использовать для шифрования длинных сообщений; он применим для шифрования ключей в многоключевых схемах.

Режим гаммирования. В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 (XOR) с 64-битным блоком гаммы шифра (рис. 2.23). Гамма шифра — псевдослучайная последовательность, которая вырабатывается следующим образом:

• • в 32-битовые регистры N_{ и N₂ записываются их начальные значения — половины 64-битной величины, называемой синхропосылкой. Синхропосылка является аналогом вектора инициализации в режимах СВС, CFB, OFB;
• • выполняется шифрование содержимого N_{ и N₀ в режиме простой замены, результаты записываются в регистры JV, и N₂;
• • содержимое N_{ складывается по модулю (2³² -1) со значением константы А_х = 2²⁴ + 2¹⁶ + 2⁸ + 4. Если получено значение, равное нулю, оно заменяется на 2 ³² — 1. Результат сложения записывается в регистр N_v С учетом сделанного замечания корректная с математической точки зрения формула для вычисления нового значения А, может быть записана как N_u = = (N_u__{ + А, — l) mod (2³² — 1) + 1;
• • содержимое N₂ складывается по модулю 2³² со значением константы А₂ = 2²⁴ + 2^lfi + 2^s + 1, результат сложения записывается в регистр N₂: N_2i = = (N_2i__{ + A₂)mod2³²;
• • содержимое регистров N_{ и JV₂ подается на выход алгоритма выработки гаммы, г. е. представляет блок гаммы, которая затем складывается с блоком открытого текста;
• • при необходимости продолжения повторяются все шаги, кроме первого.

Рис. 2.23. Режим гаммирования

Период повторения генерируемой гаммы М составляет 2³²(2³² — 1), т. е.

М ~ 2^(И.

Режим гаммирования с обратной связью. Этот режим аналогичен предыдущему, но в качестве заполнения регистров N_{ и N₂, начиная со второго блока, используется результат шифрования предыдущего блока открытого текста (рис. 2.24).

Рис. 2.24. Режим гаммирования с обратной связью.

Режим выработки имитовставки. Имитовставка — это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. Для вычисления имитовставки существует специальный режим алгоритма ГОСТ 28 147–89 (рис. 2.25), несколько похожий на режим сцепления блоков шифротекста СВС (однако без использования синхропосылки — вектора инициализации):

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

Рис. 2.25. Режим выработки имитовставки Имитовставкой является 64-битное содержимое последнего блока Y_N или его часть. Чаще всего используется 32-битная имитовставка, т. е. половина последнего блока шифра. Этого достаточно, так как имитовставка, как и любая контрольная сумма, предназначена, прежде всего, для защиты от случайных искажений информации.

В общем случае вероятность успешного навязывания ложных данных равна 2″, где п — разрядность имитовставки.

Для защиты от преднамеренной модификации данных применяют другие криптографические методы — в первую очередь электронную цифровую подпись (ЭЦП).

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

• 1) вычисление имитовставки для заданной незашифрованной информации;
• 2) подбор открытых данных иод заданную имитовставку.

Имитовставка используется следующим образом:

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

Рассмотрим подробнее влияние искажений шифротекста на полученные в результате расшифровки данные.

В режиме простой замены искажение блока шифротекста приводит при расшифровании к непредсказуемым изменениям соответствующего блока открытого текста. В режиме гаммирования все изменения открытого текста предсказуемы. В режиме гаммирования с обратной связью искажение блока шифротекста после расшифровки приводит к изменениям двух блоков открытого текста, при этом один из них оказывается искаженным предсказуемым образом, а другой — непредсказуемым образом. Непредсказуемые изменения в расшифрованном массиве данных могут быть обнаружены только в том случае, когда исходные данные избыточны, т. е. представляют осмысленный текст на естественном языке. В остальных случаях единственная возможность обнаружить изменения или, напротив, подтвердить целостность — использование контрольной суммы, криптографической контрольной суммы (имитовставки) или ЭЦП.

Имитовставка особенно полезна для проверки правильности расшифрованной ключевой информации в многоключевых схемах.

Криптостойкость алгоритма ГОСТ 28 147–89. В 1994 г. описание алгоритма ГОСТ 28 147–89 было переведено на английский язык и опубликовано. Именно после этого стали появляться результаты его анализа, выполненные зарубежными специалистами.

В течение значительного времени не было найдено каких-либо практически осуществимых атак^[4]. В открытой публикации довольно мало работ, посвященных криптоанализу ГОСТ, по их результатам можно сделать вывод о весьма высокой криптостойкости отечественного стандарта шифрования. Высокая стойкость достигается за счет:

• • большой длины ключа — 256 бит;
• • 32 раундов преобразований; уже после восьми раундов достигается полный эффект рассеивания входных данных.

Стандарт ГОСТ 28 147–89 проявляет стойкость к линейному криптоанализу уже после пяти раундов, а к классическому дифференциальному — после семи раундов (на уровне стойкости 2¹²⁸). Основной проблемой криптоалгоритома ГОСТ 28 147–89 является довольно простое расписание ключей, что позволяет строить, по крайней мере теоретически, атаки меньшей сложности, чем полный перебор ключевого пространства. Полнораундовый алгоритм ГОСТ 28 147–89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. Представляет интерес атака методом бумеранга с использованием связанных ключей^[5], которая позволяет определить ключ шифра с использованием всего 226 операций, однако требует сложного выбора исходных данных.

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

В 2011 г. предложена новая атака «рефлексивная встреча посередине», незначительно снижающая стойкость ГОСТ 28 147–89 (с 2256 до 2225)^[8]. Лучший результата криптоанализа алгоритма по состоянию на 2012 г. позволяет снизить его стойкость до 2¹⁹², требуя относительно большого размера шифротекста и объема предварительно сформированных данных^[9]. Несмотря на предложенные атаки, на современном уровне развития вычислительной техники ГОСТ 28 147–89 сохраняет практическую стойкость.

Шифр «Магма» (ГОСТ Р 34.12—2015). Стандарт ГОСТ 28 147–89 действовал в России более 25 лет. За это время он показал достаточную стойкость и хорошую эффективность программных и аппаратных реализаций, в том числе и на низкоресурсных устройствах. Хотя и были предложены криптоаналитические атаки, снижающие оценки его стойкости (лучшая — до 2¹⁹²), они далеки от возможности практической реализации. Поэтому было принято решение о включении алгоритма ГОСТ 28 147–89 во вновь разрабатываемый стандарт симметричного шифрования.

В шопе 2015 г. приняты два новых национальных криптографических стандарта: ГОСТ Р 34.12—2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» и ГОСТ Р 34.13—2015 «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров», которые вступают в действие с 1 января 2016 г.

Стандарт ГОСТ Р 34.12—2015 содержит описание двух блочных шифров с длиной блока 128 и 64 бит. Шифр ГОСТ 28 147–89 с зафиксированными блоками нелинейной подстановки включен в новый ГОСТ Р 34.12—2015 в качестве 64-битового шифра под названием «Магма» («Magma»).

Ниже приведены закрепленные в стандарте блоки замен:

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

По мнению технического комитета по стандартизации «Криптографическая защита информации» (ТК 26), фиксация блоков нелинейной подстановки сделает алгоритм ГОСТ 28 147–89 более унифицированным и поможет исключить использование «слабых» блоков нелинейной подстановки. Кроме того, фиксация в стандарте всех долговременных параметров шифра отвечает принятой международной практике. Новый стандарт ГОСТ Р 34.12—2015 терминологически и концептуально связан с международными стандартами ИСО/МЭК 10 116 «Информационные технологии. Методы обеспечения безопасности. Режимы работы для «-битовых блочных шифров» (ISO/IEC 10 116:2006 Information technology — Security techniques — Modes of operation for an n-bit block cipher) и серии ИСО/МЭК 18 033 «Информационные технологии. Методы и средства обеспечения безопасности. Алгоритмы шифрования»: ИСО/МЭК 18 033−1:2005 «Часть 1. Общие положения» (ISO/IEC 18 033−1:2005 Information technology — Security techniques — Encryption algorithms — Part 1: General) и ИСО/МЭК 18 033−3:2010 «Часть 3. Блочные шифры» (ISO/IEC 18 033−3:2010 (Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers)).

В стандарт ГОСТ P 34.12—2015 включен также новый блочный шифр («Кузнечик») с размером блока 128 бит. Ожидается, что этот шифр будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры.

Режимы работы блочных шифров (простой замены, гаммирования, гаммирования с обратной связью по выходу, гаммирования с обратной связью по шифротексту, простой замены с зацеплением и выработки имитовставки) выведены в отдельный стандарт ГОСТ Р 34.13—2015, что соответствует принятой международной практике. Эти режимы применимы как к шифру «Магма», так и к новому шифру «Кузнечик».

• [1] Осуществляется побитовый циклический сдвиг влево на 11 битов. Расшифрование осуществляется по этой же схеме, но с другим расписаниемиспользования ключей: • с 1-го по 8-й раунд расшифровки — в прямом порядке: • с 9-го по 32-й раунд расшифровки — в обратном порядке: По сравнению с шифром DES у ГОСТ 28 147–89 есть следующие достоинства: • существенно более длинный ключ (256 бит против 56 у шифра DES), атака на который путем полного перебора ключевого множества на данныймомент представляется невыполнимой; • простое расписание использования ключа, что упрощает реализациюалгоритма и повышает скорость вычислений. Проектирование S-блоков ГОСТ 28 147–89. Очевидно, что схема алгоритма ГОСТ 28 147–89 весьма проста. Это означает, что наибольшая нагрузка по шифрованию ложится именно на таблицы замен. Значения таб-
• [2] Жданов О. //., Чалкип Т. А., Чурмаптаев Д. М. Алгоритмы блочного шифрования: учеб, пособие. Красноярск: СибГАУ, 2010.
• [3] Жданов О. Н. Методика выбора ключевой информации для алгоритма блочного шифрования. М.: ИНФРА-М, 2015; Зайко Ю. Я. Криптография глазами физика // Известия Саратовского университета. 2009. Т. 9. Сер. Физика. Вып. 2. С. 34—48.
• [4] Алексеев Е. К., Смышляев С. В. ГОСТ 28 147–89: «Не спеши его хоронить». Ч. 1. Стойкость алгоритма. URL: http://www.cryptopro.ru/blog/2013/08/27/gost-28 147−89-nc-speshi-ego-khoronit-chast-1 -stoikost-algoritma
• [5] Rudskoy V. On zero practical significance of «Key recovery attack on full GOST block cipherwith zero time and memory». URL: http://eprint.iacr.org/2010/lll.pdf
• [6] Панасепко С. П. Алгоритмы шифрования: специальный справочник. СПб.: БХВ-Петер-бург, 2009.
• [7] Kara О. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
• [8] Российский стандарт шифрования: стойкость снижена. URL: http://cryptofaq.ru/index.php/2010;12−23−18−20−21/2010;12−23−18−22−09/90−2011;02−01−07−47−27
• [9] Ачексеев Е. К., Смышляев С. В. ГОСТ 28 147–89: «Не спеши его хоронить».