Устранение уязвимости в алгоритме шифрования ШОРТ

Трунов Д.Н.

УСТРАНЕНИЕ УЯЗВИМОСТИ В АЛГОРИТМЕ ШИФРОВАНИЯ ШОРТ

Введение

Авторский алгоритм шифрования ШОРТ[1] относится к потоковым шифрам [2, 3], в которых отдельные элементы данных (в данном случае — байты) обрабатываются потоком, независимо друг от друга. Для шифрования над каждым байтом исходных данных и соответствующим ему байтом-ключом выполняется операция XOR (исключающее ИЛИ). Расшифровка выполняется повторным выполнением операции XOR над зашифрованными байтами и соответствующими байтами-ключами.

Схема шифрования устроена следующим образом. На основе введённого пароля с помощью функции Gen генерируется первоначальный ключ шифрования, который сохраняется в массиве K, состоящем из 256 целых 64-битный чисел без знака. Генерация осуществляется при участии функции GFunc, которая выполняет несколько проходов шифрования ключа K потенциально необратимым способом: зная текущее состояние ключа, невозможно восстановить его прежнее состояние. Количество проходов (циклов) такого шифрования задаётся величиной Cycles, которая указывается при запуске функции Gen.

Для шифрования данных ключ K копируется в байтовый массив M, из которого и берётся поток байтов-ключей. Поскольку размер массива M ограничен (2048 байт), после использования из него всех байтов производится новое шифрование массива ключа K и его копирование в массив M. После этого из массива M опять можно брать байты-ключи.

Суть уязвимости

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

Если у некоторого злоумышленника есть зашифрованное сообщение длиной более 2048 байт и он каким-то образом узнал первые 2048 байта оригинального сообщения, то ему не составит труда восстановить весь массив M, использовавшийся при шифровании этих 2048 байт. Далее массив M обратно копируется в массив ключа K, после чего злоумышленник сможет продолжить генерацию последующих состояний ключа и расшифровать всё оставшееся сообщение.

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

Принятые меры

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

На практике это реализовано следующим образом. Во-первых, в объектном классе шифра ShortCipher объявлен дополнительный массив N, идентичный K. Ниже приведён текст объявления класса на языке программирования Object Pascal:

ShortCipher = class

private

    M: Array[0..2047] of Byte; // байтовый массив ключа

    K: Array[0..255] of UInt64; // основной массив ключа

    N: Array[0..255] of UInt64; // вспомогательный массив ключа

    _Cycles: Cardinal; // количество циклов шифрования

    Cur: Integer; // текущая позиция

    procedure GFunc(Cycles: Cardinal);

public

    procedure Gen(Psw: UnicodeString; Cycles: Cardinal);

    procedure EncryptMass(var Mass: Array of Byte; Size: Cardinal);

end;

Во-вторых, новый массив N инициализируется в функции Gen идентично массиву K:

K[0] := $F1D4B79A;

K[0] := K[0] SHL 32 + $7D503316;

N[0] := K[0];

for I := 1 to 255 do

begin

    K[I] := (NOT K[I - 1] XOR (I SHL 15));

    K[I] := ROL64(K[I], 1);

    N[I] := K[I];

end;

В-третьих, в функции GFunc выполняется зашифровка не только массива основного ключа K, но и вспомогательного массива N. Однако их зашифровка выполняется по-разному. В основном цикле шифрования производится зашифровка элемента K[I] с участием переменных, взятых из других ячеек массива K. Для этого над элементом K[I] последовательно выполняется несколько операций XOR и циклического сдвига влево (функция ROL64, реализованная в алгоритме). На одном из этапов промежуточное состояние K[I] добавляется к ячейке N[I] (тоже с помощью операции XOR):

K[I] := ROL64(K[I] XOR (A OR E), 7);

K[I] := ROL64(K[I] XOR (B AND (NOT F)), 7);

K[I] := ROL64(K[I] XOR (NOT (C AND G)), 7);

N[I] := N[I] XOR K[I];

K[I] := ROL64(K[I] XOR ((NOT D) OR H), 7);

