От ESCK-5 к ESCK-6: основные отличия нового алгоритма шифрования

Трунов Д.Н.

ОТ ESCK-5 К ESCK-6: ОСНОВНЫЕ ОТЛИЧИЯ НОВОГО
АЛГОРИТМА ШИФРОВАНИЯ

Введение

В алгоритме шифрования ESCK-5 [1] реализован некоторый способ приближения к так называемому одноразовому блокноту (он же шифр Вернама) — криптографической системе с доказанной абсолютной стойкостью [2, 3]. В классическом виде ключ такого шифра должен обладать следующими критически важными свойствами:

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

2) совпадать по размеру с шифруемым текстом (или превосходить его);

3) применяться только один раз;

4) после использования ключ должен быть уничтожен.

В ESCK-5 вместо истинно случайного ключа применяется псевдослучайный ключ, вычисленный на основе заданного основного ключа и самих шифруемых данных. Для усложнения определения возможным злоумышленником «неслучайности» ключа шифрования (то есть выявления закономерностей в нём), применяется основной ключ достаточно большой длины (8192 бита), а вычисления производятся на протяжении большого количества циклов.

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

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

Безопасность алгоритмов шифрования

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

1) сложность данных — объём данных, используемых на входе операции вскрытия;

2) сложность обработки — время, нужное для проведения вскрытия;

3) требования к памяти — объём памяти, необходимый для вскрытия.

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

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

1) другие сообщения, зашифрованные тем же алгоритмом и ключом;

2) несколько пар открытых и зашифрованных одним и тем же ключом сообщений;

3) некоторые сведения об открытом сообщении в виде стандартного начала, ключевых слов и т.д.

Уязвимости в ESCK-5

Оценка безопасности алгоритма ESCK-5 не столь однозначна: многое зависит от длины шифруемых данных, режима и циклов шифрования. Но очевидно, что чем меньше циклов, тем менее безопасен алгоритм. Самым ненадёжным будет шифрование при единственном цикле.

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

Одна из уязвимостей заключается в том, что для двух мало различающихся сообщений величины F для некоторых (или даже многих) 32-битных элементов будут одинаковыми. Знание этих величин может позволить раскрыть часть третьего зашифрованного сообщения даже без знания ключа. Ещё хуже то, что знание величин F позволяет раскрывать части ключа, от которых эти величины зависят. А при достаточном количестве информации и вычислительных ресурсов есть возможность раскрыть ключ целиком, что недопустимо. Правда, уже при 2-3 циклах шифрования возможность такого вскрытия усложняется на несколько порядков.

Другая существенная уязвимость может проявиться при шифровании неполного блока, состоящего из одного-двух 32-битных элементов. Для первого такого элемента может сложиться так, что величина F будет зависеть только от некоторой части ключа и не меняться от цикла к циклу. Если так, то независимо от длины и значения ключа злоумышленнику нужно проверить лишь 2³² варианта величины F, чтобы найти нужную и научиться раскрывать первый элемент любого сообщения, зашифрованного тем же ключом. В некоторых случаях вскрытие даже одного первого элемента может стать критическим. В новой версии алгоритма требовалось закрыть эти уязвимости.

Увеличение разрядности

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

То есть алгоритм будет по-прежнему оперировать массивом ключа K и текущим массивом M для блока данных, состоящих из 256 элементов каждый. Только теперь эти элементы будут представлять собой 64-разрядный целые числа без знака. В языке программирования C# такие числа определяются типом ulong или структурой UInt64 [5].

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

Вычисление динамических адресов

Величина Adr, содержащая динамические адреса вспомогательных элементов в ESCK-6 рассчитывается немного по-другому. Она вычисляется по функции, аргументами которой является текущий элемент ключа, а также предыдущий и следующий элемент шифруемого массива M. Для нулевого элемента вместо предыдущего берётся последний элемент массива ключа — K[255]. Для последнего шифруемого элемента следующий берётся не из массива M, а из массива K (либо из уже обработанных элементов в начале массива M). Ниже приведён фрагмент алгоритма на языке C#.

    // получение текущего элемента ключа

    A = K[I];

    // получение предыдущего элемента рабочего массива

    if (I > 0)

        B = M[I - 1];

    else

        B = K[255];

    // получение следующего элемента рабочего массива

    Adr = (uint)((I + 1) & 0xFF);

    if (Adr <= Size)

        C = M[Adr];

    else

        C = K[Adr];

    // вычисление основного адреса

    Adr = A & B;

    F = ~(A | C);

    Adr = ROL64((Adr ^ F), 7);

    F = (~B) & C;

    Adr = ROL64((Adr ^ F), 7);

