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

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

где 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-го цикла.

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

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

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⁴⁸ возможных ключей необходимо использовать счетчики, и к тому же для вскрытия понадобится слишком много данных.

Бихам и Шамир предложили свой способ атаки. Вместо использования 15-раундового дифференциала 16-раундового DES’а, они использовали 13-раундовый дифференциал и ряд приемов для прохождения последних нескольких раундов. Они также использовали некоторые хитрые математические приемы для получения потенциальных 56-битовых ключей, которые можно немедленно тестировать. Таким образом, устраняется надобность в счетчиках. Такая атака достигает успеха, как только находится правильная пара. Однако более подробная информация не приводится и остается лишь догадываться о том, как именно Бихам и Шамир осуществляли дифференциальный криптоанализ.