Гост 28147 89 сколько слабых ключей

ГОСТ 28147-89 (Часть 1. Введение и общие принципы)

Очень часто на Хабре встречаются статьи о сути, программных реализациях, вскрытиях шифров. Но непонятно одно: почему среди них нет наших, отечественных алгоритмов шифрования?

Я решил исправить это, написав повесть статью, разбитую на 5 частей для лучшего восприятия о стандарте ГОСТ 28147-89. Каждая часть, кроме первой (описывает схему алгоритма и общие принципы), повествует о каждом из четырех возможных режимах работы стандарта с приложением к ним кода на C++.

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

ГОСТ 28147-89 является отечественным блочным шифром. То есть открытый текст разбивается на блоки (в данном случае 64 бита), и каждый блок преобразовывается отдельно.

В основу алгоритма положена сеть Фейстеля, представленная на рисунке ниже.

Поясню работу данной схемы.

1. Каждый блок разбивается на два «подблока» (левый и правый, соотвественно).
2. Исходное заполнение правого блока записывается в левый блок на выходе.
3. Над правым блоком производится криптографическое преобразование с применением ключевых данных.
4. Левый (исходный) и правый (преобразованный) блоки складываются по модулю 2 в сумматоре по модулю 2.
5. Так повторяется несколько раз.

Структурная схема алгоритма

Данная схема содержит:

• Четыре накопителя по 32 бита: N₁, N₂, N₃, N₄.
• Два 32-разрядных накопителя: N₅ и N₆, — с записанными в них постоянными заполнениями C₂ и C₁ соответственно.
• Ключевое запоминающее устройство (КЗУ) на 256 бит. КЗУ состоит из восьми накопителей по 32 разряда каждый: X₀, X₁, X₂, X₃, X₄, X₅, X₆, X₇.
• 32-разрядный сумматор по модулю 2: СМ₂.
• Еще один сумматор по модулю 2, который не имеет ограничения на разрядность (но используется 64 бита): СМ₅.
• Два сумматора по модулю 2 32 разрядности 32 бита: СМ₁, СМ₃.
• Сумматор по модулю (2 32 -1): СМ₄.
• Блок подстановки К: восемь узлов замены K₁, K₂, K₃, K₄, K₅, K₆, K₇, K₈, каждый с памятью на 64 бита.
• Регистр циклического сдвига влево на 11 бит R.

Ключи

В КЗУ

КЗУ отведено 256 бит, в ГОСТ 28147-89 используется ключ длиной 256 бит. Ключ разбивается на восемь блоков по 32 бита, и каждый бит каждого блока последовательно вводится в накопитель X соответствующего порядка.

То есть, 1-й бит ключа вводится в 1-й разряд накопителя X₀, 2-й — во 2-й разряд накопителя X₀, 33-й — в 1-й разряд накопителя X₁, 65-й — в 1-й разряд накопителя X₂, и так далее, 224-й бит ключа вводится в 1-й разряд накопителя X₇, 256-й бит ключа вводится в 32-й разряд накопителя X₇.

Считывается же ключ в соответствии с выбранным режимом работы алгоритма, но в следующих частях статьи.

В блоке подстановки K

Блок подстановки содержит в себе таблицу замены размерностью 16×8, которая является долговременным ключом.

Строки таблицы определяют, грубо говоря, что требуется заменить (число от 0 до 15 в шестнадцатиричной системе счисления). Столбцы же указывают, на что заменять. При этом поступающий 32-битовый в блок вектор разбивается на восемь 4-х битовых, каждый из которых и преобразуется в соответствии с таблицой замены.

Ключи как в КЗУ, так и в блоке К, являются секретными, и требуются меры по недопущению их компрометации.

Режимы работы

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

UPD: Следующая часть статьи «Режим простой замены» доступен по ссылке.

2.2. Стандарт шифрования гост 28147-89

ГОСТ 28147-89 — советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название — «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки).

Принцип работы алгоритма

Алгоритм принципиально не отличается от DES. В нем также происходят циклы шифрования (их 32) по схеме Фейстеля (Рис. 2.9.).

Рис. 2.9. Раунды шифрования алгоритма ГОСТ 28147-89.

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k₁…k₈. Ключи k₉…k₂₄ являются циклическим повторением ключей k₁…k₈ (нумеруются от младших битов к старшим). Ключи k₂₅…k₃₂ являются ключами k₁…k₈, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A₃₃ и B₃₃ склеиваются (следует обратить внимание на то, что старшим битом становится A₃₃, а младшим — B₃₃) – результат есть результат работы алгоритма.

