PRINCE (шифр)

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

Шифр представлен в 2012 году на Шаблон:Iw. Разработчики: Julia Borghoff, Шаблон:Iw, 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Шаблон:Sfn.

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

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

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

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

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

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

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

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

S-блок

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

$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^{'}$ должен быть инволюцией, чтобы гарантировать свойство $α$ -отражения. Это требование не применяется к $M$ -уровню, используемому в функциях раунда. Здесь обеспечивается полное распространение после двух раундов. Для этого комбинируется $M^{'}$ -отображение с применением матрицы $S R$ , которое ведёт себя как строки сдвига AES и переставляет 16 полубайтов следующим образом:

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

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

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

$M_{0} = (\begin{matrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}); M_{1} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}); M_{2} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}); M_{3} = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}) .$

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

${\hat{M}}^{(0)} = (\begin{matrix} 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{matrix}); {\hat{M}}^{(1)} = (\begin{matrix} 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{matrix}) .$

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

Сравнение с AES

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

Сравнение производительности PRINCE и AESШаблон:Sfn (Шаблон:Iw)
	Площадь чипа (Шаблон:Iw)	Частота (МГц)	Мощность (мВт)
PRINCE	3779	666.7	5.7
AES-128	15880	250.0	5.8

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

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

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

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

Шаблон:Основная статья

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

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

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

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

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

Ссылки

Литература

Примечания

Шаблон:Примечания

Шаблон:Изолированная статья

PRINCE (шифр)

Содержание

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

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

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

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

S-блок

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

Сравнение с AES

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

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

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

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

Ссылки

Литература

Примечания

Навигация

PRINCE (шифр)

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

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

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

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

S-блок

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

Сравнение с AES

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

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

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

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

Ссылки

Литература

Примечания

Навигация

Поиск