Present (шифр) (Present (onsj))

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.

Данный шифр был представлен на конференции 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. $P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})<=4$, где $\Delta _{i},\Delta _{o}$ — любые возможные входные и выходные дифференциалы не равные 0.

1. $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. $[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, и вероятность характеристики не превышает $2^{-100}$. Атака на версии шифра с 16 раундами шифрования требует $2^{64}$ шифротекстов, $2^{64}$ доступов к памяти, $2^{32}$ 6-битных счетчиков и $2^{24}$ ячеек памяти для хеш-таблицы. Вероятность нахождения ключа $P\approx 0.999$

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

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

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

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

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

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

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

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

Ссылки

• 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