Атака на основе открытых текстов (Gmgtg ug kvukfy kmtjdmd] mytvmkf)

Атака на основе открытых текстов (англ. Known-plaintext attack) — вид криптоанализа, при котором в шифротексте присутствуют стандартные отрывки, смысл которых заранее известен аналитику. Во время Второй мировой войны английские криптоаналитики называли такие отрывки «подсказками» (англ. crib — подсказка, шпаргалка)^{[Прим. 1]}.

Шифровки различных стран зачастую содержали специфические выражения: Heil Hitler!, Banzai!, Пролетарии всех стран, соединяйтесь! и т. п.

Другим примером использования метода является криптографическая атака на алгоритм простого гаммирования. Если известен хотя бы один открытый текст и соответствующий ему шифртекст длины больше или равной длине гаммы (ключа), то последняя однозначно находится.

Описание

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

Дано:

P₁, P₂, …, P_i — открытые тексты
C₁=E_k(P₁), C₂=E_k(P₂), …, C_i=E_k(P_i) — соответствующие им шифртексты

Нужно найти:

k — ключ шифрования, либо
D(C) — функцию дешифрования (не как функцию от ключа, но только от шифртекста)

Отличия от других методов криптоанализа

Атака на основе только шифртекста

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

Атака на основе подобранного открытого текста

Атака на основе подобранного открытого текста — данный тип атаки является улучшением метода, основанного на открытых текстах. Здесь криптоаналитик так же имеет некоторое количество пар открытый/шифрованный текст, известных заранее. Но так же он может получить шифртексты, соответствующие текстам, заранее им выбранным. Способ получения таких шифртекстов — например, написать письмо с незашифрованным текстом, при этом изобразив из себя лицо, от которого ждут шифрованное сообщение, и при некоторых условиях можно получить ответ с цитатой данного текста, но уже в зашифрованном виде. Отличие данного метода от атаки на основе открытого текста в том что в данном методе криптоаналитик может сам выбрать какой текст он хочет зашифровать. А в методе, основанном только на открытом тексте все пары открытый / шифрованный текст известны заранее.

Атака на основе адаптивно подобранного открытого текста

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

Пример применения в истории

В случае Энигмы, Германское высшее командование было очень щепетильно в обеспечении безопасности системы, так как оно осознавало возможную проблему взлома на основе открытых текстов. Команда, которая работала над взломом, могла предположить о содержании текстов основываясь на том, когда были посланы сообщения. Например, прогноз погоды передавался каждый день в одно и то же время. Согласно регламенту военных сообщений, каждое сообщение содержало слово «Погода» (Wetter) на одном и том же месте, а знание погоды в данной местности очень помогало в предположениях о содержании остального сообщения. Также очень помогли сообщения офицера, который посылал каждый раз «Нечего сообщить» (Nothing to report), предоставляя материал для криптоанализа. Другие командующие тоже посылали стандартные ответы или их ответы содержали стандартные части.

После того, как пленный немец на допросе сознался, что операторам приказано шифровать числа путём написания буквами каждой цифры, Алан Тьюринг пересмотрел сообщения и определил, что слово «eins» встречается в 90 % сообщений. На основе этого был создан Eins каталог, который содержал все возможные положения роторов, начальные позиции и наборы ключей Энигмы.

Сейчас

Современные шифры плохо подлежат данному методу криптоанализа. Например, для взлома DES необходимо примерно $2^{47}$ пар «открытый текст / шифрованный текст».

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

Основные методы

Линейный метод криптоанализа

В открытой печати линейный метод криптоанализа впервые был предложен японским математиком Мацуи. Метод предполагает, что криптоаналитик знает открытые и соответствующие зашифрованные тексты. Чаще всего при шифровании применяется сложение по модулю 2 текста с ключом, операции перемешивания и рассеивания. Задача криптоаналитика состоит в том, чтобы найти такую линейную аппроксимацию

$x_{i_{1}}+\ldots +x_{i_{r}}+y_{j_{1}}+y_{j_{s}}=z_{k_{1}}+\ldots +z_{k_{t}}$ , (1)

которая будет наилучшей. Пусть $p$ — это вероятность того, что (1) выполняется. Понятно, что нам надо, чтобы $p\approx 0.5$ , а также чтобы величина $|p-0.5|$ была максимальна. В случае если эта величина достаточно велика и криптоаналитику известно достаточно много пар открытого и соответствующего ему шифрованного текста, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части равенства (1) равна наиболее вероятному значению суммы по модулю 2 соответствующих бит в открытом и шифрованном текстах в левой части. В случае, когда $p>0.5$ , сумма в правой части (1) равна нулю, когда сумма бит в левой части равна нулю более чем в половине пар зашифрованных текстов. Сумма бит в правой части равна единице, если сумма бит в левой части равна единице более чем в половине случаев текстов. Если $p<0.5$ , то наоборот: сумма бит в правой части равна единице, если в левой части сумма бит равна нулю более чем для половины текстов. И сумма бит в правой части равна нулю, если сумма бит в левой части равна единице более чем в половине случаев. Для нахождения каждого бита ключа теперь надо решить систему линейных уравнений для соответствующих известных комбинаций этих бит. Это не представляет сложности, так как сложность данной системы выражается полиномом не более чем третьей степени от длины ключа. Количество необходимых пар открытый/шифрованный текст для вскрытия шифра оценивается формулой $N=|p-1/2|2^{-2}$ . Для вскрытия шифра DES таким методом получается, что необходимо примерно 2⁴⁷ пар открытый / зашифрованный блок.

