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

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

История

Открытие дифференциального криптоанализа обычно приписывают Эли Бихаму и Ади Шамиру в конце 1980-х, которые опубликовали ряд атак против различных блочных шифров и хэш-функций, включая теоретическую слабость в стандарте шифрования данных (DES). Бихам и Шамир отметили, что DES оказался на удивление устойчивым к дифференциальному криптоанализу, но небольшие модификации алгоритма сделали бы его гораздо более уязвимым.

В 1994 году член первоначальной команды IBM DES Дон Копперсмит опубликовал статью, в которой говорилось, что дифференциальный криптоанализ был известен IBM еще в 1974 году и что защита от дифференциального криптоанализа была целью разработки. По словам автора Стивена Леви , IBM открыла дифференциальный криптоанализ самостоятельно, и АНБ, очевидно, хорошо знало эту технику. IBM хранила некоторые секреты, как объясняет Копперсмит: «После обсуждений с NSA было решено, что раскрытие проектных соображений раскроет метод дифференциального криптоанализа, мощный метод, который можно использовать против многих шифров. Это, в свою очередь, ослабит конкуренцию преимущество США перед другими странами в области криптографии ». В IBM дифференциальный криптоанализ был известен как «Т-атака» или «атака пощекотанием».

Хотя DES был разработан с учетом устойчивости к дифференциальному криптоанализу, другие современные шифры оказались уязвимыми. Первой целью атаки был блочный шифр FEAL . Первоначально предложенная версия с четырьмя раундами (FEAL-4) может быть взломана с использованием только восьми выбранных открытых текстов , и даже версия FEAL с 31 раундом уязвима для атаки. Напротив, схема может успешно криптоанализовать DES с усилием порядка 2 47 выбранных открытых текстов.

Механика атаки

Дифференциальный криптоанализ обычно представляет собой атаку по выбранному открытому тексту , что означает, что злоумышленник должен иметь возможность получить зашифрованные тексты для некоторого набора открытых текстов по своему выбору. Однако есть расширения, которые позволяют использовать известный открытый текст или даже атаку только зашифрованного текста . В базовом методе используются пары открытого текста, связанные постоянной разницей . Разницу можно определить несколькими способами, но обычно используется операция исключающее ИЛИ (XOR) . Затем злоумышленник вычисляет различия соответствующих зашифрованных текстов, надеясь обнаружить статистические закономерности в их распределении. Получившаяся пара разностей называется дифференциалом . Их статистические свойства зависят от природы S-блоков, используемых для шифрования, поэтому злоумышленник анализирует различия, в которых

(и ⊕ обозначает исключающими или) для каждой такой S-коробку S . Ожидается, что в основной атаке особенно часто будет встречаться одно конкретное различие зашифрованного текста. Таким образом, шифр можно отличить от случайного . Более сложные варианты позволяют восстановить ключ быстрее, чем полный поиск .

В самой простой форме восстановления ключа с помощью дифференциального криптоанализа злоумышленник запрашивает шифрованные тексты для большого количества пар открытого текста, а затем предполагает, что разность сохраняется как минимум в течение r - 1 раундов, где r - общее количество раундов. Затем злоумышленник определяет, какие ключи раунда (для последнего раунда) возможны, предполагая, что разница между блоками до последнего раунда исправлена. Когда раундовые ключи короткие, это может быть достигнуто простым исчерпывающим дешифрованием пар зашифрованного текста за один раунд с каждым возможным раундовым ключом. Когда один ключ раунда считается потенциальным ключом раунда значительно чаще, чем любой другой ключ, предполагается, что это правильный ключ раунда.

Для любого конкретного шифра необходимо тщательно выбирать входную разницу, чтобы атака была успешной. Проведен анализ внутреннего устройства алгоритма; Стандартный метод - проследить путь весьма вероятных различий на различных этапах шифрования, называемый дифференциальной характеристикой .

С тех пор, как дифференциальный криптоанализ стал общеизвестным, он стал основной заботой разработчиков шифров. Ожидается, что новые разработки будут сопровождаться доказательствами того, что алгоритм устойчив к этой атаке, и многие из них, включая Advanced Encryption Standard , доказали свою безопасность от атаки.

