Реализация потокового шифра на основе алгоритма ESCK-6, его применение и оценки надёжности

Трунов Д.Н.

РЕАЛИЗАЦИЯ ПОТОКОВОГО ШИФРА НА ОСНОВЕ АЛГОРИТМА ESCK-6, ЕГО ПРИМЕНЕНИЕ И ОЦЕНКИ НАДЁЖНОСТИ

Введение

Большинство существующих шифров с секретным ключом могут быть однозначно отнесены либо к потоковым (или поточным), либо к блочным шифрам [1]. Основное различие заключается в том, что потоковые шифры обрабатывают отдельные элементы (символы, биты или байты) потоком, независимо друг от друга, в то время как блочные шифры оперируют группами элементов фиксированной длины — блоками [2].

Классический пример потокового шифра — шифр Вернама, или одноразовый блокнот [3]. Ключ такого блокнота должен обладать тремя важными свойствами:

1) быть истинно случайным;

2) совпадать по размеру с заданным открытым текстом;

3) использоваться однократно.

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

Алгоритм ESCK-6 в качестве потокового шифра

Алгоритм шифрования ESCK-6 представляет собой блочный шифр с плавающей длиной блока (от 16 до 2048 байт, кратной 8 байтам), большим ключом (2048 байт) и регулируемым в широком диапазоне количеством циклов шифрования [5]. Длинный ключ, механизм его генерации на основе односторонней функции с большим количеством циклов, а также предусмотренная возможность менять ключ при переходе к следующему блоку делает алгоритм годным не только для блочного, но и потокового шифрования. Однако режим потокового шифра в ESCK-6 отсутствует, что предполагает либо предусмотрение такого режима, либо реализацию его в виде отдельного алгоритма.

Было решено остановиться на втором варианте: реализовать отдельный алгоритм (рабочее название — ШОРТ или Шифр на ОдноРазовых Таблицах). Его основная идея заключается в том, чтобы (подобно многим другим потоковым шифрам) на основе одноразового пароля сгенерировать одноразовую же таблицу (массив, набор) байтов-ключей k₁,k₂,…,k_n. Затем по этой таблице шифровать соответствующие байты открытого сообщения x₁,x₂,…,x_n с помощью операции XOR (исключающее «или»):

y_i = x_i ХOR k_i

Для расшифровки понадобится повторно выполнить ту же операцию XOR:

x_i = y_i ХOR k_i

В ESCK-6 ключ шифрования генерируется в виде массива из 256 64-битных чисел. В ШОРТ эти числа нужно лишь разделить на отдельные байты, чтобы получить таблицу из 2048 байтов-ключей. Если этого количества недостаточно, предполагается генерировать следующую таблицу, содержащую новые значения байтов-ключей (в ESCK-6 для этого предусмотрен механизм смены ключа).

Устройство алгоритма ШОРТ

Алгоритм ШОРТ реализован в виде объектного класса ShortCypher. Ниже приведено объявление этого класса на языке программирования Object Pascal (среда разработки Lazarus):

ShortCypher = Class

private

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

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

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

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

    procedure GFunc;

public

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

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

end;

Как видно, класс содержит всего несколько полей и методов. Массивы M и K предназначены для текущей таблицы ключей (соответственно в виде байтов и 64-разрядных целых чисел). Переменная _Cycles хранит установленное количество циклов шифрования, а Cur предназначена для учёта текущей позиции байта-ключа в массиве M.

Процедура GFunc предназначена для генерации нового значения ключа K на основе его прежнего состояния. Является полностью идентичной таковой функции в алгоритме ESCK-6. Процедура Gen предназначена для генерации начального значения ключа на основе заданного пароля Psw и количества циклов шифрования Cycles. Практически идентична процедуре Gen в ESCK-6, за исключением того, что в ШОРТ отсутствует работа с режимами шифрования.

На процедуре EncryptMass следует остановиться поподробнее, поскольку она отличается от таковой в ESCK-6. Ниже приведён текст этой процедуры на языке Object Pascal (полный текст алгоритма приведён в приложении 1):

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

var

    I: Cardinal;  // счётчик основного цикла

    J: Cardinal;  // счётчик вспомогательных циклов

    P: ^UInt64;   // ссылка на 64-битное целое

begin

    // выход, если размер массива равен 0

    if Size = 0 then

        Exit;

    // основной цикл шифрования

    for I := 0 to Size - 1 do

    begin

        // если текущая позиция равна 0

        if Cur = 0 then

        begin

            // скопировать основной ключ в байтовый массив

            for J := 0 to 255 do

            begin

                P := @M[J * 8];

                P^ := K[I]; // Опечатка. Должно быть: P^ := K[J];

            end;

        end;

        // зашифровка текущего элемента и увеличение позиции

        Mass[I] := Mass[I] XOR M[Cur];

        Cur := Cur + 1;

        // если текущая позиция вышла за пределы байтового ключа

        if Cur >= 2048 then

        begin

            // обнулить текущую позицию

            Cur := 0;

            // выполнить самозашифровку основного ключа

            for J := 1 to _Cycles do

                GFunc;

        end;

    end;

end;

Процедура предназначена для шифрования/расшифровки байтового массива Mass размером Size. В процессе шифрования над каждым байтом Mass[I] и соответствующим ему элементом M[Cur] выполняется операция XOR, при этом величина I меняется от 0 до Size-1, а Cur от 0 до 2047 (по размеру массива M). Если величина Cur равна 0, производится копирование массива ключа K в эквивалентный ему байтовый массив M. Это необходимо как в начале шифрования, когда в массиве M ещё ничего нет, так и после каждой замены ключа K. А замена ключа происходит каждый раз, когда величина Cur становится больше 2047 (при этом она снова становится равной 0).

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

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

