Уязвимости ГОСТ 28147-89 в режиме простой замены

 

Легко обнаружить, что тривиальная таблица подстановки S блока и тривиальный ключ приводят к сильной деградации алгоритма. Ключ, равный 0 (256 равных 0 битов), приведет к тому, что он никак не будет влиять на криптограмму. Если обратиться к рисунку 3.2, то можно заметить, что ключ участвует в одном-единственном блоке – сложение по модулю 2³². По правилам арифметики прибавление нуля к любому числу даст само это число. Таким образом, если ключ равен нулю, то его фактически не существует в системе.

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

Рисунок 3.3 – Тривиальная таблица подстановки

 

После выполнения блока «Подстановка S-блоком» на рисунке 3.2 вместо заменяемой тетрады будет подставлена сама же эта тетрада. В этом случае блок «Подстановка S-блоком» фактически отсутствует в схеме.

В результате получится схема, приведенная ни рисунке 3.4.

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

Кроме того [7] указывает на некоторые другие слабости алгоритма.

 

Рисунок 3.4 – Блок-схема вырожденного алгоритма ГОСТ 28147-89 в режиме простой замены

 

3.5 Контрольные вопросы

 

1 Назовите основные этапы, из которых строятся блоковые шифры.

2 Какие меры приняты в стандарте ГОСТ 28147-89 для повышения криптостойкости?

3 Перечислите известные вам уязвимые места алгоритма ГОСТ 28147-89 в режиме простой замены.

Пример приложения

 

Подготовка нового модуля

Создание отдельного модуля в проекте Delphi выполняется следующим образом. После запуска Delphi мы сразу же можем приступать к работе над новой программой, поскольку чистые заготовки для формы и соответствующего ее модуля уже созданы. Однако нам нужно создать отдельный модуль алгоритма шифрования ГОСТ 28147-89. Команда создания нового модуля доступна из меню File/New/Unit. Теперь мы сможем создать форму приложения в одном модуле, а библиотеку с функцией шифрования в другом.

 

Заголовок модуля, константы и типы

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

Заголовок модуля ГОСТ 28147-89 будет иметь вид, приведенный в листинге 3.1.

 

unit GostSubr;

 

Interface

 

////////////////////////////////////////////////////////////////////////

// КОНСТАНТЫ ДЛЯ ГОСТа

////////////////////////////////////////////////////////////////////////

 

Const

nGostIterations = 32; // Кол-во итераций в ГОСТе

nGostShiftBits = 11; // Кол-во бит при сдвиге в ГОСТе

nGostSubkeys = 8; // Кол-во подключей в ключе ГОСТа

nSBlocks = 8; // Кол-во S-блоков в ГОСТе

nSBlockLen = 16; // Кол-во элементов в 1 S-блоке в ГОСТе

 

aGostSTempl : Array [0 .. nSBlocks - 1, 0 .. nSBlockLen - 1] Of Byte =

( ( 4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3),

(14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9),

( 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11),

( 7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3),

( 6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2),

( 4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14),

(13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12),

( 1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12) );

// S таблица для безопасной инициализации S блока

 

////////////////////////////////////////////////////////////////////////

// ТИПЫ ДЛЯ ГОСТа

////////////////////////////////////////////////////////////////////////

 

Type

 

aGostKey = Array [0 .. nSBlocks - 1] Of Longword;

// Ключ ГОСТа трактуется как 8 32-битных слов

 

aGostS = Array [0 .. nSBlocks - 1, 0 .. nSBlockLen - 1] Of Byte;

// S таблица ГОСТа трактуется как 8 16-байтных блоков

Листинг 3.1 – Заголовок модуля ГОСТ 28147-89

 

В разрабатываемом модуле объявляются 6 констант. Они определены в секции модуля const и все прокомментированы. Эти константы содержат основные параметры алгоритма ГОСТ. Разумеется, все числовые характеристики можно было сразу же вставить в текст программы, но для улучшения читабельности кода вместо цифр лучше использовать осмысленный набор слов. Кроме того, в секции type объявляются два новых типа, для ключа и S-таблицы ГОСТ.

Заголовки подпрограмм приведены в листинге 3.2.

 

////////////////////////////////////////////////////////////////////////

// ЗАГОЛОВКИ ПОДПРОГРАММ ДЛЯ ГОСТа