Функция f(A_i,K_i) вычисляется следующим образом: A_i и K_i складываются по модулю 2 32 , затем результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, т. е. столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д. Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов. Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, т.е. разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовала используемые в Интернет узлы замены.

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

Режимы работы алгоритма ГОСТ 28147-89

Алгоритм ГОСТ 28147-89 имеет четыре режима работы.

1.Режим простой замены принимает на вход данные, размер которых кратен 64-м битам. Результатом шифрования является входной текст, преобразованный блоками по 64 бита в случае зашифрования циклом «32-З», а в случае расшифрования — циклом «32-Р».

2.Режим гаммирования принимает на вход данные любого размера, а также дополнительный 64-битовый параметр — синхропосылку. В ходе работы синхропосылка преобразуется в цикле «32-З», результат делится на две части. Первая часть складывается по модулю 2 32 с постоянным значением 1010101₁₆. Если вторая часть равна 2 32 -1, то её значение не меняется, иначе она складывается по модулю 2 32 -1 с постоянным значением 1010104₁₆. Полученное объединением обеих преобразованных частей значение, называемое гаммой шифра, поступает в цикл «32-З», его результат порязрядно складывается по модулю 2 с 64-разрядным блоком входных данных. Если последний меньше 64-х разрядов, то лишние разряды полученного значения отбрасываются. Полученное значение подаётся на выход. Если ещё имеются входящие данные, то действие повторяется: составленный из 32-разрядных частей блок преобразуется по частям и так далее.

3.Режим гаммирования с обратной связью также принимает на вход данные любого размера и синхропосылку. Блок входных данных поразрядно складывается по модулю 2 с результатом преобразования в цикле «32-З» синхропосылки. Полученное значение подаётся на выход. Значение синхропосылки заменяется в случае зашифрования выходным блоком, а в случае расшифрования — входным, то есть зашифрованным. Если последний блок входящих данных меньше 64 разрядов, то лишние разряды гаммы (выхода цикла «32-З») отбрасываются. Если ещё имеются входящие данные, то действие повторяется: из результата зашифрования заменённого значения образуется гамма шифра и т.д.

4.Режим выработки имитовставки принимает на вход данные, размер которых составляет не меньше двух полных 64-разрядных блоков, а возвращает 64-разрядный блок данных, называемый имитовставкой. Временное 64-битовое значение устанавливается в 0, далее, пока имеются входные данные, оно поразрядно складывается по модулю 2 с результатом выполнения цикла «16-З», на вход которого подаётся блок входных данных. После окончания входных данных временное значение возвращается как результат.

Криптоанализ шифра

В шифре ГОСТ 28147-89 используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время компьютере общего применения нельзя подобрать ключ за время, меньшее многих сотен лет. Российский стандарт ГОСТ 28147-89 проектировался с большим запасом и по стойкости на много порядков превосходит американский стандарт DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 .

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

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

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

Таблица замен является долговременным ключевым элементом, то есть действует в течение гораздо более длительного срока, чем отдельный ключ. Предполагается, что она является общей для всех узлов шифрования в рамках одной системы криптографической защиты. От качества этой таблицы зависит качество шифра. При «сильной» таблице замен стойкость шифра не опускается ниже некоторого допустимого предела даже в случае ее разглашения. И наоборот, использование «слабой» таблицы может уменьшить стойкость шифра до недопустимо низкого предела. Никакой информации по качеству таблицы замен в открытой печати России не публиковалось, однако существование «слабых» таблиц не вызывает сомнения — примером может служить «тривиальная» таблица замен, по которой каждое значение заменяется на него самого. В ряде работ ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.16

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 2.25. Режим выработки имитовставки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Анализ алгоритма ГОСТ 28147-89: поиск слабых блоков Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Бабенко Людмила Климентьевна, Ищукова Евгения Александровна

Рассмотрено влияние S-блоков замены на устойчивость алгоритма шифрования ГОСТ 28147-89 (далее по тексту ГОСТ) к методу линейного криптоанализа . Представлен детальный, программно ориентированный универсальный алгоритм поиска слабых блоков замены по отношению к методу линейного криптоанализа . Показана возможность построения эффективных линейных статистических аналогов для упрощенной версии алгоритма ГОСТ, содержащего слабые S-блоки. Данное исследование направлено на предотвращение использования слабых блоков замены для тех алгоритмов блочного шифрования, в которых данные элементы не являются фиксированными. Работа разработанного алгоритма поиска слабых блоков была опробована на примере анализа блоков замены для алгоритма шифрования ГОСТ 28147-89 . Применение разработанного алгоритма позволяет без труда обнаружить большое число ослабленных блоков замены , использование которых может значительно ослабить стойкость используемого алгоритма шифрования. Использование данного алгоритма может быть полезно для тех, кто пользуется данным шифром, но не владеет навыками криптоанализа.

