Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

История [ править ]

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

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

В то время как 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 (например) имеет аффинное отображение после инверсии.

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

  • Дифференциальный криптоанализ высшего порядка
  • Усеченный дифференциальный криптоанализ
  • Невозможный дифференциальный криптоанализ
  • Бумеранг атака

См. Также [ править ]

  • Криптография
  • Линейный криптоанализ
  • Дифференциальные уравнения сложения

Ссылки [ править ]

  1. ↑ Бихам и Шамир, 1993, стр. 8-9
  2. ^ a b c Медник, Дон (май 1994 г.). «Стандарт шифрования данных (DES) и его сила против атак» (PDF) . Журнал исследований и разработок IBM . 38 (3): 243–250. DOI : 10.1147 / rd.383.0243 . (требуется подписка)
  3. ^ Леви, Стивен (2001). Крипто: как повстанцы кода победили правительство - сохранение конфиденциальности в цифровую эпоху . Книги пингвинов . С. 55–56. ISBN 0-14-024432-8.
  4. ^ Мэтт Блейз, sci.crypt , 15 августа 1996, Re: обратный инжиниринг и чип Clipper "
Общий
  • Эли Бихам, Ади Шамир, Дифференциальный криптоанализ стандарта шифрования данных, 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 г. (Постскриптум)

Внешние ссылки [ править ]

  • Учебное пособие по дифференциальному (и линейному) криптоанализу
  • Ссылки Хельгера Липмаа на дифференциальный криптоанализ
  • Описание атаки, примененной к DES на Wayback Machine (архивировано 19 октября 2007 г.)