Дифференциальный криптоанализ
Дифференциальный криптоанализ — это общая форма криптоанализа , применимая в первую очередь к блочным шифрам, а также к потоковым шифрам и криптографическим хеш-функциям. В самом широком смысле это исследование того, как различия во входной информации могут повлиять на результирующую разницу на выходе. В случае блочного шифра это относится к набору методов отслеживания различий в сети преобразования, обнаружения неслучайного поведения шифра и использования таких свойств для восстановления секретного ключа (криптографического ключа).
Открытие дифференциального криптоанализа обычно приписывают Эли Бихаму и Ади Шамиру в конце 1980-х годов, которые опубликовали ряд атак против различных блочных шифров и хеш-функций, включая теоретическую слабость в стандарте шифрования данных (DES). Бихам и Шамир отметили, что DES на удивление устойчив к дифференциальному криптоанализу, но небольшие модификации алгоритма сделают его гораздо более восприимчивым. [1]
В 1994 году член первоначальной команды IBM DES, Дон Копперсмит , опубликовал статью, в которой утверждалось, что дифференциальный криптоанализ был известен IBM еще в 1974 году и что целью разработки была защита от дифференциального криптоанализа. [2] По словам автора Стивена Леви , IBM самостоятельно открыла дифференциальный криптоанализ, и АНБ , очевидно, было хорошо осведомлено об этой технике. [3]Как поясняет Копперсмит, IBM хранила некоторые секреты: «После обсуждений с АНБ было решено, что раскрытие сведений о конструкции раскроет технику дифференциального криптоанализа, мощную технику, которую можно использовать против многих шифров. преимущество Соединенных Штатов перед другими странами в области криптографии». [2] В IBM дифференциальный криптоанализ был известен как «Т-атака» [2] или «Атака щекотки». [4]
Хотя DES был разработан с учетом устойчивости к дифференциальному криптоанализу, другие современные шифры оказались уязвимыми. Первой целью атаки был блочный шифр FEAL . Первоначально предложенная версия с четырьмя раундами (FEAL-4) может быть взломана с использованием только восьми выбранных открытых текстов , и даже 31-раундовая версия FEAL подвержена атаке. Напротив, схема может успешно криптоанализировать DES с усилием порядка 2 47 выбранных открытых текстов.
Дифференциальный криптоанализ обычно представляет собой атаку с выбранным открытым текстом , что означает, что злоумышленник должен иметь возможность получить зашифрованные тексты для некоторого набора открытых текстов по своему выбору. Однако существуют расширения, которые позволяют атаковать по известному открытому тексту или даже атаковать только зашифрованным текстом . Базовый метод использует пары открытого текста, связанные постоянной разностью . Разницу можно определить несколькими способами, но обычно используется операция исключающее ИЛИ (XOR) . Затем злоумышленник вычисляет различия соответствующих зашифрованных текстов, надеясь обнаружить статистические закономерности в их распределении. Полученная пара разностей называетсядифференциал . Их статистические свойства зависят от природы S-блоков , используемых для шифрования, поэтому злоумышленник анализирует различия там, где
