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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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