Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
б) Злоумышленник заранее приготовил несколько зашифрованных сообщений.
1. Злоумышленник посылает оракулу О заранее подготовленное зашифрованное сообщение с € С.
2. Оракул О расшифровывает сообщение с и возвращает результат расшифровки Злоумышленнику.
(* Сообщение с называется подобранным зашифрованным текстом (chosen-ciphertext) или индифферентным подобранным шифрованным текстом (indifferent chosen-ciphertext). Считается, что возврат результата расшифровки позволяет Злоумышленнику пройти "курс обучения криптоанализу". Злоумышленник может попросить об этой услуге, повторяя запросы столько, сколько захочет. Для ускорения процесса обучения он может даже использовать специальную программу. *)
3. Пройдя полный "курс обучения расшифровке", Злоумышленник предлагает оракулу О сыграть в игру CPA (протокол 14.1).
(* В этом варианте игры CPA подобранные исходные сообщения то и mi называются адаптивно подобранными зашифрованными текстами (adaptive chosen-plaintext). Иначе говоря, эти два сообщения могут зависеть от предыстории "курса обучения расшифровке", пройденного на этапах 1 и 2. Этап поиска начинается с первого пункта протокола и заканчивается получением зашифрованного оклика с* бС, который с одинаковой вероятностью может шифровать как сообщение то, так и сообщение mi из пространства Л4. *)
(* Резонно предположить, что Злоумышленник может вычислять адаптивно подобранные исходные сообщения, несмотря на ограниченное время атаки, поскольку создать исходное сообщение намного легче, чем зашифрованный текст. *)
(* Итак, ленч завершился. Теперь Злоумышленник должен угадать результаты жеребьевки оракула и послать число 0 или 1. Однако, несмотря на то, что игра закончена, Злоумышленник остается на этапе угадывания, пока не ответит на вопросы оракула. *)
538
Часть V. Методы формального доказательства стойкости
• Довольно часто во многих прикладных криптосистемах (в частности, в криптографических протоколах) пользователь (участник протокола), получивший запрос, должен выполнить расшифровку, используя свой закрытый ключ, и отослать результат обратно. Так работает механизм оклика-отзыва (см. главы 2 и 11).
• На практике многие пользователи безнадежно наивны и неспособны проявлять бдительность, чтобы предотвратить попытки взлома. Можно даже ска-1 зать, что самые строгие и стойкие криптосистемы разрабатываются именно' для наивных пользователей.
• Злоумышленник может внедрять запросы на расшифровку внутри нормальных и невинных сообщений, причем ответы он может получать так же неяв-1 но. Примеры 9.2 и 14.3 — яркое свидетельство этому. Такие атаки трудна отличить от обычных сеансов связи. Невозможно запретить пользователям] отвечать на зашифрованные запросы, поскольку это ограничивает возмож-1 ности для обмена секретными сообщениями.
• Злоумышленник может даже использовать обходной канал, как, например, в атаке на основе временного анализа (см. раздел 12.5.4), в ходе которой! Злоумышленник измеряет разницу между временными задержками.
Правильное отношение к Злоумышленнику — встретить его лицом к лицэд и предоставить ему возможность пройти "курс обучения криптоанализу" по erj требованию. Курс обучения может включать как шифрование, так и расшифровка целых блоков или отдельных битов. Стратегия такова: разрабатывать настоль! ко стойкие криптосистемы, чтобы "курс обучения криптоанализу" не давал Зло! умышленнику никаких преимуществ!
Повторяя рассуждения, приведенные в разделе 14.2, касающиеся оценки преимущества Злоумышленника при взломе криптосистемы в ходе атаки CPA (прото-j кол 14.1), можно оценить преимущество Злоумышленника в ходе атаки во время ленча.
Prob[l <— Злоумышленник^*,mo, mi,Hist-CCA) | с* - ?kd{mi)]
1 д j (14.5.1)
= - + Adv.
Итак, мы готовы сформулировать новое понятие стойкости, более сильное, чем понятие стойкости к атаке INA-CPA.
Определение 14.2 (Стойкость к атаке на основе неразличимых подобранных зашифрованных текстов (IND-CCA Security)). Криптосистема с параметром безопасности к называется стойкой к атаке на основе неразличимых подобран-) ных зашифрованных текстов (стойкой IND-CCA), если в результате атаки, описанной в протоколе 14.3, участником которой является произвольный полиноА миально ограниченный Злоумышленник, преимущество Adv. заданное фюрмулой (14.5.1), является пренебрежимо малой величиной по сравнению с параметром к.
Глава 14. Определения формальной и сильной стойкости криптосистем... 539
Поскольку в атаке во время ленча предполагается, что Злоумышленник может получить помощь при расшифровке сообщений (пройти "курс обучения криптоанализу"), новая атака должна упростить задачу криптоанализа. Следовательно, следует ожидать, что некоторые криптосистемы, считавшиеся стойкими к атаке IND-CCA, теперь станут уязвимыми.
Стойкость IND-CCA ни одной из криптосистем, описанных ранее в этой главе, не была доказана. Увы, среди них есть даже совершенно нестойкие*. В частности, к ним относится криптосистема Блюма-Голдвассера, основанная на применении эффективного CSPRB-генератора (раздел 14.3.6).
