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

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

Описание

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

Дано: $P_{1},C_{1}=E_{k}(P_{1}),\,P_{2},C_{2}=E_{k}(P_{2}),\,...\,P_{i},C_{i}=E_{k}(P_{i}),$

где $P-$ подобранный криптоаналитиком открытый текст, $C-$шифротекст, $E-$функция шифрования, $k-$ключ.

Получить: Либо $k$, либо алгоритм, как получать $P_{i+1}$ из $C_{i+1}=E_{k}(P_{i+1}).$

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

Атака на основе подобранного открытого текста относится к активным атакам на криптосистемы. При таких атаках нарушается целостность и конфиденциальность передаваемой информации.

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

На рис.1 приведена схема атаки на основе подобранного открытого текста. Атакующий (A) получает шифротекст $C=E(P,K)$ от пользователя (С). Задача атакующего — «угадать» открытый текст $P^{'}=P$. Так как атакующий имеет доступ к блоку шифрования $E$, он имеет возможность зашифровывать свои сообщения $P_{i}$ и анализировать полученные шифротексты. $C_{i}=E(P_{i},K)$. В итоге, атакующий подбирает сообщение $P^{'}$ и пересылает его пользователю.

Виды атак

Различают два вида атак на основе подобранного открытого текста:

• автономная (англ. batch chosen-plaintext attack) — криптоаналитик подготавливает набор открытых текстов заранее, до получения шифрованных текстов.
• оперативная или атака на основе адаптивно подобранного открытого текста (англ. adaptive chosen-plaintext attack, CPA2) — криптоаналитик подбирает следующие открытые тексты на основе уже полученных шифротекстов. Так как при выборе последующих отправляемых на шифрование блоков учитываются предыдущие результаты, возникает обратная связь, которая даёт атаке на основе адаптивно подобранного открытого текста преимущество перед другими типами атак. Реализация атаки такого типа возможна, например, если криптоаналитик имеет доступ к шифрующему устройству в течение достаточно долгого времени, для осуществления анализа получаемых результатов.

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

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

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

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

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

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

В истории

Атака на основе подобранного открытого текста применялась во время Второй мировой войны.

В 1942 году криптоаналитики военно-морских сил США перехватили зашифрованный приказ японского командования. Расшифровав часть сообщения, американские криптоаналитики узнали о готовящемся наступлении на загадочное «AF», однако узнать место нападения не удалось. Предполагая, что скорее всего целью японцев является остров Мидуэй, американцы пошли на хитрость. Они составили донесение о том, что на острове не хватает пресной воды и отправили его по незащищенному каналу. Через несколько дней американские разведчики перехватили японский шифротекст, в котором сообщалось, что на «AF» мало пресной воды. Таким образом, американское командование заранее узнало о грядущем наступлении на атолл Мидуэй.

Британские криптоаналитики из Блетчли-парка успешно применяли атаку на основе подобранного открытого текста при дешифровании немецкой переписки. Британцы провоцировали противника использовать определённые слова и названия в текстах сообщений. Например, если немцы в недавнем времени освободили какой-либо участок прибрежных вод от мин, британские спецслужбы могли объявить о том, что данная территория была снова заминирована. Это провоцировало поток зашифрованных сообщений от немецкого командования, включающих слово «мины» и название территории. Таким образом, британцы могли достаточно эффективно подбирать открытый текст и анализировать шифротексты для взлома немецких шифров. Данную атаку можно квалифицировать как атаку на основе адаптивно подобранного открытого текста, так как британские криптоаналитики могли подбирать следующий открытый текст, подлежащий шифрованию, основываясь на уже полученных результатах.

Примеры атак

Криптосистемы с закрытым ключом

Атака на аффинный шифр

Рассмотрим простой пример атаки на аффинный шифр, использующий латинские символы от A до Z.

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Функция шифрования: $y=mx+n\ mod\ 26.$

Криптоаналитик производит атаку на основе подобранного открытого текста. Выбранный открытый текст — «HAHAHA», соответствующий шифротекст — «NONONO». Цель криптоаналитика — найти явный вид функции шифрования, то есть вычислить коэффициенты $m$ и $n$.

Используя полученную пару открытый текст — шифротекст, составим систему уравнений:

${\begin{cases}m\cdot 7+n\equiv 13\ mod\ 26\\m\cdot 0+n\equiv 14\ mod\ 26\end{cases}}$

Решая систему, находим: $n=14,\ m=11.$

Функция шифрования: $y=11x+14\ mod\ 26.$

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

Основная статья: Дифференциальный криптоанализ