Похожие темы научных работ по математике , автор научной работы — Бабенко Людмила Климентьевна, Ищукова Евгения Александровна

ANALYSIS OF ALGORITHM GOST 28147-89: RESEARCH OF WEAK S-BOXES

This work is devoted to finding the influence of S-Boxes to resistance of GOST 28147-89 algorithm ( GOST ) against linear cryptanalysis . The universal algorithm for searching particular layouts of S-Boxes, which are vulnerable to linear cryptanalysis is presented. The possibility of building of efficient linear statistical analogs for simplified GOST with weak S-Boxes has been shown. This research is aimed to ensuring that certain arbitrary S-Box layouts are not weak when they are not fixed. Applicability of the presented method was tested by analyzing S-Boxes used in GOST . Application of the designed method made it possible to discover a number of weak S-Boxes, which make the overall cryptographic strength of GOST much lower.

Текст научной работы на тему «Анализ алгоритма ГОСТ 28147-89: поиск слабых блоков»

Раздел IV. Методы и средства криптографии и стеганографии

Л.К. Бабенко, Е.А. Ищукова АНАЛИЗ АЛГОРИТМА ГОСТ 28147-89: ПОИСК СЛАБЫХ БЛОКОВ*

Рассмотрено влияние S-блоков замены на устойчивость алгоритма шифрования ГОСТ 28147-89 (далее по тексту ГОСТ) к методу линейного криптоанализа. Представлен детальный, программно ориентированный универсальный алгоритм поиска слабых блоков замены по отношению к методу линейного криптоанализа. Показана возможность построения эффективных линейных статистических аналогов для упрощенной версии алгоритма ГОСТ, содержащего слабые S-блоки. Данное исследование направлено на предотвращение использования слабых блоков замены для тех алгоритмов блочного шифрования, в которых данные элементы не являются фиксированными. Работа разработанного алгоритма поиска слабых блоков была опробована на примере анализа блоков замены для алгоритма шифрования ГОСТ 28147-89. Применение разработанного алгоритма позволяет без труда обнаружить большое число ослабленных блоков замены, использование которых может значительно ослабить стойкость используемого алгоритма шифрования. Использование данного алгоритма может быть полезно для тех, кто пользуется данным шифром, но не владеет навыками криптоанализа.

Симметричные алгоритмы шифрования; анализ стойкости; сеть Фейстеля; ГОСТ 28147-89; раундовые ключи шифрования; блок замены; линейный криптоанализ.

L.K. Babenko, E.A. Ischukova

ANALYSIS OF ALGORITHM GOST 28147-89: RESEARCH OF WEAK S-BOXES

This work is devoted to finding the influence of S-Boxes to resistance of GOST 28147-89 algorithm (GOST) against linear cryptanalysis. The universal algorithm for searching particular layouts of S-Boxes, which are vulnerable to linear cryptanalysis is presented. The possibility of building of efficient linear statistical analogs for simplified GOST with weak S-Boxes has been shown. This research is aimed to ensuring that certain arbitrary S-Box layouts are not weak when they are not fixed. Applicability of the presented method was tested by analyzing S-Boxes used in GOST. Application of the designed method made it possible to discover a number of weak S-Boxes, which make the overall cryptographic strength of GOST much lower.

GOST; S-Box; secret key; linear cryptanalysis; probability.

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

Работа выполнена при поддержке грантов РФФИ №12-07-33007_мол_а_вед, № 12-07-00037-а.

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

Наше исследование направлено на изучение стойкости к методу линейного криптоанализа алгоритма ГОСТ, определенного в качестве государственного стандарта в Российской Федерации. До сих пор в открытой печати имеется сравнительно мало информации о возможных уязвимостях данного шифра. Отличительной чертой алгоритма ГОСТ является использование в его структуре нефиксированных блоков замены. Предполагается, что при любом заполнении S-блоков тридцати двух раундов шифрования будет достаточно для того, чтобы противостоять таким мощным методам анализа, как линейный и дифференциальный криптоанализ. Долгое время считалось, что если оставлять S-блоки в секрете, то их можно рассматривать как дополнительный ключевой материал [2]. Однако в работе [3] предложен метод, применение которого позволяет достаточно просто восстановить значения S-блоков, используемых для шифрования данных. В настоящей работе предлагается рассмотреть влияние блоков замены на устойчивость алгоритма ГОСТ к методу линейного криптоанализа. Для этого предлагается разработанный нами универсальный алгоритм поиска блоков, использование которых может значительно ослабить стойкость алгоритма ГОСТ. Исследование преследует две цели. Во-первых, необходимо получить инструмент для быстрого определения полного списка слабых блоков по отношению в линейному криптоанализу для исследования их влияния на стойкость ГОСТ. Во-вторых, при использовании нашего алгоритма можно легко получить полный список блоков, не рекомендованных к использованию для алгоритма ГОСТ, что может быть полезно для тех, кто пользуется данным шифром, но не владеет навыками криптоанализа.

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

