Скользящая атака - Slide attack

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

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

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

Идея скользящей атаки уходит корнями в статью, опубликованную Эдной Гроссман и Брайантом Такерманом в техническом отчете IBM в 1977 году. Гроссман и Такерман продемонстрировали атаку на слабый блочный шифр под названием 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 ^ {п / 2}}$${\ Displaystyle 2 ^ {п / 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 ^ {п / 2}}$

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

использованная литература

• Е. К. Гроссман и Б. Такерман (1977). «Анализ шифра типа Фейстеля, ослабленного отсутствием вращающегося ключа». Отчет об исследовании IBM Thomas J. Watson RC 6375. Цитировать журнал требует |journal=( помощь )
• Генри Бекер и Фред Пайпер (1982). Шифровальные системы: защита коммуникаций . Джон Вили и сыновья . С. 263–267. ISBN 978-0-471-89192-5. (содержит резюме статьи Гроссмана и Такермана)
• Алекс Бирюков и Давид Вагнер (март 1999 г.). Атаки на слайды ( PDF / PostScript ) . 6-й Международный семинар по быстрому программному шифрованию (FSE '99). Рим : Springer-Verlag . С. 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 . DOI : 10.1007 / bf00203965 . ISSN  0933-2790 . S2CID  19776908 . Проверено 3 сентября 2007 .
• М. Сиет, Дж. Пирет, Дж. Кискватер (2002). «Атаки по связанным клавишам и слайдам: анализ, связи и улучшения» (PDF / PostScript) . Проверено 4 сентября 2007 . Цитировать журнал требует |journal=( помощь )CS1 maint: несколько имен: список авторов ( ссылка )