Подробная атака

Атака основана в первую очередь на том факте, что данная модель разности входов / выходов возникает только для определенных значений входов. Обычно атака применяется по существу к нелинейным компонентам, как если бы они были сплошным компонентом (обычно это фактически справочные таблицы или S-блоки ). Наблюдение за желаемой выходной разницей (между двумя выбранными или известными входными текстами) предлагает возможные ключевые значения.

Например, если дифференциал 1 => 1 (подразумевающий разницу в младшем значащем бите (LSB) входа приводит к разнице выходного в LSB) возникает с вероятностью 4/256 (возможно с нелинейной функцией в шифре AES, например), то такой дифференциал возможен только для 4 значений (или 2 пар) входов. Предположим, у нас есть нелинейная функция, в которой ключ подвергается операции XOR перед вычислением, а значения, допускающие дифференциал, - это {2,3} и {4,5}. Если злоумышленник отправляет значения {6, 7} и наблюдает правильную разность выходных данных, это означает, что ключ равен либо 6 ⊕ K = 2, либо 6 K = 4, что означает, что ключ K равен 2 или 4.

По сути, для n-битной нелинейной функции в идеале следовало бы искать как можно ближе к 2 - ( n - 1), чтобы достичь дифференциальной однородности . Когда это происходит, дифференциальная атака требует для определения ключа столько же работы, сколько и простой перебор ключа.

Нелинейная функция AES имеет максимальную дифференциальную вероятность 4/256 (однако большинство записей имеют значение 0 или 2). Это означает, что теоретически можно определить ключ, затратив вдвое меньше работы, чем грубая сила, однако высокая ветвь AES предотвращает существование любых высоконадежных следов за несколько раундов. Фактически, шифр AES будет столь же невосприимчив к дифференциальным и линейным атакам с гораздо более слабой нелинейной функцией. Невероятно высокая ветвь (количество активных S-блоков) 25 на 4R означает, что за 8 раундов ни одна атака не включает менее 50 нелинейных преобразований, а это означает, что вероятность успеха не превышает Pr [атака] ≤ Pr [лучшая атака на S-box] 50 . Не , например, с текущим S-блока AES выделяет никаких фиксированных дифференциал с вероятностью выше (4/256) 50 или 2 -300 , который значительно ниже требуемого порога 2 -128 для 128-битного блочного шифра. Это дало бы место для более эффективного S-блока, даже если бы он был однородным по 16, вероятность атаки все равно была бы 2 -200 .

Для входов / выходов одинакового размера с 2-однородностью не существует взаимных отклонений. Они существуют в нечетных полях (таких как GF (2 7 )), используя кубирование или инверсию (можно использовать и другие показатели степени). Например, S (x) = x 3 в любом нечетном двоичном поле невосприимчив к дифференциальному и линейному криптоанализу. Отчасти поэтому конструкции MISTY используют 7- и 9-битные функции в 16-битной нелинейной функции. То, что эти функции получают от невосприимчивости к дифференциальным и линейным атакам, они теряют при алгебраических атаках. То есть их можно описать и решить с помощью решателя SAT . Отчасти поэтому AES (например) имеет аффинное отображение после инверсии.

Специализированные типы

Смотрите также

использованная литература

Общий
  • Эли Бихам, Ади Шамир, Дифференциальный криптоанализ стандарта шифрования данных, Springer Verlag, 1993. ISBN  0-387-97930-1 , ISBN  3-540-97930-1 .
  • Бихам, Э. и А. Шамир. (1990). Дифференциальный криптоанализ DES-подобных криптосистем. Достижения в криптологии - CRYPTO '90. Springer-Verlag. 2–21.
  • Эли Бихам, Ади Шамир, "Дифференциальный криптоанализ полного 16-раундового DES", CS 708, Proceedings of CRYPTO '92, Volume 740 of Lecture Notes in Computer Science, декабрь 1991 г. (Постскриптум)

внешние ссылки