Дифференциальный криптоанализ

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

История

Идея использования разностей для анализа шифров возникла ещё в 1970-х годах, но систематическое исследование провели Бихам и Шамир. В 1990 году они представили атаку на полный 16-раундовый DES, требующую 2^47 выбранных открытых текстов (что значительно меньше полного перебора 2^56 ключей). Позднее выяснилось, что разработчики DES (IBM и АНБ) в 1970-х годах уже знали о дифференциальном криптоанализе и специально спроектировали S-блоки DES для устойчивости к нему, но держали это в секрете. Этот факт был раскрыт в 1994 году.

После публикации Бихама и Шамира метод стал стандартным инструментом анализа блочных шифров. Многие современные шифры (например, AES, ГОСТ 28147-89, Twofish) проектировались с учётом защиты от дифференциального криптоанализа. В 1990-е годы были разработаны его варианты: усечённый дифференциальный анализ, высшие дифференциалы, невозможные дифференциалы, дифференциально-линейный анализ.

Основные принципы

Разность и её преобразование

Дифференциальный криптоанализ рассматривает пары открытых текстов (P1, P2) с фиксированной разностью ΔP = P1 ⊕ P2 (где ⊕ — операция XOR). После каждого раунда шифрования разность между частично зашифрованными текстами преобразуется. Для шифров, использующих S-блоки (нелинейные таблицы замен), разность на выходе S-блока зависит от входной разности и конкретных значений входных данных. Эта зависимость описывается таблицей дифференциальных распределений (Difference Distribution Table, DDT) для каждого S-блока.

Дифференциальная характеристика

Последовательность разностей на каждом раунде (от входа до выхода шифра) называется дифференциальной характеристикой. Вероятность характеристики — произведение вероятностей преобразования разности на каждом раунде. Для успешной атаки требуется характеристика с вероятностью, существенно превышающей случайную (для случайной перестановки вероятность любой ненулевой разности на выходе равна 1/2^n, где n — размер блока).

Выделение ключа

Атака состоит из двух этапов:

1. Поиск дифференциальной характеристики — нахождение последовательности разностей с высокой вероятностью.
2. Извлечение битов ключа — сбор статистики по парам открытых текстов и соответствующих шифротекстов. Для каждой пары анализируются возможные значения последнего раундового ключа, которые могли бы привести к наблюдаемой разности на выходе. Правильный ключ даёт наибольшее число совпадений с ожидаемой разностью.

Разновидности

Усечённый дифференциальный криптоанализ

Рассматривает не полные разности, а лишь их части (например, только некоторые байты). Применяется для шифров с большим размером блока (например, 128 бит и более), где полные характеристики слишком маловероятны.

Невозможные дифференциалы

Метод, при котором ищется характеристика, имеющая нулевую вероятность (то есть разность, которая гарантированно не может появиться на выходе). Если такая разность обнаружена, то соответствующий ключ отбрасывается. Этот подход эффективен против некоторых шифров, включая AES.

Высшие дифференциалы

Обобщение метода на случай использования разностей не первого, а более высокого порядка (например, вторые разности). Применяется для анализа шифров с алгебраической структурой, таких как шифры на основе конечных полей.

Дифференциально-линейный криптоанализ

Комбинация дифференциального и линейного методов. Сначала дифференциальная характеристика используется для получения частичной информации, а затем линейная аппроксимация — для уточнения.

Применение к известным шифрам

DES

Для полного 16-раундового DES Бихам и Шамир нашли 13-раундовую характеристику с вероятностью ~2^-47. Атака требовала 2^47 выбранных текстов и 2^37 операций. Это показало, что DES не является стойким к дифференциальному анализу, хотя его S-блоки были спроектированы с учётом защиты.

AES (Rijndael)

AES был спроектирован с высокой устойчивостью к дифференциальному криптоанализу. Для полного 10-раундового AES-128 не найдено практических дифференциальных атак, превосходящих полный перебор. Однако существуют атаки на усечённые версии (до 6-7 раундов) с использованием невозможных дифференциалов.

ГОСТ 28147-89

Российский стандарт шифрования (ГОСТ 28147-89) обладает большой длиной ключа (256 бит) и использует 32 раунда. Дифференциальный анализ против полного ГОСТа считается неэффективным из-за большого числа раундов и нелинейности S-блоков, однако для некоторых вариантов S-блоков (слабо спроектированных) возможны атаки на 8-10 раундов.

Современные шифры

Практически все современные блочные шифры (Serpent, Twofish, Camellia, «Кузнечик» (ГОСТ Р 34.12-2015) и др.) проходят обязательную проверку на устойчивость к дифференциальному криптоанализу. Для этого разработчики доказывают верхние границы вероятности дифференциальных характеристик (обычно не выше 2^-n для n-битного блока).

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

• Требовательность к ресурсам: классический дифференциальный анализ требует большого числа выбранных открытых текстов (часто 2^40–2^50), что может быть непрактично.
• Зависимость от структуры шифра: метод плохо работает против шифров с непредсказуемыми S-блоками или с большим числом раундов.
• Контрмеры: разработчики шифров используют S-блоки с равномерными таблицами дифференциальных распределений (DDT) и вводят дополнительные раунды, чтобы снизить вероятность любой характеристики до пренебрежимо малой.

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

• В 1994 году Дон Копперсмит (IBM) опубликовал статью, в которой подтвердил, что разработчики DES в 1970-х годах знали о дифференциальном криптоанализе и специально усилили S-блоки.
• Метод был впервые применён не к DES, а к шифру FEAL (1987), который был взломан Бихамом и Шамиром с помощью дифференциального анализа.
• В 2000-е годы появились атаки на хеш-функции (например, MD5, SHA-1), основанные на дифференциальных методах, что привело к их вытеснению.

Источники

• Biham E., Shamir A. Differential Cryptanalysis of the Data Encryption Standard. — Springer, 1993.
• Biham E., Shamir A. Differential Cryptanalysis of DES-like Cryptosystems // Journal of Cryptology. — 1991. — Vol. 4, № 1.
• Knudsen L. R. Truncated and Higher Order Differentials // Fast Software Encryption. — 1995.
• Daemen J., Rijmen V. The Design of Rijndael: AES — The Advanced Encryption Standard. — Springer, 2002.
• ГОСТ Р 34.12-2015. Информационная технология. Криптографическая защита информации. Блочные шифры.