Метод линейного криптоанализа впервые предложен в начале 90-х годов XX века японским ученым М. Матсуи (Matsui). В работе [1] М. Матсуи показал, как можно осуществить атаку на алгоритм шифрования DES, сократив сложность анализа до 247. Существенным недостатком метода стала необходимость иметь в наличии большой объем данных, зашифрованных на одном и том же секретном ключе, что делало метод малопригодным для практического применения к вскрытию шифра. Однако, если предположить, что к аналитику в руки попал шифрованный текст, содержащий важные сведения, а также некий черный ящик (устройство или программа), который позволяет выполнить любое число текстов, зашифрованных с помощью известного алгоритма шифрования на секретном ключе, не раскрывая при этом самого ключа, то применение метода линейного криптоанализа становится вполне реальным. Многие алгоритмы шифрования, известные на момент опубликования работы [1], в последствии были проверены на устойчивость к этому методу и не все из них оказались достаточно стойкими и, как следствие, потребовали доработки.

Любой алгоритм шифрования в самом общем виде можно представить как некоторую функцию E, зависящую от входного сообщения Х, секретного ключа К и возвращающую шифрованное сообщение Y:

Зная само преобразование Е и входное сообщение Х, нельзя однозначно сказать каким будет выходное сообщение Y. В данном случае нелинейность функции зависит от внутренних механизмов преобразования Е и секретного ключа К.М. Матсуи показал, что существует возможность представить функцию шифрования в виде системы

уравнений, которые выполняются с некоторой вероятностью р. При этом для успешного проведения анализа вероятность уравнений р должна быть как можно дальше удалена от значения 0,5.

Так как уравнения, получаемые в ходе анализа криптоалгоритма, являются вероятностными, то их называют линейными статистическими аналогами. Линейным статистическим аналогом нелинейной функции шифрования (1) называется величина Р, равная сумме по модулю два скалярных произведений входного вектора Х, выходного вектора Y и вектора секретного ключа К соответственно с двоичными векторами а, в и у, имеющими хотя бы одну координату равную единице:

в том случае, если вероятность того, что Р=0 отлична от 0,5 (Р(Р=0)^0,5).

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

где р — вероятность, с которой выполняется линейный аналог.

Отклонение определяет эффективность линейного статистического аналога. Чем отклонение больше, тем выше вероятность успешного проведения анализа. Фактически отклонение показывает насколько вероятность статистического аналога отдалена от значения р = 0,5.

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

на одном и том же секретном ключе. Определить ключ (или некоторые биты ключа) путем анализа статистических данных с помощью линейных аналогов.

Первый шаг анализа заключается в нахождении эффективных статистических аналогов. Для алгоритмов шифрования, в которых все блоки заранее известны, этот шаг можно выполнить единожды, основываясь на анализе линейных свойств всех криптографических элементов шифра. Для алгоритма ГОСТ такой подход неприемлем, в связи с использованием нефиксированных S-блоков. То есть данный этап анализа каждый раз при смене используемых S-блоков необходимо повторять сначала. В результате анализа должна быть получена система уравнений, выполняющихся с некоторыми вероятностями. Левая часть уравнений должна содержать в себе сумму битов входного и выходного сообщения, правая часть уравнения — биты секретного ключа. Если первый шаг анализа является чисто теоретическим и полностью зависит от структуры алгоритма, то второй шаг — является исключительно практической частью, которая заключается в анализе известных пар открытый-закрытый текст с помощью полученной ранее системы статистических аналогов. Для этого используется следующий алгоритм.

Алгоритм. Пусть N — число всех открытых текстов и Т — число открытых текстов, для которых левая часть линейного статистического аналога равна 0. Рассмотрим два случая.

1. Если Т> N/2, то в этом случае число открытых текстов, для которых левая часть аналога равна нулю, больше половины, то есть в большинстве случаев в левой части аналога появляется значение, равное нулю, то

а) если вероятность этого линейного статистического аналога р >1/2, это говорит о том что в большинстве случаев правая и левая части аналога равны, а значит левая часть аналога, содержащая биты ключа, равна 0.

б) если вероятность этого линейного статистического аналога р < 1/2, это говорит о том что в большинстве случаев правая и левая части аналога не равны, а значит левая часть аналога, содержащая биты ключа, равна 1.

2. Если Т< N/2, то в этом случае число открытых текстов, для которых левая часть аналога равна нулю, меньше половины, то есть в большинстве случаев в левой части аналога появляется значение, равное единице, то

а) если вероятность этого линейного статистического аналога р >1/2, это говорит о том что в большинстве случаев правая и левая части аналога равны, а значит левая часть аналога, содержащая биты ключа, равна 1.

б) если вероятность этого линейного статистического аналога р < 1/2, это говорит о том что в большинстве случаев правая и левая части аналога не равны, а значит левая часть аналога, содержащая биты ключа, равна 0.

На сегодняшний день нет достаточно подробных исследований стойкости алгоритма шифрования ГОСТ к методу линенйого криптоанализа. Однако в книге Б. Шнайера [4] говорится о том, что за счет большого числа раундов шифрования линейный криптоанализ практически не применим к полнораундовому альгоритму ГОСТ.

Описание алгоритма ГОСТ. Алгоритм шифрования ГОСТ 28147-89 является государственным стандартом Российской Федерации. Его использование обязательно для шифрования данных в государственных организациях РФ. Алгоритм ГОСТ является симметричным блочным шифром, построенным по схеме Фейсте-ля (Feistel). На вход алгоритма поступает 64-битовый блок данных, который под воздействием 256-битового ключа преобразуется в 64-битовый блок шифрованных данных. В каждом раунде правая часть шифруемого сообщения поступает на вход функции F, где преобразуется с использованием трех криптографических операций: сложения данных с раундовым подключом по модулю 232, замена данных с использованием S-блоков, циклический сдвиг влево на 11 позиций. Выход функции Б складывается по модулю 2 с левой частью шифруемого сообщения, после чего правая и левая части меняются местами. Алгоритм содержит 32 раунда, в последнем раунде шифрования правая и левая части местами не меняются. Структура алгоритма ГОСТ приведена на рис. 1.

В алгоритме шифрования ГОСТ используется 8 S-блоков, которые преобразуют 4 бита на входе в S-блок в 4 бита на выходе. В отличие от большинства алгоритмов шифрования ГОСТ не имеет фиксированных блоков замены и может использовать любые варианты блоков.

Секретный ключ шифрования содержит 256 битов и представляется в виде последовательности из восьми 32-битовых слов: К1, К2, К3, К4, К5, К6, К7, К8. В каждом раунде шифрования в качестве раундового подключа используется одно из этих 32-битовых слов. При определения раундового подключа руководствуются следующим принципом: с 1 по 24 раунды используются последовательно К1, К2, К3, К4, К5, К6, К7, К8, К1, К2 и т.д. С 25 по 32 раунды: К8, К7, К6, К5, К4, К3, К2, К1.

Таким образом, получается, что в первом и последнем раундах используется один и тот же раундовый подключ К1.

Несмотря на то, что алгоритм ГОСТ является «старичком» в криптографии и насчитывает более 20 лет, в настоящее время можно найти сравнительно мало литературы, посвященной вопросам анализа данного алгоритма шифрования. Отчасти это связано с тем, что первое время алгоритм был засекречен и стал доступен широкой общественности только после 1994 г. Кроме того, до появления работы [3] считалось, что S-блоки могут служить дополнительным ключом, что существенно затрудняло проведение анализа.

Функция Р(раунд і ) Вход

Секретный ключ, 256 битов:

Рис. 1. Алгоритм шифрования ГОСТ

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

Очень часто изучение слабых свойств алгоритма шифрования начинают с исследования его упрощенных моделей [5]. Для алгоритма ГОСТ помимо использования нефиксированных S-блоков выделяют еще два момента, которые затрудняют проведение анализа алгоритма: это использование операции целочисленного сложения по модулю 232, которая используется для сложения данных с секретным ключом, и использование раундовых подключей в обратном порядке для последних 8 раундов шифрования. В [5] приводятся результаты анализа упрощенной версии алгоритма ГОСТ. Для алгоритма GOST-H изменен порядок следования раун-довых подключей в последних 8 раундах, то есть они также используются последовательно с К1 по К8. Показано, что модифицированный алгоритм гораздо слабее исходного и обладает рядом слабых ключей. Вариант упрощенной версии алгоритма ГОСТ, в которой операция целочисленного сложения заменена на операцию сложения по модулю два и количество раундов сокращено до 20, рассмотрен известными специалистами в области криптографии А. Бирюковм и Д. Вагнером [7].

Алгоритм поиска слабых блоков. Алгоритм ГОСТ содержит 8 S-блоков. При этом сами блоки не являются фиксированными. То есть теоретически считается, что могут быть использованы блоки замены, сформированные случайным образом. Криптографическую стойкость алгоритму должно обеспечить достаточно большое число раундов шифрования (32 раунда). Долгое время считалось, что если держать S-блоки в секрете, то можно рассматривать их как дополнительный ключевой материал. Однако в работе [5] было показано, что S-блоки, используемые в алгоритме шифрования, можно достаточно просто восстановить.

В связи с этим разумно рассмотреть слабые 8-блоки для алгоритма ГОСТ и оценить степень сложности атаки на основе линейного криптоанализа при их использовании.

Итак, какие же блоки необходимо считать слабыми и как их получить? Для того, чтобы ответить на этот вопрос, необходимо вспомнить о двух вещах. Во-первых, итоговая вероятность аналога будет получена, исходя из значения вероятностей для каждого S-блока, вовлеченного в процесс построения аналога. Так как в алгоритма ГОСТ используется 32 раунда шифрования, то для получения максимальной вероятности аналога желательно производить его построение так, чтобы в каждом раунде было задействовано минимальное количество S-блоков, в идеале это должен быть всего один S-блок. Во-вторых, необходимо вспомнить, что в качестве перемешивания битов в каждом раунде используется операция циклического сдвига влево на 11 позиций. Таким образом получается, что биты на выходе одного блока поступают входы двух блоков в следующем раунде. Кроме того, необходимо отметить, что слабые блоки могут быть организованы таким образом, что будут позволять конструировать линейные аналоги, вероятность которых равна нулю или единице. Таким образом, можно предположить, что слабыми блоками будут являться те блоки, которые будут позволять строить линейные аналоги для значений входов и выходов, содержащих минимальное количество единиц, то есть для значений 1, 2, 4, 8. Также слабыми будут являться те блоки, которые для любого входного значения позволят построить аналог, вероятность которого будет равна нулю или единице.

Определив критерии для отбора слабых S-блоков, мы задумались о том, каким образом нам лучше всего попробовать получить эти самые блоки. Так как на вход S-блока алгоритма ГОСТ поступает 4 бита, которые заменяются также на 4 бита, то всего возможно 16! различных комбинаций таких блоков, что соответствует примерно 2442. Перебор такого количества блоков весьма трудоемок и длителен, даже при использовании распределенных многопроцессорных вычислений. Вариант случайной генерации блока и его последующей оценки нами также был отвергнут, как не позволяющий получить полный набор необходимых нам блоков за приемлемое время. Вместо этого нами был разработан новый универсальный алгоритм поиска слабых блоков по отношению к линейному анализу. Рассмотрим его более детально.

Для начала вспомним, что для алгоритма ГОСТ на вход каждого блока замены поступает часть преобразованного входного сообщения Х, сложенная по модулю два с частью секретного ключа. Таким образом, получается, что биты сообщения Х и биты ключа К неразрывно связаны, а значит к ним всегда должен быть применен один и тот же вектор, например вектор а. В связи с этим мы можем преобразовать выражение (1) для линейного статистического аналога к виду:

По определенным ранее условиям, нам необходимо, чтобы при составлении аналога было задействовано как можно меньше блоков. Поэтому, мы предлагаем рассматривать такой вариант, когда при составлении аналога будет задействован всего один бит входного сообщения X (и соответствующий ему бит ключа К. Далее мы будем опускать значение битов ключа К, полагая что оно неразрывно связано со значением используемого бита значения Х) и всего один бит сообщения Y. И дальше рассматривать все возможные комбинации Хі ©У] для і=1. 4 и для j=1. 4. Так как нам необходимо рассмотреть все возможные комбинации блоков замен, а мы заранее не знаем какая пара значений вход-выход позволит нам получить искомый результат, то для каждого входа мы составляем таблицу размерностью 16х24. Всего у нас будет 16 таких таблиц, по одной таблице для каждого входа. В каждую таблицу заносим биты одного входа, все возможные биты выхода, а также все рассматриваемые комбинации Хі © У] для значений і=1. 4; j=1. 4. В табл. 1 приведен пример построения такой таблицы для первого рассматриваемого входа Х = 0.

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

Nmin — значение, которое соответствует искомому минимальному количеству линейных аналогов, выполняемых с вероятностью 0 или 1.

Combi — очередное возможные сочетание Nmin элементов из 16 возможных (взятое из ячеек в столбцах под номерами 9 — 24). Всего таких рассматриваемых сочетаний будет

Qvalue — значение, которое отражает чему должно быть равно значение Q для каждой из позиции в сочетании Combi

