Таблица дифференциальных распределений

Таблица дифференциальных распределений — это математический объект, используемый в криптографическом анализе для описания нелинейных свойств преобразований (обычно S-блоков) в симметричных шифрах. Она представляет собой матрицу, в которой строки соответствуют входным разностям (ΔX), столбцы — выходным разностям (ΔY), а на пересечении указывается количество пар входных значений (X, X), удовлетворяющих условию ΔX = X ⊕ X и дающих заданную выходную разность ΔY = S(X) ⊕ S(X*). Таблица позволяет оценить устойчивость шифра к дифференциальному криптоанализу.

История

Концепция дифференциальных распределений возникла в конце 1980-х годов в связи с развитием методов дифференциального криптоанализа. В 1990 году израильские криптографы Эли Бихам и Ади Шамир впервые применили этот подход для анализа шифра DES, что привело к созданию формального аппарата таблиц дифференциальных распределений. В 1991 году японский математик Казуюки Нюберг независимо ввёл понятие «таблицы разностей» (difference distribution table) для S-блоков. С тех пор таблица стала стандартным инструментом при проектировании и оценке блочных шифров, таких как AES, ГОСТ 28147-89, Кузнечик и других.

Определение

Пусть S: {0,1}^n → {0,1}^m — нелинейное преобразование (S-блок). Для заданной входной разности ΔX ∈ {0,1}^n и выходной разности ΔY ∈ {0,1}^m таблица дифференциальных распределений T определяется как:

T(ΔX, ΔY) = #{ X ∈ {0,1}^n : S(X) ⊕ S(X ⊕ ΔX) = ΔY }

Здесь ⊕ обозначает операцию побитового исключающего ИЛИ (XOR). Значение T(ΔX, ΔY) показывает, сколько пар входных значений с разностью ΔX дают разность ΔY на выходе S-блока. Для корректного шифра все ненулевые входные разности должны давать равномерное распределение выходных разностей, то есть T(ΔX, ΔY) ≈ 2^{n-m} для всех ΔX ≠ 0. Однако на практике достичь абсолютной равномерности невозможно.

Структура и свойства

Размерность таблицы

Таблица имеет размеры 2^n × 2^m. Для типичных S-блоков (например, n = m = 8) таблица содержит 256 строк и 256 столбцов, то есть 65536 ячеек. Каждая ячейка — целое число от 0 до 2^n.

Основные свойства

1. Нулевая разность: T(0, 0) = 2^n, так как при ΔX = 0 любая пара (X, X) даёт ΔY = 0. Для всех остальных ΔY при ΔX = 0 значение T(0, ΔY) = 0.
2. Симметрия: T(ΔX, ΔY) = T(ΔX, ΔY) для всех ΔX, ΔY (свойство вытекает из коммутативности XOR).
3. Сумма по столбцам: Для фиксированного ΔX ≠ 0 сумма T(ΔX, ΔY) по всем ΔY равна 2^n, так как каждая пара (X, X⊕ΔX) даёт ровно одну выходную разность.
4. Максимальное значение: Наибольшее значение T(ΔX, ΔY) для ΔX ≠ 0 называется дифференциальной вероятностью (DP) S-блока. Чем меньше DP, тем устойчивее S-блок к дифференциальному криптоанализу.

Связь с дифференциальной криптоанализом

В дифференциальном криптоанализе атакующий ищет пары (ΔX, ΔY) с высоким значением T(ΔX, ΔY), чтобы построить эффективную характеристику — последовательность разностей, проходящую через несколько раундов шифра. Если для некоторой разности T(ΔX, ΔY) значительно превышает 2^{n-m}, то вероятность угадать ключ повышается. Поэтому при проектировании шифров стремятся минимизировать максимальное значение таблицы.

Пример таблицы для 4-битного S-блока

Рассмотрим простой S-блок с n = m = 4, заданный таблицей подстановки:

Фрагмент таблицы дифференциальных распределений (первые строки и столбцы):

Из таблицы видно, что максимальное значение для ненулевых разностей равно 6 (например, для ΔX=2, ΔY=5). Это означает, что дифференциальная вероятность данного S-блока составляет 6/16 = 0.375, что является высоким показателем и делает его уязвимым для атак.

Применение

Оценка S-блоков

Таблица дифференциальных распределений используется для выбора S-блоков с низкой дифференциальной вероятностью. В современных шифрах (например, AES) максимальное значение таблицы обычно не превышает 4 для 8-битных S-блоков, что соответствует DP = 4/256 = 1/64.

Анализ стойкости шифров

При проектировании блочных шифров таблица позволяет оценить максимальную вероятность дифференциальной характеристики для всего шифра. Если для каждого раунда DP мала, то вероятность успешной атаки экспоненциально падает с числом раундов.

Поиск слабых мест

Криптоаналитики используют таблицу для поиска пар (ΔX, ΔY) с аномально высокими значениями, которые могут стать основой для атаки. Например, в шифре DES были найдены дифференциальные характеристики с вероятностью около 1/234, что позволило взломать его за 2^47 операций (вместо полного перебора 2^56).

Критика и ограничения

Таблица дифференциальных распределений является статическим инструментом и не учитывает динамику многораундовых преобразований. Для сложных шифров с большим числом раундов (например, AES с 10–14 раундами) таблица даёт лишь верхнюю оценку стойкости. Кроме того, существуют атаки, не основанные на дифференциальных свойствах (линейный криптоанализ, атаки на основе интегральных свойств), которые таблица не отражает. В последние годы для анализа S-блоков также применяют латинские квадраты, булевы функции и методы теории кодирования.

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

• В шифре ГОСТ 28147-89 (Россия) S-блоки не были опубликованы до 1994 года, что затрудняло построение таблиц дифференциальных распределений. После рассекречивания выяснилось, что их максимальная DP составляет 4/16 = 0.25.
• Для шифра «Кузнечик» (ГОСТ Р 34.12-2015) S-блоки были спроектированы с использованием методов теории конечных полей, что обеспечило максимальную DP = 4/256.
• Таблицы дифференциальных распределений являются частным случаем более общего понятия — дифференциальных характеристик, которые могут быть построены для целых раундов шифра.

Источники

• Biham E., Shamir A. Differential Cryptanalysis of the Data Encryption Standard. — Springer, 1993.
• Nyberg K. Perfect nonlinear S-boxes // Advances in Cryptology — EUROCRYPT’91. — Springer, 1991. — P. 378–386.
• Daemen J., Rijmen V. The Design of Rijndael: AES — The Advanced Encryption Standard. — Springer, 2002.
• ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры.
• Шнайер Б. Прикладная криптография. — 2-е изд. — М.: Триумф, 2002.