В криптографии S -блок ( блок подстановки ) является базовым компонентом алгоритмов симметричного ключа , который выполняет замену. В блочных шифрах они обычно используются для сокрытия связи между ключом и зашифрованным текстом , обеспечивая тем самым свойство Шеннона путаницы . Математически S-блок — это нелинейная [1] векторная булева функция . [2]
В общем, S-блок принимает некоторое количество входных битов m и преобразует их в некоторое количество выходных битов n , где n не обязательно равно m . [3] S -блок размером m × n может быть реализован в виде таблицы поиска с 2 m слов по n битов каждое. Обычно используются фиксированные таблицы, как в стандарте шифрования данных (DES), но в некоторых шифрах таблицы генерируются динамически на основе ключа (например, алгоритмы шифрования Blowfish и Twofish ).
Хорошим примером фиксированной таблицы является S-box из DES (S5 ) , преобразующий 6-битный вход в 4-битный выход:
Учитывая 6-битный входной сигнал, 4-битный выходной сигнал находится путем выбора строки, используя два внешних бита (первый и последний бит), и столбца, используя внутренние четыре бита. Например, вход « 0 1101 1 » имеет внешние биты « 01 » и внутренние биты «1101»; соответствующий результат будет «1001». [4]
Когда DES был впервые опубликован в 1977 году, критерии проектирования его S-блоков держались в секрете, чтобы не поставить под угрозу технику дифференциального криптоанализа (которая еще не была публично известна). В результате исследования того, что делает S-box хорошими, в то время были скудными. Скорее, восемь S-блоков DES были предметом интенсивного изучения в течение многих лет из-за опасений, что в шифр мог быть заложен бэкдор ( уязвимость , известная только его разработчикам). Поскольку S-блоки являются единственной нелинейной частью шифра, их компрометация приведет к компрометации всего шифра. [5]
Критерии проектирования S-box были в конечном итоге опубликованы (в Coppersmith 1994) после публичного повторного открытия дифференциального криптоанализа, показывая, что они были тщательно настроены для повышения устойчивости к этой конкретной атаке, так что это было не лучше, чем грубая сила . Бихам и Шамир обнаружили, что даже небольшие модификации S-box могут значительно ослабить DES. [6]
Любой S-блок, в котором любая линейная комбинация выходных битов создается изогнутой функцией входных битов, называется идеальным S-блоком . [7]
S-блоки можно анализировать с помощью линейного криптоанализа и дифференциального криптоанализа в форме таблицы линейной аппроксимации (LAT), преобразования Уолша и таблицы распределения различий (DDT) или таблицы и спектра автокорреляции. Его силу можно суммировать по нелинейности (изогнутая, почти изогнутая) и дифференциальной однородности (совершенно нелинейная, почти идеально нелинейная). [8] [9] [10] [2]