Сдвиговая атака

Сдвиговая атака (англ. slide attack) – криптографическая атака, являющаяся, в общем случае, атакой на основе подобранного открытого текста, позволяющая проводить криптоанализ блоковых многораундовых шифров независимо от количества используемых раундов. Предложена Алексом Бирюковым и Дэвидом Вагнером в 1999 году.

История создания

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

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

За исключением лишь некоторых вырожденных случаев, алгоритм можно сделать сколь угодно криптостойким путём увеличения числа раундов.

Оригинальный текст (англ.)

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

Так, например, некоторые шифры, предложенные в качестве кандидатов на конкурс 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 Сдвиговая атака

В простейшем случае, сдвиговая атака применяется к алгоритмам шифрования, представляющим собой многократное повторение некоторой функции шифрования $F$, на вход которой на каждом раунде подается зашифрованный текст (результат шифрования на предыдущем раунде) и некоторый раундовый ключ $K$, одинаковый для всех раундов. Главными требованиями для успешной реализации данной атаки являются:

1. Идентичность раундов (что гарантируется использованием одной и той же функции $F$ и одного и того же ключа $K$ на каждом раунде)
2. Возможность простого нахождения ключа $K$, зная текст на входе $P$ и текст на выходе $F(P)$ некоторого раунда

Алгоритм простейшей атаки

Шаг 1. Возьмем некоторый открытый текст $M$ на входе и соответствующий ему шифротекст $C$ на выходе алгоритма шифрования.

Шаг 2. Возьмем некоторый другой открытый текст $M'$ и соответствующий ему шифротекст $C'$ такие, что пара $(M',C')$ отлична от уже выбранной пары $(M,C)$.

Шаг 3. Предположим, что $M'$ связан с $M$ соотношением $M'$ = $F(M)$, и $C'$ связан с $C$ соотношением $C'=F(C)$, т.е. $M'$ и $C'$ являются результатами однораундового шифрования $M$ и $C$ соответственно. Назовем такую пару $(M,C),(M',C')$ «сдвиговой парой» (slid pair). Используя утверждение о том, что ключ шифрования можно легко вычислить, зная текст на входе $P$ и текст на выходе $F(P)$ некоторого раунда, вычислим ключ на первом раунде шифрования $K_{first}$ по соотношению $M'=F(M)$, и ключ на последнем раунде шифрования $K_{last}$ по соотношению $C'=F(C)$.

Шаг 4. Проверим равенство $K_{first}=K_{last}$. Т.к. по условию все раундовые ключи одинаковы, то данное равенство должно выполняться, иначе предположение, сделанное на шаге 3 неверно, и необходимо вернуться к шагу 2, исключив проверенную пару $(M',C')$ из списка возможных кандидатов. Выполнение равенства $K_{first}=K_{last}$ свидетельствует о том, что ключ $K=K_{first}=K_{last}$ потенциально является искомым раундовым ключом.

Шаг 5. Для проверки найденного ключа $K$ на ложноположительность следует его подставить в алгоритм шифрования и проверить правильность работы на нескольких различных заведомо известных парах «открытый текст – шифротекст». Несмотря на то, что прохождение неверным ключом данной проверки возможно, в случае хороших шифров вероятность этого крайне мала, а значит проверенный ключ с высокой долей вероятности является искомым раундовым ключом. Таким образом, в случае успешной проверки объявляем ключ $K$ искомым, иначе возвращаемся к шагу 2, исключив проверенную пару $(M',C')$ и ключ $K$ из списка возможных кандидатов.

Примечания к алгоритму

• Согласно парадоксу дней рождения, две пары $(M,C)$ и $(M',C')$ такие, что $K_{first}=K_{last}$, найдутся с высокой долей вероятности уже среди $2^{n/2}$ пар «открытый текст – шифротекст», где $n$ – длина блока шифрования в битах. Из этого следует, что перед проведением атаки можно заранее сгенерировать набор из $2^{n/2}$ различных открытых текстов и впоследствии проверять кандидатов только из этого набора.
• Требование 2, в общем случае, может быть ослаблено. Так, единственным требованием к функции шифрования $F$ будет являться уязвимость функции $F$ для атак на основе открытых текстов при наличии хотя бы двух заранее известных различных пар «открытый текст – шифротекст». Из этого следует, что для того, чтобы найти потенциальный искомый раундовый ключ, необходимо сначала найти сдвиговую пару $(M,C),(M',C')$. Конкретные алгоритмы поиска сдвиговой пары применительно к разным шифрам, вообще говоря, различны, но в то же время они используют одинаковый принцип. Прежде чем искать сдвиговую пару, генерируется набор из $2^{n/2}$ различных открытых текстов, о чем было упомянуто в предыдущем примечании, а затем произвольно выбирается пара $(M,C),(M',C')$, и подбираются ключи, одновременно удовлетворяющие соотношениям $M'=F(M)$ и $C'=F(C)$, если такие ключи вообще существуют. Если найден хотя бы один такой ключ, то выбранная пара $(M,C),(M',C')$ объявляется сдвиговой, и после этого необходимо только проверить подобранные ключи на ложноположительность.
• К простейшему случаю легко сводится вариант, когда ключевое расписание (англ. key schedule) шифра предполагает циклическое повторение некоторого набора ключей. Для этого данный набор можно объявить раундовым ключом и считать последовательность этапов шифрования, использующих этот набор, отдельным раундом. Такие шифры называются шифрами с p-раундовым самоподобием (англ. p-round self-similarity ciphers). Однако при таком объединении раундов сдвиговая атака может стать неэффективной – так, например, в случае объединения $p$ раундов размер раундового ключа увеличится соответственно в $p$ раз, что может значительно усложнить криптоанализ функции шифрования на отдельном раунде.

