Общие сведения о дифференциальном криптоанализе

Понятие дифференциального криптоанализа впервые было введено в 1990 году Эли Бихамом и Ади Шамиром. Используя этот метод, Бихам и Шамир нашли способ атаки алгоритма DES с использованием подобранного открытого текста, который оказался эффективнее атаки «в лоб».

Ядро метода составляет атака на основе выборочного открытого текста. Анализ заключается в изучении процесса изменения несходства для пары открытых текстов, имеющих определенные исходные различия, в процессе прохождения через циклы шифрования с одним и тем же ключом. Не существует каких-либо ограничений на выбор открытых текстов. Достаточно различия в некоторых позициях.

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

Пусть некоторый блочный шифратор с длиной блока N строится по схеме, приведенной на рис. 6.1.

Схема блочного шифратора

Рисунок 6.1

где K = (K(1), K(2), …, K(r)) получается по некоторой схеме из К₀, или независимо и равновероятно выбирается для каждого цикла. Пусть Х(1) и Х’(1) – пара открытых текстов. Рассмотрим следующие разности:

DХ(1) = Х(1) – Х’(1);

DY(i) = Y(i) – Y’(i).

Задача дифференциального криптоанализа заключается в том, чтобы найти такие DХ(1), что при случайном равновероятном выборе Х(1), К(1), К(2), …, К(r-1) с вероятностью более 1/(2^N) появится DY(r-1).

Назовем пару (a, b) возможных значений вектора (DХ(1), DY(i)) называется дифференциалом I-го цикла.

Тогда дифференциальный анализ описывается следующей моделью (рис. 6.2).

Модель дифференциального криптоанализа

Рисунок 6.2

Подключ последнего цикла шифрования можно найти, используя следующий алгоритм:

1. Выбираем дифференциал (r-1) – го цикла (a, b), для которого вероятность Р(DХ(1) = a, DY(r-1) = b) большая.

2. Случайно выбираем Х(1) и подбираем Х’(1) так, чтобы DХ(1) = a. Пусть известны Y(r) и Y’(r).

3. Делаем предположение, что DY(r-1) = b и, зная Y(r) и Y’(r), находим К(r).

4. Повторяем 2 и 3 пока один подключ не начнет появляться чаще других.

Несмотря на кажущуюся простоту приведенного алгоритма, существует ряд проблем его реализации. Так, например, при атаке на алгоритм шифрования DES, для хранения вероятностей 2⁴⁸ возможных ключей необходимо использовать счетчики, и к тому же для анализа понадобится слишком много данных, зашифрованных на одном и том же значении секретного ключа.

Метод «встреча посередине»

Метод встреча посередине применим к алгоритмам шифрования, в которых используется два различных ключа К. Это может быть доятигнуто в том случае, если секретные подключи появляются с какой-то периодичночтью, или, например, если было произведено двойное зашифрование данных, то есть сначала данные зашифрованли на одном ключе К₁, а затем полученный результат шифрования еще раз зашифровали на другом секретном ключе К₂.

Пусть нам известна пара открытый – закрытый текст, зашифрованная подобным образом. В этом случае, необходимо произвести зашифрование открытого текста на всех возможных значениях ключа К₁. Паралелльно с этим необходимо произвести дешифрование закрытого текста на всех возможных значениях ключа К₂. Та пара ключей (К₁, К₂), для которой результат шифрования открытого текста и результат дешифрования закрытого текста совпадут, и будет являться искомой.

Метод «разделяй и побеждай»

Метод анализа «разделяй и побеждай» основан на том, что множество ключей К допускает представление K = K₁xK₂. То есть каждый ключ kÎK может быть записан в виде вектора k = (k₁, k₂), где k₁ÎK₁ и k₂ÎK₂.

Также обязательным условием является существование некоторого критерия h, позволяющего при известных открытом и закрытом текстах проверять правильность первого подключа k₁ в ключе k = (k₁, k₂).

Метод «разделяй и побеждай» предлагает опробовать сначала элементы множества K₁, отбраковывая варианты k₁ по критерию h. Отсюда мы определим k₁ – первую компоненту вектора k = (k₁, k₂). Затем, используя найденное значение k₁ и известный шифртекст, опробуем варианты k₂. Трудоемкость определения компоненты k1 равна в среднем операций опробования, соответственно трудоемкость определения k2 равна в среднем операций опробования. Тогда в среднем трудоемкость метода равна против при методе полного перебора.

Основная проблема при применении метода «разделяй и побеждай» состоит в нахождении критерия h, который зависит от конкретного преобразования T или вообще может не существовать. Иногда критерий h может описываться вероятностно-статистической моделью.