K[I] := ROL64(K[I] XOR ((E + F + G + H) OR (NOT Adr)), 7);

Наконец, в функции шифрования EncryptMass массив M образуется путём копирования в него результатов сложения элементов ключей K и N:

for J := 0 to 255 do

begin

    P := @M[J * 8];

    P^ := (K[J] + N[J]);

end;

Анализ внесённых изменений

Внесённые изменения по своей идее должны полностью устранить описанную в данной статье уязвимость. Формирование массива M путём суммирования элементов ключей K и N имеет следующее преимущество: даже зная весь массив M, злоумышленник не сможет восстановить состояние ни массива K, ни массива N, поскольку операция сложения является необратимой: имея сумму двух чисел, нельзя точно сказать, какие именно два числа её образовали.

Если число имеет размер 1 байт (как элементы массива M) и является суммой двух других чисел размером по 1 байт каждый, то для любого значения суммы существует 256 вариантов таких двух чисел. Если два числа являются суммой четырёх других чисел, то количество вариантов этих четырёх чисел равно 256² = 65536 комбинаций. Для 10 чисел количество вариантов составит уже 256¹⁰ ≈ 1,2·10²⁴. И все равноправные, то есть любая может оказаться той, которая и образовала сумму.

Однако всё это верно только при условии, что входящие в сумму числа являются независимыми друг от друга. Если одно число суммы однозначно получается из другого числа, то и сама сумма будет однозначно определяться, исходя из значения этого числа. И сколько бы мы таких чисел-сумм не взяли, из всех можно однозначно получить пары чисел, образующих эти суммы. То есть независимость входящих в сумму чисел является основанием необратимости их сложения.

Исходя из этой логики, получить из массива M точные значения ключей K и N не получится (для этого пришлось бы перебрать невероятно много возможных вариантов), если каждый элемент K[I] является независимым от элемента N[I]. Но являются ли они независимыми?

В процессе зашифровки ключа функцией GFunc каждый элемент ключа K[I] будет меняться в зависимости от значений других элементов этого ключа. При некотором количестве повторений цикла шифрования (не менее 6) будет достигнут такой уровень взаимосвязи элементов, что все будут зависеть от всех, а распутать эти взаимосвязи без знания начального состояния ключа будет крайне проблематично.

Что касается массива N, то каждое новое значение элемента N[I] будет зависеть от его прежнего состояния и от промежуточного значения элемента K[I], которое ещё будет изменено в процессе выполнения функции. То есть на каждый элемент N[I] и K[I] другие элементы ключа K будут оказывать влияние по-разному, а проследить взаимосвязи будет по-прежнему проблематично (при достаточном количестве повторений цикла шифрования). В этом смысле значения N[I] и K[I] можно считать независимыми друг от друга, а, значит, операцию их сложения — необратимой.

Заключение

Ключевым аспектом устранения уязвимости в алгоритме ШОРТ была реализация необратимого способа преобразования основного ключа K в байтовый массив M, из которого берётся поток байтов-ключей для шифрования и расшифровки данных. Этот способ заключается в применении дополнительного массива ключа N с отличной от K схемой генерации, а также в сложении элементов N и K перед их занесением в массив M.

С учётом сложной схемы взаимосвязи между элементами массивов ключей, которую трудно распутать без знания пароля, на основе которого они генерируются, отдельные элементы массивов K и N можно считать независимыми друг от друга. Благодаря этому операция сложения элементов K и N перед занесением в массив M становится необратимой: по массиву M будет невозможно однозначно восстановить массивы N и K.

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

Источники информации

1. Трунов Д.Н. Реализация потокового шифра на основе алгоритма ESCK-6, его применение и оценки надёжности. [Электронный ресурс] – URL: https://d-raft5.blogspot.com/2019/06/esck-6.html

2. Википедия. Потоковый шифр. [Электронный ресурс] — URL: https://ru.wikipedia.org/wiki/Потоковый_шифр

3. Гатченко М.А., Исаев А.С., Яковлев А.Д. «Криптографическая защита информации» - СПб: НИУ ИТМО, 2012. - 142 с.

4. Шнайер Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Триумф, 2002. – 816 с.