Модификации сдвиговой атаки

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

Формулировка проблемы

Пусть имеется алгоритм шифрования №1, состоящий из $N$ блоков, такой, что на $i$-м раунде используется ключ $K_{i}$ (будем считать, что всего ключей $N+1$, ключ $K_{N+1}$ потребуется позже), и пусть мы выбрали некоторую пару «открытый текст – шифротекст» $(M,C)$. На выходе первого раунда получим текст $M_{1}=F(K_{1},M)$, где $F$ – функция шифрования.

Далее сдвиговая атака предполагает шифрование текста $M_{1}\equiv M'$ новым блоковым шифром №2, состоящим из блоков со $2$ по $N+1$. Обозначим шифротекст на выходе $N+1$-го блока как $C'$. Нетрудно заметить, что в таком случае на выходе $N$-го блока мы получим уже найденный выше текст $C$, а значит текст $C$ и шифротекст $C'$ связаны соотношением $C'=F(K_{N+1},C)$.

Таким образом, мы получили пару $(M,C),(M',C')$, удовлетворяющую соотношениям $M'=F(K_{1},M)$ и $C'=F(K_{N+1},C)$, которая является ничем иным, как сдвиговой парой общего вида. Соответственно, в простейшем случае данные соотношения примут вид $M'=F(M)$ и $C'=F(C)$.

Предполагая, что некоторый текст $M'$ связан с $M$ соотношением $M'=F(K_{1},M)$, мы должны получить шифротекст $C'$ на выходе алгоритма шифрования №2 с текстом $M'$ на входе, чтобы по соотношениям $M'=F(K_{1},M)$ и $C'=F(K_{N+1},C)$ подтвердить это или опровергнуть. В случае тривиального ключевого расписания алгоритмы шифрования №1 и №2 идентичны, а значит $C'$ можно получить, зашифровав текст $M'$ уже существующим блоковым шифром. В противном случае, алгоритмы шифрования №1 и №2 различны, причем криптоаналитик не имеет возможности построить алгоритм №2, а значит шифротекст $C'$ получить невозможно.

Случай сети Фейстеля с двухраундовым самоподобием

Сдвиг с дополнением (англ. Complementation slide)

Рис.2 Сдвиг с дополнением (complementation slide)

Как было упомянуто в примечаниях к алгоритму атаки, случай криптоанализа шифров с p-раундовым самоподобием можно легко свести к простейшему случаю сдвиговой атаки путём объединения нескольких раундов в один, что эквивалентно сдвигу блоков шифрования на $p$ раундов. В случае сети Фейстеля с попеременно чередующимися раундовыми ключами $K_{0}$ и $K_{1}$, т.е. с двухраундовым самоподобием, такой подход может повысить сложность криптоанализа, а значит, сделать сдвиговую атаку неэффективной. Вместо этого было предложено, как и прежде, производить сдвиг всего на один раунд вместо двух, но при этом несколько изменить требования, накладываемые на сдвиговую пару.

В рассмотренном выше описании проблемы было указано, что для поиска сдвиговой пары, в общем случае, необходимо иметь возможность работать с двумя $N$-блоковыми шифрами – исходным, состоящим из блоков с $1$ по $N$, и новым, состоящим из блоков со $2$ по $N+1$. Complementation slide же позволяет работать только лишь с исходным блоковым шифром.

Несмотря на то, что дальнейшие рассуждения будут демонстрироваться на примере 4-раундового шифра, они могут быть расширены на любое количество раундов. Для начала рассмотрим, как изменяется открытый текст на различных раундах шифрования. Представим открытый текст в виде $<L,R>$, где $L$ и $R$ – левая и правая части текста соответственно.

