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

Согласно принципу Керкгоффса, криптоаналитик обладает всей необходимой информацией об используемой системе шифрования, кроме определённого набора засекреченных параметров, называемых ключом. Криптоаналитик знает лишь соотношение между парой ключей. Он использует шифротекст и данное соотношение, чтобы подобрать оба ключа. Известны два вида атак на основе подобранного ключа: атака на основе подобранного ключа и известного открытого текста, в которой только соотношение между парой ключей задаётся криптоаналитиком, и атака на основе подобранного ключа и открытого текста, в которой криптоаналитик задаёт как соотношение между парой ключей, так и сам открытый текст, который должен быть зашифрован.[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].

Согласно Брюсу Шнайеру, существует 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.