Атака на основе подобранного открытого текста используется в методе дифференциального криптоанализа, предложенного израильскими криптоаналитиками Эли Бихамом и Ади Шамиром в 1990 году для взлома криптосистемы DES. В основе метода лежит исследование шифротекстов, открытые тексты которых имеют определённые различия. Анализируя эволюцию различия шифротекстов при прохождении раундов DES, определяется список возможных ключей, каждому возможному ключу присваивается вероятность. В процессе анализа следующих пар шифротекстов один из ключей станет наиболее вероятным. В дальнейшем метод дифференциального криптоанализа был распространен на такие криптосистемы, как FEAL, Khafre, Lucifer, LOKI и другие.

Пусть $P$, $P^{'}-$ подобранные открытые тексты, $C$, $C^{'}-$ соответствующие шифротексты. Различие между открытыми текстами и шифротекстами определяется операцией XOR: $\Delta P=P\oplus P^{'},\Delta C=C\oplus C^{'}.$Для описания возможных изменений значения $\Delta C$ при прохождении этапов DES вводится понятие раундовой характеристики, составленной из различий открытого текста $\Delta P$, шифротекста $\Delta C$ и набора раундовых различий (различия в шифротекстах после каждого промежуточного раунда) $C_{\lambda }=(\lambda _{1},\lambda _{2}...\lambda _{n})$. Каждой характеристике присваивается вероятность того, что случайная пара открытых текстов с различием $\Delta P$ вызовет раундовые различия и различия в шифротекстах, соответствующие характеристике, после прохождения соответствующего раунда шифрования. Пара открытых текстов, прохождение которых через раунд DES в точности описывается характеристикой, называется «правильной парой», в противном случае — «неправильной парой».

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

Метод дифференциального криптоанализа является довольно непрактичным из-за высоких требований к времени и объёму данных. Например, для взлома 16-раундового DES требуется $2^{47}$подобранных открытых текстов и $2^{55}$ операций.

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

Основная статья: Линейный криптоанализ

В 1993 году японским криптоаналитиком Мицуру Мацуи был предложен метод линейного криптоанализа для вскрытия блочных шифров, таких как DES. В основе метода лежит построение линейных соотношений между открытым текстом, шифротекстом и ключом: $P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}}\oplus \dots \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \dots \oplus K_{k_{c}}$,

где $P_{n},C_{n},K_{n}$ — n-е биты текста, шифротекста и ключа, соответственно. Такие соотношения называются линейными аппроксимациями.

Суть метода заключается в подсчете вероятности возникновения линейных аппроксимаций. Если вероятность $p$ отлична от $1/2$, то возможно извлечь информацию о ключе, используя пары открытый текст-шифротекст. Первоначально для каждого отдельного раунда находится линейная аппроксимация с наибольшей вероятностью смещения. Затем раундовые аппроксимации объединяются в общую линейную аппроксимацию криптосистемы, и с помощью пар открытый текст-шифротекст производится предположение о значениях бита ключа.

Первоначально метод линейного криптоанализа использовал атаку на основе известного открытого текста. Так, например, для взлома 16-раундового DES потребовалось $2^{43}$ известных открытых текстов и 50 дней. В 2000 году Ларс Кнудсен предложил вариант линейного криптоанализа на основе подобранных открытых текстов — для вскрытия 12 бит ключа потребовалось $2^{42}$ выбранных открытых текстов.

Криптосистемы с открытым ключом

