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

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

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

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

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

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

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

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

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

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

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

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

В 1993 году японским криптоаналитиком Мицуру Мацуи был предложен метод линейного криптоанализа для вскрытия блочных шифров, таких как DES. В основе метода лежит построение линейных соотношений между открытым текстом, шифротекстом и ключом: ${\displaystyle 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}}}$,

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

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

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

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

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

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

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

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