S-box

S-box (от англ. substitution-box, «блок подстановки») — это базовый компонент симметричных криптографических алгоритмов, выполняющий нелинейное преобразование (подстановку) входного блока данных фиксированной длины в выходной блок той же длины. S-box представляет собой таблицу замены (lookup table), где каждому возможному значению входного слова (обычно 4, 6 или 8 бит) ставится в соответствие уникальное выходное значение. Основное назначение S-box — внесение нелинейности в шифр, что является критически важным для защиты от линейного и дифференциального криптоанализа.

История

Идея использования таблиц подстановки в криптографии восходит к древним шифрам замены, таким как шифр Цезаря. Однако в современном понимании S-box как математический объект впервые был систематически применён в алгоритме DES (Data Encryption Standard), разработанном в 1970-х годах в США. DES использует 8 различных 6-битных на 4-битных S-box (6 бит на входе, 4 бита на выходе), которые были тщательно спроектированы для обеспечения стойкости к дифференциальному криптоанализу. Выбор этих S-box долгое время оставался засекреченным, что порождало подозрения о возможных «закладках» со стороны АНБ.

После стандартизации DES в 1977 году S-box стали обязательным элементом многих блочных шифров. В 1990-х годах, с развитием открытой криптографии, появились алгоритмы с публично обоснованными S-box, например, AES (Rijndael), где используется единственный 8-битный на 8-битный S-box, построенный на основе алгебраических свойств конечного поля GF(2⁸). В 2000-х годах исследования в области S-box сосредоточились на поиске оптимальных таблиц с точки зрения стойкости к различным видам атак, включая алгебраический криптоанализ.

Классификация и виды

S-box классифицируют по нескольким параметрам.

По размеру

• 4×4 S-box (4 бита на входе, 4 бита на выходе) — используются в лёгких шифрах (например, PRESENT, SKINNY) и в некоторых поточных шифрах. Компактны, но имеют ограниченную нелинейность.
• 6×4 S-box — классический формат DES. 6-битный вход позволяет вводить дополнительную нелинейность за счёт использования двух битов управления строкой таблицы.
• 8×8 S-box — стандарт для современных блочных шифров (AES, Serpent, Camellia). Обеспечивает высокую нелинейность при разумном размере таблицы (256 байт).
• n×m S-box — общий случай, где n > m или n = m. Для криптографической стойкости обычно требуется n ≥ m.

По способу построения

• Случайные S-box — генерируются с помощью криптографически стойкого генератора случайных чисел. Применяются в некоторых алгоритмах, но требуют тщательной проверки на стойкость.
• Алгебраические S-box — строятся на основе математических функций, например, взятия обратного элемента в конечном поле (как в AES) или возведения в степень. Обладают предсказуемой структурой, что упрощает анализ.
• Оптимизированные S-box — получаются в результате компьютерного поиска по заданным критериям (максимальная нелинейность, минимальное дифференциальное распространение). Пример — S-box алгоритма Serpent.
• Табличные S-box — просто хранятся в виде массива констант. Самый распространённый способ реализации.

Устройство и характеристики

S-box математически представляет собой отображение S: {0,1}ⁿ → {0,1}ᵐ. На практике он реализуется либо как таблица прямого доступа (lookup table) в программном обеспечении, либо как комбинационная логическая схема в аппаратуре.

Ключевые криптографические свойства S-box:

• Нелинейность — степень отличия S-box от любого аффинного преобразования. Измеряется расстоянием до множества аффинных функций. Чем выше нелинейность, тем сложнее аппроксимировать S-box линейными функциями. Для 8-битного S-box максимальная нелинейность составляет 120.
• Дифференциальная равномерность — максимальное значение в таблице дифференциального распределения (Differential Distribution Table, DDT). Показывает, насколько равномерно входные разности отображаются в выходные. Чем меньше это значение, тем выше стойкость к дифференциальному криптоанализу. Для 8-битного S-box минимальное достижимое значение — 4.
• Лавинный эффект — способность S-box изменять выходные биты при изменении одного входного бита. Хороший S-box должен демонстрировать сильный лавинный эффект (SAC — Strict Avalanche Criterion).
• Алгебраическая степень — степень полиномиального представления S-box над GF(2). Высокая степень затрудняет алгебраические атаки.
• Отсутствие фиксированных точек — желательно, чтобы S(x) ≠ x для всех x, чтобы избежать тривиальных тождественных преобразований.

