Атака с использованием выбранного открытого текста

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

Атака с выбранным открытым текстом ( 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' .

Шифр имеет неразличимые шифрования при атаке с выбранным открытым текстом , если после проведения вышеуказанного эксперимента противник не может угадать правильно ( 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» может быть островом Мидуэй , потому что другие места на Гавайских островах имели кодовые слова, начинающиеся с «A». Чтобы доказать свою гипотезу о том, что «AF» соответствует «острову Мидуэй», они попросили американские войска на Мидуэе отправить текстовое сообщение о низком уровне запасов. Японцы перехватили сообщение и немедленно сообщили своим начальникам, что «AF» имеет низкий уровень воды, что подтвердило гипотезу ВМС и позволило им расположить свои силы так, чтобы выиграть битву . [ ^{3] [4]}

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

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

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

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

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

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

Смотрите также

• GMR (криптография)

Ссылки

1. Росс Андерсон, Security Engineering: A Guide to Building Dependable Distributed Systems . Первое издание (2001): http://www.cl.cam.ac.uk/~rja14/book.html
2. Баррера, Джон Фреди; Варгас, Карлос; Тебальди, Мириан; Торроба, Роберто (15.10.2010). «Атака с выбранным открытым текстом на систему шифрования с коррелятором совместного преобразования». Optics Communications . 283 (20): 3917–3921. Bibcode : 2010OptCo.283.3917B. doi : 10.1016/j.optcom.2010.06.009. ISSN  0030-4018.
3. Katz, Jonathan ; Lindell, Yehuda (2007). Введение в современную криптографию: принципы и протоколы . Boca Raton: Chapman and Hall/CRC. ISBN 978-1584885511. OCLC  893721520.
4. Уидон, Патрик Д. «Как криптология позволила Соединенным Штатам переломить ход войны на Тихом океане». www.navy.mil . ВМС США. Архивировано из оригинала 2015-01-31 . Получено 2015-02-19 .
5. Моррис, Кристофер (1993), «Плохие отношения Navy Ultra», в Хинсли, Ф. Х.; Стрип, Алан (ред.), Взломщики кодов: внутренняя история Блетчли-парка , Оксфорд: Oxford University Press, стр. 235, ISBN 978-0-19-280132-6
6. Келли, Джон (27 января 2011 г.). «Кусок бумаги, который обманул Гитлера». BBC . Получено 1 января 2012 г. Нацисты считали, что Пухоль, которого они называли Алариком Арабель, был одним из их ценных активов.
7. Seaman (2004). «Первый код, который немцы дали Гарбо для его беспроводной связи, оказался идентичным коду, который в то время использовался в немецких сетях».

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

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

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