Present (шифр)

У этого термина существуют и другие значения, см. Present.

Present
Опубликован:	CHES в 2007;
Размер ключа:	80 бит (Present-80), 128 бит (Present-128)
Размер блока:	64 бит
Число раундов:	31
Тип:	SP-сеть

Present — блочный шифр с размером блока 64 бита, длиной ключа 80 или 128 бит и количеством раундов 32. Основное назначение данного шифра — использование в узкоспециализированных приборах, наподобие RFID меток или сетей сенсоров. Данный шифр был представлен на конференции CHES 2007. Авторы: Богданов, Кнудсен, Леандр, Паар, Пошманн, Робшо, Соа, Викельсоа.

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

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

Основным критерием при разработке шифра была простота реализации при обеспечении средних показателей защищенности. Также важным моментом была возможность эффективной аппаратной имплементации. Входные данные подвергаются операции XOR с раундовым ключом $K_i$, состоящим из 64 бита, определяемых функцией обновления ключа. Далее блок пропускается через 16 одинаковых S-box`ов и блок перестановки бит.

S-layer

В шифре используются 16 одинаковых 4-4 бита S-box`ов:

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

Ссылки

• PRESENT: An Ultra-Lightweight Block Cipher
• Algebraic Techniques in Differential Cryptanalysis
• Differential Cryptanalysis of Reduced-Round PRESENT
• A Statistical Saturation Attack against the Block Cipher PRESENT