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

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-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

В якості раундового ключа $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. ${\displaystyle [k_{19}k_{18}k_{17}k_{16}k_{15}]=[k_{19}k_{18}k_{17}k_{16}k_{15}]\oplus }$round_counter

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

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

Даний шифр володіє властивістю, що будь-яка 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 по відношенню до інших блочних і потокових шифрів.

Назва	Розмір ключа	Розмір блоку	Пропускна здатність (Kpbs)	Площа (в 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
• Алгебраїчна Techniques in Differential Криптоаналіз
• Differential Криптоаналіз of Reduced-Round PRESENT
• Weak Keys of Reduced-Round PRESENT for Linear Криптоаналіз, 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