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

Атака на основе подобранного ключа (англ. Chosen-key attack ) — один из способов криптоаналитического вскрытия, в котором ведётся наблюдение за работой алгоритма шифрования, использующего несколько секретных ключей. Криптоаналитик изначально обладает лишь информацией о некотором математическом соотношении, связывающим между собой ключи.

Описание

Согласно принципу Керкгоффса, криптоаналитик обладает всей необходимой информацией об используемой системе шифрования, кроме определённого набора засекреченных параметров, называемых ключом. Криптоаналитик знает лишь соотношение между парой ключей. Он использует шифротекст и данное соотношение, чтобы подобрать оба ключа. Известны два вида атак на основе подобранного ключа: атака на основе подобранного ключа и известного открытого текста, в которой только соотношение между парой ключей задаётся криптоаналитиком, и атака на основе подобранного ключа и открытого текста, в которой криптоаналитик задаёт как соотношение между парой ключей, так и сам открытый текст, который должен быть зашифрован.

Атака на основе подобранного ключа осуществляется одинаково на все криптосистемы, включая так называемый «чёрный ящик», у которого все свойства неизвестны. Данный «чёрный ящик» использует функцию шифрования $E_{k}$, которая выбирается одинаково для случайных перестановок сообщений. Биты ключа $k$ выбираются случайным образом, таким, что знание шифротекста $E_{k}(m)$ ничего не может сказать о шифротексте $E_{h}(m')$ для ключа $h\neq k$.

Алгоритм атаки на основе подобранного ключа на «черный ящик», помимо стандартных операций, в любой момент вычислений может потребовать:

• зашифровать $E_{k\oplus l}(m)$ или расшифровать $E_{k\oplus l}^{-1}(m)$, используя секретный ключ $k$ и подобранные сообщение $m$ и вектор инверсии $l$,
• использовать «черный ящик» для вычисления $E_{h}(m)$ или $E_{h}^{-1}(m)$ с помощью ключа $h$ (не являющегося функцией $k$), подобрав сообщение $m$.

Также, у алгоритма может иметься доступ к генератору случайных битов. В конце вычислений выводится предполагаемый ключ $k$.

Таким образом, если пользователь использует секретный ключ $k$ и открытую криптосистему $E$ (криптосистема с открытым ключом), то в любой момент криптоаналитик может выбрать сообщение $m$ и вектор инверсии $l$ и выполнить шифрование $E_{k\oplus l}$ или расшифрование $E_{k\oplus l}^{-1}$. Основным применением атаки на основе подобранного ключа является верификация систем, но при определённых обстоятельствах эта атака может быть применена на практике. Если поточный шифр используется для передачи сессионного ключа $k$ от пользователя $A$ к пользователю $B$, и криптоаналитик получает контроль над линией передачи, то он может изменить любые биты ключа на своё усмотрение, и $B$ получит изменённый ключ $k\oplus l$ вместо $k$. Затем, когда $B$ начнет передачу с неверным ключом, $A$ получит искаженное сообщение и начнет процедуру восстановления. Тем временем, криптоаналитик получит зашифрованный ключом $k\oplus l$ текст. (Хорошая криптозащита может отражать такие атаки, используя новые независимые сессионные ключи или добавляя нелинейные биты детектирования ошибок в сессионный ключ всякий раз, когда процедура восстановления необходима. Однако, история показывает, что хорошая криптозащита не всегда следует этому и желательно иметь систему, которая не падает под такой атакой).

Основной вид атаки на основе подобранного ключа

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

Теорема. Пусть $E$ — блочный шифр с n-битным ключом. Предположим, что криптоаналитик может выполнить $2^{p}$ инверсий и имеет $2^{p}$ слов памяти. Тогда он сможет взломать шифр $E$ за $2^{n-p}$ дополнительных шага.

Доказательство:

Аналитик заменяет последние $p$ бит в ключе всеми возможными $2^{p}$ способами. Например, он зашифровывает значения

$E_{k}(m),E_{k\oplus (00\dots 01)}(m),\dots ,E_{k\oplus j}(m),\ldots ,E_{k\oplus (00\dots 011\dots 1)}(m)$,

где $k$ секретный ключ пользователя и $m$ любое подходящее сообщение. Он создает хеш-таблицу из $2^{p}$ значений $(E_{k\oplus j},j)$.

Затем он совершает $2^{n-p}$ шифрований, меняя первые $n-p$ бит ключа и обнуляя последние $p$ бит:

$E_{(00\dots 0)}(m),E_{(00\dots 10\dots )}(m),\dots ,E_{(11\dots 10\ldots 0)}(m)$.

После всех вычислений, каждое значение проверяется на соответствие в хеш-таблице.

Если изначальный ключ $k$ взламывается через $(a,b)$, где $b$ состоит из последних $p$ бит, тогда запись $(E_{k\oplus b},b)$ будет соответствовать результату через $a^{th}$ шифрований во второй стадии. Когда же соответствие будет найдено, $(a,b)$ будет кандидатом в ключи. Возможно несколько ложных тревог, если несколько ключей подходят к сообщению $m$, но, как в атаке на основе подобранного текста, один или два дополнительных блока известного открытого текста почти наверняка исключают их, незначительно влияя на время работы.

Вывод: Используя неограниченное количество атак на основе подобранного ключа, любой блочный шифр с n-битным ключом может быть взломан с использованием не более $O(2^{n/2})$ вычислений в памяти.

Доказательство: Выберем $p=n/2$.

Замечание: Для большого количества примеров и большого количество доступной памяти, будет намного эффективнее поменять местами две стадии в доказательстве теоремы. Вычислить и сохранить $2^{n-p}$ шифрований в памяти. Для каждой задачи совершить $2^{p}$ инверсий и проверить таблицу на соответствие. Таким образом, на каждую дополнительную задачу будет затрачено $2^{p}$ итераций.

Уязвимость блочного кода для атаки на основе подобранного ключа

Продемонстрируем возможности данного типа атаки на криптосистему, которая показала себя крайне устойчивой против атаки на основе подобранного текста.

Пусть $E$ — секретный блочный шифр с размером ключа $n$ бит. Определим новый блочный шифр $F$.

$F_{k}(m)=E_{k}(m)$, если первый бит $k$ равен 0

$F_{k}(m)=E_{k'}(m)\oplus k$ в остальных случаях, где $k'$ результат инверсии первого бита $k$, например, $k'=k\oplus (1,0,\ldots ,0)$.

$F$ легитимный блочный шифр:

$F_{k}^{-1}(m)=E_{k}^{-1}(m)$, если первый бит ключа $k$ равен 0

$F_{k}^{-1}(m)=E_{k'}^{-1}(m\oplus k)$, в остальных случаях

Если основной шифр $E$ имеет качественную n-битную защиту, то взлом шифра $F$ при помощи атаки на основе анализа текста требует расширенного поиска по ключевому пространству $n-1$ бит. Иными словами, если аналитик не обладает информацией о шифре $E$, то он может получить нужную информацию, если только он шифрует или расшифровывает ключами $k$ или $k'$.

Хотя шифр $F$ трудно взломать атакой на основе подобранного текста, он очень легко поддается взлому атакой на основе подобранного ключа. Аналитик нуждается в двух шифрах: $F_{k}(m)$ и $F_{k'}(m)$ для некоторого подходящего сообщения $m$. Если первый бит $k$ равен нулю, то

$F_{k}(m)\oplus F_{k'}(m)=E_{k}(m)\oplus (E_{k''}(m)\oplus k')=k'$

В остальных случаях,

$F_{k}(m)\oplus F_{k'}(m)=(E_{k'}(m)\oplus k)\oplus (E_{k'}(m)=k$.

Таким образом, аналитик сразу получает все биты ключа $k$, кроме первого, и может завершить операцию, так как ему известен открытый текст.

Примеры атак

Атака на LOKI89

В шифре LOKI89 каждый выбор двух подключей, один из чётного цикла и один из нечётного, имеет соответствующий 64-битный ключ. Так как все алгоритмы получения двух подключей из предыдущих двух одинаковы, местоположение циклов, в которых находятся два текущих подключа не влияет на вывод следующих подключей. Если мы зафиксируем два подключа $K2$ и $K3$ ключа $K$ и определим второй ключ $K^{*}$ выбрав$K1^{*}=K2$ и $K2^{*}=K3$, то значения подключей $Ki^{*}$ ключа $K^{*}$ будут такими же, как и следующие подключи $K(i+1)$ ключа $K$. В таком случае, $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$. Данное соотношение сохраняется для любых двух ключей, выбранных таким образом: если информация перед вторым циклом шифрования ключом $K$ совпадают с информацие перед первым шифрованием ключом $K^{*}$, то информация и входные данные функции $F$ одинаковы в обоих операциях, сдвинутых на один цикл. В таком случае, если открытый текст $P$ шифруется ключом $K$, то шифротекст перед вторым циклом будет равняться $(P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))$. Полученные данные совпадают с теми, которые будут найдены перед первым циклом шифрования с ключом $K^{*}$, значение которого будет $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$, и, таким образом, в данной паре

$$P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_{L}))$$

Можно заметить, что правая часть выражения $P$ совпадает с левой частью выражения $P^{*}$, и отношение двух других частей зависит от ключа. В такой паре существует похожее соотношение между шифротекстами:

$$C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}),C_{L}).$$