Номер раунда	Левая часть	Правая часть
1	$L$	$R$
2	$R$	$L\oplus f(R\oplus K_{0})$
3	$L\oplus f(R\oplus K_{0})$	$R\oplus f(L\oplus f(R\oplus K_{0})\oplus K_{1})$
4	$R\oplus f(L\oplus f(R\oplus K_{0})\oplus K_{1})$	$L\oplus f(R\oplus K_{0})\oplus f(R\oplus f(L\oplus f(R\oplus K_{0})\oplus K_{1})\oplus K_{0})$

Обозначим текст на выходе 1 раунда $<L_{1},R_{1}>$, а шифротекст $<M,N>$. Теперь заметим, что для того, чтобы найти шифротекст на выходе 4-раундового блокового шифра с ключевым расписанием $(K_{1},K_{0},K_{1},K_{0})$, достаточно лишь на каждом раунде исходного шифра внести в правую часть разницу $\Delta =K_{0}\oplus K_{1}$, а затем зашифровать текст $<L_{1},R_{1}>$ полученным шифром (рис.2, правая схема). Для этого на вход исходного шифра подадим текст $<L',R'>=<L_{1}\oplus \Delta ,R_{1}\oplus \Delta >=<L_{1},R_{1}>\oplus <\Delta ,\Delta >$. Шифротекст обозначим как $<M',N'>$. Рассмотрим, как изменяется текст $<L',R'>$ на различных раундах шифрования.

Номер раунда	Левая часть	Правая часть
1	$L'=R\oplus \Delta$	$R'=L\oplus f(R\oplus K_{0})\oplus \Delta$
2	$L\oplus f(R\oplus K_{0})\oplus \Delta$	$R\oplus f(L\oplus f(R\oplus K_{0})\oplus K_{1})\oplus \Delta$
3	$R\oplus f(L\oplus f(R\oplus K_{0})\oplus K_{1})\oplus \Delta =$ $=M\oplus \Delta$	$L\oplus f(R\oplus K_{0})\oplus f(R\oplus f(L\oplus f(R\oplus K_{0})\oplus K_{1})\oplus K_{0})\oplus \Delta =$ $=N\oplus \Delta$
4	$N\oplus \Delta$	$M\oplus f(N\oplus K_{0})\oplus \Delta$

Отсюда видно, что введенная разница $<\Delta ,\Delta >$ сохраняется на каждом раунде, а значит шифротексты $<M,N>$ и $<M',N'>$ связаны соотношениями: $M'=N\oplus \Delta$ и $N'=M\oplus f(N\oplus K_{0})\oplus \Delta$, а пары «открытый текст – шифротекст» $(P,C)=(<L,R>,<M,N>)$ и $(P',C')=(<L',R'>,<M',N'>)$ соотношениями $P'=F(P)\oplus \Delta$ и $C'=F(C)\oplus \Delta$.

В случае, если тексты $P,P'$ связаны соотношением $F(P)\oplus P'=d$, говорят, что тексты $P$ и $P'$ имеют сдвиговую разницу (англ. slid difference) $d$.

Таким образом, для сдвиговой пары $(P,C),(P',C')$ получены следующие уравнения:

$<L',R'>=<R,L\oplus f(K_{0}\oplus R)>\oplus <\Delta ,\Delta >$
$<M',N'>=<N,M\oplus f(K_{1}\oplus N\oplus \Delta )>\oplus <\Delta ,\Delta >$

Как и раньше, в случае $n$-битных текстов для нахождения сдвиговой пары потребуется $2^{n/2}$ открытых текстов. Сдвиговая пара теперь должна удовлетворять уравнению $L'\oplus M'=R\oplus N$ (см. рис.2). В случае нахождения потенциальной сдвиговой пары, второе уравнение позволяет найти кандидата $\Delta$, причем если функция $f$ достаточно уязвима для криптоанализа, то данные уравнения позволяют найти и потенциальные искомые ключи $K_{0}$ и $K_{1}$. После этого их остается только проверить на ложноположительность.

Сдвиг с поворотом (англ. Sliding with a twist)

Рис.3 Сдвиг с поворотом (Sliding with a twist)

Указанное в формулировке проблемы требование возможности работать с исходным шифром №1, состоящим из блоков с $1$ по $N$, и новым шифром №2, состоящим из блоков со $2$ по $N+1$, может быть легко преобразовано с помощью так называемого подхода сдвига с поворотом.

Если исключить последнюю перестановку левой и правой частей текста и изменить порядок следования ключей на противоположный, то расшифровка в сети Фейстеля будет происходить точно так же, как и шифрование. Подход сдвига с поворотом состоит в использовании этого свойства, а именно, он предлагает использовать в качестве шифра №2 алгоритм расшифровки (см. рис.3).

