Войти
Дифференциальный криптоанализ - это общая форма криптоанализа, применимая в первую очередь к блочным шифрам, но также к потоковым шифрам и криптографическим хеш-функциям. В самом широком смысле, это исследование того, как различия во входящей информации могут повлиять на результирующую разницу на выходе. В случае блочного шифра , это относится к набору методов для отслеживания различий в сети преобразования, обнаружения, где шифр проявляет неслучайное поведение, и использования таких свойств. восстановить секретный ключ (ключ криптографии).
Открытие дифференциального криптоанализа обычно приписывается Эли Бихаму и Ади Шамиру в конце 1980-х годов, которые опубликовали ряд атак на различные блочные шифры и хэш-функции. включая теоретическую слабость в стандарте шифрования данных (DES). Бихам и Шамир отметили, что DES оказался на удивление устойчивым к дифференциальному криптоанализу, но небольшие модификации алгоритма сделали бы его гораздо более восприимчивым.
В 1994 году член первоначальной команды IBM DES Дон Копперсмит опубликовал статью, в которой говорилось, что дифференциальный криптоанализ был известен IBM еще в 1974 году и что защита от дифференциального криптоанализа была целью разработки. Согласно автору Стивену Леви, IBM открыла дифференциальный криптоанализ самостоятельно, и АНБ, очевидно, хорошо осведомлены об этой технике. IBM хранила некоторые секреты, как объясняет Копперсмит: «После обсуждений с NSA было решено, что раскрытие проектных соображений позволит раскрыть технику дифференциального криптоанализа, мощную технику, которую можно использовать против многих шифров. Это, в свою очередь, ослабит конкуренцию. преимущество США перед другими странами в области криптографии ». В IBM дифференциальный криптоанализ был известен как «T-атака» или «атака пощекотанием».
Хотя DES был разработан с учетом устойчивости к дифференциальному криптоанализу, другие современные шифры оказались уязвимыми. Первой целью атаки был блочный шифр FEAL. Первоначально предложенная версия с четырьмя раундами (FEAL-4) может быть взломана с использованием только восьми выбранных открытых текстов, и даже версия FEAL с 31 раундом уязвима для атаки. Напротив, схема может успешно криптоанализовать DES с усилием на 2 выбранных открытых текстах.
Дифференциальный криптоанализ обычно представляет собой атаку с использованием открытого текста, что означает, что злоумышленник должен иметь возможность получить зашифрованные тексты для некоторого набора открытые тексты по их выбору. Однако существуют расширения, которые допускают известный открытый текст или даже атаку только зашифрованного текста. В базовом методе используются пары открытого текста, связанные постоянной разницей. Разница может быть определена несколькими способами, но обычно используется операция исключающее ИЛИ (XOR). Затем злоумышленник вычисляет различия соответствующих шифрованных текстов, надеясь обнаружить статистические закономерности в их распределении. Полученная пара разностей называется дифференциалом . Их статистические свойства зависят от природы S-блоков, используемых для шифрования, поэтому злоумышленник анализирует различия (Δ X, Δ Y), где Δ Y = S (X ⊕ Δ X) ⊕ S (X) (и ⊕ означает исключающее или) для каждого такого S-блока S. При базовой атаке одно конкретное различие зашифрованного текста является ожидается, что это будет особенно часто; таким образом, шифр можно отличить от random. Более сложные варианты позволяют восстановить ключ быстрее, чем исчерпывающий поиск.
В наиболее простой форме восстановления ключа с помощью дифференциального криптоанализа злоумышленник запрашивает зашифрованные тексты для большого количества пар открытого текста, а затем предполагает, что разность сохраняется. не менее 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, чтобы достичь дифференциальной однородности. Когда это происходит, дифференциальная атака требует для определения ключа столько же работы, сколько и простой перебор ключа.
Нелинейная функция AES имеет максимальную дифференциальную вероятность 4/256 (однако большинство элементов имеют значение 0 или 2). Это означает, что теоретически можно определить ключ, затратив вдвое меньше работы, чем грубая сила, однако высокая ветвь AES предотвращает существование каких-либо трасс с высокой вероятностью за несколько раундов. Фактически, шифр AES будет столь же невосприимчив к дифференциальным и линейным атакам с гораздо более слабой нелинейной функцией. Невероятно высокая ветвь (количество активных S-блоков) 25 на 4R означает, что за 8 раундов ни одна атака не включает менее 50 нелинейных преобразований, что означает, что вероятность успеха не превышает Pr [атака] ≤ Pr [лучшая атака на S-бокс]. Например, с текущим S-блоком AES не излучает фиксированный дифференциал с вероятностью выше (4/256) или 2, что намного ниже требуемого порога 2 для 128-битного блочного шифра. Это дало бы место для более эффективного S-блока, даже если он будет 16-однородным, вероятность атаки все равно будет 2.
Не существует взаимных отклонений для входов / выходов одинакового размера с 2-однородностью.. Они существуют в нечетных полях (таких как GF (2)), используя кубирование или инверсию (есть и другие показатели, которые также можно использовать). Например, S (x) = x в любом нечетном двоичном поле невосприимчив к дифференциальному и линейному криптоанализу. Отчасти поэтому конструкции MISTY используют 7- и 9-битные функции в 16-битной нелинейной функции. То, что эти функции получают от невосприимчивости к дифференциальным и линейным атакам, они теряют при алгебраических атаках. То есть их можно описать и решить с помощью решателя SAT. Отчасти поэтому AES (например) имеет аффинное отображение после инверсии.
