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

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

В шифре используются 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. , где  — любые возможные входные и выходные дифференциалы не равные 0.
  1. , где .

Блок, перемешивающий биты, задан следующей матрицей:

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

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

  1. round_counter

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

[править | править код]

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

[править | править код]

Данный шифр обладает свойством, что любая 5-раундовая дифференциальная характеристика затрагивает по меньшей мере 10 S-box`ов. Таким образом, например, для 25 раундов шифра будут задействованы как минимум 50 S-box, и вероятность характеристики не превышает . Атака на версии шифра с 16 раундами шифрования требует шифротекстов, доступов к памяти, 6-битных счетчиков и ячеек памяти для хеш-таблицы. Вероятность нахождения ключа

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

[править | править код]

Максимальный наклон аппроксимированной прямой для 4 раундов не превышает . Таким образом, для 28 раундов максимальный наклон будет . Поэтому, если учесть, что для взлома 31 раунда необходима аппроксимация для 28, то понадобится известных пар текст-шифротекст, что превышает размер возможного теста для шифрования.

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

[править | править код]
  • Алгебраическая атака с использованием дифференциальных характеристик. Основная идея — представить шифр системой уравнений низкого порядка. Далее, для нескольких пар текст-шифротекст соответствующие им системы уравнений объединяются. Если в качестве этих пар выбрать пары, соответствующие некоторой характеристике с вероятностью p, то система будет верна с этой вероятностью p и решения может быть найдено при использовании пар. Ожидается, что решение такой системы проще, чем изначальной, соответствующей одной паре текст-шифротекст. Для Present-80 с 16 раундами данная атака позволяет узнать 4 бита ключа за секунд.
  • Метод статистического насыщения. В данной атаке используются недостатки блока перемешивания бит. Для взлома Present-80 с 24 раундами требуется пар текст-шифротекст вычислений .

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

[править | править код]

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