Present (шифр)

В шифре используются 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}}$.