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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отдельной модификацией можно считать одновременное использование двух описанных выше подходов – 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).

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

• Spectr-H64[11]
• KeeLoq[12]
• 4K-DES[9]

• MD4 [14]
• MD5 [15]
• SHA-1 [15]
• Grindahl-256
• Grindahl-512
• RadioGatun
• MAC
• HMAC