Сдвиговая атака () – криптографическая атака, являющаяся, в общем случае, атакой на основе подобранного открытого текста, позволяющая проводить криптоанализ блоковых многораундовых шифров независимо от количества используемых раундов. Предложена Алексом Бирюковым и Дэвидом Вагнером в 1999 году.
История создания Впервые идея создания сдвиговой атаки появилась у Эдны Гроссман и Брайана Такермана в 1977 году. Соответствующий отчет был опубликован совместно с IBM. Гроссман и Такерман смогли показать возможность атаки на достаточно слабый шифр New Data Seal (NDS). Атака использует тот факт, что шифр в каждом раунде только перемешивает один и тот же ключ, используя одинаковую таблицу в каждом раунде. Использование открытых текстов позволяет обойти это и позволяет считать самой ранней версией атаки сдвига.
В 1990 году был предложен дифференциальный криптоанализ, продемонстрировавший уязвимость многораундовых DES-подобных криптосистем. Одним из способов обеспечения их криптостойкости стало увеличение числа используемых раундов, которое повышало вычислительную сложность атаки пропорционально их количеству. Использование данного улучшения для многих алгоритмов шифрования основывалось, в частности, на эмпирическом суждении, что любые, даже довольно слабые шифры, можно сделать криптостойкими, многократно повторяя операции шифрования:
За исключением лишь некоторых вырожденных случаев, алгоритм можно сделать сколь угодно криптостойким путём увеличения числа раундов.
Так, например, некоторые шифры, предложенные в качестве кандидатов на конкурс AES в 1997 г., имели достаточно большое число раундов: RC6(20), MARS(32), SERPENT(32), CAST(48).
Однако в 1999 г. была опубликована статья Алекса Бирюкова и Дэвида Вагнера с описанием сдвиговой атаки, которая опровергла данное предположение. Особенностью данной атаки являлось то, что она не зависела от количества раундов шифра; для её успешности требовались только идентичность раундов и возможность криптоанализа функции шифрования на отдельном раунде. В статье также было описано применение данной атаки к шифру TREYFER и упрощенным версиям шифров DES (2K-DES) и BLOWFISH.
В 2000 году была опубликована вторая статья, в которой были продемонстрированы улучшенные версии сдвиговой атаки – “Sliding with a twist” и “Complementation slide”, позволяющие распространить её на шифры, раунды которых имеют небольшие отличия. Так, с помощью данных улучшений были взломаны некоторые модификации шифра DES, а также упрощенная 20-раундовая версия стандарта шифрования ГОСТ 28147-89 .
Общее описание
В простейшем случае, сдвиговая атака применяется к алгоритмам шифрования, представляющим собой многократное повторение некоторой функции шифрования , на вход которой на каждом раунде подается зашифрованный текст (результат шифрования на предыдущем раунде) и некоторый раундовый ключ , одинаковый для всех раундов. Главными требованиями для успешной реализации данной атаки являются: Идентичность раундов (что гарантируется использованием одной и той же функции и одного и того же ключа на каждом раунде) Возможность простого нахождения ключа , зная текст на входе и текст на выходе некоторого раунда
Алгоритм простейшей атаки Шаг 1. Возьмем некоторый открытый текст на входе и соответствующий ему шифротекст на выходе алгоритма шифрования.
Шаг 2. Возьмем некоторый другой открытый текст и соответствующий ему шифротекст такие, что пара отлична от уже выбранной пары .
Шаг 3. Предположим, что связан с соотношением = , и связан с соотношением , т.е. и являются результатами однораундового шифрования и соответственно. Назовем такую пару «сдвиговой парой» (slid pair). Используя утверждение о том, что ключ шифрования можно легко вычислить, зная текст на входе и текст на выходе некоторого раунда, вычислим ключ на первом раунде шифрования по соотношению , и ключ на последнем раунде шифрования по соотношению .
Шаг 4. Проверим равенство . Т.к. по условию все раундовые ключи одинаковы, то данное равенство должно выполняться, иначе предположение, сделанное на шаге 3 неверно, и необходимо вернуться к шагу 2, исключив проверенную пару из списка возможных кандидатов. Выполнение равенства свидетельствует о том, что ключ потенциально является искомым раундовым ключом.
Шаг 5. Для проверки найденного ключа на ложноположительность следует его подставить в алгоритм шифрования и проверить правильность работы на нескольких различных заведомо известных парах «открытый текст – шифротекст». Несмотря на то, что прохождение неверным ключом данной проверки возможно, в случае хороших шифров вероятность этого крайне мала, а значит проверенный ключ с высокой долей вероятности является искомым раундовым ключом. Таким образом, в случае успешной проверки объявляем ключ искомым, иначе возвращаемся к шагу 2, исключив проверенную пару и ключ из списка возможных кандидатов.
Примечания к алгоритму
Согласно парадоксу дней рождения, две пары и такие, что , найдутся с высокой долей вероятности уже среди пар «открытый текст – шифротекст», где – длина блока шифрования в битах. Из этого следует, что перед проведением атаки можно заранее сгенерировать набор из различных открытых текстов и впоследствии проверять кандидатов только из этого набора. Требование 2, в общем случае, может быть ослаблено. Так, единственным требованием к функции шифрования будет являться уязвимость функции для атак на основе открытых текстов при наличии хотя бы двух заранее известных различных пар «открытый текст – шифротекст». Из этого следует, что для того, чтобы найти потенциальный искомый раундовый ключ, необходимо сначала найти сдвиговую пару . Конкретные алгоритмы поиска сдвиговой пары применительно к разным шифрам, вообще говоря, различны, но в то же время они используют одинаковый принцип. Прежде чем искать сдвиговую пару, генерируется набор из различных открытых текстов, о чем было упомянуто в предыдущем примечании, а затем произвольно выбирается пара , и подбираются ключи, одновременно удовлетворяющие соотношениям и , если такие ключи вообще существуют. Если найден хотя бы один такой ключ, то выбранная пара объявляется сдвиговой, и после этого необходимо только проверить подобранные ключи на ложноположительность. К простейшему случаю легко сводится вариант, когда ключевое расписание () шифра предполагает циклическое повторение некоторого набора ключей. Для этого данный набор можно объявить раундовым ключом и считать последовательность этапов шифрования, использующих этот набор, отдельным раундом. Такие шифры называются шифрами с p-раундовым самоподобием (). Однако при таком объединении раундов сдвиговая атака может стать неэффективной – так, например, в случае объединения раундов размер раундового ключа увеличится соответственно в раз, что может значительно усложнить криптоанализ функции шифрования на отдельном раунде.
Модификации сдвиговой атаки В случае современных блоковых шифров раундовые ключи обычно неодинаковы. Это приводит к тому, что алгоритм, использованный при построении простейшей атаки, в общем виде для таких шифров неприменим и требует некоторых дополнений.
Формулировка проблемы Пусть имеется алгоритм шифрования №1, состоящий из блоков, такой, что на -м раунде используется ключ (будем считать, что всего ключей , ключ потребуется позже), и пусть мы выбрали некоторую пару «открытый текст – шифротекст» . На выходе первого раунда получим текст , где – функция шифрования.
Далее сдвиговая атака предполагает шифрование текста новым блоковым шифром №2, состоящим из блоков со по . Обозначим шифротекст на выходе -го блока как . Нетрудно заметить, что в таком случае на выходе -го блока мы получим уже найденный выше текст , а значит текст и шифротекст связаны соотношением .
Таким образом, мы получили пару , удовлетворяющую соотношениям и , которая является ничем иным, как сдвиговой парой общего вида. Соответственно, в простейшем случае данные соотношения примут вид и .
Предполагая, что некоторый текст связан с соотношением , мы должны получить шифротекст на выходе алгоритма шифрования №2 с текстом на входе, чтобы по соотношениям и подтвердить это или опровергнуть. В случае тривиального ключевого расписания алгоритмы шифрования №1 и №2 идентичны, а значит можно получить, зашифровав текст уже существующим блоковым шифром. В противном случае, алгоритмы шифрования №1 и №2 различны, причем криптоаналитик не имеет возможности построить алгоритм №2, а значит шифротекст получить невозможно.
Случай сети Фейстеля с двухраундовым самоподобием
Сдвиг с дополнением ()
Как было упомянуто в примечаниях к алгоритму атаки, случай криптоанализа шифров с p-раундовым самоподобием можно легко свести к простейшему случаю сдвиговой атаки путём объединения нескольких раундов в один, что эквивалентно сдвигу блоков шифрования на раундов. В случае сети Фейстеля с попеременно чередующимися раундовыми ключами и , т.е. с двухраундовым самоподобием, такой подход может повысить сложность криптоанализа, а значит, сделать сдвиговую атаку неэффективной. Вместо этого было предложено, как и прежде, производить сдвиг всего на один раунд вместо двух, но при этом несколько изменить требования, накладываемые на сдвиговую пару.
В рассмотренном выше описании проблемы было указано, что для поиска сдвиговой пары, в общем случае, необходимо иметь возможность работать с двумя -блоковыми шифрами – исходным, состоящим из блоков с по , и новым, состоящим из блоков со по . Complementation slide же позволяет работать только лишь с исходным блоковым шифром.
Несмотря на то, что дальнейшие рассуждения будут демонстрироваться на примере 4-раундового шифра, они могут быть расширены на любое количество раундов. Для начала рассмотрим, как изменяется открытый текст на различных раундах шифрования. Представим открытый текст в виде , где и – левая и правая части текста соответственно.
Номер раундаЛевая частьПравая часть 1 2 3 4
Обозначим текст на выходе 1 раунда , а шифротекст . Теперь заметим, что для того, чтобы найти шифротекст на выходе 4-раундового блокового шифра с ключевым расписанием , достаточно лишь на каждом раунде исходного шифра внести в правую часть разницу , а затем зашифровать текст полученным шифром (рис.2, правая схема). Для этого на вход исходного шифра подадим текст . Шифротекст обозначим как . Рассмотрим, как изменяется текст на различных раундах шифрования.
Номер раундаЛевая частьПравая часть 1 2 3 4
Отсюда видно, что введенная разница сохраняется на каждом раунде, а значит шифротексты и связаны соотношениями: и , а пары «открытый текст – шифротекст» и соотношениями и .
В случае, если тексты связаны соотношением , говорят, что тексты и имеют сдвиговую разницу () .
Таким образом, для сдвиговой пары получены следующие уравнения:
Как и раньше, в случае -битных текстов для нахождения сдвиговой пары потребуется открытых текстов. Сдвиговая пара теперь должна удовлетворять уравнению (см. рис.2). В случае нахождения потенциальной сдвиговой пары, второе уравнение позволяет найти кандидата , причем если функция достаточно уязвима для криптоанализа, то данные уравнения позволяют найти и потенциальные искомые ключи и . После этого их остается только проверить на ложноположительность.
Сдвиг с поворотом ()
Указанное в формулировке проблемы требование возможности работать с исходным шифром №1, состоящим из блоков с по , и новым шифром №2, состоящим из блоков со по , может быть легко преобразовано с помощью так называемого подхода сдвига с поворотом.
Если исключить последнюю перестановку левой и правой частей текста и изменить порядок следования ключей на противоположный, то расшифровка в сети Фейстеля будет происходить точно так же, как и шифрование. Подход сдвига с поворотом состоит в использовании этого свойства, а именно, он предлагает использовать в качестве шифра №2 алгоритм расшифровки (см. рис.3).
Принципиальных отличий от простейшего алгоритма данный подход не имеет. Как и в простейшем случае, требования, предъявляемые к сдвиговой паре , где . Таким образом, получаем уравнения: