Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

ИССЛЕДОВАНИЕ АЛГОРИТМОВ АНАЛИЗА ШИФРА CLEFIA

Ищукова Е.А. 1 Куликов А.В. 1
1 Южный федеральный университет Институт компьютерных технологий и информационной безопасности
В статье рассмотрен симметричный блочный алгоритм шифрования CLEFIA, представляющий собой обобщенную структуру Фейстеля. Данный алгоритм шифрования в 2012 г. был включен в международный стандарт облегченного шифрования ISO/IEC. В статье представлены результаты анализа основных криптографических операций, используемых в Clefia. Также был проанализирован Механизм переключения рассеивания (Diffusion Switching Mechanism – DSM), чередующий блоки замены и матрицы рассеивания. С целью оценки вклада механизма DSM в повышение криптографической стойкости к дифференциальному криптоанализу были проанализированы различные вариации упрощений алгоритма шифрования CLEFIA. В качестве упрощений были рассмотрены как уменьшение количества раундов шифрования, так и ослабление механизма DSM в виде отключения чередования блоков замены и/или матриц рассеивания. В результате работы был проанализирован DSM механизм, его степень влияния на стойкость шифра к дифференциальному классу атак. Перебор грубой силой для упрощённого шифра из девяти раундов можно осуществить со сложностью 1/2128, в то время как дифференциальным анализом удалось достигнуть результата в 1/212539. В работе представлены экспериментальные результата анализа. Было показано, что использование DSM-механизма в составе алгоритма шифрования CLEFIA не случайно, а имеет обоснованные причины использования.
криптография
блочный шифр
CLEFIA
дифференциальный анализ
разность текстов
1. ISO. ISO/IEC 29192-2:2012. [Электронный ресурс]. URL: https://www.iso.org/standard/56552.html (date of access: 08.11.2019).
2. Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, Tetsu Iwata The 128-bit Blockcipher CLEFIA (Extended Abstract) [Электронный ресурс]. URL: https://www.iacr.org/archive/fse2007/45930182/45930182.pdf (date of access: 08.11.2019).
3. Biham E., Shamir A. Differential Cryptanalysis of the Full 16-round DES. Advances in Cryptology. Crypto’92, Springer-Velgar, 1998. Р. 487–496.
4. Biham E., Shamir A. Differential Cryptanalysis of DESlike Cryptosystems, Extended Abstract. Crypto’90. SpringerVelgar, 1998. 105 р.
5. Ищукова Е.А., Бабенко Л.К., Толоманенко Е.А. Дифференциальный анализ шифра Кузнечик // Известия ЮФУ. Технические науки. Таганрог: Изд-во ЮФУ, 2017. № 5. С. 25–37.
6. Ищукова Е.А., Калмыков И.А. Дифференциальные свойства S-блоков замены для алгоритма ГОСТ 28147-89 // Инженерный вестник Дона. 2015. № 4 [Электронный ресурс]. URL: ivdon.ru/ru/ magazine/archive/n4y2015/3284 (дата обращения: 08.11.2019).

CLEFIA – блочный алгоритм шифрования, в основе конструкции которого лежит структура Фейстеля. На вход данный алгоритм шифрования ожидает 128 бит, которые в дальнейшем разбиваются на 4 части по 32 бита. Алгоритм шифрования авторами позиционируется как легковесный, и в 2012 г. организации ISO и IEC включили алгоритм CLEFIA в международный стандарт облегчённого шифрования ISO/IEC 29192-2:2012 [1]. Одной из ключевых особенностей в проектировании данного алгоритма шифрования является использование так называемого Механизма переключения рассеивания (Diffusion Switching Mechanism – DSM), благодаря которому обеспечивается использование различный F-функций в разных раундах шифрования [2]. Механизм подразумевает чередование криптографических примитивов в виде блоков замены и матриц рассеивания. Согласно данному механизму, различается принцип использования математических F-функций. Для четных и нечетных F-функций различается порядок использования блоков замен S0 и S1, а также используются различные матрицы М0 и М1 для перемножения данных.

Цель работы: исследовать влияние механизма DSM на стойкость алгоритма Clefia.

Материалы и методы: алгоритм шифрования CLEFIA, метод дифференциального криптоанализа, ПЭВМ AMD Ryzen 5 1600 Six-Core Processor, язык программирования Python.

Алгоритм CLEFIA подразумевает использование четырех веток. Преобразование открытого текста может выполняться под воздействием секретного ключа длиной 128, 192 или 256 бит. В зависимости от этого преобразование будет выполняться в течение 18, 22 и 26 раундов соответственно. В данной статье анализировался шифр с четырьмя ветками и ключом, размером 128 бит. Через GFNd,r мы обозначим d-веточную и r-раундовую функцию используемую в CLEFIA.

Буквой T обозначим промежуточное значение, RKi – раундовый ключ, необходимый для вычислений, а X и Y тексты на входе и выходе соответственно. Тогда алгоритм GFNd,r можно расписать следующим образом:

ihuk01.wmf

ihuk02.wmf

ihuk03.wmf

Обратная функция ihuk04.wmf использует подключи RKi в обратном порядке, также меняется направление сдвигов на этапах 2.2 и 3.

Алгоритм обработки данных CLEFIA можно представить функцией ENCr для зашифровки и DECr для расшифровки. Эти функции используют структуру GFN4,r, которая фактически представляет собой сеть Фейстеля с четырьмя ветками. Обозначим пару значений открытый текст – шифрованный текст как ihuk05.wmf. Будем считать, что каждый текст может содержать 4 фрагмента ihuk06.wmf, где ihuk07.wmf и ihuk08.wmf. Обозначим как ihuk09.wmf отбеливающие подключи и обозначим как ihuk10.wmf раундовые подключи. Функция DECr является обратной по отношению к функции ENCr, за счёт использования обратной функции ihuk11.wmf. На рис. 1 проилюстрирована функция ENCr.

Алгоритм выработки раундовых подключей подразумевает различную реализацию для 128, 192 и 256 бит ключа. Так как в данной статье рассматривается версия алгоритм шифрования для секретного ключа размерностью 128 бит, то в дальнейшем будет рассмотрен алгоритм выработки раундовых подключей для 128-битного секретного ключа.

ihukov1.tif

Рис. 1. Функция ENCr

Определим функцию DoubleSwap, используемую при выработке ключей, следую- щим образом:

ihuk12.wmf,

где ihuk13.wmf обозначает битовую строку, вырезанную начиная с бита a по бит b из строки X.

Алгоритм выработки раундовых подключей делится на две логические части: генерация промежуточного ключа L из исходного секретного ключа K и расширение K и L с целью генерации WKi и RKi. Промежуточный ключ L имеет длину 128 бит. Он генерируется с помощью функции ihuk14.wmf, на вход которой в качестве данных поступает значение секретного ключа ihuk15.wmf. При этом для преобразования в качестве раундовых подключей используется двадцать четыре 32-битных константы ihuk16.wmf. Таким образом раундовые ключи K и промежуточный ключ L используются для генерации отбеливающих подключей ihuk17.wmf и раундовых подключей ihuk18.wmf. На следующем шаге используется тридцать шесть 32-битных константных значений ihuk19.wmf. Таким образом получается, что для генерации всех подключей требуется шестьдесят константных значений.

ihuk20.wmf

Функция F, используемая в процессе шифрования, имеет две реализации: F1 и F2. В самих функциях используются матрицы рассеивания, обозначаемые как M, и блоки замены, обозначаемые S. Работу каждой из F-функций можно описать следующим образом:

ihuk21.wmf ihuk22.wmf

S0 и S1 представляют собой нелинейные 8-битные S-блоки. При этом в каждой из F-функций используется свой порядок применения S-блоков. Также разные F-функции используют на шаге 3 разные матрицы (М0 и М1). Матрицы имеют следующий вид (значения в матрице представлены в 16-ричном виде, a соответствует значению 10):

ihuk23.wmf ihuk24.wmf

При этом полиномиальное перемноже- ние между матрицами и векторами производится в поле GF(28). В качестве нормализующего полинома используется полиномом z8 + z4 + z3 + z2 + 1. Структура для функций F0 и F1 приведена на рис. 2.

IH2a.tif IH2b.tif

Рис. 2. Функции F0 и F1

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

В качестве метода исследования нами был выбран метод дифференциального криптоанализа, как один из наиболее популярных методов анализа симметричных блочных шифров [2]. Метод дифференциального криптоанализа рассматривает пары текстов при их изменении в зависимости от действий, совершаемых в каждом раунде. Впервые метод дифференциального криптоанализа был применен Э. Бихамом и А. Шамиром к анализу алгоритма шифрования DES [3, 4]. Сейчас этот метод широко применяется к анализу большинства шифров. В качестве дифференциала или разности рассматривается результат операции поразрядного сложения данных по модулю 2.

Матрицы рассеивания М0 и М1 размером 4х4 делят текст, поданный на вход, на 4 части по 8 бит, а далее эти 4 части подставляются в следующие уравнения:

ihuk25.wmf

Все вычисления необходимо выполнять в поле GF(28) над многочленом z8 + z4 + z3 + z2 + 1, что подразумевает трактовку сложения как операцию побитового xor, а умножения – как перемножения двух полиномов по модулю z8 + z4 + z3 + z2 + 1 [5, 6]. Коэффициенты перед x представляют собой полиномы, которые выглядят следующим образом: ihuk26.wmf

В первую очередь в ходе анализа была доказана обратимость матриц рассеивания по отношению к самим себе. Это позволяет нам легче находить удобную характеристику, если необходимо получить некоторую разность, которая дважды будет проходить через одну матрицу рассеивания. Следующим этапом было проанализировано поведение различных входов.

ihuk27.wmf ihuk28.wmf

Учитывая обратимость матрицы самой себе, можно получить следующую закономерность: при 1 ненулевом входе, мы всегда будем получать 4 ненулевых выхода, подавая 2 ненулевых выхода, мы получим 3–4 ненулевых, при подаче 3 ненулевых мы можем получить на выходе от 2 до 4 ненулевых текстов и, подавая 4 ненулевых текста, на выходе получаем от 1 до 4 ненулевых текстов. Количество ненулевых выходов зависит от того, какие коэффициенты будут подобраны [5].

В ходе анализа блоков замены было выяснено, что блоки замены S0 представляют больший интерес в рамках дифференциального криптоанализа, так как вероятность преобразования одной разности в другую у данного блока замены может достичь более высоких вероятностей по сравнению с S1 [6]. Данный вывод легко сделать, обратив внимание на табл. 1.

Таблица 1

Таблица со статистикой преобразований в блоках замены

Вероятность

n

S0

S1

Вероятность

n

S0

S1

0

0

40022

33151

≈1/25,41

6

848

0

1/27

2

19501

32130

1/25

8

119

0

1/26

4

5037

255

≈1/24,68

10

9

0

Для анализа DSM механизма было необходимо ограничить область воздействия данного механизма или полностью его отключить. Отключение и ограничение подразумевают собой исключение разнообразия блоков замены и/или матриц рассеивания. Таким образом, к примеру, будут использоваться только S0, даже там, где должен был быть блок замены S1. То же касается матриц рассеивания.

Результаты исследования и их обсуждение

В ходе работы были проанализированы следующие вариации упрощений: шесть раундов без разнообразия M и S блоков, двенадцать раундов без разнообразия M и S блоков, двенадцать раундов без разнообразия M блоков, шесть раундов с DSM механизмом и девять раундов с DSM механизмом. Вариации с шестью раундами использовались не столько для получения сложности нахождения дифференциальной характеристики, сколько для того, чтобы убедиться в правильности найденных характеристик с помощью персонального компьютера. Таким образом шестираундовые характеристики были вручную найдены на персональном компьютере, в то время как остальные были разработаны теоретически. Перебор и вычисления осуществлялись с помощью ПЭВМ со следующими характеристиками: процессор AMD Ryzen 5 1600 Six-Core Processor.

