Present (шифр)

Present
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^[1]^[2].

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

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

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

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

Далее производится рассеивающее преобразование — блок пропускается через 16 одинаковых 4-битных S-блоков. Затем блок подвергается перемешивающему преобразованию (перестановке бит)^[3].

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

$P (\forall x \in [0, F] : S (x) + S (x + Δ_{i}) = Δ_{o}) < = 4$ , где $Δ_{i}, Δ_{o}$ — любые возможные входные и выходные дифференциалы не равные 0.

$P (\forall x \in [0, F] : S (x) + S (x + Δ_{i}) = Δ_{o}) = 0$ , где $w t (Δ_{i}) = w t (Δ_{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$ обновляется по следующему алгоритму:

$[k_{79} k_{78} ... k_{1} k_{0}] = [k_{18} k_{17} ... k_{20} k_{19}]$
$[k_{79} k_{78} k_{77} k_{76}] = S [k_{79} k_{78} k_{77} k_{76}]$
$[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}$ известных пар текст-шифротекст, что превышает размер возможного теста для шифрования.

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

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

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

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

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

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

Примечания

1 2 Katholieke Universiteit Leuven. Ultra-lightweight encryption method becomes international standard . Дата обращения: 28 февраля 2012. Архивировано из оригинала 6 апреля 2013 года.
↑ Masanobu Katagi, Shiho Moriai, Lightweight Cryptography for the Internet of Things Архивная копия от 23 июня 2018 на Wayback Machine, 2011
↑ Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011
↑ Axel York Poschmann. Lightweight Cryptography: Cryptographic Engineering for a Pervasive World. — 2009. — [Архивировано 8 марта 2021 года.]
↑ PRESENT: An Ultra-Lightweight Block Cipher, Table 2
↑ ISO. ISO/IEC 29192-2:2012 . Дата обращения: 28 февраля 2012. Архивировано из оригинала 5 апреля 2013 года.
↑ Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO Архивная копия от 27 апреля 2018 на Wayback Machine // Osp.ru, 02-2012
↑ LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ Архивировано 28 июля 2013 года., С. С. Агафьин // Безопасность информационных технологий № 2011-4
↑ Observations on H-PRESENT-128 Архивная копия от 17 мая 2017 на Wayback Machine, Niels Ferguson (Microsoft)

Ссылки

PRESENT: An Ultra-Lightweight Block Cipher
Algebraic Techniques in Diﬀerential 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

[KUL-1] 1 2 Katholieke Universiteit Leuven. Ultra-lightweight encryption method becomes international standard . Дата обращения: 28 февраля 2012. Архивировано из оригинала 6 апреля 2013 года.

[2] Masanobu Katagi, Shiho Moriai, Lightweight Cryptography for the Internet of Things Архивная копия от 23 июня 2018 на Wayback Machine, 2011

[3] Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011

[4] Axel York Poschmann. Lightweight Cryptography: Cryptographic Engineering for a Pervasive World. — 2009. — [Архивировано 8 марта 2021 года.]

[5] PRESENT: An Ultra-Lightweight Block Cipher, Table 2

[6] ISO. ISO/IEC 29192-2:2012 . Дата обращения: 28 февраля 2012. Архивировано из оригинала 5 апреля 2013 года.

[ospwho-7] Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO Архивная копия от 27 апреля 2018 на Wayback Machine // Osp.ru, 02-2012

[8] LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ Архивировано 28 июля 2013 года., С. С. Агафьин // Безопасность информационных технологий № 2011-4

[9] Observations on H-PRESENT-128 Архивная копия от 17 мая 2017 на Wayback Machine, Niels Ferguson (Microsoft)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Симметричные криптосистемы
Потоковые шифры	A3 A5 A8 Decim F-FCSR Grain HC-256 KCipher-2 MICKEY MUGI PIKE Phelix RC4 Rabbit SEAL SNOW SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Сеть Фейстеля	ГОСТ 28147-89 (Магма) Blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Cobra DEAL DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NewDES NDS RC5 RC6 SEED Simon Sinople Skipjack SM4 Speck TEA XTEA XXTEA Raiden RTEA Triple DES Twofish
SP-сеть	Кузнечик 3-WAY ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing BassOmatic BelT CRYPTON Diamond2 Grand Cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna^[англ.] Lucifer Present Rainbow SAFER SHARK SQUARE Serpent Threefish
Другие	FROG NUSH REDOC SC2000 SHACAL CS-Cipher SAVILLE^[англ.]