Здесь A, B, C и F – вспомогательные 64-битные переменные типа ulong, а функция ROL64 выполняет циклический сдвиг влево на заданное число бит для 64-разрядных целых чисел.

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

Замена схемы шифрования

В алгоритме ESCK-5 текущий элемент M[I] шифровался при помощи величины F, которая вычислялась в течение нескольких последовательных операций с участием части ключа и четырёх вспомогательных величин A, B, C и D, взятых из шифруемого массива или массива ключа по динамическим адресам. С помощью вычисленной величины F менялся уже текущий элемент M[I]. Как уже упоминалось, такая схема могла стать весьма уязвимой при малом количестве циклов шифрования.

В ESCK-6 было решено выполнять операции не над промежуточной величиной F, а сразу над шифруемым элементом M[I]. Кроме того предполагалось увеличить количество частей ключа, участвующих в шифровании элемента M[I]. Поскольку 64-битная переменная Adr может хранить теперь 8 динамических адресов, вместо четырёх вспомогательных величин также было решено применять восемь: четыре (A, B, C, D) брать из массива ключа K, а ещё четыре (E, F, G, H) – из шифруемого массива M. Как всегда, если нельзя брать элемент из массива M (совпадение адреса с текущим номером I или выход за пределы шифруемого размера), величина берётся из массива K с тем же адресом.

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

    // последовательная зашифровка текущего элемента

    M[I] = ROL64(M[I] ^ (~((A + B + C + D) ^ K[I])), 7);

    M[I] = ROL64(M[I] ^ (A | E), 7);

    M[I] = ROL64(M[I] ^ (B & (~F)), 7);

    M[I] = ROL64(M[I] ^ (~(C & G)), 7);

    M[I] = ROL64(M[I] ^ ((~D) | H), 7);

    M[I] = ROL64(M[I] ^ ((E + F + G + H) | (~Adr)), 7);

Режимы шифрования

Как упоминалось выше, уязвимость алгоритма при шифровании блока малого размера устраняется при условии, что блок будет состоять минимум из двух 64-битных элементов. Поэтому в ESCK-6 не допускается шифрование менее двух таких элементов: если шифруемых данных меньше 16 байт (128 бит), они обязательно дополняются недостающими байтами, чтобы сформировать необходимые два элемента по 64 бита.

В алгоритме ESCK-5 для такого дополнения недостающими байтами применялся режим mdMin16, который по умолчанию был отключен, мог быть включен по требованию. В ESCK-6 любое шифруемое сообщение обязательно дополняется до минимум 16 байт, если оно короче. Потому включение или выключение режима mdMin16 становится бесполезным, из-за чего было решено исключить этот режим из алгоритма.

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

    // режимы шифрования

    public const byte mdChng = 1; // смена ключа при переходе между блоками

    public const byte mdStr = 2; // удлинение неполного блока

    public const byte mdRndm = 4; // заполнение свободных ячеек случайными числами

    public const byte mdChain = 8;// смена ключа по цепочке

Заключение

Алгоритм шифрования ESCK-6 является доработанной и исправленной версией алгоритма ESCK-5. Все изменения, отличающие новый алгоритм от прежнего, призваны повысить общую безопасность шифрования и устранить некоторые конкретные уязвимости. Так улучшенная схема вычисления динамических адресов позволяет обеспечить надёжную связь шифруемых элементов и их зависимость от меняющихся от цикла в цикл элементов ключа. Изменённая схема шифрования затрудняет вскрытие шифра без знания ключа и/или получение части ключа даже при шифровании по одному циклу. Увеличение разрядности повышает общую безопасность алгоритма и позволяет применять больше элементов с динамическими адресами. Исключается режим шифрования mdMin16, который теперь всегда включен. Всё остальное вошло из ESCK-5 в ESCK-6 без изменений, не считая исправлений, связанных с повышением разрядности.

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

1. Трунов Д.Н. Алгоритм шифрования ESCK-5: описание, принцип работы, исходные тексты [Электронный ресурс] – URL: http://d-raft5.blogspot.com/2018/04/esck-5.html

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

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

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

5. Шилдт, Герберт. Полный справочник по C#. Пер. с англ. – М.: Издательский дом «Вильямс», 2004. – 752 с.: ил.