////////////////////////////////////////////////////////////////////////

 

procedure GostSimpleSubstitute(var iLeft, iRight : Longword;

aKey : aGostKey;

aGostS : aGostS;

isCrypting : Boolean);

 

// Подпрограмма простой подстановки по алгоритму ГОСТ

// Вход : iLeft - Левая половина шифруемого слова

// iRight - Правая половина шифруемого слова

// aKey - Ключ шифрования

// isCrypting - Флаг режима работы (True - шифр, False - дешифр)

// Выход: iLeft - Левая часть зашифрованного/расшифрованного слова

// iRight - Правая часть зашифрованного/расшифрованного слова

 

function GostGetIterationSubkey(aKey : aGostKey;

i : Integer;

isCrypting : Boolean) : Longword;

 

// Подпрограмма получения подключа шифрования для данной итерации

// Вход : aKey - Массив ключей ГОСТ

// i - № итерации, для которой вычисляется подключ

// isCrypting - Флаг режима работы (True - шифр, False - дешифр)

// Выход: [Подключ для итерации № i]

 

function GostLeftShift(Reg : Longword; nBits : Integer) : Longword;

 

// Подпрограмма циклического сдвига влево

// Вход : Reg - Сдвигаемый регистр

// nBits - Кол-во бит, на которое сдвигается регистр

// Выход: [Сдвинутый циклически влево на 11 бит регистр]

 

procedure GostInitSBlock(var S : aGostS);

 

// Подпрограмма инициализации S блока

// Вход : S - S-блок ГОСТа для приема таблицы подстановки

// Выход: S - S-блок ГОСТа с таблицей подстановки

 

function GostSBlockSubstitute(Reg : Longword; S : aGostS) : Longword;

 

// Подпрограмма подстановки S блоком

// Вход : Reg - Подставляемый регистр

// S - Блок подстановки

// Выход: [Подстановленный регистр]

 

procedure ExchangeRegs(var iLeft, iRight : Longword);

 

// Подпрограмма обмена значениями регистров

// Вход : iLeft - Левый регистр

// iRight - Правый регистр

// Выход: iLeft - [Правый регистр]

// iRight - [Левый регистр]

Листинг 3.2 – Заголовки подпрограмм модуля ГОСТ 28147-89

 

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

Тело подпрограммы GostSimpleSubstitute приведено в листинге 3.3.

 

Implementation

 

////////////////////////////////////////////////////////////////////////

// ТЕЛА ПОДПРОГРАММ ДЛЯ ГОСТа

////////////////////////////////////////////////////////////////////////

 

procedure GOSTSimpleSubstitute(var iLeft, iRight : Longword;

aKey : aGostKey;

aGostS : aGostS;

isCrypting : Boolean);

Var

i : Integer;

tmpReg : LongWord; // Вспомогательный регистр

Begin

For i := 0 To nGostIterations - 1 Do

Begin

tmpReg := iRight;

// Сохраняем правый регистр во временной переменной

 

iRight := iRight + GOSTGetIterationSubKey(aKey, i, isCrypting);

// Операция №1 - Сложение по модулю 2^32 с подключом

 

iRight := GOSTSBlockSubstitute(iRight, aGostS);

// Операция №2 - Подстановка S блоком

 

iRight := GOSTLeftShift(iRight, nGostShiftBits);

// Операция №3 - Циклический сдвиг влево на 11 битов

 

iRight := iLeft Xor iRight;

// Операция №4 - Сложение с другим регистром по модулю 2

 

iLeft := tmpReg;

// Возвращаем старый правый регистр на место нового левого

End;

 

ExchangeRegs(iLeft, iRight);

 

end;

Листинг 3.3 – Код подпрограммы простой замены по алгоритму ГОСТ 28147-89

 

Наконец, после ключевого слова implementation начинается секция, содержащая тела подпрограмм. Тело подпрограммы GOSTSimpleSubstitute точно соответствует алгоритму шифрования. Единственная операция, которая, пожалуй, нуждается в комментариях – это операция №1 – сложение по модулю 2³². В программе она реализуется в виде простого сложения. Весь фокус заключается в корректном переполнении. Переменная iRight имеет тип Longword (беззнаковый 32-х битный целочисленный тип). При переполнении переменная обнуляется (происходит перенос в более старший разряд, которого у переменной нетт перенос в более старший разраго тся ()го сложения. омментариях - это цифр лучше использовать осмысленный набор слов.) и далее результат накапливается как при обычном сложении. Фактически происходит сложение по модулю 2³².

