Сдвиговая атака (англ. slide attack) – криптографическая атака, являющаяся, в общем случае, атакой на основе подобранного открытого текста, позволяющая проводить криптоанализ блоковых многораундовых шифров независимо от количества используемых раундов. Предложена Алексом Бирюковым и Дэвидом Вагнером в 1999 году[1].
Впервые идея создания сдвиговой атаки появилась у Эдны Гроссман и Брайана Такермана в 1977 году. Соответствующий отчет был опубликован[2] совместно с IBM. Гроссман и Такерман смогли показать возможность атаки на достаточно слабый шифр New Data Seal (NDS). Атака использует тот факт, что шифр в каждом раунде только перемешивает один и тот же ключ, используя одинаковую таблицу в каждом раунде. Использование открытых текстов позволяет обойти это и позволяет считать самой ранней версией атаки сдвига.
В 1990 году был предложен дифференциальный криптоанализ, продемонстрировавший уязвимость многораундовых DES-подобных криптосистем[3]. Одним из способов обеспечения их криптостойкости стало увеличение числа используемых раундов, которое повышало вычислительную сложность атаки пропорционально их количеству. Использование данного улучшения для многих алгоритмов шифрования основывалось, в частности, на эмпирическом суждении, что любые, даже довольно слабые шифры, можно сделать криптостойкими, многократно повторяя операции шифрования:
За исключением лишь некоторых вырожденных случаев, алгоритм можно сделать сколь угодно криптостойким путём увеличения числа раундов.
Оригинальный текст (англ.)Except in a few degenerate cases, an algorithm can be made arbitrarily secure by adding more rounds.— B. Preneel, V. Rijmen, A. Bosselears: Principles and Performance of Cryptographic Algorithms[4]
Так, например, некоторые шифры, предложенные в качестве кандидатов на конкурс AES в 1997 г., имели достаточно большое число раундов: RC6(20), MARS(32), SERPENT(32), CAST(48)[1].
Однако в 1999 г. была опубликована статья Алекса Бирюкова и Дэвида Вагнера с описанием сдвиговой атаки, которая опровергла данное предположение. Особенностью данной атаки являлось то, что она не зависела от количества раундов шифра; для её успешности требовались только идентичность раундов и возможность криптоанализа функции шифрования на отдельном раунде. В статье также было описано применение данной атаки к шифру TREYFER и упрощенным версиям шифров DES (2K-DES) и BLOWFISH[1].
В 2000 году была опубликована вторая статья, в которой были продемонстрированы улучшенные версии сдвиговой атаки – “Sliding with a twist” и “Complementation slide”, позволяющие распространить её на шифры, раунды которых имеют небольшие отличия. Так, с помощью данных улучшений были взломаны некоторые модификации шифра DES, а также упрощенная 20-раундовая версия стандарта шифрования ГОСТ 28147-89[5][6].
В простейшем случае[7], сдвиговая атака применяется к алгоритмам шифрования, представляющим собой многократное повторение некоторой функции шифрования , на вход которой на каждом раунде подается зашифрованный текст (результат шифрования на предыдущем раунде) и некоторый раундовый ключ , одинаковый для всех раундов. Главными требованиями для успешной реализации данной атаки являются[7]:
В случае современных блоковых шифров раундовые ключи обычно неодинаковы. Это приводит к тому, что алгоритм, использованный при построении простейшей атаки, в общем виде для таких шифров неприменим и требует некоторых дополнений.
Пусть имеется алгоритм шифрования №1, состоящий из блоков, такой, что на -м раунде используется ключ (будем считать, что всего ключей , ключ потребуется позже), и пусть мы выбрали некоторую пару «открытый текст – шифротекст» . На выходе первого раунда мы, очевидно, получим текст , где – функция шифрования.
Далее сдвиговая атака предполагает шифрование текста новым блоковым шифром №2, состоящим из блоков со по . Обозначим шифротекст на выходе -го блока как . Нетрудно заметить, что в таком случае на выходе -го блока мы получим уже найденный выше текст , а значит текст и шифротекст связаны соотношением .
Таким образом, мы получили пару , удовлетворяющую соотношениям и , которая является ничем иным, как сдвиговой парой общего вида. Соответственно, в простейшем случае данные соотношения примут вид и .
Предполагая, что некоторый текст связан с соотношением , мы должны получить шифротекст на выходе алгоритма шифрования №2 с текстом на входе, чтобы по соотношениям и подтвердить это или опровергнуть. В случае тривиального ключевого расписания алгоритмы шифрования №1 и №2 идентичны, а значит можно получить, зашифровав текст уже существующим блоковым шифром. В противном случае, алгоритмы шифрования №1 и №2 различны, причем криптоаналитик не имеет возможности построить алгоритм №2, а значит шифротекст получить невозможно.
Как было упомянуто в примечаниях к алгоритму атаки, случай криптоанализа шифров с p-раундовым самоподобием можно легко свести к простейшему случаю сдвиговой атаки путём объединения нескольких раундов в один, что эквивалентно сдвигу блоков шифрования на раундов. В случае сети Фейстеля с попеременно чередующимися раундовыми ключами и , т.е. с двухраундовым самоподобием, такой подход может повысить сложность криптоанализа, а значит, сделать сдвиговую атаку неэффективной. Вместо этого было предложено, как и прежде, производить сдвиг всего на один раунд вместо двух, но при этом несколько изменить требования, накладываемые на сдвиговую пару.
В рассмотренном выше описании проблемы было указано, что для поиска сдвиговой пары, в общем случае, необходимо иметь возможность работать с двумя -блоковыми шифрами – исходным, состоящим из блоков с по , и новым, состоящим из блоков со по . Complementation slide же позволяет работать только лишь с исходным блоковым шифром.
Несмотря на то, что дальнейшие рассуждения будут демонстрироваться на примере 4-раундового шифра, они могут быть расширены на любое количество раундов. Для начала рассмотрим, как изменяется открытый текст на различных раундах шифрования. Представим открытый текст в виде , где и – левая и правая части текста соответственно.
Номер раунда | Левая часть | Правая часть |
---|---|---|
1 | ||
2 | ||
3 | ||
4 |
Обозначим текст на выходе 1 раунда , а шифротекст . Теперь заметим, что для того, чтобы найти шифротекст на выходе 4-раундового блокового шифра с ключевым расписанием , достаточно лишь на каждом раунде исходного шифра внести в правую часть разницу , а затем зашифровать текст полученным шифром (рис.2, правая схема). Для этого на вход исходного шифра подадим текст . Шифротекст обозначим как . Рассмотрим, как изменяется текст на различных раундах шифрования.
Номер раунда | Левая часть | Правая часть |
---|---|---|
1 | ||
2 | ||
3 |
|
|
4 |
Отсюда видно, что введенная разница сохраняется на каждом раунде, а значит шифротексты и связаны соотношениями: и , а пары «открытый текст – шифротекст» и соотношениями и .
В случае, если тексты связаны соотношением , говорят, что тексты и имеют сдвиговую разницу (англ. slid difference) .
Таким образом, для сдвиговой пары получены следующие уравнения:
Как и раньше, в случае -битных текстов для нахождения сдвиговой пары потребуется открытых текстов. Сдвиговая пара теперь должна удовлетворять уравнению (см. рис.2). В случае нахождения потенциальной сдвиговой пары, второе уравнение позволяет найти кандидата , причем если функция достаточно уязвима к криптоанализу, то данные уравнения позволяют найти и потенциальные искомые ключи и . После этого их остается только проверить на ложноположительность.
Указанное в формулировке проблемы требование возможности работать с исходным шифром №1, состоящим из блоков с по , и новым шифром №2, состоящим из блоков со по , может быть легко преобразовано с помощью так называемого подхода сдвига с поворотом.
Если исключить последнюю перестановку левой и правой частей текста и изменить порядок следования ключей на противоположный, то расшифровка в сети Фейстеля будет происходить точно так же, как и шифрование[1]. Подход сдвига с поворотом состоит в использовании этого свойства, а именно, он предлагает использовать в качестве шифра №2 алгоритм расшифровки (см. рис.3).
Принципиальных отличий от простейшего алгоритма данный подход не имеет. Как и в простейшем случае, требования, предъявляемые к сдвиговой паре , где . Таким образом, получаем уравнения:
и условие, позволяющее проще находить сдвиговые пары:
Как обычно, в случае -битных текстов для поиска сдвиговой пары потребуется открытых текстов. В случае её нахождения уязвимость функции позволяет найти из уравнений ключ .
Количество требуемых текстов на данном шаге можно сократить до . Для этого зашифруем различных текстов вида , и расшифруем различных текстов вида , где и фиксированы и удовлетворяют условию . Таким образом, поскольку теперь мы, фактически, работаем с – битными текстами, согласно парадоксу дней рождения среди этих пар «открытый текст – шифротекст» с большой долей вероятности найдется сдвиговая пара.
Ключ можно найти, применив способ, описанный для общего случая блоковых шифров с p-раундовым самоподобием, а именно, объединив каждые последующие два раунда в один - таким образом мы сводим задачу к простейшем случаю. Несмотря на то, что размер раундового ключа увеличится вдвое, это не приведет к усложнению криптоанализа, поскольку ключ , являющийся половиной нового раундового ключа, уже известен, и нам необходимо найти лишь вторую половину, равную по размеру раундовому ключу в исходной задаче.
Отдельной модификацией можно считать одновременное использование двух описанных выше подходов – Complementation slide и Sliding with a twist, позволяющее распространить сдвиговую атаку на шифры с 4-раундовым самоподобием[5].
От всех рассмотренных до этого случаев отличается задача криптоанализа шифров с неодинаковыми раундами, при решении которой ни одна из рассмотренных модификаций атаки не может быть использована. Для случая подобных шифров была предложена сдвиговая атака с преобразованием (англ. realigning slide attack)[8], продемонстророванная на примере модификаций шифра DES, в частности, на примере полного 16-раундового варианта DES
Сдвигово – линейная атака (англ. slide-linear attack)[9] является примером реализации сдвиговой атаки с применением принципов линейного криптоанализа. Работа данной атаки была показана на шифре 4K-DES.
Также существуют улучшения, позволяющие ускорить реализацию уже существующих модификаций сдвиговой атаки. В частности, одно из таких улучшений, описанное в работе Eli Biham, Orr Dunkelman, Nathan Keller: Improved Slide Attacks[10], позволяет значительно быстрее находить сдвиговые пары, используя при этом циклическую структуру шифров и соответствующие ей перестановки ключей. Работа данной модификация была показана на примере различных вариантов шифра ГОСТ 28147-89 (GOST).
Помимо своего первоначального назначения – атаки блоковых шифров, принципы сдвиговой атаки также нашли применение в области криптоанализа хеш-функций. Подобно случаю блоковых шифров, где сдвиговая атака применялась для нахождения ключевого расписания, она оказалась потенциально применимой для нахождения секретного ключа, используемого для генерации и валидации хеша передаваемого сообщения. В частности, данный подход был продемонстрирован на примере генерации имитовставки (MAC).
Сдвиговая атака также оказалась полезной не только в случае криптографических хеш-функций, принимающих в качестве параметра значение некоторого секретного ключа, но и в случае хеш-функций, вырабатывающих хеш только на основе сообщения. Анализ таких функций на основе сдвиговой атаки позволяет с высокой долей вероятности выявлять некоторые сдвиговые свойства и, как следствие, определенные закономерности в работе алгоритмов хеширования.
Так как при проведении сдвиговой атаки используются уязвимости ключевого расписания, то одной из мер является, очевидно, его усложнение. В частности, необходимо по возможности избегать циклических повторений в ключевом расписании или хотя бы использовать достаточно большой период повторения. В случае же небольшого количества ключей, вместо простого периодического повторения следует использовать некоторый случайный порядок их следования.
Помимо слабости ключевого расписания сдвиговая атака также использует одинаковость раундов. Одним из способов избежать этого является использование в качестве параметра функции шифрования на отдельных раундах некоторых различных раундовых констант – это позволяет внести различия в работу отдельных блоков шифрования без значительного усложнения алгоритма шифрования в целом.
Также эффективность сдвиговой атаки можно значительно снизить, повысив криптостойкость раундовой функции шифрования. Так, её устойчивость к атакам на основе открытых текстов значительно затруднит нахождение раундового ключа даже при наличии сдвиговой пары.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .