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

Атака на основе связанных ключей (англ. Related-key attack) — вид криптографической атаки, в которой криптоаналитик может наблюдать за работой алгоритма шифрования или расшифрования, использующем несколько секретных ключей. Данная атака не является простым перебором всех возможных значений ключа. Изначально криптоаналитик ничего не знает о точном значении ключей, но предполагается, что атакующему известно некоторое математическое отношение, связывающее между собой ключи. Например, соотношение может быть просто значением xor с известной константой: $~KB=KA~xor~C$ или более сложная связь вида $~KB=F(KA)$, где $F$ — произвольная функция, выбранная атакующим. В реальной жизни такие зависимости могут возникнуть при сбоях в аппаратном обеспечении или плохо спроектированных протоколах безопасности.

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

Первым кто предложил данный тип атаки, был Эли Бихам. Атака на связанных ключах, описанная им, напоминает на [[::en:: Slide attack|сдвиговую атаку]]. Главное различие заключается в том, что сдвиговая атака использует два открытых текста $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}$ может дать криптоаналитику много возможностей для осуществления несанкционированного доступа к информации. Например, формирование ключа алгоритма [[::en::LOKI|LOKI89]] построено таким образом, что $k_{1}$ представляет собой просто левую 32-битную часть ключа $K$. Поскольку в данном алгоритме используется 64-битный ключ, то после вычисления $k_{1}$ для нахождения $K$ достаточно всего лишь перебора $2^{32}$ вариантов.

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

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

Атака на DES

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

Наименее безопасным к атаке является модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа. Для того чтобы взломать такой вариант алгоритма криптоаналитику потребуется только 2¹⁷ выбранных открытых текстов для выбранных ключей или 2³³ известных открытых текстов для выбранных ключей.

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

• Это первая попытка криптоаналитического вскрытия алгоритма генерации подключей в DES.
• Вскрытие не зависит от количества этапов криптографического алгоритма, он одинаково эффективен против DES с 16, 32 или 1000 этапами.
• Алгоритм шифрования DES невосприимчив к такому вскрытию, так как число сдвигов в ключе алгоритма планирования не одинаково во всех раундах. В то время как регистры ключа обычно сдвинуты на два бита после каждого цикла, то после первого, восьмого и пятнадцатого раундов регистры сдвинуты лишь на один бит. Однако, если изменить эту схему переключений, смещать регистр ключа на одинаковое число битов во всех раундах, результирующая криптосистема становится уязвимой для атаки со связанными ключами. Нижеследующая таблица описывает сдвиг перед каждым раундом в алгоритме DES и конечный сдвиг, получившийся после замены, которая сделала алгоритм уязвимым для атаки.

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

Атака на AES

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

AES представлен в трех вариантах, каждый из которых обеспечивает тот или иной уровень безопасности, зависящий от длины секретного ключа. Ключ может иметь длину 128, 192 и 256 бит. С 2001 года, после выбора AES, как криптографического стандарта, прогресс в его криптоанализе крайне низок. Лучшие результаты были получены в процессе проведения атак, основанных на связанных ключах в 2009 году. Алекс Бирюков вместе с Дмитрием Ховратовичем, предоставили первую криптоаналитическую атаку на основе связанных ключей на полнораундовые AES-192 и AES-256, разработанный метод работает быстрее, чем полный перебор.

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

Атака на 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) = 272 пройдут первый раунд. Таким образом, получаем 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.

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

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

Литература

• Шнаер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — 2-е изд. — Триумф, 2012. — 815 с. — ISBN 978-5-89392-527-2.
• 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.