Графики описывают соотношения между подключами двух ключей и соотношения между значениями в процессе шифрования.

СХЕМЫ

Атака на основе подобранного ключа и подобранного открытого текста, опирающаяся на данные свойства, выбирает 32-битное значение $P_{R}$, $2^{16}$ открытых текстов $P_{0},...,P_{65535}$, правые части которых равны $P_{R}$, и чьи 32-битные левые половины выбраны случайно, и $2^{16}$ открытых текстов $P_{0}^{*},...,P_{65535}^{*}$, чьи левые части равны $P_{R}$, а правые выбраны случайным образом. Два неизвестных связанных ключа используются для шифрования данных открытых текстов на исследуемой системе: ключ $K$ используется для шифрования первых $2^{16}$ открытых текстов, и ключ $K^{*}=(K_{R},ROL12(K_{L}))$ используется для шифрования оставшихся $2^{16}$ открытых текстов. Для каждой пары открытых текстов $P_{i}$ и $P_{j}^{*}$ гарантировано, что $P_{jL}^{*}=P_{iR}$, и с высокой вероятностью существуют два открытых текста такие, что $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L})$. Для такой пары данные остаются такими же, если оба выполнения сдвинуть на один цикл. Такую пару легко подобрать, если она существует, проверив равенство $C_{R}^{*}=C_{L}.$ Вероятность пройти данный тест случайным образом составляет $2^{-32}$, следовательно только несколько пар смогут пройти его.

