Что означает экзистенциальная невозможность подделки в схеме цифровой подписи?

В схеме цифровой подписи (Gen, Sign, Verfiy), которая удовлетворяет требованиям правильности и экзистенциальной невозможности подделки, можете ли вы предположить, что выходные данные Sign() вычислительно неотличимы от случайных?

Что означает экзистенциальная невозможность подделки в схеме цифровой подписи?

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

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

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

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

Обычно экзистенциальная подделка может быть распространена на осмысленные сообщения или использована каким-либо коварным образом (например, переполнение буфера, отказ в обслуживании или внедрение кода). Также часто злоумышленники могут влиять на подписываемые сообщения в достаточной степени, чтобы сделать атаку возможной, даже если она не квалифицируется как полноценная атака с выбранным сообщением. Существует также опасность того, что злоумышленники просто притворятся, что другие злоумышленники нарушили безопасность, подорвав доверие к системе. Таким образом, стало базовым требование к Existential UnForgeability при атаке с выбранным сообщением (EUF-CMA). Это адекватно защищает от изменения сообщения без одобрения держателя открытого ключа.

я имею в виду этот ответ для более формальной таксономии вариантов UF.

Лучшая практика для современных схем подписи: сильный EUF-CMA, плюс Сигнатурная устойчивость к столкновениям, и Универсальное эксклюзивное право собственности. См. Денниса Джексона, Каса Кремерса, Катриэль Кон-Гордон и Ральфа Сассе: Кажется законным: автоматический анализ скрытых атак на протоколы, использующие сигнатуры, в Cryptology ePrint Archive, отчет 2019/779, изначально в материалах ACM CCS 2019.

В схеме цифровой подписи (Gen, Sign, Verfiy), которая удовлетворяет требованиям правильности и экзистенциальной невозможности подделки, можете ли вы предположить, что выходные данные Sign() вычислительно неотличимы от случайных?

Нет. Например РСАССА-ПСС доказуемо sEUF-CMA, но его подписи можно отличить от случайных (путем проверки старшего бита первого байта неукрашенной подписи, которая смещена в сторону 0, если только открытый ключ не имеет много старших битов в 1 или/ и что-то в процедуре подписи создано, чтобы сделать такую ​​предвзятость менее заметной, что легко, но необычно). Это даже без открытого ключа или сообщения. Очевидно, что если открытый ключ и сообщение известны, никакая правильная схема подписи не может иметь подпись, неотличимую от случайной; верификатор - отличитель!

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

1. Атака только с ключом (EU-KOA): Неформально противник имеет только открытый ключ и может выбрать любое сообщение для подделки подписи после получения открытого ключа.

$(pk,sk)\leftarrow Gen$

Беги противника $А(пк,1^п)$

Получить ответ $(м,с) $ как пара подписей сообщения для противника

2. Атака известными сообщениями (EU-KMA): Неформально злоумышленник имеет доступ ко многим парам сообщений, подписей вместе с открытым ключом, который он может использовать в качестве информации для подделки подписи любого другого сообщения.

$(pk,sk)\leftarrow Gen$

Беги противника $А(пк,1^п)$

Создать $m_1,m_2...m_k$ сообщения и подписывайте их все. Отправка пар сообщение-подпись $(m_1,s_1),(m_2,s_2)...(m_k,s_k)$

Получить ответ $(м,с) $ как пара подписей сообщения для противника, где $m \notin {m_1,m_2..m_k}$

3. Атака с выбранным сообщением (CMA): неформально злоумышленник может получать подписи для сообщений по своему выбору. Мы моделируем это, предоставляя злоумышленнику доступ к подписывающему оракулу. $(pk,sk)\leftarrow Gen$

Беги противника $A(pk,1^n,O^{sk})$ Здесь $О^{ск}$ подписывает оракула

Враждебные запросы $m_1,m_2...m_k$ сообщения $О^{ск}$ и получить подписи. Сообщения могут быть выбраны адаптивно. Злоумышленник получает пары сообщение-подпись $(m_1,s_1),(m_2,s_2)...(m_k,s_k)$

Получить ответ $(м,с) $ как пара подписей сообщения для противника, где $m \notin {m_1,m_2..m_k}$

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

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