Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному кри п-тоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что же обр а-зует хороший S-блок.
S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Ранее я упоминал об одной большой таблице отображения 64-битовых входов на 64-битовые выходы, такая таблица представляла бы собой S-блок размером 64*64 бита. S-блок с от-битовым входом и n-битовым выходом называется побитовым S-блоком.S-блоки обычно являются единственным нелинейным действием в алгоритме, именно они
обеспечивают безопасность блочного шифра. В общем случае чем S-блоки больше, тем лучше.
В DES восемь различных 6*4-битовых S-блоков. В Khufu и Khafre единственный 8*32-битовый S-блок, в LOKI 12*8-битовый S-блок, а в Blowfish и CAST 8*32-битовые S-блоки. В IDEA S-блоком по сути является умножение по модулю, это 16*16-битовый S-блок. Чем больше S-блок, тем труднее обнаружить статистические отклонения, нужные для вскрытия с использованием либо дифференциального, либо линейного криптоанализа [653, 729, 1626]. Кроме того, хотя случайные S-блоки обычно не оптимальны с точки зрения устойчивости к дифференциальному и линейному криптоанализу, сильные S-блоки легче найти среди S-блоков большего ра з-мера. Большинство случайных S-блоков нелинейны, невырождены и обладают сильной устойчивостью к лине й-ному криптоанализу - и с уменьшением числа входных битов эта доля снижается медленно [1185, 1186, 1187].
Размер т важнее размера п. Увеличение размера п снижает эффективность дифференциального криптоанализа, но значительно повышает эффективность дифференциального криптоанализа. Действительно, если п>2т-т, то наверняка существует линейная зависимость для входных и выходных битов S-блока. И если п>2т, то линейная зависимость существует только для выходных битов [164].
Заметной частью работы по проектированию S-блоков является изучение логических функций[94, 1098, 1262, 1408]. Для обеспечения безопасности булевы функции, используемые в S-блоках, должны отвечать опр е-деленным условиям. Они не должны быть ни линейными, ни аффинными, ни даже быть близкими к линейным или аффинным [9, 1177, 1178, 1188]. Количество нулей и единиц должно быть сбалансированным, и не должно быть никаких корреляций между различными комбинациями битов. При изменении на противоположный л ю-бого входного бита выходные биты должны вести себя независимо. Эти критерии проектирования также связ а-ны с изучением функций изгиба:функций, которые, как может быть показано, являются оптимально нелине й-ными. Хотя они определены просто и естественно, их изучение очень нелегко [1344, 1216, 947, 905, 1176, 1271, 295, 296, 297, 149, 349, 471, 298].
Очень важным свойством представляется лавинный эффект: сколько выходных битов S-блока изменяется при изменении некоторого подмножества выходных битов. Нетрудно задать для булевых функций условия, в ы-полнение которых обеспечивает определенный лавинный эффект, но проектирование таких функций является более сложной задачей. Строгий лавинный критерий(strict avalanche criteria, SAC) обеспечивает, что с изм е-нением одного входного бита изменяется ровно половина выходных битов [1586]. См. также [982, 571, 1262, 399]. В одной из работ эти критерии рассматриваются в терминах утечки информации [1640].
Несколько лет назад криптографы предложили выбирать S-блоки так, чтобы таблица распределения разл и-чий для каждого S-блока была однородной. Это обеспечило бы устойчивость к дифференциальному криптоан а-лизу за счет сглаживания дифференциалов на любом отдельном этапе [6, 443, 444, 1177]. Примером такого проектирования является LOKI. Однако такой подход иногда способствует дифференциальному криптоанализу [172]. Действительно, лучшим подходом является минимизирование максимального дифференциала. Кванджо Ким (Kwangjo Kim) выдвинул пять критериев проектирования S-блоков [834], похожих на критерии проектир о-вания S-блоков DES.
Выбор хороших S-блоков - не простая задача, существует множество различных идей, как лучше сделать это. Можно выделить четыре главных подхода.
1. Случайно выбрать. Ясно, что небольшие случайные S-блоки небезопасны, но большие случайные S-блоки могут оказаться достаточно хороши. Случайные S-блоки с восемью и более входами достаточно сильны [1186, 1187]. Еще лучше 12-битовые S-блоки. Устойчивость S-блоков возрастает, если они одновременно являются и случайными, и зависящими от ключа. В IDEA используются большие зависящие от ключа S-блоки.
2. Выбрать и проверить. В некоторых шифрах свойства S-блоков, генерированных случайным образом, проверяются. Примеры такого подхода содержатся в [9, 729].
3. Разработать вручную. При этом математический аппарат используется крайне незначительно: S-блоки создаются с использованием интуитивных приемов. Барт Пренел (Bart Preneel) заявил, что "... теор е-тически интересные критерии недостаточны [для выбора булевых функций S-блоков] ...", и что "... н е-обходимы специальные критерии проектирования" [1262].
4. Разработать математически. S-блоки создаются в соответствии с математическими законами, поэтому они обладают гарантированной надежностью по отношению к дифференциальному и линейному криптоанализу, а также хорошими диффузными свойствами. Прекрасный пример такого подхода можно найти в [1179].
Существует ряд призывов объединить "математический" и "ручной" подходы [1334], но реально, по вид и-мому, конкурируют случайно выбранные S-блоки и S-блоки с определенными свойствами. Конечно преимущ е-ством последнего подхода является оптимизация против известных методов вскрытия - дифференциального и линейного криптоанализа - но обеспечиваемая этим подходом степень защиты от неизвестных методов вскр ы-
тия также неизвестна. Разработчикам DES было известно о дифференциальном криптоанализе, и его S-блоки были оптимизированы соответствующим образом. Скорее всего, о линейном криптоанализе они не знали, и S-блоки DES очень слабы по отношению к такому способу вскрытия [1018]. Случайно выбранные S-блоки в DES были бы слабее против дифференциального криптоанализа, но сильнее против линейного криптоанализа.
С другой стороны случайные S-блоки могут не быть оптимальными по отношению к данным способам вскрытия, но они могут быть достаточно большими и, следовательно, достаточно надежными. Кроме того, они, скорее всего, будут достаточно устойчивы и против неизвестных способов вскрытия. Спор все еще кипит, но лично мне кажется, что S-блоки должны быть такими большими, насколько это возможно, случайными и зав и-сеть от ключа.