Дифференциальный метод криптоанализа.

Дифференциальный метод криптоанализа (ДКА) был в 1990 году предложен Э.Бихамом и А.Шамиром. Дифференциальный криптоанализ — это попытка вскрыть секретный ключ блочных шифров, которые основаны на повторном применении криптографически слабых операций шифрования r раз. При криптоанализе предполагается, что на каждом цикле шифрования используется свой подключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты. Главным условием успеха попыток вскрытия r-циклического шифра является существование дифференциалов (r-1)-го цикла, которые имеют большую вероятность. Дифференциал i-го цикла определяется как пара чисел $(\alpha ,\beta )_{i},$ таких что пара различных открытых текстов x и x* c разностью $\alpha$ может после i-го цикла дать на выходе пару y и y* с разностью $\beta$ . Вероятность i-циклового дифференциала — это условная вероятность $P(\Delta y(i)=\beta |\Delta x=\alpha )$ того, что разность y и y* после i-го цикла равна $\beta$ при условии, что изначально были x и x* с разностью $\alpha$ . Открытый текст x и подключи к¹, к², …, кⁱ считаем независимыми и случайными. Процедура ДКА r-циклического шифра с выбранными открытыми текстами может быть следующей:

Данный этап является этапом предвычислений. На нём мы ищем множество (r-1)-цикловых дифференциалов $(\alpha _{1},\beta _{1})_{r-1},(\alpha _{2},\beta _{2})_{r-1},....(\alpha _{s},\beta _{s})_{r-1}$ . Упорядочиваем данное множество по величине их вероятностей.
Данный этап требует от нас выбрать x и x*, так чтобы их разность была равна $\alpha _{1}$ , для них имеем пару шифртекстов y(r), y*(r). Считаем, что на выходе предпоследнего цикла разность равна наиболее вероятной $\Delta y(r-1)=\beta _{1}$ . Для тройки $(\Delta y(r-1),y(r),y^{*}(r))$ находим каждое возможное значение подключа k^(r). Увеличиваем счетчик появления каждого такого значения подключа к^(r).
На данном этапе повторяем предыдущий пункт до тех пор пока один или несколько подключей не начнут появляться чаще других. Берем данный ключ (или множество ключей) в качестве решения к^(r).
На данном этапе мы повторяем пункты 1-3 для (r-1)-го цикла при этом значения y(r-1) вычисляются расшифровыванием y(r) с использованием ключа к^(r), найденного в предыдущем пункте. И повторяем данные действия пока не найдем ключи всех циклов.

Данный метод был изначально предложен для решения одного шифра, но затем он показал успехи в криптоанализе многих марковских шифров. Шифр называется марковским, если у него уравнение на одном цикле удовлетворяет условию, что вероятность дифференциала не зависит от выбора открытых текстов. Тогда если ключи циклов независимы, то последовательность разностей каждого цикла образует марковскую цепь, в которой каждый последующий элемент зависит только от предыдущего. Примерами марковских шифров являются DES и FEAL. Покажем, что марковский r-цикличный шифр с независимыми подключами является уязвимым для ДКА тогда и только тогда, когда для одного цикла ключ легко вычисляется по известной тройке $(y,y^{*},\Delta x)$ . Также существует (r-1) дифференциал $(\alpha ,\beta )_{r-1}$ , причем его вероятность удовлетворяет выражению $P(\Delta y(r-1)=\beta |\Delta x=\alpha )\gg 2^{-n},$ где n — количество бит в блоке шифруемого текста. Сложность нахождения ключа r-цикличного шифра Q(r) определяется как число используемых шифрований с последующим нахождением ключа: $Q(r)\geqslant 2/(P_{\mathrm {max} }-1/(2^{n}-1)),$ где $P_{\mathrm {max} }=\operatorname {max} (\alpha )\operatorname {max} (\beta )(P(\Delta y(r-1)=\beta |\Delta x=\alpha )).$ В частности, в случае если $P_{\mathrm {max} }\approx 1/(2^{n}-1)$ , то такая атака не будет успешной. Так как операция нахождения подключа более трудоемкая чем операция шифрования, то единицей измерения сложности является сложность нахождения возможных подключей для одного цикла по известным тройкам $(\Delta y(r-1),y(r),y^{*}(r)).$ Отличительной чертой дифференциального криптоанализа является то, что он почти не использует алгебраических свойств шифра (таких как линейность, замкнутость, аффинность и прочие.) Он основан только на неравномерности распределения вероятностей дифференциалов.

Примечания

↑ Слово crib (как существительное, так и глагол) имеет в английском десятки значений, в том числе сленговых. В частности, на школьном сленге crib означает подсказку, шпаргалку и т. п. незаконные методы сдачи экзаменов

Литература

Брюс Шнайер. Прикладная криптография. Архивная копия от 28 февраля 2014 на Wayback Machine}
Дэвид Кан. Взломщики кодов.

Welchman, Gordon (1982), The Hut Six Story: Breaking the Enigma Codes, Harmondsworth: Allen Lane, ISBN 0713912944

[1] Слово crib (как существительное, так и глагол) имеет в английском десятки значений, в том числе сленговых. В частности, на школьном сленге crib означает подсказку, шпаргалку и т. п. незаконные методы сдачи экзаменов

[Прим. 1]