Атака на основе подобранного открытого текста может быть использована при вскрытии асимметричных криптосистем. В таких системах открытый ключ доступен любому пользователю, что обеспечивает криптоаналитику полный контроль над алгоритмом шифрования. Таким образом, против криптосистем с открытым ключом всегда можно организовать атаку на основе подобранного открытого текста. Например, если злоумышленник перехватил шифротекст $C=E_{k}(P)$, для расшифровки достаточно подобрать другое сообщение $P^{'}$ и зашифровать его с помощью открытого ключа $C^{'}=E_{k}(P^{'})$. Если $P\neq P^{'}$, производится ещё одна попытка.

Вероятностное шифрование

Обычно асимметричные криптосистемы проектируют так, чтобы противостоять вскрытиям с использованием подобранных открытых текстов. Например, средства защиты криптосистемы RSA от атак на основе подобранного открытого текста основаны на сложности вычисления корня $e$-й степени от шифротекста по составному целочисленному модулю $n$. Ещё одним способом устранить утечки информации в криптосистемах с открытым ключом является вероятностное шифрование, предложенное Шафи Голдвассер и Сильвио Микали. Основной идеей вероятностного шифрования является сопоставление одному и тому же открытому тексту $P$ нескольких случайно выбранных шифротекстов $C_{1},C_{2},C_{3},\ldots$. Таким образом, если криптоаналитик попытается угадать открытый текст P для расшифровки $C=E_{k}(P)$, он получит совершенно другой шифротекст $C^{'}\neq C$ и не сможет проверить правильность своего предположения.

Атака на криптосистему RSA

Несмотря на защищенность криптосистемы RSA от атак на основе подобранного текста, существует ряд уязвимостей, позволяющих криптоаналитику расшифровать шифротекст. Рассмотрим следующий алгоритм атаки на систему электронной подписи на основе RSA, предложенный Джорджем Давида в 1982 году. Атака производится в предположении, что криптоаналитик перехватил шифротекст $C=M^{e}\ mod\ n$. Цель криптоаналитика — получить открытое сообщение $M$. Для проведения атаки криптоаналитику необходимо иметь возможность подписывать любые выбранные им сообщения.

1. На первом этапе атаки производится разложение шифротекста $C$ на множители (необязательно простые): $C=C_{1}C_{2}...C_{t}$. Отсюда следует, что сообщение $M$ также представимо в виде произведения $t$ множителей $M=M_{1}M_{2}...M_{t}$, и справедливы равенства: $C=C_{1}C_{2}...C_{t}=(M_{1}M_{2}...M_{t})^{e}\ mod\ n=M_{1}^{e}M_{2}^{e}...M_{t}^{e}\ mod\ n$, и $M_{i}=C_{i}^{d}\ mod\ n$.
2. Криптоаналитик подбирает открытое сообщение $X$ и отправляет его на подпись. Также он просит подписать сообщения $XC_{1}$,$XC_{2}$$...XC_{t}$. Подпись производится следующим образом: $S=X^{d}\ mod\ n$, при этом $S_{i}=(XC)_{i}^{d}\ mod\ n,i=1...t$.
3. Вычисляется обратный элемент $S^{-1}=X^{-d}\ mod\ n$.
4. Умножая полученное выражения на $S_{i}$ возможно получить $M_{i}$: $S_{i}S^{-1}=(X)^{-d}(XC_{i})^{d}\ mod\ n=C_{i}^{d}\ mod\ n=M_{i}$.
5. В итоге восстанавливается исходное сообщение: $M=M_{1}M_{2}...M_{t}\ mod\ n$

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

Литература

• Б. Шнайер. Прикладная криптография. — Триумф, 2003. — 816 с. — ISBN 5-89392-055-4.
• Б. Шнайер, Н. Фергусон. Практическая криптография. — Вильямс, 2002. — 424 с. — ISBN 5-8459-0733-0.
• Э. Габидулин, А. Кшевецкий, А. Колыбельников, С. Владимиров. Защита информации. Учебное пособие.
• Д. Кан. Взломщики кодов. — Центрполиграф, 2000. — 124 с. — ISBN 5-227-00678-4.
• F. H. Hinsley, A. Stripp. Codebreakers: The Inside Story of Bletchley Park. — Oxford University Press, 2001. — 360 с. — ISBN 978-0192801326.
• D. Stinson. Cryptography. Threory and Practice. — Chapman & Hall/CRC, 2006. — 611 с. — ISBN 978-1-58488-508-5.
• В. Мао. Современная криптография. Теория и практика.. — Вильямс, 2005. — 768 с. — ISBN 5-8459-0847-7.
• E. Biham, A. Shamir. Differential Cryptanalysis of DES-like Cryptosystems. — Journal of Cryptology, 1990. — Т. 4.
• E. Biham, A. Shamir. Differential Cryptanalysis of Feal and N-Hash. — Advances in Cryptology — EUROCRYPT ’91, 1991. — Т. 547.
• E. Biham, A. Shamir. Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. — Advances in Cryptology — CRYPTO’ 91, 1991.
• M. Matsui. Linear Cryptanalysis Method for DES Cipher. — Advances in Cryptology — EUROCRYPT’ 93, 1993.
• L. Knudsen, J. Mathiassen. A Chosen-Plaintext Linear Attack on DES. — International Workshop on Fast Software Encryption, 2000.
• D. E. Denning. Digital signatures with RSA and other public-key cryptosystems. — Communications of the ACM, 1984. — Т. 27.
• G. Davida. Chosen signature cryptanalysis of the RSA (MIT) public key cryptosystem. — Dept. of Electrical Engineering and Computer Science, Univ. of Wisconsin, 1982.