Атака по выбранному открытому тексту - Chosen-plaintext attack

А атака с выбранным открытым текстом (CPA) является модель атаки для криптоанализ что предполагает, что злоумышленник может получить шифртексты для произвольных открытые тексты.[1] Цель атаки - получить информацию, которая снижает безопасность схемы шифрования.

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

Введение

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

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

Различные формы

Есть две формы атак с выбранным открытым текстом:

  • Пакетная атака по выбранному открытому тексту, где злоумышленник выбирает все открытые тексты до того, как увидит какой-либо из соответствующих зашифрованных текстов. Это часто подразумевается под «атакой по выбранному открытому тексту», когда это не определено.
  • Адаптивная атака по выбранному открытому тексту (CPA2), где злоумышленник может запросить зашифрованные тексты дополнительных открытых текстов после просмотра зашифрованных текстов некоторых открытых текстов.

Общий способ атаки

Обычная пакетная атака с использованием выбранного открытого текста выполняется следующим образом[неудачная проверка ]:

  1. Злоумышленник может выбрать п открытые тексты. (Этот параметр п указывается как часть модель атаки, он может быть или не быть ограниченным.)
  2. Затем злоумышленник отправляет эти п открытые тексты к оракулу шифрования.
  3. Затем оракул шифрования зашифрует открытые тексты злоумышленника и отправит их обратно злоумышленнику.
  4. Атакующий получает п возвращает зашифрованный текст от оракула таким образом, чтобы злоумышленник знал, какой зашифрованный текст соответствует каждому открытому тексту.
  5. На основе пар открытый текст-зашифрованный текст злоумышленник может попытаться извлечь ключ, используемый оракулом для кодирования открытых текстов. Поскольку злоумышленник в этом типе атаки может свободно создавать открытый текст в соответствии со своими потребностями, сложность атаки может быть уменьшена.

Рассмотрим следующее расширение вышеупомянутой ситуации. После последнего шага

  1. Противник выводит два открытых текста м0 и м1.
  2. Немного б выбирается равномерно случайным образом .
  3. Противник получает шифрование мб, и пытается "угадать", какой открытый текст он получил, и выводит бит б '.

Шифр имеет неразличимое шифрование при атаке с выбранным открытым текстом если после проведения вышеуказанного эксперимента с п=1[неудачная проверка ] противник не может правильно угадать (б=б ') с вероятностью не-незначительно лучше 1/2.[2]

Примеры

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

Шифр цезаря

Следующая атака на Шифр цезаря позволяет полностью восстановить секретный ключ:

  1. Предположим, злоумышленник отправляет сообщение: Атака на рассвете,
  2. и оракул возвращается Nggnpx ng qnja.
  3. Затем злоумышленник может восстановить ключ так же, как вы расшифровываете шифр Цезаря. Противник мог вывести замены А → N, Т → г и так далее. Это привело бы к тому, что противник определил, что 13 было ключом, используемым в шифре Цезаря.

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

Одноразовые колодки

Следующая атака на одноразовый блокнот позволяет полностью восстановить секретный ключ. Предположим, длина сообщения и длина ключа равны п.

  1. Противник отправляет строку, состоящую из п нули к оракулу.
  2. Оракул возвращает побитовый Эксклюзивный или ключа со строкой нулей.
  3. Строка, возвращаемая оракулом является секретный ключ.

В то время как одноразовый блокнот используется как пример теоретически безопасный криптосистема, эта безопасность сохраняется только при более слабых определениях безопасности, чем безопасность CPA. Это связано с тем, что согласно формальному определению безопасности CPA оракул шифрования не имеет состояния. Эта уязвимость может быть применима не ко всем практическим реализациям - одноразовый блокнот все же можно сделать безопасным, если избежать повторного использования ключа (отсюда и название «одноразовый блокнот»).

На практике

В Вторая Мировая Война Криптоаналитики ВМС США обнаружили, что Япония планировала атаковать место, называемое «AF». Они считали, что "AF" может быть Остров Мидуэй, потому что другие места в Гавайские острова были кодовые слова, начинающиеся с "А". Чтобы доказать свою гипотезу о том, что «AF» соответствует «Острову Мидуэй», они попросили войска США в Мидуэй отправить текстовое сообщение о нехватке запасов. Японцы перехватили сообщение и немедленно сообщили своему начальству, что "ВС" мало на воде, что подтвердило гипотезу ВМФ и позволило им разместить свои силы для победы боевой.[2][3]

Также во время Вторая Мировая Война, Союзные дешифровщики на Bletchley Park иногда спрашивал королевские воздушные силы установить мины на позиции, для которой не было сокращений или альтернатив в системе координат немецкой военно-морской системы. Была надежда, что немцы, увидев мины, воспользуются Энигма машина чтобы зашифровать предупреждающее сообщение о минах и сообщение «все очищено» после того, как они были удалены, давая союзникам достаточно информации о сообщении, чтобы взломать немецкую военно-морскую Энигму. Этот процесс посадка известный открытый текст был вызван садоводство.[4] Взломщики кодов союзников также помогли создать сообщения, отправленные двойным агентом. Хуан Пухоль Гарсия, чьи зашифрованные радиоотчеты были получены в Мадриде, расшифрованы вручную, а затем повторно зашифрованы с помощью Энигма машина для передачи в Берлин.[5] Это помогло дешифровщикам расшифровать код, использованный на второй ветви, предоставив исходный текст.[6]

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

Для некоторых атак с выбранным открытым текстом злоумышленнику может потребоваться выбрать только небольшую часть открытого текста; такие атаки известны как атаки с использованием инъекции открытого текста.

Отношение к другим атакам

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

Однако атака с использованием выбранного открытого текста менее эффективна, чем атака. атака по выбранному зашифрованному тексту, где злоумышленник может получить открытые тексты произвольных зашифрованных текстов. CCA-злоумышленник иногда может взломать систему безопасности CPA.[2] Например, Шифр Эль Гамаля защищен от атак с выбранным открытым текстом, но уязвим для атак с выбранным зашифрованным текстом, потому что он безусловно податливый.

использованная литература

  1. ^ Росс Андерсон, Разработка безопасности: руководство по созданию надежных распределенных систем. Первое издание (2001 г.): http://www.cl.cam.ac.uk/~rja14/book.html
  2. ^ а б c Кац, Джонатан; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы. Бока-Ратон: Чепмен и Холл / CRC. ISBN  978-1584885511. OCLC  893721520.
  3. ^ Уидон, Патрик Д. «Как криптология помогла Соединенным Штатам переломить ход войны на Тихом океане». www.navy.mil. ВМС США. Архивировано из оригинал на 2015-01-31. Получено 2015-02-19.
  4. ^ Моррис, Кристофер (1993), "Плохие отношения военно-морского флота", в Хинсли, Ф.; Стрипп, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-парка, Oxford: Oxford University Press, стр. 235, г. ISBN  978-0-19-280132-6
  5. ^ Келли, Джон (27 января 2011 г.). «Бумага, которая обманула Гитлера». BBC. Получено 1 января 2012. Нацисты считали Пужоль, которого они кодируют по имени Аларик Арабель, был одним из своих призовых активов.
  6. ^ Моряк (2004). «Первый код, который Гарбо был дан немцами для его беспроводной связи, оказался идентичным кодом, который в настоящее время используется в немецких сетях».