Для того, чтобы стало немного понятнее, рассмотрим как будут соотноситься эти три значения между собой на примере табл. 1. Пусть Nmin = 5; Qvalue = 12. Например, для первой строки табл. 1, соответствующей паре (X,Y)=(0000, 0000) ни одно из сочетаний ячеек не даст значения Qvalue = 01100. То же самое справедливо и для последней строки табл. 1, соответствующей паре (X,Y)=(1111, 1111). Для всех остальных таблиц возможно получить сочетания ячеек в строке такое, которое будет соответствовать значению Qvalue = 01100. На рис. 2 для примера представлен один из вариантов (но не единственно возможный. ) комбинаций ячеек для строк 2 и 8.

Если во всех других таблицах сочетание данных ячеек таблицы совпадет со значением Qvalue, и при этом не произойдет перекрытие значений выходов, то значения X-Y соответствующей строки в каждой из 16 таблиц будут отражать работу искомого блока замены. Таким образом, для нахождения всех возможных вариантов заполнения блоков замены, отвечающих условиям слабого блока, необходимо для каждого значения Qvalue перебрать все возможные комбинации ячеек Comb.

Nmin = б Qvalue=1210= 011002

В общем виде вышеописанный алгоритм сводится к выполнению следующих шагов:

1. Инициализация значения Nmin;

3. Определение очередного значения Comfy;

4. Определение строк в каждой из 16 таблиц, для которых ячейки комбинации строк совпадают со значением Qvalue;

5. Если в каждой таблице есть строка, для которой Comb = Qvalue и при этом нет перекрытия значений выходов (то есть номера выбранных строк в каждой из 16 анализируемых таблиц разные), то искомая таблица найдена;

7. если (i < C), то переход к пункту 3;

9. если (Qvalue < 2Nmm), то переход к пункту 3.

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

Результаты экспериментов. Алгоритм, представленный выше, был реализован и опробован на практике. Полный анализ выполняется в течение нескольких минут (все исследования проводились на процессоре Intel Celeron M CPU 530 1.73 GHz, RAM 1007Mb). В ходе эксперимента варьировался критерий слабого блока по минимальному количеству экстремумов, которое необходимо найти. Результаты экспериментов представлены в табл. 2.

Номер эксперимента Минимальное количество экстремумов Количество найденных слабых блоков

Как видно из табл. 2, при увеличении числа искомых экстремумов количество найденных блоков уменьшается. Однако при этом уменьшается и стойкость обнаруживаемых блоков замены.

я „ > р > ? © © © і © © з > © й © © * р © © й > © а © ©

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 і [о! і; 0 0 м 1) 0 і , 11 0 0 0 1

0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1

0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

0 0 0 0 0 1 0 I 0 0 ] 0 0 0 1 0 1

0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 ] 0 ї 1

0 0 0 0 0 1 1 0 1 1 SL 1 і а. ft,. 1 1 1 1

0 0 0 0 0 1 1 1 0 1 1 1' ,oJ J< ,0 ,1 і .°к 1 1 11 *0.! 1 1 1

0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0

0 0 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 1 0 1

0 0 0 0 1 0 1 1 0 1 1 0 1 0 І 0 1 1 0 1

0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1

0 0 0 0 1 L 1 I 1 1 0 0 І 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 І 1 1 1 1

0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1

0 0 0 0 1 1 1 ] ] I 1 1 1 ] 1 1 І І 1 ] 1 1 1 1

Рис. 2. Анализ таблиц

Для более наглядного примера, рассмотрим одну из таблиц замены (табл. 3), полученную в результате использования предложенного нами алгоритма анализа.

Слабый блок замены, определенный в результате работы предложенного

Вход 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Выход 15 7 11 3 13 5 9 1 14 6 10 2 12 4 8 0

Блок замены в табл. 3 имеет таблицу анализа, отражающую возможность построения линейных аналогов для линейного криптоанализа, предствленную в табл. 4.

Таблица анализа полученного S-блока

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1 8 8 8 8 8 8 8 0 8 8 8 8 8 8 8

2 8 8 8 0 8 8 8 8 8 8 8 8 8 8 8

3 8 8 8 8 8 8 8 8 8 8 8 16 8 8 8

4 8 0 8 8 8 8 8 8 8 8 8 8 8 8 8

5 8 8 8 8 8 8 8 8 8 16 8 8 8 8 8

6 8 8 8 8 8 16 8 8 8 8 8 8 8 8 8

7 8 8 8 8 8 8 8 8 8 8 8 8 8 0 8

8 0 8 8 8 8 8 8 8 8 8 8 8 8 8 8

9 8 8 8 8 8 8 8 8 16 8 8 8 8 8 8