Принципиальных отличий от простейшего алгоритма данный подход не имеет. Как и в простейшем случае, требования, предъявляемые к сдвиговой паре $(P,C),(P',C'):P'=F(K_{0},P),C'=F(K_{0},C)$, где $(P,C)=(<L,R>,<M,N>),(P',C')=(<M',N'>,<L',R'>)$. Таким образом, получаем уравнения:

$<M',N'>=<L\oplus f(K_{0}\oplus R),R>$
$<L',R'>=<M\oplus f(K_{0}\oplus N),N>$

и условие, позволяющее проще находить сдвиговые пары: $N'=R,R'=N$

Как обычно, в случае $n$-битных текстов для поиска сдвиговой пары потребуется $2^{n/2}$ открытых текстов. В случае её нахождения уязвимость функции $f$ позволяет найти из уравнений ключ $K_{0}$.

Количество требуемых текстов на данном шаге можно сократить до $2^{n/4+1}$. Для этого зашифруем $2^{n/4}$ различных текстов вида $(L_{i},R)$, и расшифруем $2^{n/4}$ различных текстов вида $(M'_{j},N')$, где $R$ и $N'$ фиксированы и удовлетворяют условию $R=N'$. Таким образом, поскольку теперь мы, фактически, работаем с $n/2$ – битными текстами, согласно парадоксу дней рождения среди этих пар «открытый текст – шифротекст» с большой долей вероятности найдется сдвиговая пара.

Ключ $K_{1}$ можно найти, применив способ, описанный для общего случая блоковых шифров с p-раундовым самоподобием, а именно, объединив каждые последующие два раунда в один - таким образом мы сводим задачу к простейшем случаю. Несмотря на то, что размер раундового ключа увеличится вдвое, это не приведет к усложнению криптоанализа, поскольку ключ $K_{0}$, являющийся половиной нового раундового ключа, уже известен, и нам необходимо найти лишь вторую половину, равную по размеру раундовому ключу в исходной задаче.

Другие модификации

Отдельной модификацией можно считать одновременное использование двух описанных выше подходов – Complementation slide и Sliding with a twist, позволяющее распространить сдвиговую атаку на шифры с 4-раундовым самоподобием.

От всех рассмотренных до этого случаев отличается задача криптоанализа шифров с неодинаковыми раундами, при решении которой ни одна из рассмотренных модификаций атаки не может быть использована. Для случая подобных шифров была предложена сдвиговая атака с преобразованием (англ. realigning slide attack), продемонстророванная на примере модификаций шифра DES, в частности, на примере полного 16-раундового варианта DES

Сдвигово – линейная атака (англ. slide-linear attack) является примером реализации сдвиговой атаки с применением принципов линейного криптоанализа. Работа данной атаки была показана на шифре 4K-DES.

Также существуют улучшения, позволяющие ускорить реализацию уже существующих модификаций сдвиговой атаки. В частности, одно из таких улучшений, описанное в работе Eli Biham, Orr Dunkelman, Nathan Keller: Improved Slide Attacks, позволяет значительно быстрее находить сдвиговые пары, используя при этом циклическую структуру шифров и соответствующие ей перестановки ключей. Работа данной модификация была показана на примере различных вариантов шифра ГОСТ 28147-89 (GOST).

Алгоритмы шифрования, уязвимые для сдвиговой атаки и её модификаций

Описанные в оригинальных статьях:

• 2K-DES (DES with alternating keys)
• DES with Brown-seberry Key Schedule
• DESX
• GOST
• MISTY
• TREYFER
• WAKE-ROFB
• Blowfish variants

Описанные в других источниках

• Spectr-H64
• KeeLoq
• 4K-DES

Сдвиговые атаки класса хеш-функций

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

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

Хеш-функции, уязвимые для сдвиговой атаки:

• MD4
• MD5
• SHA-1
• Grindahl-256
• Grindahl-512
• RadioGatun
• MAC
• HMAC

Способы повышения криптостойкости к модификациям сдвиговых атак

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

Помимо слабости ключевого расписания сдвиговая атака также использует одинаковость раундов. Одним из способов избежать этого является использование в качестве параметра функции шифрования на отдельных раундах некоторых различных раундовых констант – это позволяет внести различия в работу отдельных блоков шифрования без значительного усложнения алгоритма шифрования в целом.

Также эффективность сдвиговой атаки можно значительно снизить, повысив криптостойкость раундовой функции шифрования. Так, её устойчивость к атакам на основе открытых текстов значительно затруднит нахождение раундового ключа даже при наличии сдвиговой пары.