PRINCE (шифр)

PRINCE
Создатель	Датский технический университет, INRIA, Рурский университет, NXP Semiconductors
Опубликован	2012 г.
Размер ключа	128 бит
Размер блока	64 бит
Число раундов	12
Тип	SPN

PRINCE — блочный шифр с малой задержкой при аппаратной реализации (размер блока 64 бита, ключ 128 бит). Особенностью шифра является «α-отражение» (дешифрование выполняется, повторно используя процесс шифрования с немного изменённым ключом). Шифр происходит от алгоритмов AES и Present.

Шифр представлен в 2012 году на международной конференции по теории и применению криптологии и информационной безопасности. Разработчики: Julia Borghoff, Anne Canteaut, Lars R. Knudsen, Gregor Leander, Christan Rechberger, Soeren S. Thomsen, Elif Bilge Kavun, Tolga Yalcin, Tim Güneysu, Christof Paar, Miroslav Knezevic, Ventzi Nikov, Peter Rombouts.

Характеристики

Основан на SP-сети с двенадцатью раундами. PRINCE относится к категории легковесных шифров. На это указывает его небольшой размер реализации, требуемые ресурсы (объём памяти или регистров для хранения данных и промежуточного состояния), сложность реализации (типы необходимых операций и размер операндов), энергия, необходимая для выполнения операций безопасности. Также шифр имеет небольшие размеры блоков (64 бит), что характерно для легковесных шифров. Это может уменьшить размер сообщения для коротких пересылок из-за меньшего заполнения. Но с другой стороны, количество данных, которые можно защитить с помощью данного ключа, будет намного меньше по сравнению, например, с AES. Короткий ключ 128 бит снижает надёжность обеспечиваемой защиты и сокращает срок службы используемого ключа.

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

Шифр представляет собой SP-сеть, которая имеет 12 раундов. 64-битное состояние можно рассматривать как массив 4×4 полубайтов, но в реализациях состояние рассматривается как массив из 16 полубайтов. Каждая функция раунда $R_{i}$, включает в себя: уровень S-блока (обозначенный $S$), линейный слой ($M$), операцию сложения ключей и добавление константы раунда ($RC_{i}$). Все операции также нуждаются в реализации своих обратных операций, которые используются в последних шести раундах.

Ключевое расписание

128-битный ключ делится на две части: $k_{0}$ и $k_{1}$. $k_{0}$ используется для генерации другого ключа: $k_{0}^{'}=(k_{0}>>>1)\oplus (k_{0}>>63)$. Ключи $k_{0}$ и $k_{0}^{'}$ используются в качестве клавиш до и после отбеливания, то есть добавляются исключающие «ИЛИ» к состоянию до и после выполнения всех циклических функций. Раундовый ключ $k_{0}$ одинаковый для всех раундов и также добавляется с помощью операции исключающее «ИЛИ» на этапе добавления ключа.

Раундовая константа

В шифре константы $RC_{i}$ для каждого $i$ (номер раунда) различаются. Примечательным свойством раундовых констант является то, что $RC_{i}\oplus RC_{11-i}=\alpha ,\forall i\in [0,11]$. Складывание констант раунда является двоичным сложением, как и добавление раундового ключа. Эти две операции можно объединить.

S-блок

Уровень S-блок использует преобразование, которое принимает на входе 4 бит и возвращает 4 бит, как определено в следующей таблице.

$i$	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
$S[i]$	B	F	3	2	A	C	9	1	6	7	8	0	E	5	D	4

Линейный слой

На слоях $M$ и $M^{'}$ 64-битное состояние умножается на матрицу $M$ 64×64 (соответственно $M^{'}$), определённую ниже. К двум линейным слоям разные требования. Слой $M^{'}$используется только в среднем раунде, поэтому слой $M^{'}$ должен быть инволюцией, чтобы гарантировать свойство $\alpha$-отражения. Это требование не применяется к $M$-уровню, используемому в функциях раунда. Здесь обеспечивается полное распространение после двух раундов. Для этого комбинируется $M^{'}$-отображение с применением матрицы $SR$, которое ведёт себя как строки сдвига AES и переставляет 16 полубайтов следующим образом:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	$\longrightarrow$	0	5	10	15	4	9	14	3	8	13	2	7	12	1	6	11

То есть $M=SR\circ M^{'}$.

Для того, чтобы минимизировать затраты на реализацию, количество единиц в матрицах $M^{'}$и $M$ должно быть минимальным. В то же время необходимо, чтобы хотя бы 16 S-блока были активны в четырёх последовательных раундах. Таким образом, каждый выходной бит S-блока должен влиять на 3 S-блока в следующем раунде, и поэтому минимальное количество единиц в строке и столбце равно 3. Этим условиям соответствуют следующие четыре матрицы 4×4 в качестве строительных блоков для $M^{'}$-слоя.

$M_{0}={\begin{pmatrix}0&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}};M_{1}={\begin{pmatrix}1&0&0&0\\0&0&0&0\\0&0&1&0\\0&0&0&1\end{pmatrix}};M_{2}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&0\\0&0&0&1\end{pmatrix}};M_{3}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&0\end{pmatrix}}.$

На следующем шаге генерируется блочная матрица ${\hat {M}}$ 4×4, где каждая строка и столбец являются перестановкой матриц $M_{0},...,M_{3}$. Комбинации выбираются таким образом, чтобы получалась симметричная блочная матрица. Выбор строительных блоков и симметричной структуры гарантирует, что результирующая матрица 16×16 будет инволюцией:

${\hat {M}}^{(0)}={\begin{pmatrix}M_{0}&M_{1}&M_{2}&M_{3}\\M_{1}&M_{2}&M_{3}&M_{0}\\M_{2}&M_{3}&M_{0}&M_{1}\\M_{3}&M_{0}&M_{1}&M_{2}\end{pmatrix}};{\hat {M}}^{(1)}={\begin{pmatrix}M_{1}&M_{2}&M_{3}&M_{0}\\M_{2}&M_{3}&M_{0}&M_{1}\\M_{3}&M_{0}&M_{1}&M_{2}\\M_{0}&M_{1}&M_{2}&M_{3}\end{pmatrix}}.$

Чтобы получить перестановку для полного 64-битного состояния, строится блочная диагональная матрица $M^{'}$ размером 64×64 с ${\bigl (}{\hat {M^{(0)}}},{\hat {M^{(1)}}},{\hat {M^{(1)}}},{\hat {M^{(0)}}}{\bigr )}$ в качестве диагональных блоков.

Сравнение с AES

Хотя AES имеет 10 раундов при использовании 128-битного ключа, раунды в PRINCE проще в реализации. Аппаратно легко объединить раунды, чтобы уменьшить задержку и добиться лучшей производительности по сравнению с AES. Это обеспечивает отбеливание непосредственно в самом блочном шифре, чего не хватает AES. Ключевое расписание в PRINCE также гораздо проще, чем у AES.

Сравнение производительности PRINCE и AES (Nangate 45nm Generic)

	Площадь чипа (GE)	Частота (МГц)	Мощность (мВт)
PRINCE	3779	666.7	5.7
AES-128	15880	250.0	5.8

Криптоанализ

Особенность шифра PRINCE заключающаяся в том, что можно выполнить дешифрование, повторно используя процесс шифрования с немного изменённым ключом. Эта возможность, которую назвали свойством α-отражения, явно обеспечивает преимущество в реализациях, требующих как шифрования, так и дешифрования. Но в то же время вынудила разработчиков снизить ожидания безопасности по сравнению с идеальным шифром. Они заявили, что безопасность шифра обеспечивается до $2^{127-n}$ операций при выполнении $2n$ запросов на шифрование/дешифрование. Эта граница указана только для модели с одним ключом, и авторы не сделали никаких заявлений относительно модели связанных ключей.

Чтобы стимулировать интерес к криптоанализу шифра PRINCE разработчики устроили открытый конкурс «THE PRINCE CHALLENGE»[1].

Метод встречи посередине

Основная статья: Метод встречи посередине

Атака была представлена в 2015 году в рамках конкурса. Создатели обнаружили, что подходы, основанные на методе встречи посередине и SAT могут привести к практическим атакам в половине раундов. Реализованные атаки были признаны лучшими для 4, 6 и 8 раундов. Кроме того, в ходе исследований PRINCE была обнаружена новая атака на 10 раундов, которая имеет сложность данных $2^{57}$ выбранных открытых текстов.

Интегральный криптоанализ

Основная статья: Интегральный криптоанализ

Pawel Morawiecki в 2017 году представил несколько новых атак на PRINCE с уменьшенным количеством раундов (до 7 раундов). Он сосредоточился на практических атаках, большинство из которых реализованы и проверены на одном ПК. Такой анализ должен помочь оценить запас безопасности шифра, особенно в отношении реальных сценариев и потенциального развёртывания алгоритма. Используя интегральный криптоанализ, ему удалось достичь 6 раундов с низкой сложностью данных (время — $2^{41}$, количество открытых текстов — $6\cdot 2^{16}$). Так же была проведена 7-раундовая атака с помощью дифференциального криптоанализа более высокого порядка (время — $2^{57}$, количество открытых текстов — $6\cdot 2^{57}$).

Атака методом бумеранга

Основная статья: Атака методом бумеранга

Криптоанализ блочного шифра PRINCE основан на некоторых типах атаки методом бумеранга (для 4, 5 и 6 раундов), таких как бумеранг со связанными ключами и бумеранг с одним ключом для выбранной раундовой константы. Количество открытых текстов и временная сложность атак малы, чтобы их можно было рассматривать как практические атаки (оба показателя меньше, чем $2^{34}$).

Ссылки

• J. Strömbergson. Some Notes on the Lightweight Block Cipher PRINCE (англ.). — 2020.
• THE PRINCE CHALLENGE (англ.).

Литература

• J.Borghoff, A. Canteaut, L. R. Knudsen, G. Leander, C. Rechberger, S. S. Thomsen, E. Bilge Kavun, T. Yalcin, T. Güneysu, C. Paar, M. Knezevic, V. Nikov, P. Rombouts. A Low-latency Block Cipher for Pervasive Computing Applications. — 2012.
• R. Posteuca, Cristina-L. Duta, G. Negara. New Approaches for Round-Reduced PRINCE Cipher Cryptanalysis (англ.) // Proceedings of the Romanian Academy Series A. — 2015.
• A. Shahverdi, C. Chen, T. Eisenbarth. AVRprince - An Efficient Implementation of PRINCE for 8-bit Microprocessors. — 2015.
• J. Jean, I. Nikoli, T. Peyrin, L. Wang, S. Wu. Security Analysis of PRINCE. — 2013.
• P. Derbez and L. Perrin. Meet-in-the-Middle Attacks and Structural Analysis of Round-Reduced PRINCE. — 2015.
• P. Morawiecki. Practical Attacks on the Round-reduced PRINCE. — 2017.