Обоснование конструкции S-блока дано в разделе 4.3 статьи. Я постараюсь расширить аргументацию.
Худший тип S-блока будет линейной функцией, т.е. такой, где каждый бит вывода является просто XOR определенных битов ввода. Поскольку остальная часть функции PRESENT round просто включает в себя перемещение битов и операцию XOR вокруг ключа раунда, линейный S-блок приведет к шифру, в котором каждый бит вывода является XOR определенных входных битов и битов ключа раунда.Сбор нескольких совпадающих входных и выходных данных позволил бы очень просто взломать шифр с помощью линейной алгебры.
Криптоанализ блочного шифра часто сосредотачивается на свойствах шифра, которые близки к тому, чтобы вести себя как линейная функция в обнаруживаемой части времени.
Линейный криптоанализ
Все равно было бы плохо, если бы XOR определенного набора входных битов и битов ключа был равен XOR определенного набора выходных бит значительно больше, чем в половине случаев. Точные детали того, как превратить это в атаку, очень длинные, но это потребует сбора большого количества пар совпадений ввода/вывода, вычисления соответствующих XOR и проверки того, совпадают ли они в большинстве случаев или нет. Это даст информацию о битах круглого ключа. Чтобы избежать этой ситуации, криптографы ищут S-блоки, в которых для любого подмножества входных битов и любого подмножества выходных бит XOR равны только примерно в половине случаев (или настолько близки, насколько это возможно). Критерий 3 статьи гласит, что для НАСТОЯЩЕГО S-блока XOR будут равны по крайней мере 4 раза из 16 и не более 12 раз из 16. Все могло бы быть хуже, если бы подмножество, которое мы выбирали в каждом случае, было одним битом. в этом случае мы могли бы сопоставить один бит ввода с одним битом вывода, отслеживая только один S-блок в каждом раунде. Это мотивирует критерий 4, который указывает, что когда подмножества состоят из одного бита, они совпадают либо ровно 6 раз из 16, либо ровно 10 раз из 16.
Дифференциальный криптоанализ
Другой способ выразить линейное свойство шифра состоит в том, чтобы сказать, что для всех входных данных $а$ и $b$ у нас есть $\mathrm{Enc}(a\oplus b)=\mathrm{Enc}(a)\oplus\mathrm{Enc}(b)$. Опять же, если подобные свойства проявляются в нашем шифре значительную часть времени, это можно использовать. Поэтому криптографы также пытаются разрабатывать шифры таким образом, чтобы при любой фиксированной разнице входных данных $\Дельта х$ и любая фиксированная разница выходов $\Дельта у$ уравнение $\mathrm{Enc}(x\oplus\Delta x)=\mathrm{Enc}(x)\oplus\Delta y$ только примерно одно решение $х$ (примерно два решения в половине случаев и отсутствие решений в половине случаев). Опять же, поскольку S-блок является единственной нелинейной частью шифра, это становится требованием, чтобы входные и выходные различия в S-блоке коррелировали как можно меньше. Затем критерий 1 говорит, что из всех возможных входных и выходных различий максимальная корреляция состоит в том, чтобы найти входное различие, которое дает одно и то же выходное различие для 4 из 16 возможных входных данных (т. Е. Две пары). Опять же, однобитовое свойство более опасно, так как разница будет распространяться по раундам, проходя через один S-блок в каждом раунде. Соответственно, тогда добавляется критерий 2, который говорит, что для любых входов, отличающихся только одним битом, их выходы не отличаются только одним битом.
Ведь их всего 16! возможных 4-битных S-блоков и большой степени симметрии между определенными классами S-блоков можно полностью протестировать все возможные S-блоки на предмет свойств, описанных выше. Этот анализ был проведен, что позволило криптографам выбирать S-блоки такого размера, зная, что они по существу оптимальны с точки зрения линейных и дифференциальных свойств. Есть еще несколько S-блоков, отвечающих этим требованиям, и команда PRESENT утверждает, что выбрала тот, который особенно хорошо подходит для аппаратной реализации. Я понимаю, что это означает, что функция, представленная S-блоком, может быть оценена с небольшим количеством вентилей или с небольшой глубиной схемы (у меня нет подробностей по этому конкретному вопросу).
