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, Рурском университете в Бохуме и Датском техническом университете.
Схема шифрования
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Present_cypher_alg.png/220px-Present_cypher_alg.png)
Основным критерием при разработке шифра была простота реализации при обеспечении средних показателей защищенности. Также важным моментом была возможность эффективной аппаратной реализации.
Представляет собой SP-сеть с 31 раундом шифрования. Каждый раунд состоит из операции XOR с раундовым ключом , состоящим из 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 составлена таким образом, чтобы увеличить сопротивляемость линейному и дифференциальному криптоанализу. В частности:
- , где — любые возможные входные и выходные дифференциалы не равные 0.
- , где .
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
[править | править код]В качестве раундового ключа используются 64 левых бит из регистра , содержащего весь ключ. После получения раундового ключа регистр обновляется по следующему алгоритму:
- round_counter
Криптоустойчивость
[править | править код]Дифференциальный криптоанализ
[править | править код]Данный шифр обладает свойством, что любая 5-раундовая дифференциальная характеристика затрагивает по меньшей мере 10 S-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box, и вероятность характеристики не превышает . Атака на версии шифра с 16 раундами шифрования требует шифротекстов, доступов к памяти, 6-битных счетчиков и ячеек памяти для хеш-таблицы. Вероятность нахождения ключа
Линейный криптоанализ
[править | править код]Максимальный наклон аппроксимированной прямой для 4 раундов не превышает . Таким образом, для 28 раундов максимальный наклон будет . Поэтому, если учесть, что для взлома 31 раунда необходима аппроксимация для 28, то понадобится известных пар текст-шифротекст, что превышает размер возможного теста для шифрования.
Другие методы
[править | править код]- Алгебраическая атака с использованием дифференциальных характеристик. Основная идея — представить шифр системой уравнений низкого порядка. Далее, для нескольких пар текст-шифротекст соответствующие им системы уравнений объединяются. Если в качестве этих пар выбрать пары, соответствующие некоторой характеристике с вероятностью p, то система будет верна с этой вероятностью p и решения может быть найдено при использовании пар. Ожидается, что решение такой системы проще, чем изначальной, соответствующей одной паре текст-шифротекст. Для Present-80 с 16 раундами данная атака позволяет узнать 4 бита ключа за секунд.
- Метод статистического насыщения. В данной атаке используются недостатки блока перемешивания бит. Для взлома Present-80 с 24 раундами требуется пар текст-шифротекст вычислений .
Сравнение с другими шифрами
[править | править код]В таблице ниже приведена сравнительная характеристика шифра 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 2 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 года.
- ↑ 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