10 8 8 8 8 16 8 8 8 8 8 8 8 8 8 8

11 8 8 8 8 8 8 8 8 8 8 8 8 0 8 8

12 8 8 16 8 8 8 8 8 8 8 8 8 8 8 8

13 8 8 8 8 8 8 8 8 8 8 0 8 8 8 8

14 8 8 8 8 8 8 0 8 8 8 8 8 8 8 8

15 8 8 8 8 8 8 8 8 8 8 8 8 8 8 16

Из табл. 4 можно видеть, что в найденной таблице экстремумов гораздо больше минимального числа. Это связано с тем, что рассматриваются только те входы и выходы, которые содержат в своем составе одну единицу, то есть это значения 1, 2, 4, 8. Использование такого блока анализа крайне не желательно, так как будет заметно ослаблять свойства используемого алгоритма шифрования.

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

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

1. Matsui M. Linear Cryptanalysis Method for DES Cipher, Advances in Cryptology -EUROCRYPT’93, Springer-Verlag, 1998. — 386 p.

2. Popov V., Kurepkin I., Leontiev S. Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.Ю-94, GOST R 34.Ю-2оо1, and GOST R 34.11-94 Algorithms. — January 2ооб. — http://www.ietf.org/rfc/rfc4357.

3. Saarien M.-J. A Chosen Key Attack Against the Secret S-boxes of GOST // http://www.rn.-js.com — Helsinki University of Technology, Finland.

4. Schneier B. Applied Cryptography, Protocols, Algorithms and Source Code in C (Second Edition). John Wiley and Sons, Inc. 1996.

5. Oreku G.S., Li J., Pazynyuk T., Mtenzi F.J. Modified S-box to Archive Accelerated GOST // http://paper.ijcsns.org, International Journal of Computer Science and Network Security. — June 2оо7. — Vol. 7, № 6.

6. Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems, Extended Abstract, Crypto^, Springer-Velgar, 1998. — P. 2.

7. BirukovA., WagnerD. Advanced Slide Attacks // http://citeseer.ist.psu.edu.

8. Babenko L.K., Ishchukova E.A., Maro E.A. Theory and Practice of Cryptography Solutions for Secure Information Sysmems. GOST Encryption Algorithm and Approaches to its Analysis. IGI Global book series Advances in Information Security, Privacy, and Ethics (AISPE) Book Series, USA, 2о13. — Р. 34-62.

9. Babenko L.K., Ishchukova E.A., Maro E.A. Research about Strength of GOST 28147-89 Encryption Algorithm. — Proceedings of the 5th international conference on Security of information and networks (SIN 2о12). — ACM, New York, NY, USA, 2о12. — Р. 138-142.

10. Babenko L.K., Ishchukova E.A. Differential Analysis of GOST Encryption Algorithm. — Proceedings of the 3rd International Conference of Security of Information and Networks (SIN 2оЮ). — ACM, New York, NY, USA, 2о1о. — P. 149-157.

Статью рекомендовал к опубликованию д.т.н., профессор Я.Е. Ромм.

Бабенко Людмила Климентьевна — Южный федеральный университет; e-mail: blk@fib.tsure.ru; 347928, г. Таганрог, ул. Чехова, 2, корпус "И"; тел.: 88634312018; кафедра безопасности информационных технологий; профессор.

Ищукова Евгения Александровна — e-mail: jekky82@mail.ru; тел.: 88634371905; кафедра безопасности информационных технологий; доцент.

Babenko Lyudmila Klimentevna — Southern Federal University; e-mail: blk@fib.tsure.ru; Block “I”, 2, Chehov street, Taganrog, 347928, Russia; phone: +78634312о18; the department of security of information technologies; professor.

Ischukova Evgeniya Aleksandrovna — e-mail: jekky82@mail.ru; phone: +786343719о5; the department of security of information technologies; associate professor.

Л.К. Бабенко, Е.А. Ищукова

ИСПОЛЬЗОВАНИЕ СЛАБЫХ БЛОКОВ ЗАМЕНЫ ДЛЯ ЛИНЕЙНОГО КРИПТОАНАЛИЗА БЛОЧНЫХ ШИФРОВ*

Работа является продолжением исследований влияния используемых слабых S-блоков на возможность проведения атаки с помощью метода линейного криптоанализа для алгоритма шифрования ГОСТ 28147-89. Ранее авторами статьи разработан универсальный алгоритм поиска блоков замены, ослабленных по отношению к методу линейного криптоа-

Работа выполнена при поддержке грантов РФФИ №12-о7-31120_мол_а, №12-о7-33007_мол_а_вед, № 12-о7-ооо37-а.