Атака на связанных ключах

Ата́ка на свя́занных ключа́х (англ. Related-key attack) — вид криптографической атаки, в которой криптоаналитик выбирает связь между парой ключей, но сами ключи остаются ему неизвестны. Данные шифруются обоими ключами. В варианте с известным открытым текстом криптоаналитику известны открытый текст и шифротекст данных, шифрованных двумя ключами. Цель злоумышленника состоит в том, чтобы найти фактические секретные ключи. Предполагается, что атакующий знает или выбирает некоторое математическое отношение, связывающее между собой ключи. Соотношение имеет вид $K$_$B$ $=$ $F$($K$_$A$) , где $F$ — функция, выбранная атакующим, $K$_$A$ и $K$_$B$ — связанные ключи. К каждому шифрованию соотношение между ключами подбирается индивидуально. Существует много способов найти это соотношение правильно. По сравнению с другими атаками, в которых атакующий может манипулировать только открытым текстом и/или зашифрованным текстом, выбор соотношения между секретными ключами даёт дополнительную степень свободы для злоумышленника. Недостатком этой свободы является то, что такие нападения могут быть более трудными на практике. Тем не менее, проектировщики обычно пытаются создать «идеальные» примитивы, которые могут быть автоматически использованы без дальнейшего анализа в максимально широком наборе протоколов или режимов работы. Таким образом, сопротивление таким атакам является важной целью проектирования блочных шифров, и фактически это была одна из заявленных целей проектирования алгоритма Rijndael.

Расширение ключа

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

Назначение процедуры расширения ключа

Получается, что алгоритм шифрования можно логически разделить на два субалгоритма: собственно шифрующие преобразования и процедура расширения ключа. К процедуре расширения ключа предъявляется ряд требований:

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

Классическая атака на связанных ключах

Данный тип атаки впервые был предложен израильским учёным Эли Бихамом в 1992 году в статье New Types of Cryptanalytic Attacks Using Related Keys. Атака на связанных ключах, описанная им, напоминает сдвиговую атаку. Сдвиговая атака (англ. slide attack) — криптографическая атака, являющаяся, в общем случае, атакой на основе подобранного открытого текста, позволяющая проводить криптоанализ блоковых многораундовых шифров независимо от количества используемых раундов. Предложена Алексом Бирюковым и Дэвидом Вагнером в 1999 году. Сдвиговая атака использует два открытых текста $P$ и $P'$, удовлетворяющих следующему соотношению: $P'=F(P,k_{1})$, где $F()$ — функция раунда, а $k_{1}$ — подключ 1-го раунда. В атаке на связанных ключах применяется похожее соотношение между ключами. Допустим, что искомый ключ шифрования K после модификации его процедурой расширения ключа $Ex(K)$ даёт последовательность подключей: $Ex(K)=\left\{{k_{1},k_{2},\ldots ,k_{r-1},k_{r}}\right\}$, где $r$ — количество раундов алгоритма шифрования. Предположим, что существует ключ $K'$, расширение которого даёт следующую последовательность: $Ex(K')=\left\{{k_{2},k_{3},\ldots ,k_{r},k_{1}}\right\}$, то есть последовательность подключей, создаваемая на основе ключа $K'$, циклически сдвинута относительно последовательности искомого ключа $K$ на 1 раунд.

Суть атаки

1. Предположим, что криптоаналитику известно $2^{\frac {n}{2}}$ пар $\left({P,C}\right)$ открытых текстов и соответствующих им шифротекстов (зашифрованных при помощи ключа $K$), где $n$ — размер блока шифруемых данных, представленного в битах.
2. Кроме того, криптоаналитику известно $2^{\frac {n}{2}}$ пар текстов $\left({P',C'}\right)$, зашифрованных с использованием ключа $K'$, связанного с $K$ приведённым выше соотношением.
3. Для каждого соотношения текстов $\left({P,C}\right)$ и $\left({P',C'}\right)$ криптоаналитику необходимо найти решения системы уравнений:

${\begin{cases}F(P,k^{*})=P'\\F(C,k^{*})=C'\end{cases}}$

