13-07-2023
Атака на основе связанных ключей (англ. Related-key attack) — вид криптографической атаки, в которой криптоаналитик может наблюдать за работой алгоритма шифрования или расшифрования, использующем несколько секретных ключей. Данная атака не является простым перебором всех возможных значений ключа. Изначально криптоаналитик ничего не знает о точном значении ключей, но предполагается, что атакующему известно некоторое математическое отношение, связывающее между собой ключи. Например, соотношение может быть просто значением xor с известной константой: или более сложная связь вида , где — произвольная функция, выбранная атакующим. В реальной жизни такие зависимости могут возникнуть при сбоях в аппаратном обеспечении или плохо спроектированных протоколах безопасности.
Первым, кто предложил данный тип атаки, был Эли Бихам. Атака на связанных ключах, описанная им, напоминает на сдвиговую атаку. Главное различие заключается в том, что сдвиговая атака использует два открытых текста и , удовлетворяющих следующему соотношению: , где — функция раунда, а — подключ 1-го раунда. В атаке на связанных ключах применяется похожее соотношение между ключами. Допустим, что искомый ключ шифрования K после модификации его процедурой расширения ключа дает последовательность подключей: , где — количество раундов алгоритма шифрования. Предположим, что существует ключ , расширение которого дает следующую последовательность: , то есть последовательность подключей, создаваемая на основе ключа , циклически сдвинута относительно последовательности искомого ключа на 1 раунд.[1]
Какой из текстов соответствует каждому тексту из , криптоаналитик не знает заранее. Но, вероятность того, что два случайно выбранных текста будут удовлетворять требуемому соотношению, равна .Тогда требуемая пара должна быть найдена после анализа не более чем текстов, в соответствии с прадоксом дней рождения. Условие текстов не является строгим, оно является оценочным и будет выполнятся лишь в среднем.
Ключ , найденный из приведенной выше системы, и есть искомый подключ . В зависимости от операции формирования ключа, знание может дать криптоаналитику много возможностей для осуществления несанкционированного доступа к информации. Например, формирование ключа алгоритма LOKI89 построено таким образом, что представляет собой просто левую 32-битную часть ключа . Поскольку в данном алгоритме используется 64-битный ключ, то после вычисления для нахождения достаточно всего лишь перебора вариантов.
Функция раунда алгоритма, на который производится атака, должна быть достаточно слабой для вычисления , что применительно к большинству современных алгоритмов шифрования. Кроме того, трудоемкость атаки может быть значительно снижена по отношению к описанному выше случаю, все зависит от выбранного алгоритма шифрования открытого текста. К примеру, вычисления упрощаются для алгоритмов, основанных на сбалансированной сети Фейстеля.
Алгоритм шифрования DES не подвержен к такой атаке. В процессе шифрования для основной функции шифрования, требуется вычислить шестнадцать 48-битовых ключа, которые являются результатом преобразования 56-битового исходного ключа (подробнее в разделе «Генерирование ключей »). Число сдвигов в алгоритме вычисления ключей не одинаково во всех раундах. Однако если изменить эту схему переключений, установить сдвиг одинаковым во всех раундах, то результирующая криптосистема становится уязвимой для атаки со связанными ключами. Наименее безопасным к атаке является модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа.[2]
Для того чтобы взломать такой вариант алгоритма криптоаналитику потребуется только 217 выбранных открытых текстов для выбранных ключей или 233 известных открытых текстов для выбранных ключей. Для взлома модифицированного DES необходимо выполнить 1.43*253 операций, что является небольшим выигрышем, по сравнению с полным перебором, где количество операций равно 256.[3] Огромные требования к времени и объему данных, не позволяют реализовать атаку на практике, без помощи дорогостоящего оборудования. К примеру, в 1998 году с помощью суперкомпьютера стоимостью 250 тыс. долл., DES был взломан менее чем за три дня. [4] Но, тем не менее, атака интересна по двум причинам:
AES представлен в трех вариантах, каждый из которых обеспечивает тот или иной уровень безопасности, зависящий от длины секретного ключа. Ключ может иметь длину 128, 192 и 256 бит. С 2001 года, после выбора AES, как криптографического стандарта, прогресс в его криптоанализе крайне низок.[5] Лучшие результаты были получены в процессе проведения атак, основанных на связанных ключах в 2009 году. Алекс Бирюков вместе с Дмитрием Ховратовичем, предоставили первую криптоаналитическую атаку на основе связанных ключей на полнораундовые AES-192 и AES-256, разработанный метод работает быстрее, чем полный перебор.
Разработанная атака на AES-256 подходит для всех типов ключей и имеет сложность порядка 296.Также была представлена атака на AES-192. В обеих атаках осуществляется минимизирование числа активных S-блоков алгоритма создания ключей. Данная операция применяется с помощью атаки бумерангом. Дифференциальные характеристики для бумеранга были установлены путем поиска локальных коллизий в шифре.[6] Основная особенность AES-256, которая являются определяющей для рассматриваемых атак, заключается в том, что алгоритм шифрования имеет 14 раундов и 256-битный ключ, который удваивается во внутреннем состоянии. Поэтому, алгоритм выработки ключей состоит только из 7 раундов, а каждый раунд в свою очередь имеет 8 S-блоков. Аналогично для AES-192 за счет того, что ключ становится в полтора раза больше во внутреннем состоянии, алгоритм выработки ключа состоит лишь из 8, а не 12 раундов. Каждый раунд имеет только 4 S-блока.
Необходимо выполнить следующие шаги 225,5 раз:
Каждая структура имеет всевозможные варианты значений нулевого столбца, нулевой строки и константное значение в других байтах. Из 272 текстов в каждой структуре можно сравнить 2144 пар. Из этих пар 2(144−8*9) = 272 пройдут первый раунд. Таким образом, получаем 1 нужный квартет из 2(96-72) = 224 структур и 3 нужных квартета из 225,5 структур. Вычислим количество квартетов прошедших 6 шагов, их будет около 2(144-56-16) = 272 пар. Следующим шагом будет применение 16-битного фильтра, так получим общее количество возможных квартетов 2(72+25,5−6) = 291,5.
Алгоритм создания ключа в данном случае имеет лучшую диффузию. Поэтому атака бумерангом использует два подследа по 6 раундов в каждом. Проанализируем 273 структур с 248 текстами по следующей схеме[7]:
Обе представленные атаки представляют в основном лишь теоретический интерес и на практике не создают реальной угрозы для приложений, использующих AES.
Описанные атаки с использованием связанных ключей не выглядят практичными. Во многих разработках они не сильно выигрывают по сравнению с полным перебором, кроме того требуют большого количества предположений. Данная атака большой период времени считалась достаточно эффективной, но лишь теоретической. Тем не менее, сегодня начинают появляться идеи, которые, по словам экспертов, могут иметь практическое применение. Некоторые реализации криптоалгоритмов или сетевых протоколов (например, протоколов аутентификации или обмена ключами) уже сейчас могут быть подвержены атаке с использованием связанных ключей. Одно из потенциальных применений это анализ хэш-функций. Теоретически атаки на связанных ключах могут быть опасны в случае использования алгоритмов симметричного шифрования для построения хэш-функций. В настоящее время неизвестно конкретного приложения к хеш-функциям, но разработчики хеш-функции должны учитывать при проектировании, что существует такая слабость. В любом случае, категорически рекомендуется принимать в расчет криптоанализ на связанных ключах при разработке алгоритмов шифрования и их реализации.[8]
Атака на основе связанных ключей.