CLEFIA (от фр. clef «ключ») — блочный шифр с размером блока 128 битов, длиной ключа 128, 192 или 256 битов и количеством раундов 18, 22, 26 соответственно. Этот криптоалгоритм относится к «легковесным» алгоритмам и использует сеть Фейстеля как основную структурную единицу. CLEFIA был разработан корпорацией Sony и представлен в 2007 году. Авторами являются сотрудники компании Тайдзо Сираи, Кёдзи Сибутани, Тору Акисита, Сихо Мориаи, а также доцент Нагойского университета Тэцу Ивата.
CLEFIA | |
---|---|
![]() | |
Создатель | Тайзо Ширай, Кёдзи Шибутани, Тору Акишита, Шихо Мориаи, Тэцу Ивата |
Создан | 2007 г. |
Опубликован | 22 марта 2007 г. |
Размер ключа | 128, 192, 256 бит |
Размер блока | 128 бит |
Число раундов | 18/22/26 (зависит от размера ключа) |
Тип | Сеть Фейстеля |
Основное назначение данного шифра — использование в качестве безопасной альтернативы AES в сфере защиты авторских прав и DRM-систем, а также применение в RFID-метках и смарт-картах.
Является одним из самых эффективных криптоалгоритмов при аппаратной реализации: аппаратная реализация CLEFIA может достигать эффективности 400,96 Kbps на эквивалентную логическую ячейку[англ.] шифратора, что является самым высоким показателем среди алгоритмов, включённых в стандарты ISO на 2008 год[1].
Алгоритм стал одним из первых шифров, применяющим технологию DSM (англ. Diffusion Switching Mechanism) для увеличения защищённости от линейного и дифференциального криптоанализа[2][3].
Схема шифрования данных
правитьПрефикс для двоичной строки в шестнадцатеричной форме | |
показывает длину в битах | |
Конкатенация | |
Обновление значения значением | |
Побитовое исключающее ИЛИ | |
Умножение в |
Алгоритм состоит из двух составных частей: части обработки ключа и части обработки данных. Число раундов CLEFIA зависит от длины ключа и составляет соответственно 18, 22 или 26 раундов, при этом используется 36, 44 и 52 подключа. Алгоритм использует ключевое забеливание[англ.] с дополнительным подключами перед обработкой данных и после неё.
Базовым этапом шифрования данных в CLEFIA является применение обобщённой сети Фейстеля с 4 или 8 ветвями, которая используется как в части обработки данных, так и в части обработки ключа (рисунок 1). В общем случае, если обобщённая сеть Фейстеля имеет d-ветвей и r-раундов, она обозначается как (англ. generalized Feistel network). Далее рассмотрен алгоритм работы сети Фейстеля в случае использования 4-х ветвей и блока данных в 128 бит.
В , кроме 4-x 32-х битных входов ( ) и 4-x 32-х битных выходов ( ), также используются раундовые ключи . Их количество составляет в связи с тем, что для каждого раунда требуется в два раза меньше ключей, чем ветвей. генерируются в части обработки ключа[4].
Каждая ячейка Фейстеля задействует также две различные -функции: . -функции относятся к SP-типу функций и используют:
- блок подстановок (S-блок, англ. s-box);
- матрицы распространения[англ.] в поле Галуа (англ. MDS matrix).
F-функции
правитьДве -функции и , используемые в , включают в себя нелинейные 8-битные S-блоки и , рассмотренные далее, и матрицы и размером . В каждой -функции эти S-блоки используются в различном порядке, и применяется своя матрица распространения для умножения в поле Галуа. На рисунках показана содержательная часть -функций[4]. -функции определяются следующим образом:
Функция Шаг 1. Шаг 2. Шаг 3.
Функция Шаг 1. Шаг 2. Шаг 3.
S-блоки
правитьВ CLEFIA используется два разных типа S-блоков, размером по 8 бит каждый. Они сгенерированы так, чтобы минимализировать занимаемую ими площадь при аппаратной реализации. Первый ( ) состоит из 4-битных случайных S-блоков. Во втором ( ) используется обратная функции над полем . В таблицах ниже представлены выходные значения в шестнадцатеричной системе счисления для S-блоков. Старшие 4-бита для 8-битного ввода S-блока обозначают строку, а младшие 4-бита обозначают столбец. Например, если введено значение , то блок выводит [3].
Первый S-блок
правитьсоздан с помощью применения четырёх 4-битных S-блоков следующим образом:
Алгоритм получения выходных данных при использования блока Шаг 1. Шаг 2. Шаг 3.
Умножение в выполняется в над многочленами, которое определяется неприводимым полиномом . В таблице можно найти соответствующий полученный S-box .
|
|
Второй S-блок
правитьБлок определяется как:
При этом обратная функция находится в поле , которое задано неприводимым полиномом . — аффинные преобразования над , определённые следующим образом:
|
|
Здесь используется, что и . Таким образом получается блок .
.0 | .1 | .2 | .3 | .4 | .5 | .6 | .7 | .8 | .9 | .a | .b | .c | .d | .e | .f | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0. | 6c | da | c3 | e9 | 4e | 9d | 0a | 3d | b8 | 36 | b4 | 38 | 13 | 34 | 0c | d9 |
1. | bf | 74 | 94 | 8f | b7 | 9c | e5 | dc | 9e | 07 | 49 | 4f | 98 | 2c | b0 | 93 |
2. | 12 | eb | cd | b3 | 92 | e7 | 41 | 60 | e3 | 21 | 27 | 3b | e6 | 19 | d2 | 0e |
3. | 91 | 11 | c7 | 3f | 2a | 8e | a1 | bc | 2b | c8 | c5 | 0f | 5b | f3 | 87 | 8b |
4. | fb | f5 | de | 20 | c6 | a7 | 84 | ce | d8 | 65 | 51 | c9 | a4 | ef | 43 | 53 |
5. | 25 | 5d | 9b | 31 | e8 | 3e | 0d | d7 | 80 | ff | 69 | 8a | ba | 0b | 73 | 5c |
6. | 6e | 54 | 15 | 62 | f6 | 35 | 30 | 52 | a3 | 16 | d3 | 28 | 32 | fa | aa | 5e |
7. | cf | ea | ed | 78 | 33 | 58 | 09 | 7b | 63 | c0 | c1 | 46 | 1e | df | a9 | 99 |
8. | 55 | 04 | c4 | 86 | 39 | 77 | 82 | ec | 40 | 18 | 90 | 97 | 59 | dd | 83 | 1f |
9. | 9a | 37 | 06 | 24 | 64 | 7c | a5 | 56 | 48 | 08 | 85 | d0 | 61 | 26 | ca | 6f |
a. | 7e | 6a | b6 | 71 | a0 | 70 | 05 | d1 | 45 | 8c | 23 | 1c | f0 | ee | 89 | ad |
b. | 7a | 4b | c2 | 2f | db | 5a | 4d | 76 | 67 | 17 | 2d | f4 | cb | b1 | 4a | a8 |
c. | b5 | 22 | 47 | 3a | d5 | 10 | 4c | 72 | cc | 00 | f9 | e0 | fd | e2 | fe | ae |
d. | f8 | 5f | ab | f1 | 1b | 42 | 81 | d6 | be | 44 | 29 | a6 | 57 | b9 | af | f2 |
e. | d4 | 75 | 66 | bb | 68 | 9f | 50 | 02 | 01 | 3c | 7f | 8d | 1a | 88 | bd | ac |
f. | f7 | e4 | 79 | 96 | a2 | fc | 6d | b2 | 6b | 03 | e1 | 2e | 7d | 14 | 95 | 1d |
Матрицы распространения
правитьМатрицы распространения заданы следующим образом:
|
|
Умножения матрицы и векторов выполняются в поле , определённое неприводимым полиномом .
Общая структура шифрования
правитьТаким образом, на основе обобщённой сети Фейстеля (4 входа для блока данных; 2r входа для раундовых ключей; 4 выхода для шифротекста):
Алгоритм шифрования и расшифрования данных:
Шифрование ( ) Шаг 1. Шаг 2. Шаг 2.1. Шаг 2.2. Шаг 3.
Расшифрование ( ) Шаг 1. Шаг 2. Шаг 2.1. Шаг 2.2. Шаг 3.
Число раундов составляет 18, 22 и 26 для 128-битных, 192-битных и 256-битных ключей соответственно. Общее количество зависит от длины ключа, поэтому часть обработки данных требует 36, 44 и 52 раундовых ключей для 128-битных, 192-битных и 256-битных ключей соответственно.
Результат от также подвергается ключевому забеливанию[англ.].
Использование ключевого забеливания
правитьВ часть обработки данных CLEFIA, состоящую из для шифрования и для расшифрования, входят процедуры исключающее «или» между текстом и отбеливающими ключами в начале и в конце алгоритма.
Таким образом, пусть — открытый текст и зашифрованный текст, и пусть — части открытого текста и зашифрованного текста, где и , и пусть — отбеливающие ключи, а — раундовые ключи, предоставляемые частью обработки ключа. Тогда алгоритм шифрования с использованием ключевого забеливания:
Функция шифрования Шаг 1. Шаг 2. Шаг 3.
Функция расшифрования Шаг 1. Шаг 2. Шаг 3.
Алгоритм обработки ключа
правитьЧасть обработки ключей в шифре CLEFIA поддерживает 128, 192 и 256-битные ключи и в результате выдаёт отбеливающие ключи и раундовые ключи для части обработки данных. Пусть будет ключом, а — промежуточным ключом (получается с помощью сокращённой части обработки данных), тогда часть обработки ключа состоит в трёх этапах:
- Генерация из .
- Генерация из .
- Генерация из и .
Чтобы сгенерировать из , часть обработки ключа для 128-битного ключа использует 128-битную (4 входа по 32 бита), в то время как для 192/256-битных ключей используется 256-битная (8 входов по 32 бита). Далее приведёно описание алгоритма в случае 128-битного ключа.
Функция перестановки бит
правитьДанный алгоритм использует функцию перестановки бит DoubleSwap (обозначение: ):
Причём обозначает битовую строку, вырезанную с -го бита по -й бит из .
Генерация констант
правитьСхема требует на вход раундовые ключи в количестве (если ), и, когда эта схема применяется в части обработки ключа, шифр CLEFIA применяет заранее сгенерированные константы как раундовые ключи. Также дополнительные константы необходимы при втором этапе, при генерации и , и их количество равно (но в данном случае константы и из части обработки данных).
Эти 32-х битные константы обозначаются как , где — номер константы, — используемое количество бит для ключа(может быть 128, 196, 256). Тогда количество констант будет 60, 84, 92 для 128, 192, 256 битовых ключей соответственно.
Пусть и . Тогда алгоритм для генерации (в таблице количество итераций и начальные значения ):
Шаг 1. Шаг 2. Шаг 2.1. Шаг 2.2. Шаг 2.3.
Где — логическое отрицание, — циклический левый сдвиг на -бит; а умножение происходит в поле и определённо неприводимым многочленом .
Обработка ключа в случае 128-битного ключа
править128-разрядный промежуточный ключ генерируется путём применения , который принимает на вход двадцать четыре 32-разрядные константы в качестве раундовых ключей и в качестве данных для шифрования. Затем и используются для генерации и в следующих шагах:
Генерация из : Шаг 1.
Генерация из : Шаг 2.
Генерация из и : Шаг 3. Шаг 3.1. Шаг 3.2. Шаг 3.3. Шаг 3.4.
Особенности шифра
правитьCLEFIA может быть эффективно реализована как в аппаратном, так и в программном обеспечении. В таблице показаны основные преимущества технологий, использованных в этом шифре[3].
| |
SP-тип -функций |
|
DSM |
|
S-блоки |
|
Матрицы |
|
Часть обработки ключа |
|
Преимуществами и особенностями в алгоритма CLEFIA являются:
- Обобщённую сеть Фейстеля ;
- DSM (англ. Diffusion Switching Mechanism);
- Два S-бокса.
Особенности реализации GFN
правитьCLEFIA использует обобщённую структуру Фейстеля с 4 ветвями, которая рассматривается как расширение традиционной структуры Фейстеля с 2 ветвями. Существует много типов обобщённых структур Фейстеля. В алгоритме CLEFIA используется второй тип этой структуры (схема 1)[5]. Структура второго типа имеет две F-функции в одном раунде для четырёх линий данных.
Структура типа 2 имеет следующие особенности:
- -функции меньше, чем у традиционной структуры Фейстеля;
- множественные -функции могут обрабатываться одновременно;
- как правило, требует больше раундов, чем традиционная структура Фейстеля.
Первая особенность является большим преимуществом для программных и аппаратных реализаций; а вторая особенность подходит для эффективной реализации, особенно в аппаратном обеспечение. Но при этом, заметно увеличивается количество раундов из-за третьей особенности. Однако преимущества структуры второго типа превосходят недостатки для данной конструкции блочного шифр, так как используется новая методика программирования, использующая DSM и два типа S-боксов, что позволяет эффективно сократить количество раундов.
Использование Diffusion Switching Mechanism
правитьCLEFIA использует две разные матрицы распространения для повышения устойчивости к дифференциальным атакам и линейным атакам с использованием механизма DSM (схема 2). Эта методика проектирования была первоначально разработана для традиционных сетей Фейстеля[3]. Эта техника была перенесена на , что является одним из уникальных свойств этого шифра. Также, благодаря DSM можно увеличить гарантированное количество активных S-блоков при том же количество раундов.
Следующая таблица показывает гарантированное количество активных S-блоков в шифре CLEFIA. Данные получены при помощи компьютерного моделирования с использованием алгоритма поиска исчерпывающего типа[3]. Столбцы «D» и «L» в таблице показывают гарантированное количество активных S-блоков при дифференциальном и линейном криптоанализе соответственно. Из этой таблицы можно видеть, что влияние DSM проявляется уже при , и гарантированное количество S-боксов увеличиваются примерно на 20 % — 40 %, в отличие от структуры без DSM. Следовательно, количество раундов может быть уменьшено, что означает, что производительность улучшается.
Гарантированное число активных S боксов |
---|
В таблице красным выделена строка, указывающая на минимальное требуемое количество раундов, чтобы шифр был устойчив к криптоанализу методом полного перебора(см. также). Синим цветом выделены строки, количество раундов которых используется в алгоритме CLEFIA с 128/192/256-битовыми ключами соответственно.
Особенности двух S-боксов
правитьCLEFIA использует два разных типа 8-битных S-блоков: один основан на четырёх 4-битных случайных S-блоках; а другой основан на обратной функции в , которая имеет максимально возможную трудоёмкость атаки для дифференциального криптоанализа и линейного криптоанализа . Оба S-блока выбраны для эффективной реализации, особенно в аппаратном обеспечении.
Для параметров безопасности составляет , а его составляет . Для и оба равны [6].
Криптостойкость
правитьДифференциальный криптоанализ
правитьПо таблице количества активных S боксов с DSM(в пункте Использование Diffusion Switching Mechanism) минимальное число раундов равно 12. Таким образом, используя 28 активных S-блоков для 12-раундового CLEFIA и (см. также), определяем, что вероятность характеристики . Это означает, что трудоёмкость атаки выше и для атакующего нет полезной дифференциальной характеристики в 12 раундов. Кроме того, поскольку имеет более низкий , ожидается, что фактическая верхняя граница будет ниже, чем приведённая выше оценка[3]. В результате мы считаем, что полный цикл CLEFIA защищён от дифференциального криптоанализа (в CLEFIA используется 18 раундов).
Линейный криптоанализ
правитьДля оценки сложности линейного криптоанализа применяется подход на основе подсчёта активных S-блоков при заданном количестве раундов. Поскольку , используя 30 активных S-блоков для 12-раундового CLEFIA, . Это даёт вывод, что злоумышленнику трудно найти достаточное количество пар текст-шифротекст, которые можно использовать для успешной атаки на CLEFIA. В результате полнофункциональный CLEFIA достаточно защищён от линейного криптоанализа[6].
Невозможный дифференциальный криптоанализ
правитьСчитается, что невозможная дифференциальная атака[англ.] является одной из самых мощных атак против CLEFIA. Найдены следующие два невозможных дифференциальных пути[7]:
где — любая ненулевая величина. Таким образом, используя описанный выше отличительный признак, можно смоделировать атаку (для каждой длины ключа), которая будет восстанавливать текущий ключ. В следующей таблице приведены данные о сложностях, необходимых для невозможных дифференциальных атак. Согласно этой таблице ожидается, что у CLEFIA с полным циклом есть достаточный запас безопасности против этой атаки.
Количество раундов | Длина ключа | Ключевое забеливание | Количество открытых текстов | Временная сложность |
---|---|---|---|---|
10 | 128,192,256 | + | ||
11 | 192,256 | + | ||
12 | 256 | - |
Сравнение с другими шифрами
правитьCLEFIA обеспечивает компактную и быструю реализацию одновременно без ущерба для безопасности. По сравнению с AES, наиболее широко используемым 128-битным блочным шифром, CLEFIA имеет преимущество в аппаратной реализации. CLEFIA может реализовывать скорость 1,6 Гбит/с с площадью менее 6 тысяч эквивалентных логических ячеек[англ.], а пропускная способность на шлюз является самой высокой в мире на 2008 год (в случае аппаратной реализации)[1].
В таблице ниже приведена сравнительная характеристика шифра CLEFIA по отношению к некоторым другим известным шифрам[1]:
Алгоритм | Размер блока(биты) | Размер ключа(биты) | Количество раундов | Пропускная способность(Mpbs) | Площадь (Kgates) | Эффективность (Kpbs/gates) |
---|---|---|---|---|---|---|
CLEFIA | 128 | 128 | 18 | 1,605.94 | 5.98 | 268.63 |
36 | 715.69 | 4.95 | 144.59 | |||
AES | 128 | 128 | 10 | 3,422.46 | 27.77 | 123.26 |
Camellia | 128 | 128 | 23 | 1,488.03 | 11.44 | 130.11 |
SEED | 128 | 128 | 16 | 913.24 | 16.75 | 54.52 |
52 | 517.13 | 9.57 | 54.01 | |||
CAST-128 | 64 | 128 | 17 | 386.12 | 20.11 | 19.20 |
MISTY1 | 64 | 128 | 9 | 915.20 | 14.07 | 65.04 |
30 | 570.41 | 7.92 | 72.06 | |||
TDEA | 64 | 56, 112, 168 | 48 | 355.56 | 3.76 | 94.50 |
Алгоритм | Размер блока(биты) | Размер ключа(биты) | Количество раундов | Пропускная способность(Mpbs) | Площадь (Kgates) | Эффективность (Kpbs/gates) |
---|---|---|---|---|---|---|
CLEFIA | 128 | 128 | 18 | 3,003.00 | 12.01 | 250.06 |
36 | 1,385.10 | 9.38 | 147.71 | |||
AES | 128 | 128 | 10 | 7,314.29 | 45.90 | 159.37 |
Camellia | 128 | 128 | 23 | 2,728.05 | 19.95 | 136.75 |
SEED | 128 | 128 | 16 | 1,556.42 | 25.14 | 61.90 |
52 | 898.37 | 12.33 | 72.88 | |||
CAST-128 | 64 | 128 | 17 | 909.35 | 33.11 | 27.46 |
MISTY1 | 64 | 128 | 9 | 1,487.68 | 17.22 | 86.37 |
30 | 772.95 | 10.12 | 76.41 | |||
TDEA | 64 | 56, 112, 168 | 48 | 766.28 | 5.28 | 145.10 |
Применение
правитьВ 2019 году организации ISO и IEC включили алгоритмы PRESENT и CLEFIA в международный стандарт облегчённого шифрования ISO/IEC 29192-2:2019[8].
Существует библиотека CLEFIA_H на языке программирования C, реализующая шифр CLEFIA[9].
Примечания
править- ↑ 1 2 3 Takeshi Sugawara, Naofumi Homma, Takafumi Aoki, Akashi Satoh. High-performance ASIC Implementations of the 128-bit Block Cipher CLEFIA (англ.) // 2008 IEEE International Symposium on Circuits and Systems. — Seattle, WA, USA: IEEE, 2008. — 13 июнь. — ISBN 978-1-4244-1683-7. — ISSN 0271-4302. — doi:10.1109/ISCAS.2008.4542070.
- ↑ Shirai T., Shibutani K. On Feistel Structures Using a Diffusion Switching Mechanism (англ.). — Berlin, Heidelberg: Springer, 2006. — ISBN 978-3-540-36597-6. — doi:10.1007/11799313_4. Архивировано 17 июня 2018 года.
- ↑ 1 2 3 4 5 6 Taizo Shirai, Kyoji Shibutani, Toru Akishita, Shiho Moriai, Tetsu Iwata. The 128-bit Blockcipher CLEFIA(Extended Abstract) (англ.). — 2007. Архивировано 1 марта 2022 года.
- ↑ 1 2 Sony Corporation. The 128-bit Blockcipher CLEFIA Algorithm Specification (англ.). — 2007. Архивировано 19 января 2022 года.
- ↑ Y. Zheng, T. Matsumoto, H. Imai. On the construction of block ciphers provably secure and not relying on any unproved hypotheses (англ.). — Springer-Verlag: Crypto’89 , LNCS 435, 1989. — P. 461—480. Архивировано 9 июня 2018 года.
- ↑ 1 2 Sony Corporation. The 128-bit Blockcipher CLEFIA Security and Performance Evaluations (англ.). — 2007. Архивировано 20 января 2022 года.
- ↑ Wei Wang, Xiaoyun Wang. Improved Impossible Differential Cryptanalysis of CLEFIA (англ.). — 2008. Архивировано 10 ноября 2019 года.
- ↑ ISO. ISO/IEC 29192-2:2012 . Дата обращения: ноябрь 2019. Архивировано 21 октября 2020 года.
- ↑ Cipher Reference . Дата обращения: 5 декабря 2019. Архивировано 3 ноября 2019 года.