Какой из $2^{\frac {n}{2}}$ текстов $P$ соответствует каждому тексту из $P$, криптоаналитик не знает заранее. Но, вероятность того, что два случайно выбранных текста будут удовлетворять требуемому соотношению, равна ${\frac {1}{2^{n}}}$.Тогда требуемая пара $\left({P,P'}\right)$ должна быть найдена после анализа не более чем $2^{{\frac {n}{2}}+1}$ текстов, в соответствии с парадоксом дней рождения. Условие $2^{{\frac {n}{2}}+1}$ текстов не является строгим, оно является оценочным и будет выполняться лишь в среднем.

Ключ $k^{*}$, найденный из приведённой выше системы, и есть искомый подключ $k_{1}$. В зависимости от операции формирования ключа, знание $k_{1}$ может дать криптоаналитику много возможностей для осуществления несанкционированного доступа к информации. Например, формирование ключа алгоритма LOKI89 построено таким образом, что $k_{1}$ представляет собой просто левую 32-битную часть ключа $K$. Поскольку в данном алгоритме используется 64-битный ключ, то после вычисления $k_{1}$ для нахождения $K$ достаточно всего лишь перебора $2^{32}$ вариантов.

Функция раунда $F()$ алгоритма, на который производится атака, должна быть достаточно слабой для вычисления $k^{*}$, что применительно к большинству современных алгоритмов шифрования. Кроме того, трудоёмкость атаки может быть значительно снижена по отношению к описанному выше случаю, все зависит от выбранного алгоритма шифрования открытого текста. К примеру, вычисления упрощаются для алгоритмов, основанных на сбалансированной сети Фейстеля.

Атаки на различные алгоритмы шифрования

Атака на DES

Основная статья: DES

DES (англ. data encryption standard) — алгоритм для симметричного шифрования, разработанный фирмой IBM и утверждённый правительством США в 1977 году как официальный стандарт (FIPS 46-3). Размер блока для DES равен 64 бита. В основе алгоритма лежит сеть Фейстеля с 16 циклами (раундами) и ключом, имеющим длину 56 бит. Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований.

Алгоритм шифрования DES устойчив к такой атаке. В процессе шифрования для основной функции шифрования, требуется вычислить шестнадцать 48-битовых ключа, которые являются результатом преобразования 56-битового исходного ключа (подробнее в разделе «Генерирование ключей $k_{i}$»). Количество сдвигов в алгоритме вычисления ключей $k_{i}$ не совпадает во всех раундах. Обычно регистры ключей смещаются на два бита после каждого раунда и только на один бит после первого, девятого и пятнадцатого раундов. Однако если изменить эту схему переключений, установить сдвиг одинаковым во всех раундах, то результирующая криптосистема становится уязвимой для атаки со связанными ключами. Наименее безопасным к атаке является модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа.

Изменение схемы переключений

Таблица описывает количество сдвигов перед каждым раундом генерирования ключа и вариант с изменённым количеством сдвигов, который уязвим для атаки на связанных ключах. Для того чтобы взломать такой вариант алгоритма криптоаналитику потребуется только 2¹⁷ выбранных открытых текстов для выбранных ключей или 2³³ известных открытых текстов для выбранных ключей. Для взлома модифицированного DES необходимо выполнить 1.43*2⁵³ операций, что является небольшим выигрышем, по сравнению с полным перебором, где количество операций равно 2⁵⁶. В 1998 году с помощью суперкомпьютера EFF DES cracker стоимостью 250 тыс. долл., DES был взломан менее чем за три дня. EFF DES cracker для взлома использовал полный перебор. Огромные требования к времени и объёму данных, не позволяют реализовать атаку на связных ключах, без помощи дорогостоящего оборудования. Но, тем не менее, атака интересна по двум причинам:

• Это первая попытка криптоаналитической атаки на алгоритм генерации подключей в DES.
• Сложность не зависит от количества этапов криптографического алгоритма, он одинаково эффективен против DES с 16, 32 или 1000 этапами.

Атака на AES

Основная статья: Advanced Encryption Standard

Advanced Encryption Standard (AES), также известный как Rijndael (произносится [rɛindaːl] (Рэндал)) — симметричный алгоритм блочного шифрования (размер блока 128 бит, ключ 128/192/256 бит), принятый в качестве стандарта шифрования правительством США по результатам конкурса AES. Этот алгоритм хорошо проанализирован и сейчас широко используется, как это было с его предшественником DES. AES представлен в трёх вариантах, каждый из которых обеспечивает тот или иной уровень безопасности, зависящий от длины секретного ключа. Ключ может иметь длину 128, 192 и 256 бит. С 2001 года, после выбора AES, как криптографического стандарта, прогресс в его криптоанализе крайне низок. Лучшие результаты были получены в процессе проведения атак, основанных на связанных ключах в 2009 году. Алекс Бирюков вместе с Дмитрием Ховратовичем предоставили первую криптоаналитическую атаку на основе связанных ключей на полнораундовые AES-192 и AES-256, разработанный метод работает быстрее, чем полный перебор.

Разработанная атака на AES-256 подходит для всех типов ключей и имеет сложность порядка 2⁹⁶.Также была представлена атака на AES-192. В обеих атаках осуществляется минимизирование числа активных S-блоков алгоритма создания ключей. Данная операция применяется с помощью атаки бумерангом. Дифференциальные характеристики для бумеранга были установлены путём поиска локальных коллизий в шифре. Основная особенность AES-256, которая являются определяющей для рассматриваемых атак, заключается в том, что алгоритм шифрования имеет 14 раундов и 256-битный ключ, который удваивается во внутреннем состоянии. Поэтому, алгоритм выработки ключей состоит только из 7 раундов, а каждый раунд в свою очередь имеет 8 S-блоков. Аналогично для AES-192 за счёт того, что ключ становится в полтора раза больше во внутреннем состоянии, алгоритм выработки ключа состоит лишь из 8, а не 12 раундов. Каждый раунд имеет только 4 S-блока.

Лучшие атаки на AES-192 и AES-256

Атака на AES-256

Необходимо выполнить следующие шаги 2^25,5 раз:

1. Подготовить структуру открытых текстов, как указано ниже.
2. Зашифровать его на ключах $K_{A}$ и $K_{B}$ и сохранить полученные множества $S_{A}$ и $S_{B}$.
3. Необходимо осуществить операцию $xor~\Delta _{C}$ для всех шифротекстов в $S_{A}$ и расшифровать изменённые шифротексты ключом $K_{C}$ . $S_{C}$ — новое множество открытых текстов.
4. Аналогично для $S_{B}$ и ключа $K_{D}$. $S_{D}$ — новое множество открытых текстов.
5. Сравнение всех пар открытых текстов из $S_{C}$ и $S_{D}$ с длиной 56 бит.
6. Для всех остальных выполнить проверку на различие значения вероятности $p_{i,0}$ при $i>1$.Если оно равно с обеих сторон 16-битного фильтра, то для пар ключей или ещё их называют квартетом $\left({K_{A},K_{B}}\right)$ и $\left({K_{C},K_{D}}\right)$, при $\nabla k_{i,7}^{0}=0$, $\Delta k_{i,0}^{0}$ тоже будут равны с обеих сторон.
7. Необходимо отобрать квартеты, различия которых не могут быть затронуты активными S-блоками в первом раунде и активными S-блоками в алгоритме выработки ключа.
8. Отфильтровывая неправильные квартеты, частично восстановим значение ключа.

Каждая структура имеет всевозможные варианты значений нулевого столбца, нулевой строки и константное значение в других байтах. Из 2⁷² текстов в каждой структуре можно сравнить 2¹⁴⁴ пар. Из этих пар 2^(144−8*9) = 2⁷² пройдут первый раунд. Таким образом, получаем 1 нужный квартет из 2^(96-72) = 2²⁴ структур и 3 нужных квартета из 2^25,5 структур. Вычислим количество квартетов прошедших 6 шагов, их будет около 2^(144-56-16) = 2⁷² пар. Следующим шагом будет применение 16-битного фильтра, так получим общее количество возможных квартетов 2^{(72+25,5−6)} = 2^91,5.

Атака на AES-192

Алгоритм создания ключа в данном случае имеет лучшую диффузию. Поэтому атака бумерангом использует два подследа по 6 раундов в каждом. Проанализируем 2⁷³ структур с 2⁴⁸ текстами по следующей схеме:

1. Сравнить все пары возможных открытых текстов для пар ключей $\left({K_{A},K_{B}}\right)$ и $\left({K_{C},K_{D}}\right)$.
2. Сравнить и сохранить все квартеты для шифротекстов.
3. Для каждого предполагаемого байта ключа : $k^{0,3}$, $k^{2,3}$ и $k^{0,5}$ в $K_{A}$; $k^{0,5}$ в $K_{A}$ и $K_{B}$:
   1. вычислить значения для этих байтов во всех ключах из разностного следа. Получить различия ключей в $\Delta K^{0}$ и $\nabla K^{8}$;
   2. выбрать квартеты, противоречащие$\nabla K^{8}$;
   3. подготовить счётчики для невычисленных байтов ключа, которые соответствуют активным S-блокам в первых двух и последнем: $K^{0,0}$, $k^{0,1}$, $k^{1,2}$, $k^{3,0}$ — в ключах $K_{A}$ и $K_{C}$, $k^{0,0}$, $k^{0,1}$, $k^{0,2}$, $k^{0,3}$ — в ключах $K_{A}$ и $K_{B}$, всего 16 байт;
   4. для каждого квартета установить возможные значения для их неизвестных байтов и увеличить счётчики;
   5. создать группу из 16 ключевых байтов с максимальными номерами;
   6. попробовать все возможные значения пока неизвестных 9 байтов ключа в $K^{0}$ и проверить этот ключ на правильность. При неудачном раскладе перейти к первому шагу.

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

Практическое применение

Описанные атаки с использованием связанных ключей не выглядят практичными. Во многих разработках они не сильно выигрывают по сравнению с полным перебором, кроме того, требуют большого количества предположений. Данная атака довольно долго считалась достаточно мощной, но сугубо теоретической. Однако сейчас такие эксперты как John Kelsey и Bruce Schneier считают, что атаки на связанных ключах могут иметь практическое применение. Некоторые реализации криптоалгоритмов или сетевых протоколов (например, протоколов аутентификации или обмена ключами) уже сейчас могут быть подвержены атаке с использованием связанных ключей. Одно из потенциальных применений — это анализ хеш-функций. Теоретически атаки на связанных ключах могут быть опасны в случае использования алгоритмов симметричного шифрования для построения хеш-функций. В настоящее время неизвестно конкретного приложения к хеш-функциям, но разработчики хеш-функции должны учитывать при проектировании, что существует такая слабость. В любом случае, категорически рекомендуется принимать в расчёт криптоанализ на связанных ключах при разработке алгоритмов шифрования и их реализации. В работе отмечается, что основное условие для атаки выглядит достаточно странно: криптоаналитик может писать ключ то есть модифицировать искомый неизвестный ключ требуемым образом, но не может его читать. Тем не менее, некоторые реализации криптоалгоритмов или сетевых протоколов могут быть атакованы с использованием связанных ключей. В любом случае, категорически рекомендуется принимать в расчёт криптоанализ на связанных ключах при разработке алгоритмов шифрования и их реализации. Так же отмечается, что атаки на связанных ключах могут быть весьма опасны в случае использования алгоритмов симметричного шифрования для построения функций хеширования.

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

• нестойкость к атакам класса «встреча посередине» поскольку данные атаки эксплуатируют тот факт, что первая часть шифрующих преобразований атакуемого алгоритма использует иной набор битов ключа. нежели вторая часть.
• слабые ключи — ключи, зашифровывание с использованием которых эквивалентно расшифровыванию, или обладающие другими характеристиками, существенно упрощающими вскрытие.
• эквивалентные ключи — различные ключи, но дающие один и тот же результат зашифровывания на неком подмножестве открытых текстов.
• классы ключей — возникают, когда криптоаналитик может относительно легко определить подмножество ключевого множества, которому принадлежит искомый ключ, и, соответственно, уменьшить таким образом область полного перебора ключа.

См. также

• Атака на основе подобранного ключа

Литература

• Шнаер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — Триумф, 2002. — 816 с. — ISBN 5-89392-055-4, 0-471-11709-9.
• Eli Biham. New types of cryptanalytic attacks using related keys (англ.) // Springer-Verlag : журнал. — 1994. — No. 4. — P. 229—246. — ISSN 1432-1378. — doi:10.1007/BF00203965.
• Alex Biryukov, Dmitry Khovratovich. Related-Key Cryptanalysis of the Full AES-192 and AES-256 (англ.) // Springer Berlin Heidelberg : журнал. — 2009. — P. 1—18. — ISSN 978-3-642-10366-7. — doi:10.1007/978-3-642-10366-7_1.
• Alex Biryukov, David Wagner. Slide Attacks (англ.) // Fast Software Encryption. 6th International Workshop, FSE’99 Rome, Italy, March 24–26, 1999 Proceedings. — Springer Berlin Heidelberg, 1999. — ISBN 978-3-540-66226-6. (недоступная ссылка)
• Панасенко C. Криптоаналитические атаки на связанных ключах // CIO-World : журнал. — 2007.
• Панасенко C. Алгоритмы шифрования. Специальный справочник. — БХВ-Петербург. — 2009. — С. 53—59.
• Александр Тыренко. Алгоритм DES взломан за три дня // Computerworld Россия : журнал. — 1998. — № 28—29.
• John Kelsey, Bruce Schneier, David Wagner. Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES (англ.) // Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 1996, Proceedings : журнал. — 1996.
• Mihir Bellare and Tadayoshi Kohno. A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications. — EUROCRYPT. — 2003. — С. 491—506.