Русская Википедия:Атака на основе подобранного открытого текста

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Атака на основе подобранного открытого текста (Шаблон:Lang-en, Шаблон:Lang-en2) — один из основных способов криптоаналитического вскрытия. Криптоаналитик обладает определённым числом открытых текстов и соответствующих шифротекстов, кроме того, он имеет возможность зашифровать несколько предварительно выбранных открытых текстовШаблон:Sfn.

Описание

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

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

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

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

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

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

Файл:Chosen-plaintext attack.png
Рис.1 Атака на основе подобранного открытого текста

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

Виды атак

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

  • автономная (Шаблон:Lang-en) — криптоаналитик подготавливает набор открытых текстов заранее, до получения шифрованных текстов.
  • оперативная или атака на основе адаптивно подобранного открытого текста (Шаблон:Lang-en) — криптоаналитик подбирает следующие открытые тексты на основе уже полученных шифротекстов. Так как при выборе последующих отправляемых на шифрование блоков учитываются предыдущие результаты, возникает обратная связь, которая даёт атаке на основе адаптивно подобранного открытого текста преимущество перед другими типами атак. Реализация атаки такого типа возможна, например, если криптоаналитик имеет доступ к шифрующему устройству в течение достаточно долгого времени, для осуществления анализа получаемых результатовШаблон:Sfn.

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

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

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

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

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

В истории

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

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

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

Примеры атак

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

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

Рассмотрим простой пример атаки на аффинный шифр, использующий латинские символы от 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

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

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

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

<math>\begin{cases} m\cdot7 + n \equiv 13 \ mod \ 26 \\ m\cdot0 + n \equiv 14 \ mod \ 26 \end{cases} </math>

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

Функция шифрования: <math>y = 11x + 14 \ mod \ 26. </math>Шаблон:Sfn

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

Шаблон:Main

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

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

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

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

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

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

где <math>P_n, C_n, K_n</math> — n-е биты текста, шифротекста и ключа, соответственно. Такие соотношения называются линейными аппроксимациями.

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

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

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

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

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

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

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

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

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

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

Примечания

Шаблон:Примечания

Литература

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Атака_на_основе_подобранного_открытого_текста&oldid=9048533