Слайд-атака

Форма криптоанализа

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

Впервые приступ описали Дэвид Вагнер и Алексей Бирюков . Брюс Шнайер первым предложил им термин « атака слайдом» , и они использовали его в своей статье 1999 года, описывающей атаку.

Единственное требование для того, чтобы атака скольжением работала над шифром, - это то, что ее можно разбить на несколько раундов идентичной функции F. Вероятно, это означает, что он имеет циклическое расписание ключей. Функция F должна быть уязвима для атаки с использованием известного открытого текста . Атака слайдом тесно связана с атакой связанной клавиши .

Идея атаки слайдом уходит корнями в статью, опубликованную Эдной Гроссман и Брайантом Такерманом в техническом отчете IBM в 1977 году. ^[1] Гроссман и Такерман продемонстрировали атаку на слабый блочный шифр под названием New Data Seal (NDS). Атака основывалась на том факте, что шифр имеет одинаковые подразделы в каждом раунде, поэтому шифр имел циклическое расписание ключей с циклом только одного ключа, что делает его ранней версией атаки слайдом. Краткое изложение отчета, включая описание блочного шифра NDS и атаки, приведено в Cipher Systems (Beker & Piper, 1982).

Настоящая атака

Прежде всего, введем некоторые обозначения. В этом разделе предполагается, что шифр использует n битовых блоков и имеет расписание ключей, использующее в качестве ключей любую длину. ${\displaystyle K_{1}\cdots K_{m}}$

Атака слайдом работает путем разбиения шифра на идентичные функции перестановки F . Эта функция F может состоять из более чем одного раунда шифрования; это определяется ключевым расписанием. Например, если шифр использует попеременное расписание ключей, в котором он переключается между a и для каждого раунда, функция F будет состоять из двух раундов. Каждый из них появится хотя бы один раз в F . ${\displaystyle K_{1}}$ ${\displaystyle K_{2}}$ ${\displaystyle K_{i}}$

Следующим шагом является сбор пар открытый текст-зашифрованный текст. В зависимости от характеристик шифра может хватить и меньшего количества, но к моменту рождения не больше, чем необходимо. Эти пары, обозначенные как, затем используются для поиска скользящей пары , которая обозначается . Скользящая пара обладает свойством то и то . Как только скользящая пара идентифицирована, шифр взламывается из-за уязвимости к атакам с использованием известного открытого текста. Ключ можно легко извлечь из этой пары. Скользящую пару можно рассматривать как то, что происходит с сообщением после одного применения функции F. Он «продвигается» в течение одного раунда шифрования, и именно здесь атака получила свое название. ${\displaystyle 2^{n/2}}$ ${\displaystyle 2^{n/2}}$ ${\displaystyle (P,C)}$ ${\displaystyle (P_{0},C_{0})(P_{1},C_{1})}$ ${\displaystyle P_{0}=F(P_{1})}$ ${\displaystyle C_{0}=F(C_{1})}$

Процесс поиска скользящей пары несколько отличается для каждого шифра, но следует одной и той же базовой схеме. Один использует тот факт, что относительно легко извлечь ключ всего за одну итерацию F . Выберите любую пару пар открытый текст-зашифрованный текст и проверьте, какие ключи соответствуют и . Если эти ключи совпадают, это скользящая пара; в противном случае переходите к следующей паре. ${\displaystyle (P_{0},C_{0})(P_{1},C_{1})}$ ${\displaystyle P_{0}=F(P_{1})}$ ${\displaystyle C_{0}=F(C_{1})}$

В парах открытый текст-зашифрованный текст ожидается одна скользящая пара, а также небольшое количество ложных срабатываний в зависимости от структуры шифра. Ложные срабатывания можно устранить, используя ключи другой пары сообщение-зашифрованный текст, чтобы проверить правильность шифрования. Вероятность того, что неправильный ключ правильно зашифрует два или более сообщения, для хорошего шифра очень мала. ${\displaystyle 2^{n/2}}$

Иногда структура шифра значительно уменьшает количество необходимых пар открытый текст-зашифрованный текст и, следовательно, большой объем работы. Самым ярким из этих примеров является шифр Фейстеля , использующий циклическое расписание ключей. Причиной этого является поиск файла . Это уменьшает количество возможных парных сообщений с нуля до (поскольку половина сообщения фиксирована), и поэтому для нахождения скользящей пары требуется максимум пары открытый текст-зашифрованный текст. ${\displaystyle P=(L_{0},R_{0})}$ ${\displaystyle P_{0}=(R_{0},L_{0}\bigoplus F(R_{0},K))}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n/2}}$ ${\displaystyle 2^{n/4}}$

Рекомендации

1. ЭК Гроссман; Б. Такерман (1977). Анализ шифра типа Фейстеля, ослабленного отсутствием вращающегося ключа (технический отчет). Исследовательский центр IBM Томаса Дж. Уотсона. РЦ 6375.

• Генри Бекер и Фред Пайпер (1982). Системы шифрования: защита коммуникаций . Джон Уайли и сыновья . стр. 263–267. ISBN 978-0-471-89192-5.(содержит краткое изложение статьи Гроссмана и Такермана)
• Алексей Бирюков и Дэвид Вагнер (март 1999 г.). Слайд-атаки ( PDF / PostScript ) . 6-й международный семинар по быстрому программному шифрованию (FSE '99). Рим : Шпрингер-Верлаг . стр. 245–259 . Проверено 3 сентября 2007 г.
• Алекс Бирюков и Дэвид Вагнер (май 2000 г.). Расширенные слайд-атаки (PDF/PostScript) . Достижения в криптологии, Труды EUROCRYPT 2000. Брюгге : Springer-Verlag. стр. 589–606 . Проверено 3 сентября 2007 г.
• С. Фуруя (декабрь 2001 г.). Слайд-атаки с использованием криптоанализа с известным открытым текстом (PDF) . 4-я Международная конференция по информационной безопасности и криптологии (ICISC 2001). Сеул : Springer-Verlag. стр. 214–225 . Проверено 3 сентября 2007 г.
• Эли Бихам (1994). «Новые типы криптоаналитических атак с использованием связанных ключей» (PDF/PostScript) . Журнал криптологии . 7 (4): 229–246. CiteSeerX  10.1.1.48.8341 . дои : 10.1007/bf00203965. ISSN  0933-2790. S2CID  19776908 . Проверено 3 сентября 2007 г.
• М. Сиет, Г. Пире, Ж. Кискатер (2002). «Атаки с использованием связанных клавиш и слайдов: анализ, связи и улучшения» (PDF/PostScript) . Проверено 4 сентября 2007 г. {{cite journal}}: Требуется цитировать журнал |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )