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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Классическая атака на основе связанных ключей[править | править вики-текст]

Первым, кто предложил данный тип атаки, был Эли Бихам. Атака на связанных ключах, описанная им, напоминает на сдвиговую атаку. Главное различие заключается в том, что сдвиговая атака использует два открытых текста 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]

Суть атаки[править | править вики-текст]
  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 не подвержен к такой атаке. В процессе шифрования для основной функции шифрования, требуется вычислить шестнадцать 48-битовых ключа, которые являются результатом преобразования 56-битового исходного ключа (подробнее в разделе «Генерирование ключей k_i»). Число сдвигов в алгоритме вычисления ключей k_i не одинаково во всех раундах. Однако если изменить эту схему переключений, установить сдвиг одинаковым во всех раундах, то результирующая криптосистема становится уязвимой для атаки со связанными ключами. Наименее безопасным к атаке является модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа.[2]

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

Для того чтобы взломать такой вариант алгоритма криптоаналитику потребуется только 217 выбранных открытых текстов для выбранных ключей или 233 известных открытых текстов для выбранных ключей. Для взлома модифицированного DES необходимо выполнить 1.43*253 операций, что является небольшим выигрышем, по сравнению с полным перебором, где количество операций равно 256.[3] Огромные требования к времени и объему данных, не позволяют реализовать атаку на практике, без помощи дорогостоящего оборудования. К примеру, в 1998 году с помощью суперкомпьютера стоимостью 250 тыс. долл., DES был взломан менее чем за три дня. [4] Но, тем не менее, атака интересна по двум причинам:

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

Атака на AES[править | править вики-текст]

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-блока.

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

Атака на AES-256[править | править вики-текст]

Необходимо выполнить следующие шаги 225,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^{0}_{i,7} = 0, \Delta k^{0}_{i,0} тоже будут равны с обеих сторон.
  7. Необходимо отобрать квартеты, различия которых не могут быть затронуты активными S-блоками в первом раунде и активными S-блоками в алгоритме выработки ключа.
  8. Отфильтровывая неправильные квартеты, частично восстановим значение ключа.

Каждая структура имеет всевозможные варианты значений нулевого столбца, нулевой строки и константное значение в других байтах. Из 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.

Атака на AES-192[править | править вики-текст]

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

  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 и проверить этот ключ на правильность. При неудачном раскладе перейти к первому шагу.[7]

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

Практическое применение[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Панасенко С., 2007
  2. Biham, 1994, p. 15
  3. Biham, 1994, p. 17
  4. Computerworld, 1998
  5. Biryukov, 2009, p. 1
  6. Biryukov, 2009, p. 2
  7. 1 2 Biryukov, 2009, p. 12
  8. Biham, 1994, p. 2

Литература[править | править вики-текст]