Для проведения полного анализа механизма DSM были проведены эксперименты для различных вариантов использования блоков замены и матриц М0 и М1. были по очереди отключены разнообразия блоков замены и матриц М. В ходе работы были разработаны алгоритмы анализа с учетом различных вариантов упрощений шифра. Кроме того, чтобы иметь возможность оценить влияние DSM-механизма в полной мере, были построены дифференциальные характеристики для различного числа раундов шифрования (от 6 до 12) и для них теоретически просчитаны значения вероятностей. Результаты теоретических рассчетов и практических экспериментальных данных сведены в табл. 2. В каждом эксперименте было атаковано 8 бит ключа.

Таблица 2

Сложность анализа в зависимости от конфигурации алгоритма

Раунды

S

М

Реализация

Итоговая сложность

6

только S0

только М0

практическая

1/214,04

6

S0 и S1

М0 и М1

практическая

1/216,36

9

S0 и S1

М0 и М1

теоретическая

1/2125,39

12

только S0

только М0

теоретическая

1/294,7

12

S0 и S1

только М0

теоретическая

1/295

Можно видеть, что при использовании только одной матрицы М0 в DSM-механизме, сложность анализа 12 раундов будет ниже сложности анализа 9 раундов, где используются обе матрицы М0 и М1. Это связано с тем, что в случае с двумя матрицами М0 и М1, чем больше раундов, тем тяжелее подобрать удобные разности для построения итогового дифференциала. В ходе анализа было показано, что при использовании обеих матриц М0 и М1 невозможно получить одинаковые выходы разностей при использовании одинаковых разностей на входах в F-функцию. Одним из приемов, который часто используется в дифференциальном криптоанализе, является пропуск некоторых преобразований, где на вход поступает разность, равная нулю. В данном же случае, при использовании разных матриц М0 и М1, выявленное свойство не позволяет пропускать преобразования и вероятность начинает уменьшаться слишком быстро. При использовании в каждой F-функции одинаковых матриц в результате анализа удалось построить характеристику для 12 раундов шифрования. Вероятность появления такой характеристики составила 1/294,7. В то же время при использовании разных матриц М0 и М1 удалось построить характеристику только для 9 раундов. При этом вероятность появления такой характеристики оказалась слишком маленькой 1/2125,39, что слишком близко к полному перебору.

Аналогичный эксперимент проводился и для чередования S-блоков замены. Было показано, что для блока S0 в таблице присутствуют более высокие значения вероятностей, чем для блока S1. Также было показано, что для блоков S0 и S1 одинаковые значения входных разностей очень часто не могут быть преобразованы к одинаковым значениям разностей на выходе, что сильно затрудняет построение многораундовых характеристик.

Заключение

В результате проделанной работы было показано, что использование DSM-механизма в составе алгоритма шифрования CLEFIA не случайно, а имеет обоснованные причины использования. Наличие DSM-механизма значительно увеличивает сложность анализа шифра. Как следствие, при рассмотрении варианта шифра с использованием DSM-механизма можно проанализировать гораздо меньше раундов шифрования, чем при рассмотрении шифра без DSM-механизма.

Работа выполнена при поддержке гранта РФФИ № 17-07-00654 «Разработка и исследование последовательных и параллельных алгоритмов анализа современных симметричных шифров с использованием технологий MPI, NVIDIA CUDA, SageMath».


Библиографическая ссылка

Ищукова Е.А., Куликов А.В. ИССЛЕДОВАНИЕ АЛГОРИТМОВ АНАЛИЗА ШИФРА CLEFIA // Современные наукоемкие технологии. – 2019. – № 12-2. – С. 287-292;
URL: https://top-technologies.ru/ru/article/view?id=37873 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674