Present (шифр)
Present | |
---|---|
Опубликован | CHES, 2007-08-23; |
Размер ключа | 80 бит (Present-80), 128 бит (Present-128) |
Размер блока | 64 бит |
Число раундов | 31 |
Тип | SP-сеть |
Present — блочный шифр с размером блока 64 бита, длиной ключа 80 или 128 бит и количеством раундов 32.
Основное назначение данного шифра — использование в узкоспециализированных приборах, наподобие RFID-меток или сетей сенсоров.
Является одним из самых компактных криптоалгоритмов: существует оценка, что для аппаратной реализации PRESENT требуется приблизительно в 2,5 раза меньше логических элементов чем для AES или CLEFIA[1][2].
Данный шифр был представлен на конференции CHES 2007. Авторы: Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Викельсоа. Авторы работают в Orange Labs, Рурском университете в Бохуме и Датском техническом университете.
Схема шифрования
![](https://cdn.xn--h1ajim.xn--p1ai/thumb.php?f=Present_cypher_alg.png&width=300)
Основным критерием при разработке шифра была простота реализации при обеспечении средних показателей защищенности. Также важным моментом была возможность эффективной аппаратной реализации.
Представляет собой SP-сеть с 31 раундом шифрования. Каждый раунд состоит из операции XOR с раундовым ключом [math]\displaystyle{ K_i }[/math], состоящим из 64 бит, определяемых функцией обновления ключа.
Далее производится рассеивающее преобразование — блок пропускается через 16 одинаковых 4-битных S-блоков. Затем блок подвергается перемешивающему преобразованию (перестановке бит)[3].
S-layer
В шифре используются 16 одинаковых 4-битных S-блоков:
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
S[x] | C | 5 | 6 | B | 9 | 0 | A | D | 3 | E | F | 8 | 4 | 7 | 1 | 2 |
S-box составлена таким образом, чтобы увеличить сопротивляемость линейному и дифференциальному криптоанализу. В частности:
- [math]\displaystyle{ P(\forall x \in [0,F] : S(x) + S(x + \Delta_i ) = \Delta_o ) \lt = 4 }[/math], где [math]\displaystyle{ \Delta_i, \Delta_o }[/math] — любые возможные входные и выходные дифференциалы не равные 0.
- [math]\displaystyle{ P(\forall x \in [0,F] : S(x) + S(x + \Delta_i ) = \Delta_o ) = 0 }[/math], где [math]\displaystyle{ wt(\Delta_i) = wt(\Delta_o) = 1 }[/math].
P-layer
Блок, перемешивающий биты, задан следующей матрицей:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
P(i) | 0 | 16 | 32 | 48 | 1 | 17 | 33 | 49 | 2 | 18 | 34 | 50 | 3 | 19 | 35 | 51 |
i | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
P(i) | 4 | 20 | 36 | 52 | 5 | 21 | 37 | 53 | 6 | 22 | 38 | 54 | 7 | 23 | 39 | 55 |
i | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
P(i) | 8 | 24 | 40 | 56 | 9 | 25 | 41 | 57 | 10 | 26 | 42 | 58 | 11 | 27 | 43 | 59 |
i | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 |
P(i) | 12 | 28 | 44 | 60 | 13 | 29 | 45 | 61 | 14 | 30 | 46 | 62 | 15 | 31 | 47 | 63 |
Key schedule
В качестве раундового ключа [math]\displaystyle{ K_i }[/math] используются 64 левых бит из регистра [math]\displaystyle{ K }[/math], содержащего весь ключ. После получения раундового ключа регистр [math]\displaystyle{ K }[/math] обновляется по следующему алгоритму:
- [math]\displaystyle{ [k_{79} k_{78} . . . k_1 k_0 ] = [k_{18} k_{17} . . . k_{20} k_{19} ] }[/math]
- [math]\displaystyle{ [k_{79} k_{78} k_{77} k_{76} ] = S[k_{79} k_{78} k_{77} k_{76} ] }[/math]
- [math]\displaystyle{ [k_{19} k_{18} k_{17} k_{16} k_{15} ] = [k_{19} k_{18} k_{17} k_{16} k_{15} ] \oplus }[/math]round_counter
Криптоустойчивость
Дифференциальный криптоанализ
Данный шифр обладает свойством, что любая 5-раундовая дифференциальная характеристика затрагивает по меньшей мере 10 S-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box, и вероятность характеристики не превышает [math]\displaystyle{ 2^{-100} }[/math]. Атака на версии шифра с 16 раундами шифрования требует [math]\displaystyle{ 2^{64} }[/math] шифротекстов, [math]\displaystyle{ 2^{64} }[/math] доступов к памяти, [math]\displaystyle{ 2^{32} }[/math] 6-битных счетчиков и [math]\displaystyle{ 2^{24} }[/math] ячеек памяти для хеш-таблицы. Вероятность нахождения ключа [math]\displaystyle{ P \approx 0.999 }[/math]
Линейный криптоанализ
Максимальный наклон аппроксимированной прямой для 4 раундов не превышает [math]\displaystyle{ \frac{1}{2^7} }[/math]. Таким образом, для 28 раундов максимальный наклон будет [math]\displaystyle{ 2^6 * {(\frac{1}{2^7})^7} = 2^{-43} }[/math]. Поэтому, если учесть, что для взлома 31 раунда необходима аппроксимация для 28, то понадобится [math]\displaystyle{ 2^{84} }[/math] известных пар текст-шифротекст, что превышает размер возможного теста для шифрования.
Другие методы
- Алгебраическая атака с использованием дифференциальных характеристик. Основная идея — представить шифр системой уравнений низкого порядка. Далее, для нескольких пар текст-шифротекст соответствующие им системы уравнений объединяются. Если в качестве этих пар выбрать пары, соответствующие некоторой характеристике [math]\displaystyle{ \delta }[/math] с вероятностью p, то система будет верна с этой вероятностью p и решения может быть найдено при использовании [math]\displaystyle{ \frac{1}{p} }[/math] пар. Ожидается, что решение такой системы проще, чем изначальной, соответствующей одной паре текст-шифротекст. Для Present-80 с 16 раундами данная атака позволяет узнать 4 бита ключа за [math]\displaystyle{ \approx 6*2^{12} }[/math] секунд.
- Метод статистического насыщения. В данной атаке используются недостатки блока перемешивания бит. Для взлома Present-80 с 24 раундами требуется пар текст-шифротекст [math]\displaystyle{ \approx 2^{60} }[/math] вычислений [math]\displaystyle{ \approx 2^{20} }[/math].
Сравнение с другими шифрами
В таблице ниже приведена сравнительная характеристика шифра Present-80[4] по отношению к другим блочным и потоковым шифрам[5]:
Название | Размер ключа | Размер блока | Пропускная способность(Kpbs) | Площадь (в GE) |
---|---|---|---|---|
Present-80 | 80 | 64 | 11.7 | 1075 |
AES-128 | 128 | 128 | 12.4 | 3400 |
Camelia | 128 | 128 | 640 | 11350 |
DES | 56 | 64 | 44.4 | 2309 |
DESXL | 184 | 64 | 44.4 | 2168 |
Trivium | 80 | 1 | 100 | 2599 |
Grain | 80 | 1 | 100 | 1294 |
Применение
В 2012 году организации ISO и IEC включили алгоритмы PRESENT и CLEFIA в международный стандарт облегченного шифрования ISO/IEC 29192-2:2012[1][6][7].
На базе PRESENT была создана компактная хеш-функция H-PRESENT-128[8][9].
Примечания
- ↑ 1,0 1,1 Katholieke Universiteit Leuven. Ultra-lightweight encryption method becomes international standard (недоступная ссылка). Дата обращения: 28 февраля 2012. Архивировано 6 апреля 2013 года.
- ↑ Masanobu Katagi, Shiho Moriai, Lightweight Cryptography for the Internet of Things Архивная копия от 23 июня 2018 на Wayback Machine, 2011
- ↑ Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011
- ↑ Axel York Poschmann. Lightweight Cryptography: Cryptographic Engineering for a Pervasive World. — 2009. Архивная копия от 8 марта 2021 на Wayback Machine
- ↑ PRESENT: An Ultra-Lightweight Block Cipher, Table 2
- ↑ ISO. ISO/IEC 29192-2:2012 (недоступная ссылка). Дата обращения: 28 февраля 2012. Архивировано 5 апреля 2013 года.
- ↑ Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO Архивная копия от 27 апреля 2018 на Wayback Machine // Osp.ru, 02-2012
- ↑ LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ Архивировано 28 июля 2013 года., С. С. Агафьин // Безопасность информационных технологий № 2011-4
- ↑ Observations on H-PRESENT-128 Архивная копия от 17 мая 2017 на Wayback Machine, Niels Ferguson (Microsoft)
Ссылки
- PRESENT: An Ultra-Lightweight Block Cipher
- Algebraic Techniques in Differential Cryptanalysis
- Differential Cryptanalysis of Reduced-Round PRESENT (недоступная ссылка)
- Weak Keys of Reduced-Round PRESENT for Linear Cryptanalysis, Kenji Ohkuma // Lecture Notes in Computer Science Volume 5867, 2009, pp 249—265 doi:10.1007/978-3-642-05445-7_16
- A Statistical Saturation Attack against the Block Cipher PRESENT (недоступная ссылка)
- Сергей Панасенко, Сергей Смагин, Облегченные алгоритмы шифрования // «Мир ПК», № 07, 2011