Основы дифференциального криптоанализа

Дифференциальный криптоанализ (Бихам и Шамир, 1990) — это атака с выбранным открытым текстом, которая анализирует распространение различий в парах открытых текстов через шифр. Находя различия на входе, которые с высокой вероятностью порождают предсказуемые различия на выходе, атакующий статистически восстанавливает биты ключа.

Для шифров на основе XOR: разность ΔX = X XOR X'. Для шифров на основе сложения: разность ΔX = X - X' mod 2^n. Разности XOR используются чаще всего, поскольку XOR коммутирует с наложением ключа с помощью XOR: эффекты расписания ключа сокращаются в дифференциальных парах.

Дифференциальная пара (P, P') имеет разность на входе ΔP = P XOR P'. После шифрования получаем (C, C') с разностью на выходе ΔC = C XOR C'. Полезная дифференциальная характеристика — это ΔP → ΔC с высокой вероятностью p, то есть множество пар (P, P') с разностью ΔP порождает разность на выходе ΔC.

DDT (таблица распределения разностей) подсчитывает для каждой разности на входе Δx и разности на выходе Δy количество входов x, удовлетворяющих условию S(x) XOR S(x XOR Δx) = Δy. Деление на 2^n даёт вероятность. У хорошего S-блока максимальное значение DDT равно 2 (вероятность 1/2^{n-1}), поэтому сильных дифференциальных характеристик нет.

Для блочного шифра с r раундами найдите последовательность ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}, в которой вероятность каждого перехода между раундами известна. Перемножьте вероятности раундов: общая вероятность p = p1 * p2 * ... * p_{r-1}. Для восстановления ключа последнего раунда атака использует 2/p пар.

При дифференциальной характеристике r-1 раундов с высокой вероятностью соберите N = 2/p пар открытых текстов. Для каждого кандидата на ключ последнего раунда K' расшифруйте оба шифртекста на один раунд, примените XOR к результатам и проверьте, совпадает ли разность с ΔU_{r-1}. Правильный K' совпадёт примерно N/2 раз, а неправильные ключи — примерно N/2^{bit_size} раз.

S-блок AES — это мультипликативная инверсия над GF(2^8), за которой следует аффинное преобразование. Максимум его DDT равен 4 из 256, поэтому дифференциальная вероятность для одного S-блока не превышает 4/256 = 1/64. В каждом раунде AES используются 4 S-блока, но проектирование по стратегии широкого следа гарантирует, что вероятность полных дифференциальных следов ниже 2^{-100}.

Стратегия широкого следа Джоана Деймэна, использованная в AES/Rijndael: определить число ветвей B для MixColumns. Любой нетривиальный дифференциальный след через один раунд активирует не менее B S-блоков. 4 раунда × 4 S-блока на раунд гарантируют не менее 25 активных S-блоков → вероятность < 2^{-100}.

Усечённые дифференциальные характеристики задают только часть разности, например какие столбцы активны, но не точные значения разностей. Это позволяет атаковать больше раундов, когда полные дифференциальные характеристики слишком слабы. Такой подход используется против AES с уменьшенным числом раундов, SERPENT и других шифров SPN.

Невозможная дифференциальная характеристика — это пара (ΔP, ΔC), которая не может возникнуть ни при каком ключе. Любой ключ, который отображает наблюдаемую пару (P, P') с такой разностью, исключается. Собрав достаточно пар, можно исключить все неправильные ключи и оставить правильный.

Атака бумерангом (Вагнер, 1999) объединяет две короткие дифференциальные характеристики в адаптивную атаку с выбранными открытыми текстами и шифртекстами. Она разделяет шифр на две половины, каждая из которых имеет короткую дифференциальную характеристику с высокой вероятностью, что позволяет атаковать больше раундов, чем допускает любая отдельная характеристика.

Каково назначение таблицы распределения разностей (DDT) в криптоанализе?

Дифференциальный криптоанализ использует распространение разностей на входе→выходе с высокой вероятностью. AES противостоит ему благодаря оптимальному с точки зрения DDT S-блоку и стратегии широкого следа. Далее: линейный криптоанализ и таблицы аппроксимаций.