Подпрограмма выборки подключа для заданной итерации приведена в листинге 3.4.

 

function GOSTGetIterationSubKey(aKey : aGostKey;

i : Integer;

isCrypting : Boolean) : Longword;

Begin

If isCrypting Then

// Шифруем - порядок прямой

If i < 24 Then Result := aKey[i mod 8]

Else Result := aKey[7 - (i mod 8)]

Else

// Дешифрируем - порядок обратный

If i < 8 Then Result := aKey[i]

Else Result := aKey[7 - (i mod 8)];

end;

Листинг 3.4 – Код подпрограммы выборки подключа для заданной итерации

 

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

Код подпрограммы циклического сдвига влево приведен в листинге 3.5.

 

function GOSTLeftShift(Reg : Longword; nBits : Integer) : LongWord;

Var

tmpReg : Longword; // Вспомогательный регистр

Begin

tmpReg := Reg Shr (32 - nBits);

// Передернули вправо и сохранили регистр

Result := (Reg Shl nBits) + tmpReg;

// Передернули влево и вернули результат

end;

Листинг 3.5 – Код подпрограммы циклического сдвига влево

 

К сожалению, в языке Object Pascal нет команды циклического сдвига (есть только линейный, но он не годится, потому что сдвинутая часть в этом случае просто исчезает). Но, тем не менее, для того чтобы организовать циклический сдвиг, мы воспользуемся функциями линейного сдвига (shl – влево, shr - вправо). В первой команде мы сдвигаем вправо весь регистр на 32 – 11 = 21 бит и сохраняем во вспомогательной переменной tmpReg только те биты, которые «выскакивают» из регистра при сдвиге. Следующей командой мы сдвигаем регистр влево на 11 бит («выскочившие» биты при этом теряются, но мы их предварительно сохранили в переменной tmpReg). В той же команде мы плюсуем эти сохраненные биты к сдвинутому регистру Reg. Результат (циклически сдвинутый регистр) возвращается в вызывающую подпрограмму.

Код подпрограммы инициализации S блока приведен в листинге 3.6.

 

procedure GostInitSBlock(var S : aGostS);

var i, j : Integer;

Begin

For i := 0 To nSBlocks - 1 Do

For j := 0 To nSBlockLen - 1 Do

S[i, j] := aGostSTempl[i, j];

end;

Листинг 3.6 – Код подпрограммы инициализации S-блока

 

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

Код подпрограммы подстановки S-блока приведен в листинге 3.7.

 

function GostSBlockSubstitute(Reg : Longword; S : aGostS) : Longword;

var tmpReg : Longword;

i : Integer;

Begin

For i := 0 To nSBlocks - 1 Do

Begin

tmpReg := Reg;

// Копируем подставляемый регистр в вспомогательную переменную

 

tmpReg := tmpReg shl (4 * i); // Убираем лишние биты слева

tmpReg := tmpReg shr (4 * (nSBlocks - 1));

// Убираем лишние биты справа

 

Result := Result shl 4;

Result := Result + S[i, tmpReg];

// Накапливаем подстановку

End;

end;

Листинг 3.7 – Код подпрограммы подстановки S-блока

 

Подстановка S-блоком осуществляется с помощью достаточно сложных манипуляций с логическими функциями. Цикл состоит из 8 итераций, на каждой итерации заменяется одна тетрада (8*4 = 32). Замены осуществляется в два этапа. Сначала выделяется нужная тетрада посредством последовательных сдвигов влево и вправо и накапливается в переменной tmpReg. Затем возвращаемое подпрограммой значение сдвигается на четыре бита влево (при этом освобождается место для приема заменяющей тетрады). Наконец, с помощью обычной функции сложения заменяющая тетрада записывается в возвращаемое программой значение.

Код подпрограммы обмена регистров приведен в листинге 3.8.

 

procedure ExchangeRegs(var iLeft, iRight : Longword);

var tmpReg : Longword;

Begin

tmpReg := iLeft;

iLeft := iRight;

iRight := tmpReg;

end;

Листинг 3.8 – Код подпрограммы обмена регистров

 

Обмен регистров строится по классической для программирования схеме – через вспомогательную переменную.