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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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)}$,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle F_{k}(m)\oplus F_{k'}(m)=(E_{k'}(m)\oplus k)\oplus (E_{k'}(m)=k}$^[3].

Таким образом, аналитик сразу получает все биты ключа ${\displaystyle k}$, кроме первого, и может завершить операцию, так как ему известен открытый текст^[4].

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

СХЕМЫ

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

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

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

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

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

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

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

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

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

• 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.