В нашей стране установлен единый алгоритм криптографического представления данных для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексов и ЭВМ, который определяется ГОСТ 28147-89 .
Этот алгоритм криптографического преобразования данных представляет собой 64-битовый блочный алгоритм с 256-битовым ключом, предназначен для аппаратной и программной реализации, удовлетворяет криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации.
При описании алгоритма используются следующие обозначения:
L и R - последовательности битов;
LR - конкатенация последовательностей L и R, в которой биты
последовательности R следуют за битами последовательности L;
(+) - поразрядное сложение по модулю 2 (операция "исключающее ИЛИ");
[+] - сложение 32-разрядных чисел по модулю 2 32 ;
{+} - сложение 32-разрядных чисел по модулю 2 32 -1.
Числа суммируются по следующему правилу:
A [+] B = A + B, если A + B < 2 32 ,
A [+] B = A + B - 2 32 , если A + B >= 2 32 .
A {+} B = A + B , если A + B < 2^32 - 1,
A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.
Алгоритм предусматривает четыре режима работы:
В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей K i:
K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .
Расшифрование выполняется по тому же ключу, что и шифрование, но этот
процесс является инверсией процесса шифрования данных.
Режим простой замены
Первый и самый простой режим - замена . Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T 0 включает 32 цикла (j=1...32).
Блок T 0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) - левые или старшие биты, A(0) - правые или младшие биты.
Эти последовательности вводят в накопители N 1 и N 2 перед началом первого цикла шифрования.
Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:
Здесь i обозначает номер итерации (i = 1, 2,..., 32).
Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 2 32 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).
Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) ... К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0...15.
Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-х разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки К содержит ключевые элементы, общие для сети ЭВМ и редко изменяемые.
Вторая операция - циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т ш представляется в виде Т ш =A(32)B(32).
Остальные блоки открытых данных в режиме простой замены зашифровываются аналогично.
Следует иметь в виду, что режим простой замены допустимо использовать для
шифрования данных только в ограниченных случаях. К этим случаям относится
выработка ключа и зашифрование его с обеспечением имитозащиты (защиты от
навязывания ложных данных) для передачи по каналам связи или хранения в памяти
ЭВМ.
Режим гаммирования
Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m, где m определяется обьемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит, то есть Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).
Уравнение зашифрования данных в режиме гаммирования может быть представлено в следующем виде:
Ш(i) = A (Y(i-1) [+] C2, Z(i-1) {+} C1) (+) T(i) = Г(i) (+) T(i) .
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены (аргументами этой функции
являются два 32-разрядных числа),
С1 и С2 - константы, заданные в ГОСТ 28147-89,
Y(i) и Z(i) - величины, которые определяются итерационно по мере формирования
гаммы следующим образом:
(Y(0), Z(0)) = A(S), где S - 64-разрядная двоичная последовательность
(синхропосылка);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) {+} C1) для i = 1, 2,...,m.
Расшифрование данных возможно только при наличии синхропосылки, которая не
является секретным элементом шифра и может храниться в памяти ЭВМ или
передаваться по каналам связи вместе с зашированными данными.
Режим гаммирования с обратной связью
Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2,..., m , где m определяется обьемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г ш, которая вырабатывается блоками по 64 бит:
Г ш = (Г(1),Г(2),...,Г(i),...,Г(m)).
Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.
Уравнение зашифрования данных в режиме гаммирования с обратной связью может быть представлено в следующем виде:
Здесь Ш(i) - 64-разрядный блок зашифрованного текста,
A - функция шифрования в режиме простой замены. Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих - предыдущий блок зашифрованных данных Ш(i-1).
Bыработки имитовставки
Процесс выработки имитовстаки единообразен для любого из режимов шифрования данных.
Имитовставка - это блок из р бит (имитовставка Ир), который вырабатывается либо перед шифрованием всего сообщения, либо параллельно с шифрованием по блокам. Первые блоки открытых данных, которые участвуют в выработке имитовставки, могут содержать служебную информацию (например, адресную часть, время, синхропосылку) и не зашифровываться. Значение параметра р (число двоичных разрядов в имитовставке) определяется криптографическими требованиями с учетом того, что вероятность навязывания ложных помех равна 1/2^р.
Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2,..., m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.
Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных Т(2). Результат суммирования снова подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Полученное 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных Т(3) и т.д. Последний блок Т(m) при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.
Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются, и из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир", которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.
Краткое описание шифра
ГОСТ 28147-89 - советский и российский стандарт симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название - «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.
ГОСТ 28147-89 - блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра - Сеть Фейстеля. Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки).
Принцип работы алгоритма
Алгоритм принципиально не отличается от DES. В нем также происходят циклы шифрования (их 32) по схеме Фейстеля (Рис. 2.9.).
Рис. 2.9. Раунды шифрования алгоритма ГОСТ 28147-89.
Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: k 1 …k 8 . Ключи k 9 …k 24 являются циклическим повторением ключей k 1 …k 8 (нумеруются от младших битов к старшим). Ключи k 25 …k 32 являются ключами k 1 …k 8 , идущими в обратном порядке.
После выполнения всех 32 раундов алгоритма, блоки A 33 и B 33 склеиваются (следует обратить внимание на то, что старшим битом становится A 33 , а младшим - B 33) – результат есть результат работы алгоритма.
Функция 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 16 . Если вторая часть равна 2 32 -1, то её значение не меняется, иначе она складывается по модулю 2 32 -1 с постоянным значением 1010104 16 . Полученное объединением обеих преобразованных частей значение, называемое гаммой шифра, поступает в цикл «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-битным ключом).
Этот алгоритм является обязательным для применения в качестве алгоритма шифрования в государственных организациях РФ и ряде коммерческих .
Описание алгоритма
Схема алгоритма показана на рис. 3.1 . Как видно, схема этого алгоритма достаточно проста, что однозначно упрощает его программную или аппаратную реализацию.
Алгоритм ГОСТ 28147-89 шифрует информацию блоками по 64 бита, которые разбиваются на два субблока по 32 бита (N1 и N2). Субблок N1 определенным образом обрабатывается, после чего его значение складывается
со значением субблока N2 (сложение выполняется по модулю 2), затем субблоки меняются местами. Такое преобразование выполняется определенное количество раундов: 16 или 32 в зависимости от режима работы алгоритма (описаны далее). В каждом раунде выполняются следующие операции:
1. Наложение ключа. Содержимое субблока /VI складывается по модулю 2 32 с частью ключа Кх.
Ключ шифрования алгоритма ГОСТ 28147-89 имеет размерность 256 битов, а Кх— это его 32-битная часть, т. е. 256-битный ключ шифрования представляется в виде конкатенации 32-битных подключей (рис. 3.2):
Щ ATI, АГ2, Ю, АГ4, К5, Кб, К7.
В процессе шифрования используется один из этих подключей — в зависимости от номера раунда и режима работы алгоритма.
Рис. 3.1. Схема алгоритма ГОСТ 28147-
Рис. 3.2. Ключ шифрования алгоритма ГОСТ 28147-89
2. Табличная замена. После наложения ключа субблок /VI разбивается на 8 частей по 4 бита, значение каждой из которых по отдельности заменяется в соответствии с таблицей замены для данной части субблока. Табличные замены (Substitution box, S-box) часто используются в современных алгоритмах шифрования, поэтому стоит рассмотреть их подробнее.
Табличная замена используется таким образом: на вход подается блок данных определенной размерности (в этом случае — 4-битный), числовое представление которого определяет номер выходного значения. Например, имеем S-box следующего вида:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Пусть на вход пришел 4-битный блок «0100», т. е. значение 4. Согласно таблице, выходное значение будет равно 15, т.е. «1111» (0 заменяется на 4, 1 — на 11, значение 2 не изменяется и т. д.).
Как видно, схема алгоритма весьма проста, что означает, что наибольшая нагрузка по шифрованию данных ложится на таблицы замен. К сожалению, алгоритм обладает тем свойством, что существуют «слабые» таблицы замен, при использовании которых алгоритм может быть раскрыт криптоаналитическими методами. К числу слабых относится, например, таблица, в которой выход равен входу :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Побитовый циклический сдвиг влево на 11 битов.
Режимы работы алгоритма
Алгоритм ГОСТ 28147-89 имеет 4 режима работы:
□ режим простой замены;
□ режим гаммирования;
П режим гаммирования с обратной связью;
□ режим выработки имитоприставок.
Эти режимы несколько отличаются от общепринятых (описанных в разд. 1.4), поэтому стоит рассмотреть их подробнее.
Данные режимы имеют различное назначение, но используют одно и то же описанное выше шифрующее преобразование.
Режим простой замены
В режиме простой замены для зашифровывания каждого 64-битного блока информации просто выполняются 32 описанных выше раунда. 32-битные подключи используются в следующей последовательности:
□ КО, Kl, К2, КЗ, К4, К5, Кб, АГ7, КО, ATI и т. д. — в раундах с 1-го по 24-й;
□ К1, Кб, К5, К4, КЗ, К2, К\, КО —в раундах с 25-го по 32-й.
Расшифровывание в режиме простой замены производится совершенно так же, но с несколько другой последовательностью применения подключей:
□ КО, К\, К2, КЗ, К4, К5, Кб, КП — в раундах с 1-го по 8-й;
□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб и т. д. — в раундах с 9-го по 32-й.
Аналогично стандартному режиму ЕСВ, по причине раздельного шифрования блоков режим простой замены категорически не рекомендуется использовать для шифрования собственно данных; он должен использоваться только для шифрования других ключей шифрования в многоключевых схемах.
Режим гаммирования
В режиме гаммирования (рис. 3.3) каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бита. Гамма шифра — это специальная последовательность, которая вырабатывается с помощью описанных выше преобразований следующим образом:
1. В регистры N1 и N2 записывается их начальное заполнение— 64-битная величина, называемая «синхропосылкой» (синхропосылка, практически, является аналогом вектора инициализации в режимах СВС, CFB и OFB).
2. Выполняется зашифровывание содержимого регистров /VI и N2 (в данном случае — синхропосылки) в режиме простой замены.
3. Содержимое N1 складывается по модулю (2 32 – 1) с константой CI = 2 24 + 2 16 + 2 8 + 4 , результат сложения записывается в регистр /VI.
4. Содержимое N2 складывается по модулю 2 с константой С2 = 2 24 + 2 16 + 2 8 +1, результат сложения записывается в регистр N2.
5. Содержимое регистров /VI и N2 подается на выход в качестве 64-битного блока гаммы шифра (т. е. в данном случае /VI и N2 образуют первый блок гаммы).
6. Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифровывание или расшифровывание), выполняется возврат к шагу 2.
Для расшифровывания аналогичным образом выполняется выработка гаммы, затем снова применяется операция XOR к битам зашифрованного текста и гаммы.
Для выработки той же самой гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же самый ключ и то же значение синхропосылки, которые применялись при зашифровывании информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не является секретным элементом, однако синхропосылка может быть так же секретна, как и ключ шифрования. В этом случае можно считать, что эффективная длина ключа алгоритма (256 битов) увеличивается еще на 64 бита синхропосылки, которую можно рассматривать как дополнительный ключевой элемент.
Режим гаммирования с обратной связью
В режиме гаммирования с обратной связью в качестве заполнения регистров /VI и Л/2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифровывания предыдущего блока открытого текста (рис. 3.4). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
Рис. 3.4. Выработка гаммы шифра в режиме гаммирования с обратной связью
Режим выработки имитоприставки
Имитоприставка — это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. Для ее вычисления существует специальный режим алгоритма ГОСТ 28147-89.
Генерация имитоприставки выполняется следующим образом:
1. Первый 64-битный блок информации, для которой вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены, в котором выполняются первые 16 раундов из 32.
2. Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
3. М и N2 снова зашифровываются в сокращенном режиме простой замены и т. д. до последнего блока информации.
Имитоприставкой считается 64-битное результирующее содержимое регистров N1 и N2 или его часть. Чаще всего используется 32-битная имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как и любая контрольная сумма, имитоприставка предназначена, прежде всего, для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы — в первую очередь электронная цифровая подпись {см. разд. 1.1).
Имитоприставка используется следующим образом:
1. При зашифровывании какой-либо информации вычисляется имитоприставка открытого текста и посылается вместе с шифртекстом.
2. После расшифровывания имитоприставка снова вычисляется и сравнивается с присланной.
3. Если вычисленная и присланная имитоприставки не совпадают— шифр-текст был искажен при передаче или использовались неверные ключи при расшифровывании.
Имитоприставка особенно полезна для проверки правильности расшифровывания ключевой информации при использовании многоключевых схем.
Имитоприставка— это некоторый аналог кода аутентификации сообщений MAC, вычисляемого в режиме СВС; отличие состоит в том, что при вычислении имитоприставки не используется синхропосылка, тогда как при вычислении MAC используется вектор инициализации.
Криптостойкость алгоритма
В 1994 г. описание алгоритма ГОСТ 28147-89 было переведено на английский язык и опубликовано ; именно после этого стали появляться результаты его анализа, выполненного зарубежными специалистами; однако в течение значительного времени не было найдено каких-либо атак, приближающихся к практически осуществимым .
□ большой длины ключа — 256 битов; вместе с секретной синхропосылкой эффективная длина ключа увеличивается до 320 битов;
□ 32 раундов преобразований; уже после 8 раундов достигается полный эффект рассеивания входных данных: изменение одного бита блока открытого текста повлияет на все биты блока шифртекста, и наоборот, т. е. существует многократный запас стойкости.
Рассмотрим результаты криптоанализа алгоритма ГОСТ 28147-89.
Анализ таблиц замен
Поскольку таблицы замен в стандарте не приведены, в ряде работ (например, в ) высказывается предположение, что «компетентная организация» может выдать как «хорошие», так и «плохие» таблицы замен. Однако в известнейший эксперт Брюс Шнайер называет такие предположения «слухами». Ясно, что криптостойкость алгоритма во многом зависит от свойств используемых таблиц замен, соответственно, существуют слабые таблицы замен (пример см. выше), применение которых может упростить вскрытие алгоритма. Тем не менее, возможность использования различных таблиц замен кажется весьма достойной идеей, в пользу которой можно привести два следующих факта из истории стандарта шифрования DES (подробности см. в разд. 3.15):
□ атаки с помощью как линейного, так и дифференциального криптоанализа алгоритма DES используют конкретные особенности таблиц замен; при использовании других таблиц криптоанализ придется начинать сначала;
□ были предприняты попытки усилить DES против линейного и дифференциального криптоанализа путем использования более стойких таблиц замен; такие таблицы, действительно более стойкие, были предложены, например, в алгоритме s 5 DES ; но, увы, заменить DES на s 5 DES было невозможно, поскольку таблицы замен жестко определены в стандарте , соответственно, реализации алгоритма наверняка не поддерживают возможность смены таблиц на другие.
В ряде работ (например, , и ) ошибочно делается вывод о том, что секретные таблицы замен алгоритма ГОСТ 28147-89 могут являться частью ключа и увеличивать его эффективную длину (что несущественно, поскольку алгоритм обладает весьма большим 256-битным ключом). Однако в работе доказано, что секретные таблицы замен могут быть вычислены с помощью следующей атаки, которая может быть применена практически:
1. Устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т. е. значения z = /(0), где /() — функция раунда алгоритма. Этот этап занимает порядка 2 операций шифрования.
2. С помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2 11 операций.
Модификации алгоритма и их анализ
В работе проведен криптоанализ модификаций алгоритма ГОСТ 28147-89:
□ алгоритма GOST-H, в котором, относительно оригинального алгоритма, изменен порядок использования подключей, а именно в раундах с 25-го по 32-й подключи используются в прямом порядке, т. е. точно так же, как и в предыдущих раундах алгоритма;
□ 20-раундового алгоритма GOST®, в раунде которого для наложения ключа используется операция XOR вместо сложения по модулю 2 32 .
По результатам анализа сделан вывод о том, что GOST-H и GOST© слабее исходного алгоритма ГОСТ 28147-89, поскольку оба имеют классы слабых ключей. Стоит отметить, что в части криптоанализа GOST© работа слово в слово повторяет раздел, посвященный криптоанализу алгоритма ГОСТ 28147-89, вышедшей в 2000 г. известной работы (без каких-либо ссылок на оригинал). Это ставит под сомнение профессионализм авторов работы и остальные ее результаты.
Весьма интересная модификация алгоритма предложена в работе : таблицы S\…Ss обязательно должны быть различными; в каждом раунде алгоритма должна выполняться их перестановка по определенному закону. Данная перестановка может быть зависимой от ключа шифрования, а может быть и секретной (т. е. являться частью ключа шифрования большего размера по сравнению с исходным 256-битным ключом). Оба этих варианта, по мнению их авторов, существенно усиливают стойкость алгоритма против линейного и дифференциального криптоанализа.
И еще одна модификация, связанная с таблицами замен, приведена в работе , в которой анализируется один из возможных методов вычисления таблиц замен на основе ключа шифрования. Авторы работы сделали вывод, что подобная зависимость ослабляет алгоритм, поскольку приводит к наличию слабых ключей и к некоторым потенциальным уязвимостям алгоритма.
Анализ полнораундового алгоритма
Существуют атаки и на полнораундовый ГОСТ 28147-89 без каких-либо модификаций. Одна из первых открытых работ, в которых был проведен анализ алгоритма,— широко известная работа — посвящена атакам, использующим слабости процедуры расширения ключа ряда известных алгоритмов шифрования. В частности, полнораундовый алгоритм ГОСТ 28147-89 может быть вскрыт с помощью дифференциального криптоанализа на связанных ключах, но только в случае использования слабых таблиц замен. 24-раундовый вариант алгоритма (в котором отсутствуют первые 8 раундов) вскрывается аналогичным образом при любых таблицах замен, однако сильные таблицы замен (например, приведенная в ) делают такую атаку абсолютно непрактичной.
Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. в работе предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифртекстов с достаточно низкой сложностью. Криптоанализ алгоритма продолжен в работе .
В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 битов секретного ключа . Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрования. Как видно, данная атака, практически, бесполезна для реального вскрытия алгоритма.
Алгоритм, определяемый ГОСТ 28147-89, имеет длину ключа шифрования 256 бит. Он шифрует информацию блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2) (рисунок 1). Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - «исключающее или»), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз («раундов»): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.
Рисунок 1. Схема алгоритма ГОСТ 28147-89.
Первая - наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-бит частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-бит подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.
Вторая операция - табличная замена. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.
Табличные замены (Substitution box - S-box) часто используются в современных алгоритмах шифрования, поэтому стоит пояснить, как организуется подобная операция. В таблицу записываются выходные значения блоков. Блок данных определенной размерности (в нашем случае - 4-бит) имеет свое числовое представление, которое определяет номер выходного значения. Например, если S-box имеет вид 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 и на вход пришел 4-бит блок «0100» (значение 4), то, согласно таблице, выходное значение будет равно 15, т. е. «1111» (0 а 4, 1 а 11, 2 а 2 ...).
Алгоритм, определяемый ГОСТ 28147-89, предусматривает четыре режима работы: простой замены, гаммирования, гаммирования с обратной связью и генерации имитоприставок. В них используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по-разному.
В режиме простой замены для зашифрования каждого 64-бит блока информации выполняются 32 описанных выше раунда. При этом 32-бит подключи используются в следующей последовательности:
K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;
K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.
Расшифрование в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:
K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;
K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.
Все блоки шифруются независимо друг от друга, т. е. результат зашифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы - гаммирования и гаммирования с обратной связью.
В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2.
- 1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.
- 2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.
- 3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
- 4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
- 5. Содержимое регистров N1 и N2 подается на выход в качестве 64-бит блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).
Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифрование или расшифрование), выполняется возврат к операции 2.
Для расшифрования гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR. Поскольку эта операция обратима, в случае правильно выработанной гаммы получается исходный текст (таблица 1).
Таблица 1. Зашифрование и расшифрование в режиме гаммирования
Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же ключ и то же значение синхропосылки, которые применялись при зашифровании информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка - такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент.
В режиме гаммирования с обратной связью для заполнения регистров N1 и N2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифрования предыдущего блока открытого текста (рисунок 2). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
![](https://i2.wp.com/studwood.ru/imag_/15/160970/image002.jpg)
Рисунок 2. Выработка гаммы шифра в режиме гаммирования с обратной связью.
Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-бит блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-бит содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-бит имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.
При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровании какой-либо информации и посылается вместе с шифртекстом. После расшифрования вычисляется новое значение имитоприставки, которое сравнивается с присланной. Если значения не совпадают - значит, шифртекст был искажен при передаче или при расшифровании использовались неверные ключи. Особенно полезна имитоприставка для проверки правильности расшифрования ключевой информации при использовании многоключевых схем.
Алгоритм ГОСТ 28147-89 считается очень сильным алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод «грубой силы». Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).
Достоинствами ГОСТ 28147-89 являются наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТ.