Русская Википедия:Present (шифр)

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

Файл:Present cypher alg.png

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

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

Представляет собой SP-сеть с 31 раундом шифрования. Каждый раунд состоит из операции XOR с раундовым ключом <math>K_i</math>, состоящим из 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. <math> P(\forall x \in [0,F] : S(x) + S(x + \Delta_i ) = \Delta_o ) <= 4</math>, где <math>\Delta_i, \Delta_o</math> — любые возможные входные и выходные дифференциалы не равные 0.

1. <math> P(\forall x \in [0,F] : S(x) + S(x + \Delta_i ) = \Delta_o ) = 0</math>, где <math>wt(\Delta_i) = wt(\Delta_o) = 1</math>.

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

В качестве раундового ключа <math>K_i</math> используются 64 левых бит из регистра <math>K</math>, содержащего весь ключ. После получения раундового ключа регистр <math>K</math> обновляется по следующему алгоритму:

1. <math>[k_{79} k_{78} . . . k_1 k_0 ] = [k_{18} k_{17} . . . k_{20} k_{19} ]</math>
2. <math>[k_{79} k_{78} k_{77} k_{76} ] = S[k_{79} k_{78} k_{77} k_{76} ]</math>
3. <math>[k_{19} k_{18} k_{17} k_{16} k_{15} ] = [k_{19} k_{18} k_{17} k_{16} k_{15} ] \oplus </math>round_counter

Криптоустойчивость

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

Данный шифр обладает свойством, что любая 5-раундовая дифференциальная характеристика затрагивает по меньшей мере 10 S-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box, и вероятность характеристики не превышает <math>2^{-100}</math>. Атака на версии шифра с 16 раундами шифрования требует <math>2^{64}</math> шифротекстов, <math>2^{64}</math> доступов к памяти, <math>2^{32}</math> 6-битных счетчиков и <math>2^{24}</math> ячеек памяти для хеш-таблицы. Вероятность нахождения ключа <math>P \approx 0.999</math>

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

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

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

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

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

В таблице ниже приведена сравнительная характеристика шифра 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