Возможное применение алгоритма ШОРТ

Алгоритм ШОРТ, прежде всего, можно применять для непосредственного шифрования конфиденциальных данных: сообщения, отправляемые доверенному лицу по сети, или файлы, сохраняемые на диск для постоянного или временного хранения (если на диске не включено шифрование, такие файлы могут попасть в руки злоумышленников). В любом случае, для каждого отдельного сообщения/файла должен применяться уникальный ключ шифрования (на основе одноразового пароля): повторное использование одного и того же ключа делает такой шифр очень уязвимым.

Для организации одноразовых паролей можно воспользоваться схемой, напоминающей «одноразовый блокнот»: создаётся набор уникальных паролей, которые используются по очереди для шифрования (и расшифровки), после чего удаляются. Также можно генерировать одноразовые пароли (по отдельной схеме) на основе многоразового секретного пароля и некоторой уникальной информации, прикрепляемой в открытом виде к самому сообщению (например, его номер и дата отправки). Если шифруется временный файл, для этого может генерироваться случайный пароль, который будет храниться только в памяти программы, пока в этом есть необходимость.

Другое возможное применение алгоритма ШОРТ — объединение с другим блочным или потоковым шифром. Существует множество способов объединить блочные и потоковые алгоритмы для получения новых алгоритмов: многократное шифрование с одним ключом, многократное шифрование одним алгоритмом и несколькими ключами, многократное последовательное шифрование разными алгоритмами и другие [6]. Стимулом создавать подобные схемы является желание повысить безопасность шифрования, не пробираясь сквозь тернии создания нового алгоритма.

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

Надёжность алгоритма ШОРТ

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

Псевдослучайный числовой генератор должен:

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

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

Применительно к алгоритмам ESCK-6 и ШОРТ достаточно подробные статистические тесты не проводились. Однако механизм генерации ключа предполагает вычисление элементов этого ключа при взаимодействии с множеством других таких элементов в самых разных комбинациях. При достаточно большом количестве циклов подобных вычислений проследить за взаимосвязью между этими элементами практически невозможно, а результаты вычислений становятся непредсказуемыми, то есть «случайными».

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

Что касается периода генерируемой последовательности в алгоритме ШОРТ, то его точное значение неизвестно. При длине основного ключа 2048 байт (16384 бита) максимальное количество возможных вариантов такого ключа достигает 2¹⁶³⁸⁴≈1,19·10⁴⁹³² уникальных комбинаций. Каждая такая комбинация — это 2048 байт ключевой последовательности. То есть максимально возможная длина периода M составляет около 2048·1,19·10⁴⁹³²≈2,44·10⁴⁹³⁵ байт.

На практике длина периода может быть меньшей. При шифровании длинной байтовой последовательности одного ключевого набора из 2048 байт будет недостаточно. После 1-го набора понадобится генерировать 2-й, потом 3-й и т.д. После N-ного (N <M) может опять пойти 1-й (возможно, и не 1-й), затем 2-й и т.д., то есть последовательность замкнётся. Учитывая сложнопредсказуемый характер генерации ключа, величина N может принимать разные значения в зависимости от начального состояния ключа и количества циклов генерации.

Можно оценить величину N, исходя из следующих соображений. Вероятность того, что при шифровании последовательности длиной L байт случится зацикливание ключевого потока, составит L/M, где M≈2,44·10⁴⁹³⁵ байт — максимальная длина периода шифра. При шифровании файла длиной около 1 ГБ вероятность столкнуться с зацикливанием составит около 4,4·10^-4927 — фактически ноль. Если бы каждый из 7 млрд. жителей Земли ежесекундно шифровал бы подобным шифром по одному файлу размером 1 ГБ на протяжении 10 лет, вероятность хотя бы 1 случая зацикливания будет по-прежнему «нулевая» — около 9,7·10^-4909.

Заключение

Как видно, алгоритм ESCK-6, являясь блочным шифром, легко может быть реализован и в качестве потокового шифра (алгоритм ШОРТ). Однако у обеих реализаций есть определённые преимущества и недостатки. Длинный ключ и большое количество циклов шифрования призваны существенно повысить надёжность шифра, но при этом алгоритм становится несколько громоздким и медленным в сравнении со своими аналогами. При этом оценки надёжности основаны на допущениях, тщательные проверки которых не проводились.

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

Однако, если в характере взаимодействий имеются не выявленные ранее закономерности (причём негативные), все вероятностные оценки могут оказаться сильно завышенными. Тем не менее, алгоритмы ESCK-6 и ШОРТ создавались с избыточным запасом прочности, который тем больше, чем больше циклов шифрования. Если и это кажется недостаточным, можно последовательно использовать эти алгоритмы с другими, используя несвязанные ключи.

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

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

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

3. Википедия. Шифр Вернама. [Электронный ресурс] – URL: https://ru.wikipedia.org/wiki/Шифр_Вернама

4. Сушко С.А. Практическая криптология. Лекция 10. [Электронный ресурс] – URL: http://bit.nmu.org.ua/ua/student/metod/cryptology/лекция%2010.pdf

5. Трунов Д.Н. От ESCK-5 к ESCK-6: основные отличия нового алгоритма шифрования. [Электронный ресурс] – URL: http://d-raft5.blogspot.com/2018/12/esck-5-esck-6.html

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

Опубликовано 26.06.2019 на http://d-raft5.blogspot.com

© Трунов Д.Н., 2019 г.

Приложение 1. Исходный текст алгоритма ШОРТ на языке программирования Object Pascal (Lazarus)

Текст приложения приведён в оригинальном файле.

Оригинальный файл: Открыть