Атака слайдом

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

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

Впервые атака была описана Дэвидом Вагнером и Алексом Бирюковым . Термин «слайд-атака» впервые предложил им Брюс Шнайер , и они использовали его в своей статье 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 может состоять из более чем одного раунда шифра; она определяется расписанием ключей. Например, если шифр использует чередующееся расписание ключей, где он переключается между и для каждого раунда, функция 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}}$

Иногда структура шифра значительно сокращает количество необходимых пар открытый текст-зашифрованный текст, а значит, и большой объем работы. Самым понятным из этих примеров является шифр Фейстеля , использующий циклический график ключей. Причина этого в том, что при задании a выполняется поиск a . Это сокращает возможные парные сообщения с до (поскольку половина сообщения фиксирована), и поэтому для поиска скользящей пары требуется максимум пар открытый текст-зашифрованный текст. ${\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. EK Grossman; B. Tuckerman (1977). Анализ шифра типа Фейстеля, ослабленного отсутствием вращающегося ключа (технический отчет). IBM Thomas J. Watson Research Center. RC 6375.

• Генри Бекер и Фред Пайпер (1982). Системы шифрования: защита коммуникаций . John Wiley & Sons . стр. 263–267. ISBN 978-0-471-89192-5.(содержит краткое изложение статьи Гроссмана и Такермана)
• Алекс Бирюков и Дэвид Вагнер (март 1999 г.). Атаки со слайдами ( PDF / PostScript ) . 6-й международный семинар по быстрому программному шифрованию (FSE '99). Рим : Springer-Verlag . С. 245–259 . Получено 03.09.2007 .
• Алекс Бирюков и Дэвид Вагнер (май 2000 г.). Advanced Slide Attacks (PDF/PostScript) . Advances in Cryptology, Proceedings of EUROCRYPT 2000. Брюгге : Springer-Verlag. С. 589–606 . Получено 03.09.2007 .
• S. Furuya (декабрь 2001 г.). Slide Attacks with a Known-Plaintext Cryptanalysis (PDF) . 4-я Международная конференция по информационной безопасности и криптологии (ICISC 2001). Сеул : Springer-Verlag. стр. 214–225 . Получено 03.09.2007 .
• Эли Бихам (1994). "Новые типы криптоаналитических атак с использованием связанных ключей" (PDF/PostScript) . Журнал криптологии . 7 (4): 229–246. CiteSeerX  10.1.1.48.8341 . doi :10.1007/bf00203965. ISSN  0933-2790. S2CID  19776908 . Получено 03.09.2007 .
• M. Ciet, G. Piret, J. Quisquater (2002). "Атаки со связанными ключами и слайдами: анализ, связи и улучшения" (PDF/PostScript) . Получено 2007-09-04 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )