PRINCE (шифр)

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

Шифр представлен в 2012 году на международной конференции по теории и применению криптологии и информационной безопасности^[en]. Разработчики: Julia Borghoff, Anne Canteaut^[en], 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^[2].

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

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

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

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

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

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

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

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

S-блок

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

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

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

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

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

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

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

${\displaystyle 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}}.}$

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

${\displaystyle {\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-битного состояния, строится блочная диагональная матрица ${\displaystyle M^{'}}$ размером 64×64 с ${\displaystyle {\bigl (}{\hat {M^{(0)}}},{\hat {M^{(1)}}},{\hat {M^{(1)}}},{\hat {M^{(0)}}}{\bigr )}}$ в качестве диагональных блоков^[6].

Сравнение с AES

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

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

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

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

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

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

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

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

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

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

Ссылки

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

Литература

• J.Borghoff, A. Canteaut^[en], 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.

Примечания

Эта страница в последний раз была отредактирована 4 июня 2021 в 02:06.