Пары, обладающие такими свойствами открытого текста и шифротекста, удовлетворяют требованиям на ключ (1) и (2). Таким образом, для данной пары выполняется соотношение $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*}\oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ , в котором единственным неизвестным является значение $K_{L}\oplus K_{R}$. Из всех $2^{32}$ возможных вариантов значений $K_{L}\oplus K_{R}$ только несколько удовлетворяют уравнению. Пользуясь дифференциальным криптоанализом и техникой оптимизации, нахождение значения $K_{L}\oplus K_{R}$ может быть выполнено за несколько операций. После того, как было найдено значение $K_{L}\oplus K_{R}$, легко вычислить $K_{L}\oplus ROL12(K_{L})$ используя формулы (1) и (2), чтобы получить $K$ и $K^{*}$.

Похожая атака на основе подобранного ключа и известного открытого текста использует $2^{32}$ известных открытых текстов $P_{i}$, зашифрованных неизвестным ключом $K$, и $2^{32}$ открытых текстов $P_{j}^{*}$, зашифрованных связанным ключом $K^{*}=(K_{R},ROL12(K_{L}))$. Пару, обладающую данными свойствами, легко определить по 32 общим битам открытого текста и 32 общим битам шифротекста. Данная пара может быть использована для поиска ключей таким же образом, как и в атаке на основе подобранного ключа и подобранного открытого текста.

Сравнение с другими типами атак

Согласно Брюсу Шнайеру, существует 7 основных способа криптоаналитического вскрытия:

1. Вскрытие с использованием только шифротекста.
2. Вскрытие с использованием открытого текста.
3. Вскрытие с использованием выбранного открытого текста.
4. Адаптивное вскрытие с использованием открытого текста.
5. Вскрытие с использованием выбранного шифротекста.
6. Вскрытие с использованием выбранного ключа.
7. Бандитский криптоанализ.

В случае атаки на основе шифротекста криптоаналитик имеет доступ только к зашифрованному тексту. Это наиболее трудный тип атаки, из-за малого объёма доступной информации.

При атаке на основе известного открытого текста криптоаналитику известны открытый и зашифрованный тексты. Данный тип атаки результативнее, чем атака на основе шифротекста за счет большего количества известной информации о криптосистеме.

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

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

Литература

• Robert Winternitz, Martin Hellman. Chosen-key attacks on a block cipher (англ.) // Cryptologia : журнал. — 1987. — No. 11:1. — P. 16-20. — doi:10.1080/0161-118791861749.
• Eli Biham. New Types of Cryptanalytic Attacks Using Related Keys (англ.) // Helleseth T. (eds) Advances in Cryptology. — EUROCRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg, 1993. — doi:10.1007/3-540-48285-7_34.
• Б. Шнайер. Прикладная криптография. — Триумф, 2003. — 816 с. — ISBN 5-89392-055-4.