Атака с выбранным открытым текстом

Модель атаки для криптоанализа с предполагаемым доступом к зашифрованным текстам для выбранных открытых текстов

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

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

Введение

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

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

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

Существует две формы атак с использованием выбранного открытого текста:

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

Общий метод атаки

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

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

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

1. Злоумышленник выводит два открытых текста m ₀ и m ₁ .
2. Бит b выбирается равномерно случайным образом . ${\displaystyle b\leftarrow \{0,1\}}$
3. Злоумышленник получает шифрование m _b и пытается «угадать», какой открытый текст он получил, и выводит бит b' .

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

Примеры

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

шифр Цезаря

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

1. Предположим, противник отправляет сообщение: Attack at dawn,
2. и оракул возвращается Nggnpx ng qnja.
3. Затем злоумышленник может попытаться восстановить ключ так же, как и шифр Цезаря. Противник может вывести замены A→N , T→G и так далее. Это приведет к тому, что злоумышленник определит, что 13 — это ключ, используемый в шифре Цезаря.

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

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

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

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

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

На практике

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

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

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

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

Связь с другими атаками

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

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

Рекомендации

1. Росс Андерсон, Инженерия безопасности: Руководство по созданию надежных распределенных систем . Первое издание (2001 г.): http://www.cl.cam.ac.uk/~rja14/book.html.
2. Баррера, Джон Фреди; Варгас, Карлос; Тебальди, Мириан; Торроба, Роберто (15 октября 2010 г.). «Атака с использованием выбранного открытого текста на систему шифрования коррелятора совместного преобразования». Оптические коммуникации . 283 (20): 3917–3921. Бибкод : 2010OptCo.283.3917B. doi : 10.1016/j.optcom.2010.06.009. ISSN  0030-4018.
3. Кац, Джонатан ; Линделл, Иегуда (2007). Введение в современную криптографию: принципы и протоколы . Бока-Ратон: Чепмен и Холл/CRC. ISBN 978-1584885511. ОСЛК  893721520.
4. Уидон, Патрик Д. «Как криптология позволила Соединенным Штатам переломить ход войны на Тихом океане». www.navy.mil . ВМС США. Архивировано из оригинала 31 января 2015 г. Проверено 19 февраля 2015 г.
5. Моррис, Кристофер (1993), «Плохие отношения Navy Ultra», в Хинсли, FH ; Стрип, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-Парка , Оксфорд: Oxford University Press, стр. 235, ISBN 978-0-19-280132-6
6. Келли, Джон (27 января 2011 г.). «Клочок бумаги, который обманул Гитлера». Би-би-си . Проверено 1 января 2012 г. Нацисты полагали, что Пужоль, которого они называли Аларик Арабель, был одним из их ценных активов.
7. Моряк (2004). «Первый код, который немцы дали Гарбо для его беспроводной связи, оказался идентичным коду, который в настоящее время используется в немецких сетях»

Послушайте эту статью ( 11 минут )

Этот аудиофайл был создан на основе редакции этой статьи от 28 декабря 2023 года и не отражает последующие изменения. ( 2023-12-28 )

( Аудио помощь  · Больше устных статей )