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

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

Является одним из самых компактных криптоалгоритмов: существует оценка, что для аппаратной реализации PRESENT требуется приблизительно в 2,5 раза меньше чем для AES или CLEFIA .

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

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

Основным критерием при разработке шифра была простота реализации при обеспечении средних показателей защищенности. Также важным моментом была возможность эффективной аппаратной реализации.

Представляет собой SP-сеть с 31 раундом шифрования. Каждый раунд состоит из операции XOR с раундовым ключом ${\displaystyle 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}$ , где ${\displaystyle \Delta _{i},\Delta _{o}}$ — любые возможные входные и выходные дифференциалы не равные 0.

1. ${\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})=0}$ , где ${\displaystyle 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

В качестве раундового ключа ${\displaystyle K_{i}}$ используются 64 левых бит из регистра ${\displaystyle K}$ , содержащего весь ключ. После получения раундового ключа регистр ${\displaystyle K}$ обновляется по следующему алгоритму:

1. ${\displaystyle [k_{79}k_{78}...k_{1}k_{0}]=[k_{18}k_{17}...k_{20}k_{19}]}$
2. ${\displaystyle [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-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box, и вероятность характеристики не превышает ${\displaystyle 2^{-100}}$ . Атака на версии шифра с 16 раундами шифрования требует ${\displaystyle 2^{64}}$ шифротекстов, ${\displaystyle 2^{64}}$ доступов к памяти, ${\displaystyle 2^{32}}$ 6-битных счетчиков и ${\displaystyle 2^{24}}$ ячеек памяти для хеш-таблицы . Вероятность нахождения ключа ${\displaystyle P\approx 0.999}$

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

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

Другие методы

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

Сравнение с другими шифрами

В таблице ниже приведена сравнительная характеристика шифра Present-80 по отношению к другим блочным и потоковым шифрам :

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

На базе PRESENT была создана компактная хеш-функция H-PRESENT-128 .

Примечания

Ссылки

• (недоступная ссылка)
• Weak Keys of Reduced-Round PRESENT for Linear Cryptanalysis, Kenji Ohkuma // Lecture Notes in Computer Science Volume 5867, 2009, pp 249—265
• (недоступная ссылка)

• Сергей Панасенко, Сергей Смагин, // «Мир ПК», № 07, 2011