Present (шифр)

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

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

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

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

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

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

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

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

S-box составлена таким образом, чтобы увеличить сопротивляемость линейному и дифференциальному криптоанализу. В частности:

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

1. ${\displaystyle P(\forall x\in [0,F]:S(x)+S(x+\Delta _{i})=\Delta _{o})=0}$, где ${\displaystyle wt(\Delta _{i})=wt(\Delta _{o})=1}$.

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

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

1. ${\displaystyle [k_{79}k_{78}...k_{1}k_{0}]=[k_{18}k_{17}...k_{20}k_{19}]}$
2. ${\displaystyle [k_{79}k_{78}k_{77}k_{76}]=S[k_{79}k_{78}k_{77}k_{76}]}$
3. ${\displaystyle [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, и вероятность характеристики не превышает ${\displaystyle 2^{-100}}$. Атака на версии шифра с 16 раундами шифрования требует ${\displaystyle 2^{64}}$ шифротекстов, ${\displaystyle 2^{64}}$ доступов к памяти, ${\displaystyle 2^{32}}$ 6-битных счетчиков и ${\displaystyle 2^{24}}$ ячеек памяти для хеш-таблицы. Вероятность нахождения ключа ${\displaystyle P\approx 0.999}$

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

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

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

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

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

• 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