Скользящая атака

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

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

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

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

Во-первых, введем некоторые обозначения. В этом разделе предполагается, что шифр принимает n битовых блоков и имеет расписание ключей с использованием $K\; 1\; \cdots \; K\; m\; \{\backslash \; displaystyle\; K\_\; \{1\}\; \backslash \; cdots\; K\_\; \{m\}\}$в качестве ключей любой длины..

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

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

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

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

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

• Э.К. Гроссман и Б. Такерман (1977). «Анализ шифра типа Фейстеля, ослабленного отсутствием вращающегося ключа». Отчет IBM Thomas J. Watson Research Report RC 6375. Cite journal требует | journal =()
• Генри Бекер и Фред Пайпер (1982). Системы шифрования: Защита коммуникаций. John Wiley Sons. Pp. 263–267. ISBN 978-0-471-89192-5.(содержит резюме статьи Гроссмана и Такермана)
• Алекс Бирюков и Дэвид Вагнер (март 1999). Slide Attacks (PDF / PostScript ). 6-й Международный семинар по быстрому программному шифрованию (FSE '99). Rome : Springer-Verlag. Pp. 245–259. Проверено 2007-09-03.
• Алекс Бирюков и Дэвид Вагнер (май 2000 г.). Advanced Slide Attacks (PDF / PostScript). Advances in Cryptology, Proceedings of EUROCRYPT 2000. Брюгге : Springer-Verlag. Pp. 589–606. Проверено 2007-09-03.
• С. Фуруя (декабрь 2001 г.). Атаки слайдов с помощью криптоанализа с открытым текстом (PDF). 4-я Международная конференция по Информационная безопасность и криптология (ICISC 2001). Сеул : Springer-Verlag. С. 214–225. Проверено 3 сентября 2007 г.
• Эли Бихам (1994). «Новые типы криптоаналитических атак с использованием связанных ключей» (PDF / PostScript). Журнал криптологии. 7(4): 229–246. CiteSeerX 10.1.1.48.8341. doi : 10.1007 / bf00203965. ISSN 0933-2790. Проверено 3 сентября 2007.
• M. Ciet, G. Piret, J. Quisquater (2002). «Атаки по связанным клавишам и слайдам: анализ, связи и улучшения» (PDF / PostScript). Проверено 4 сентября 2007 г. Для цитирования журнала требуется | journal =() CS1 maint: multiple names: список авторов (ссылка )