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

  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 по отношению к другим блочным и потоковым шифрам.[4]

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

Применение[править | править исходный текст]

В 2012 году организации ISO и IEC включили алгоритмы PRESENT и CLEFIA в международный стандарт облегченного шифрования ISO/IEC 29192-2:2012.[5][1][6]

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

Примечания[править | править исходный текст]

  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, 2011
  3. Панасенко, Смагин, Облегченные алгоритмы шифрования // 2011
  4. PRESENT: An Ultra-Lightweight Block Cipher, Table 2
  5. ISO. ISO/IEC 29192-2:2012. Проверено 28 февраля 2012. Архивировано из первоисточника 5 апреля 2013.
  6. Алгоритм шифрования, предложенный как «более легкая» альтернатива AES, стал стандартом ISO // Osp.ru, 02-2012
  7. LW-КРИПТОГРАФИЯ: ШИФРЫ ДЛЯ RFID-СИСТЕМ, С. С. Агафьин // Безопасность информационных технологий № 2011-4
  8. Observations on H-PRESENT-128, Niels Ferguson (Microsoft)

Ссылки[править | править исходный текст]