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

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

История

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

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

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

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

Дифференциальный криптоанализ обычно представляет собой атаку с использованием выбранного открытого текста , что означает, что злоумышленник должен иметь возможность получить зашифрованные тексты для некоторого набора открытых текстов по своему выбору. Однако существуют расширения, которые допускают атаку с использованием известного открытого текста или даже атаки только с использованием зашифрованного текста . Базовый метод использует пары открытых текстов, связанных постоянной разницей . Разницу можно определить несколькими способами, но исключающего ИЛИ (XOR) обычно используется операция . Затем злоумышленник вычисляет различия соответствующих зашифрованных текстов, надеясь обнаружить статистические закономерности в их распределении. Полученная пара разностей называется дифференциалом . Их статистические свойства зависят от природы S-блоков, используемых для шифрования, поэтому злоумышленник анализирует различия. $(\Delta _{x},\Delta _{y})$ где $\Delta _{y}=S(x\oplus \Delta _{x})\oplus S(x)$ (и ⊕ обозначает исключающее или) для каждого такого S-блока S . Ожидается, что при базовой атаке особенно часто будет встречаться одно конкретное различие в зашифрованном тексте. Таким образом, шифр можно отличить от случайного . Более сложные варианты позволяют восстановить ключ быстрее, чем полный поиск .

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

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

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

Атака в деталях

Атака в первую очередь основана на том факте, что заданный шаблон разницы входных/выходных данных возникает только для определенных значений входных данных. Обычно атака по существу применяется к нелинейным компонентам, как если бы они были сплошным компонентом (обычно это на самом деле справочные таблицы или 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. ^{−( п − 1)} как можно скорее добиться дифференциальной однородности . Когда это происходит, дифференциальная атака требует столько же усилий для определения ключа, сколько и простой перебор ключа. ^{[ 7 ]}

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

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

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

См. также

Ссылки

^ Бихам Э, Шамир А (1993). Дифференциальный криптоанализ стандарта шифрования данных . Нью-Йорк: Springer Verlag. ISBN 978-0-387-97930-4 .
^ Jump up to: ^а ^б ^с Медник Д. (май 1994 г.). «Стандарт шифрования данных (DES) и его защита от атак» (PDF) . Журнал исследований и разработок IBM . 38 (3): 243–250. дои : 10.1147/rd.383.0243 . (требуется подписка)
^ Леви С (2001). Крипто: как повстанцы кода побеждают правительство — сохранение конфиденциальности в эпоху цифровых технологий . Книги о пингвинах . стр. 55–56. ISBN 0-14-024432-8 .
^ Блейз М. (15 августа 1996 г.). «Re: Реверс-инжиниринг и чип Clipper» . наука.крипта .
^ «Дифференциальный криптоанализ — обзор | Темы ScienceDirect» . www.sciencedirect.com . Проверено 13 апреля 2023 г.
^ Нечватал Дж., Баркер Э., Башам Л., Берр В., Дворкин М., Фоти Дж., Робак Э. (май – июнь 2001 г.). «Отчет о разработке расширенного стандарта шифрования (AES)» . Журнал исследований Национального института стандартов и технологий . 106 (3): 511–577. дои : 10.6028/jres.106.023 . ПМЦ 4863838 . ПМИД 27500035 . 3.2.1.3.
^ Индестидж, Себастьян; Пренил, Барт (2009). «Практические столкновения для EnRUPT» . В Данкельмане, Орр (ред.). Быстрое программное шифрование . Конспекты лекций по информатике. Том. 5665. Берлин, Гейдельберг: Springer. стр. 246–259. дои : 10.1007/978-3-642-03317-9_15 . ISBN 978-3-642-03317-9 .

Дальнейшее чтение

Бихам Э., Шамир А (январь 1991 г.). «Дифференциальный криптоанализ DES-подобных криптосистем». Журнал криптологии . 4 (1): 3–72. дои : 10.1007/BF00630563 . S2CID 33202054 .
Бихам Э., Шамир А (август 1992 г.). «Дифференциальный криптоанализ полного 16-раундового DES». . Ежегодная международная конференция по криптологии . Конспекты лекций по информатике. Том. 740. Берлин, Гейдельберг: Springer. стр. 487–496. дои : 10.1007/3-540-48071-4_34 . ISBN 978-3-540-57340-1 . S2CID 6188138 . Архивировано из оригинала 5 апреля 2005 г.
Кнудсен Л.Р., Робшоу М. (2011). «Дифференциальный криптоанализ: идея». Компаньон по блочным шифрам . Информационная безопасность и криптография. Спрингер. стр. 109–126. дои : 10.1007/978-3-642-17342-4 . ISBN 978-3-642-17341-7 .

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

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

[Biham_1993-1] Бихам Э, Шамир А (1993). Дифференциальный криптоанализ стандарта шифрования данных . Нью-Йорк: Springer Verlag. ISBN 978-0-387-97930-4 .

[coppersmith-2] Jump up to: ^а ^б ^с Медник Д. (май 1994 г.). «Стандарт шифрования данных (DES) и его защита от атак» (PDF) . Журнал исследований и разработок IBM . 38 (3): 243–250. дои : 10.1147/rd.383.0243 . (требуется подписка)

[3] Леви С (2001). Крипто: как повстанцы кода побеждают правительство — сохранение конфиденциальности в эпоху цифровых технологий . Книги о пингвинах . стр. 55–56. ISBN 0-14-024432-8 .

[4] Блейз М. (15 августа 1996 г.). «Re: Реверс-инжиниринг и чип Clipper» . наука.крипта .

[5] «Дифференциальный криптоанализ — обзор | Темы ScienceDirect» . www.sciencedirect.com . Проверено 13 апреля 2023 г.

[6] Нечватал Дж., Баркер Э., Башам Л., Берр В., Дворкин М., Фоти Дж., Робак Э. (май – июнь 2001 г.). «Отчет о разработке расширенного стандарта шифрования (AES)» . Журнал исследований Национального института стандартов и технологий . 106 (3): 511–577. дои : 10.6028/jres.106.023 . ПМЦ 4863838 . ПМИД 27500035 . 3.2.1.3.

[7] Индестидж, Себастьян; Пренил, Барт (2009). «Практические столкновения для EnRUPT» . В Данкельмане, Орр (ред.). Быстрое программное шифрование . Конспекты лекций по информатике. Том. 5665. Берлин, Гейдельберг: Springer. стр. 246–259. дои : 10.1007/978-3-642-03317-9_15 . ISBN 978-3-642-03317-9 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]