PRESENT
Розробники | Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Вікельсоа |
---|---|
Уперше оприлюднений | CHES, 2007-08-23; |
Раундів | 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-скрині
У шифрі використовуються 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-скриня створена таким чином, щоб збільшити опір до лінійного та диференційного криптоаналізу. Зокрема:
- , де — будь-які можливі вхідні і вихідні диференціали не рівні нулю.
- , де .
Що таке P і ? |
P-скриня
Блок, що перемішує біти, заданий наступною матрицею:
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 |
Зміна ключів
Як ключ раунду використовуються 64 лівих біт з регістра , який містить ввесь ключ. Після отримання ключа раунду регістр оновлюється за наступним алгоритмом:
- лічильник_раунду
Криптостійкість
Диференціальний криптоаналіз
Даний шифр володіє властивістю, що будь-яка 5-раундова диференційна характеристика зачіпає щонайменше 10 S-скриньок. Таким чином, наприклад, для 25 раундів шифру будуть задіяні як мінімум 50 S-скриньок, і ймовірність характеристики не перевищує . Атака на версії шифру з 16 раундів шифрування вимагає шифротексту, доступів до пам'яті, 6-бітних лічильників і осередків пам'яті для геш-таблиці. Ймовірність знаходження ключа .
Лінійний криптоаналіз
Максимальний нахил апроксимованої прямої для чотирьох раундів не перевищує . Таким чином, для 28 раундів максимальний нахил становитиме . Тому, якщо врахувати, що для злому 31 раунду необхідна апроксимація для 28, то знадобиться відомих пар текст-шифротекст, що перевищує розмір можливого тесту для шифрування.
Інші методи
- Алгебраїчна атака з використанням диференціальних характеристик. Основна ідея — представити шифр системою рівнянь нижчого порядку. Далі, для декількох пар текст-шифротекст відповідні їм системи рівнянь об'єднуються. Якщо як ці пари вибрати пари, відповідні деякій характеристиці з імовірністю p, то система справджуватиметься з цією ймовірністю p і рішення може бути знайдене при використанні пар. Очікується, що вирішення такої системи простіше, ніж початкової, відповідній одній парі текст-шифротекст. Для Present-80 з 16 раундами дана атака дозволяє дізнатися чотири біти ключа за секунд.
- Метод статистичного насичення. В даній атаці використовуються недоліки блоку перемішування бітів. Для злому Present-80 з 24 раундами потрібна пара текст-шифротекст обчислень .
Порівняння з іншими шифрами
У таблиці нижче наведене порівняння характеристик шифру Present-80 з характеристиками інших блочних і потокових шифрів.[4]
Назва | Розмір ключа | Розмір блоку | Пропускна здатність (кб/c) | Площа (в GE[en]) |
---|---|---|---|---|
Present-80 | 80 | 64 | 200 | 1570 |
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.[5][1][6]
На базі PRESENT була створена компактна геш-функція H-PRESENT-128.[7][8]
Примітки
- ↑ а б Katholieke Universiteit Leuven. Ultra-lightweight encryption method becomes international standard. Архів оригіналу за 6 квітня 2013. Процитовано 28 лютого 2012.
- ↑ Masanobu Katagi, Shiho Moriai, Lightweight Cryptography for the Internet of Things [Архівовано 23 червня 2018 у Wayback Machine.], 2011
- ↑ Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011
- ↑ PRESENT: An Ultra-Lightweight Block Cipher, Table 2
- ↑ ISO. ISO/IEC 29192-2:2012. Архів оригіналу за 5 квітня 2013. Процитовано 28 лютого 2012.
- ↑ Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO [Архівовано 27 квітня 2018 у Wayback Machine.] // Osp.ru, 02-2012
- ↑ LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ [Архівовано 28 липня 2013 у Wayback Machine.], С. С. Агафьин // Безопасность информационных технологий № 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 [Архівовано 31 жовтня 2015 у Wayback Machine.]
- Differential Cryptanalysis of Reduced-Round PRESENT[недоступне посилання з листопадаа 2019]
- 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[недоступне посилання з листопадаа 2019]
- п
- о
- р