Русская Википедия: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 полубайтов. Каждая функция раунда <math>R_i</math>, включает в себя: уровень S-блока (обозначенный <math>S</math>), линейный слой (<math>M</math>), операцию сложения ключей и добавление константы раунда (<math>RC_i</math>)Шаблон:Sfn. Все операции также нуждаются в реализации своих обратных операций, которые используются в последних шести раундах.
Ключевое расписание
128-битный ключ делится на две части: <math>k_0</math> и <math>k_1</math>. <math>k_0</math> используется для генерации другого ключа: <math>k_0^'=(k_0>>>1)\oplus(k_0>>63)</math>. Ключи <math>k_0</math> и <math>k_0^'</math> используются в качестве клавиш до и после отбеливания, то есть добавляются исключающие «ИЛИ» к состоянию до и после выполнения всех циклических функций. Раундовый ключ <math>k_0</math> одинаковый для всех раундов и также добавляется с помощью операции исключающее «ИЛИ» на этапе добавления ключаШаблон:Sfn.
Раундовая константа
В шифре константы <math>RC_i</math> для каждого <math>i</math> (номер раунда) различаются. Примечательным свойством раундовых констант является то, что <math>RC_i\oplus RC_{11-i}=\alpha, \forall i\in[0, 11] </math>. Складывание констант раунда является двоичным сложением, как и добавление раундового ключа. Эти две операции можно объединитьШаблон:Sfn.
S-блок
Уровень S-блок использует преобразование, которое принимает на входе 4 бит и возвращает 4 битШаблон:Sfn, как определено в следующей таблице.
| <math>i</math> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| <math>S[i]</math> | B | F | 3 | 2 | A | C | 9 | 1 | 6 | 7 | 8 | 0 | E | 5 | D | 4 |
Линейный слой
На слоях <math>M</math> и <math>M^'</math> 64-битное состояние умножается на матрицу <math>M</math> 64×64 (соответственно <math>M^'</math>), определённую ниже. К двум линейным слоям разные требования. Слой <math>M^'</math>используется только в среднем раунде, поэтому слой <math>M^'</math> должен быть инволюцией, чтобы гарантировать свойство <math>\alpha</math>-отражения. Это требование не применяется к <math>M</math>-уровню, используемому в функциях раунда. Здесь обеспечивается полное распространение после двух раундов. Для этого комбинируется <math>M^'</math>-отображение с применением матрицы <math>SR</math>, которое ведёт себя как строки сдвига AES и переставляет 16 полубайтов следующим образом:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | <math>\longrightarrow</math> | 0 | 5 | 10 | 15 | 4 | 9 | 14 | 3 | 8 | 13 | 2 | 7 | 12 | 1 | 6 | 11 |
|---|
То есть <math>M=SR\circ M^'</math>.
Для того, чтобы минимизировать затраты на реализацию, количество единиц в матрицах <math>M^'</math>и <math>M</math> должно быть минимальным. В то же время необходимо, чтобы хотя бы 16 S-блока были активны в четырёх последовательных раундах. Таким образом, каждый выходной бит S-блока должен влиять на 3 S-блока в следующем раунде, и поэтому минимальное количество единиц в строке и столбце равно 3. Этим условиям соответствуют следующие четыре матрицы 4×4 в качестве строительных блоков для <math>M^'</math>-слоя.
<math>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}.</math>
На следующем шаге генерируется блочная матрица <math>\hat{M}</math> 4×4, где каждая строка и столбец являются перестановкой матриц <math>M_0, ..., M_3</math>. Комбинации выбираются таким образом, чтобы получалась симметричная блочная матрица. Выбор строительных блоков и симметричной структуры гарантирует, что результирующая матрица 16×16 будет инволюцией:
<math>\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}.</math>
Чтобы получить перестановку для полного 64-битного состояния, строится блочная диагональная матрица <math>M^'</math> размером 64×64 с <math>\bigl(\hat{M^{(0)}}, \hat{M^{(1)}}, \hat{M^{(1)}}, \hat{M^{(0)}}\bigr)</math> в качестве диагональных блоковШаблон:Sfn.
Сравнение с AES
Хотя AES имеет 10 раундов при использовании 128-битного ключа, раунды в PRINCE проще в реализации. Аппаратно легко объединить раунды, чтобы уменьшить задержку и добиться лучшей производительности по сравнению с AES. Это обеспечивает отбеливание непосредственно в самом блочном шифре, чего не хватает AES. Ключевое расписание в PRINCE также гораздо проще, чем у AESШаблон:Sfn.
| Площадь чипа | Частота
(МГц) |
Мощность
(мВт) | |
|---|---|---|---|
| PRINCE | 3779 | 666.7 | 5.7 |
| AES-128 | 15880 | 250.0 | 5.8 |
Криптоанализ
Особенность шифра PRINCE заключающаяся в том, что можно выполнить дешифрование, повторно используя процесс шифрования с немного изменённым ключом. Эта возможность, которую назвали свойством α-отражения, явно обеспечивает преимущество в реализациях, требующих как шифрования, так и дешифрования. Но в то же время вынудила разработчиков снизить ожидания безопасности по сравнению с идеальным шифром. Они заявили, что безопасность шифра обеспечивается до <math>2^{127-n}</math> операций при выполнении <math>2n</math> запросов на шифрование/дешифрование. Эта граница указана только для модели с одним ключом, и авторы не сделали никаких заявлений относительно модели связанных ключейШаблон:Sfn.
Чтобы стимулировать интерес к криптоанализу шифра PRINCE разработчики устроили открытый конкурс «THE PRINCE CHALLENGE»[1].
Метод встречи посередине
Атака была представлена в 2015 году в рамках конкурса. Создатели обнаружили, что подходы, основанные на методе встречи посередине и SAT могут привести к практическим атакам в половине раундов. Реализованные атаки были признаны лучшими для 4, 6 и 8 раундов. Кроме того, в ходе исследований PRINCE была обнаружена новая атака на 10 раундов, которая имеет сложность данных <math>2^{57}</math> выбранных открытых текстовШаблон:Sfn.
Интегральный криптоанализ
Шаблон:Основная статья Pawel Morawiecki в 2017 году представил несколько новых атак на PRINCE с уменьшенным количеством раундов (до 7 раундов). Он сосредоточился на практических атаках, большинство из которых реализованы и проверены на одном ПК. Такой анализ должен помочь оценить запас безопасности шифра, особенно в отношении реальных сценариев и потенциального развёртывания алгоритма. Используя интегральный криптоанализ, ему удалось достичь 6 раундов с низкой сложностью данных (время — <math>2^{41}</math>, количество открытых текстов — <math>6\cdot2^{16}</math>). Так же была проведена 7-раундовая атака с помощью дифференциального криптоанализа более высокого порядка (время — <math>2^{57}</math>, количество открытых текстов — <math>6\cdot2^{57}</math>)Шаблон:Sfn.
Атака методом бумеранга
Шаблон:Основная статья Криптоанализ блочного шифра PRINCE основан на некоторых типах атаки методом бумеранга (для 4, 5 и 6 раундов), таких как бумеранг со связанными ключами и бумеранг с одним ключом для выбранной раундовой константы. Количество открытых текстов и временная сложность атак малы, чтобы их можно было рассматривать как практические атаки (оба показателя меньше, чем <math>2^{34}</math>)Шаблон:Sfn.
Ссылки
Литература
Примечания
