Определения безопасности и модели злоумышленников

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

Definition

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

Scope

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

Core questions

• Почему цели безопасности должны быть определены точно, а не интуитивно?
• Что отличает цели конфиденциальности (семантическая безопасность) от целей целостности (неподделываемость)?
• Как модели атак (CPA, CCA, адаптивные) отражают возможности злоумышленника?
• Как игровые определения и определения «идеал/реальность» выражают безопасность?
• Почему схема, доказуемо безопасная в своей модели, все же может быть уязвима для реальных атак, таких как побочные каналы?

Key concepts

• семантическая безопасность
• неразличимость шифротекста (IND)
• атака по выбранному открытому тексту (CPA)
• атака по выбранному шифротексту (CCA)
• экзистенциальная неподделываемость
• адаптивные злоумышленники
• игровые определения
• парадигма «идеал/реальность»
• разрыв побочных каналов

Key theories

Семантическая безопасность и неразличимость

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

Модели атак и возможности злоумышленника

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

Mechanisms

Определение, основанное на игре, противопоставляет челленджера злоумышленнику: для безопасности IND-CPA злоумышленник отправляет два сообщения, челленджер случайным образом шифрует одно из них, и безопасность требует, чтобы злоумышленник не мог угадать, какое именно, с вероятностью, превышающей случайную. Более сильные определения CCA также предоставляют злоумышленнику оракул дешифрования. Парадигма «идеал/реальность» вместо этого считает схему безопасной, если взаимодействие с ней неотличимо от взаимодействия с идеализированной доверенной функциональностью. Реальные злоумышленники могут использовать утечки по времени или мощности вне этих моделей, что мотивирует определения, учитывающие побочные каналы.

Clinical relevance

Выбор правильного определения имеет большое значение: шифрование, используемое в интерактивных протоколах, требует безопасности CCA, а не только CPA, а атаки с использованием оракула заполнения на реальные системы (такие как ранние версии TLS) напрямую были результатом развертывания схем, которые соответствовали слишком слабому определению. Модели злоумышленников также проясняют, от чего развертывание не защищает — например, модели, игнорирующие побочные каналы, объясняют, почему атаки по времени и мощности успешны против в остальном «безопасных» реализаций.

Evidence & guidelines

Современные стандарты требуют, чтобы схемы соответствовали строгим определениям: аутентифицированное шифрование (IND-CCA плюс целостность) является стандартом для конфиденциальности, а подписи должны быть экзистенциально неподделываемыми при адаптивной атаке по выбранному сообщению. Фреймворк универсальной композиции (Universal Composability) предоставляет определения, которые остаются безопасными при произвольной композиции. Реализации дополнительно требуют кодирования, устойчивого к побочным каналам (с постоянным временем выполнения), помимо формальной модели.

History

До 1980-х годов безопасность оценивалась неформально. Семантическая безопасность Гольдвассер и Микали (1982–1984) ввела строгие определения, основанные на неразличимости, вскоре расширенные до моделей выбранного шифротекста и до неподделываемости для подписей и MAC. Парадигма моделирования «идеал/реальность» и фреймворк универсальной композиции Каннети (2001) рассмотрели безопасность при композиции, завершив основу определений, которая теперь регулирует весь серьезный криптографический анализ.

Key figures

• Shafi Goldwasser
• Silvio Micali
• Oded Goldreich
• Ran Canetti
• Mihir Bellare

Seminal works

• goldwasser1984
• katz2020
• goldreich2004

Frequently asked questions

В чем разница между безопасностью CPA и CCA?

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

Если схема доказуемо безопасна, почему работают атаки по побочным каналам?

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