PRESENT

Present

Розробники	Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Вікельсоа
Уперше оприлюднений	CHES, 2007-08-23;
Раундів	31
Тип	SP-мережа

Present — блочний шифр з розміром блоку 64 біта, довжиною ключа 80 або 128 біт і кількістю раундів 32.

Основне призначення даного шифру — використання в спеціальних приладах, на зразок RFID міток або мереж сенсорів.

Є одним з найбільш компактних криптоалгоритмів, існує оцінка, що для апаратної реалізації PRESENT потрібно приблизно в 2.5 рази менше логічних елементів ніж для AES або CLEFIA.

Даний шифр був представлений на конференції CHES 2007. Автори: Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Вікельсоа. Автори працюють в Orange Labs, Рурському університеті в Бохумі та Данському технічному університеті.

Схема шифрування

Схема шифрування

Основним критерієм при розробці шифру була простота реалізації при забезпеченні середнього рівня захищеності. Також важливим моментом була можливість ефективної апаратної реалізації.

Являє собою SP-мережу з 31 раундом шифрування. Кожен раунд складається з операції XOR з раундовим ключем $K_{i}$, що складається з 64 біт, які визначають функцію оновлення ключа.

Далі проводиться розсіююче перетворення — блок пропускається через 16 однакових 4-бітних S-скринь. Потім блок піддається перемішуючому перетворенню (перестановка біт).

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-скриня створена таким чином, щоб збільшити опір до лінійного та диференційного криптоаналізу. Зокрема:

1. ${\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})<=4}$, де $\Delta _{i},\Delta _{o}$ — будь-які можливі вхідні і вихідні диференціали не рівні нулю.

1. ${\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})=0}$, де $wt(\Delta _{i})=wt(\Delta _{o})=1$.

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

Зміна ключів

Як ключ раунду $K_{i}$ використовуються 64 лівих біт з регістра $K$, який містить ввесь ключ. Після отримання ключа раунду регістр $K$ оновлюється за наступним алгоритмом:

1. $[k_{79}k_{78}...k_{1}k_{0}]=[k_{18}k_{17}...k_{20}k_{19}]$
2. $[k_{79}k_{78}k_{77}k_{76}]=S[k_{79}k_{78}k_{77}k_{76}]$
3. $[k_{19}k_{18}k_{17}k_{16}k_{15}]=[k_{19}k_{18}k_{17}k_{16}k_{15}]\oplus$ лічильник_раунду

Криптостійкість

Диференціальний криптоаналіз

Даний шифр володіє властивістю, що будь-яка 5-раундова диференційна характеристика зачіпає щонайменше 10 S-скриньок. Таким чином, наприклад, для 25 раундів шифру будуть задіяні як мінімум 50 S-скриньок, і ймовірність характеристики не перевищує $2^{-100}$. Атака на версії шифру з 16 раундів шифрування вимагає $2^{64}$ шифротексту, $2^{64}$ доступів до пам'яті, $2^{32}$ 6-бітних лічильників і $2^{24}$ осередків пам'яті для геш-таблиці. Ймовірність знаходження ключа $P\approx 0.999$.

Лінійний криптоаналіз

Максимальний нахил апроксимованої прямої для чотирьох раундів не перевищує ${\frac {1}{2^{7}}}$. Таким чином, для 28 раундів максимальний нахил становитиме $2^{6}*{\left({\frac {1}{2^{7}}}\right)^{7}}=2^{-43}$. Тому, якщо врахувати, що для злому 31 раунду необхідна апроксимація для 28, то знадобиться $2^{84}$ відомих пар текст-шифротекст, що перевищує розмір можливого тесту для шифрування.

Інші методи

• Алгебраїчна атака з використанням диференціальних характеристик. Основна ідея — представити шифр системою рівнянь нижчого порядку. Далі, для декількох пар текст-шифротекст відповідні їм системи рівнянь об'єднуються. Якщо як ці пари вибрати пари, відповідні деякій характеристиці $\delta$ з імовірністю p, то система справджуватиметься з цією ймовірністю p і рішення може бути знайдене при використанні ${\frac {1}{p}}$ пар. Очікується, що вирішення такої системи простіше, ніж початкової, відповідній одній парі текст-шифротекст. Для Present-80 з 16 раундами дана атака дозволяє дізнатися чотири біти ключа за $\approx 6*2^{12}$ секунд.
• Метод статистичного насичення. В даній атаці використовуються недоліки блоку перемішування бітів. Для злому Present-80 з 24 раундами потрібна пара текст-шифротекст $\approx 2^{60}$ обчислень $\approx 2^{20}$.

Порівняння з іншими шифрами

У таблиці нижче наведене порівняння характеристик шифру Present-80 з характеристиками інших блочних і потокових шифрів.

Назва	Розмір ключа	Розмір блоку	Пропускна здатність (кб/c)	Площа (в GE)
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.

На базі PRESENT була створена компактна геш-функція H-PRESENT-128.

Посилання

• 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]}