Атака на основе открытых текстов

Введение

Атака на основе открытых текстов(англ. Known-plaintext attack) — вид криптоанализа, при котором криптоаналитик располагает некоторым набором открытых текстов (на английском часто их часто называют crib) и соответствующих им шифртекстов (на английском обычно называется ciphertext).

Термин «crib» впервые появился в Англии во время второй мировой войны. Он образовался из сленгового выражения "I cribbed my answer from your test paper." Слово «crib» изначально означало дословный перевод текста с иностранного языка.

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

Описание

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

Дано:

• 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 каталог, который предполагал «eins» кодируемый в любом месте текста. Каталог содержал все возможные положения роторов, начальные позиции и наборы ключей Энигмы.

Сейчас

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

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

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

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

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

$x_{i_1}+ .... +x_{i_r} + y_{j_1} + y_{j_s}=z_{k_1} + .... + 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 и подключи к¹1 , к² ,...., кⁱ} считаем независимыми и случайными. Процедура ДКА r-циклического шифра с выбранными открытыми текстами может быть следующей:

1. Данный этап является этапом предвычислений. На нем мы ищем множество (r-1)-цикловых дифференциалов $(\alpha_1,\beta_1)_(r-1) , (\alpha_2,\beta_2)_(r-1) ,.... (\alpha_s,\beta_s)_(r-1)$. Упорядочиваем данное множество по величине их вероятностей.
2. Данный этап требует от нас выбрать 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).
3. На данном этапе повторяем предыдущий пункт до тех пор пока один или несколько подключей не начнут появляться чаще других. Берем данный ключ (или множество ключей) в качестве решения к^(r).
4. На данном этапе мы повторяем пункты 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 )>>2^{-n} ,$

Где n количество бит в блоке шифруемого текста. Сложность нахождения ключа r-цикличного шифро Q(r) определяется как число используемых шифрований с последующим нахождением ключа: $Q(r)\ge 2/ (P_{max} - 1/(2^n-1)),$ где $P_{max}=max(\alpha )max(\beta )(P(\Delta y(r-1)=\beta | \Delta x=\alpha )).$ В частности в случае если $P_{max} \approx 1/(2^n-1)$, то такая атака не будет успешной. Так как операция нахождения подключа более трудоемкая чем операция шифрования, то единицей измерения сложности является сложность нахождения возможных подключей для одного цикла по известным тройкам $( \Delta y(r-1),y(r),y^*(r)).$ Отличительной чертой дифференциального криптоанализа является то, что он подчти не использует алгебраических свойств шифра (таких как линейность, замкнутость, аффинность и прочие.) Он основан только на неравномерности распределения вероятностей дифференциалов.

Литература

1. Брюс Шнайер Прикладная криптография.
2. Дэвид Кан Взломщики кодов.

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