Применение

S-box являются неотъемлемой частью большинства симметричных криптоалгоритмов.

Блочные шифры

В блочных шифрах S-box обычно используются в рамках SP-сети (Substitution-Permutation Network) или сети Фейстеля. Например:

• AES (Rijndael) — использует один 8×8 S-box, применяемый ко всем байтам состояния. S-box построен как S(x) = A(x⁻¹), где x⁻¹ — обратный элемент в GF(2⁸), а A — аффинное преобразование.
• DES — использует 8 различных 6×4 S-box. Каждый S-box реализован в виде таблицы из 4 строк по 16 столбцов, где строка выбирается двумя внешними битами входа, а столбец — четырьмя внутренними.
• ГОСТ Р 34.12-2015 (российский стандарт «Кузнечик») — использует 8×8 S-box, построенный на основе алгебраических свойств и оптимизированный для аппаратной реализации.

Поточные шифры

В поточных шифрах S-box применяются для нелинейного преобразования внутреннего состояния. Например, в шифре Salsa20 используется 4×4 S-box на основе сложения и вращения, а в ChaCha — модифицированная версия.

Хеш-функции

Некоторые хеш-функции (например, SHA-3 на основе алгоритма Keccak) используют S-box в своей конструкции. В Keccak применяется 5×5 S-box, построенный на основе операции χ (хи), которая является нелинейным преобразованием.

Криптоанализ

S-box также являются объектом изучения в криптоанализе. Атаки, направленные на слабые S-box, включают:

• Линейный криптоанализ — использует линейные аппроксимации S-box.
• Дифференциальный криптоанализ — использует разности между парами входов/выходов.
• Алгебраический криптоанализ — пытается решить систему полиномиальных уравнений, описывающих S-box.

Примеры известных S-box

• S-box AES: 8×8, нелинейность 112, дифференциальная равномерность 4. Построен на основе обратного элемента в GF(2⁸) с последующим аффинным преобразованием.
• S-box Serpent: 8×8, нелинейность 112, дифференциальная равномерность 4. Получен в результате компьютерного поиска с оптимизацией.
• S-box DES: 6×4, нелинейность варьируется от 0 до 16 (в зависимости от S-box), дифференциальная равномерность до 16. Спроектирован вручную с учётом секретных критериев.
• S-box «Кузнечик»: 8×8, нелинейность 112, дифференциальная равномерность 4. Описан в российском стандарте ГОСТ Р 34.12-2015.

Интересные факты

• S-box AES был выбран из-за своей алгебраической простоты, что позволило реализовать его компактно в аппаратуре, но также породило опасения по поводу возможных алгебраических атак, которые, однако, не были реализованы на практике.
• В 1990 году Эли Бихам и Ади Шамир опубликовали метод дифференциального криптоанализа, который оказался эффективным против DES, если бы его S-box были слабыми. Однако разработчики DES заранее учли этот тип атак, что стало известно только после рассекречивания критериев проектирования.
• Существуют S-box с «чёрным ходом» (backdoor), которые выглядят случайными, но позволяют злоумышленнику, знающему секрет, легко взламывать шифр. Пример — алгоритм Dual_EC_DRBG (рекомендованный NIST), который содержал уязвимый S-box, позволявший АНБ предсказывать случайные числа.

Критика

Основная критика S-box связана с их «непрозрачностью»: если S-box построен без публичного обоснования, он может содержать скрытые уязвимости. Это привело к требованию открытости и проверяемости криптоалгоритмов. Кроме того, S-box фиксированного размера (например, 8×8) могут быть неоптимальны для лёгких устройств (IoT), где требуется минимизация памяти и вычислительных затрат. В ответ на это разрабатываются лёгкие S-box (4×4) и конструкции на основе нелинейных операций без таблиц (например, ARX-шифры).

Источники

• Joan Daemen, Vincent Rijmen. The Design of Rijndael: AES — The Advanced Encryption Standard. Springer, 2002.
• Eli Biham, Adi Shamir. Differential Cryptanalysis of the Data Encryption Standard. Springer, 1993.
• ГОСТ Р 34.12-2015. «Информационная технология. Криптографическая защита информации. Блочные шифры».
• Bruce Schneier. Applied Cryptography: Protocols, Algorithms, and Source Code in C. John Wiley & Sons, 1996.
• Claude Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, 2021.