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

Первые открытые упоминания в литературе с 1990 года в работах Мерфи, Бихема и Шамира. Методика анализа строится индивидуально для каждого алгоритма и основана на знании пар сообщений m и m’ для которых известны соответствующие шифртексты E_k (m) и E_k (m’) и XOR-разности между ними с рассмотрением разности между промежуточными частями блоков сообщений.

Для двухветвевой сети Файстеля Δ m_i = m_i Å m’_i. При этом для каждого раунда в отдельности справедливо следующее:

Δ m_{i+ 1} = m_{i+ 1} Å m’_{i +1} = Δ m_{i- 1} Å [ f (m_i, K_i) Å f (m’_i, K_i)]

Предполагается, что для многих пар входных данных функции f, имеющих одну и ту же XOR-разность, при использовании одного и того же подключа одинаковой оказывается и XOR-разность для соответствующих выходных пар. Формально говорят, что X влечет Y с вероятностью р, если для относительной доли р входных пар с XOR-разностью Х для соответствующих выходных пар XOR-разность оказывается равной Y. Предположим теперь, что имеется ряд значений X, которые с высокой вероятностью влекут определенные разности выходных значений. Тогда если нам с большой вероятностью известны значения Δ m_{i- 1} и Δ m_i то мы с большой вероятностью можем определить и Δ m_i- ₁. А если удастся найти достаточно много таких значений разности, становится возможным определить подключ, используемый функцией f.

Общая стратегия дифференциального криптоанализа основывается на представленной выше методике для каждого раунда шифрования в отдельности. Процедура начинается с рассмотрения двух сообщений открытого текста m и m ' с заданной разностью и имеет своей целью получение вероятностных оценок разностей промежуточных результатов последовательно раунд за раундом с тем, чтобы определить вероятностную оценку для разности соответствующих шифрованных текстов. На самом деле получаются вероятностные оценки для двух 32-битовых половинок сообщения (m ₁₇ || m ₁₆). После этого выполняется шифрование m и m’, чтобы определить реальные разности при неизвестном ключе, а затем, сравнить результат с вычисленными вероятностными оценками. Если результаты совпадают, т.е.

Е_к (m) Å Е_к (m’) = (Δ m ₁₇|| m ₁₆),

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