Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Повторяя рассуждения, приведенные в разделе 14.2, можно получить оценки преимущества Злоумышленника при взломе криптосистемы в ходе атаки пополуночи. Эта формула очень напоминает формулу (14.2.3), за исключением того, что Злоумышленник теперь вводит всю предысторию о двух предшествующих курсах обучения криптоанализу, один — для атаки ССА, а второй — для расширенной атаки ССА. Обозначим эту предысторию как Hist-CCA2. Тогда формула для преимущества Злоумышленника примет следующий вид.
РгоЬ[1 <— Злоумышленник^*, mo, mi, Hist-CCA2) | с* = ?ke(mi)] =
1 AJ (14-5.2) = - + Adv.
Теперь мы можем сформулировать новое, более строгое понятие стойкости.
Определение 14.3 (Стойкость к атаке на основе неразличимых адаптивно подобранных зашифрованных текстов (стойкость IND-CCA2)). Криптосистема с параметром безопасности к называется стойкой к атаке на основе неразличимых адаптивно подобранных зашифрованных текстов (стойкой к атаке IND-CCA2), если в результате атаки, описанной в протоколе 14.4, участником которой является произвольный полиномиально ограниченный Злоумышленник, преимущество Adv, заданное формулой (14.5.2), является пренебрежимо малой величиной по сравнению с параметром к.
542
Часть V. Методы формального доказательства стойкости
Протокол 14.4. "Атака пополуночи" (атака на основе адаптивно подобранных
неразличимых зашифрованных текстов)
ПРЕДВАРИТЕЛЬНЫЕ УСЛОВИЯ:
Как и в протоколе 14.1, Злоумышленник и оракул О используют криптосистему ?, для которой оракул О имеет фиксированный ключ шифрования.
1. Злоумышленник и оракул О разыгрывают атаку во время ленча (протокол 14.3).
(* В этой разновидности атаки во время ленча "этап поиска" совпадает с этапом поиска в протоколе 14.3. Он завершается тем, что Злоумышленник получает зашифрованный оклик с* G С, который с одинаковой вероятностью может шифровать как сообщение то, так и сообщение mi из пространства ЛЛ. Однако теперь Злоумышленник может продлить "этап угадывания". *)
2. Злоумышленник вычисляет зашифрованный текст d ? С и посылает его оракулу О для расшифровки.
(* Зашифрованный текст d называется адаптивно подобранным зашифрованным текстом (adaptive chosen-plaintext) или зашифрованным текстом, подобранным после получения оклика (post-challenge chosen ciphertexfju В отличие от него, зашифрованный текст, подобранный в ходе атаки во время ленча (протокол 14.3), называется зашифрованным текстом, подобранным до получения оклика (pre-challenge chosen ciphertext). Второй| этап представляет собой "расширенный курс обучения криптоанализу", ко* торый может повторяться столько, сколько будет угодно Злоумышленнику. * 1 (* Предполагается, что d ф с*, т.е. Злоумышленник не может посылатн зашифрованный оклик обратно для расшифровки. *)
3. Пройдя "расширенный курс обучения криптоанализу", Злоумышленник должен угадать результаты жеребьевки оракула и послать число 0 или 1.
Атаки на основе неразличимых зашифрованных текстов проиллюстрированы на рис. 14.1.
Поскольку в ходе атаки пополуночи Злоумышленник проходит "расширенный курс обучения криптоанализу", задача взлома по сравнению с атакой во время ленча должна упроститься. Таким образом, следует ожидать, что криптосистемы^ стойкие к атаке IND-CCA, могут оказаться уязвимыми для атаки IND-CCA2. Фак4 тически, за исключением алгоритма RSA-OAEP (см. алгоритм 10.6), ни одна ия\ криптосистем, описанных в книге, до сих пор не обладает доказанной стойко* стью к атаке IND-CCA2. Мы продемонстрировали большое количество примеров*
Глава 14. Определения формальной и сильной стойкости криптосистем... 543
Индифферентно подобранные зашифрованные тексты
3 л 0 Расшифровки
У м т0,т1 О
ы ш л Е н н с* р А
Адаптивно подобранные зашифрованные тексты К У Л
Расшифровки
и
к Осмысленное угадывание: 0 или 1
}
АТК = CCA, ССА2
}
АТК = ССА2
Рис. 14.1. Атаки на основе неразличимых зашифрованных текстов
криптосистем, уязвимых как к атаке ССА2, т.е. по принципу "все или ничего", так и к атаке IND-CCA2 (см. примеры 8.5, 8.7, 8.9, 9.2, 14.2 и 14.3).
Введя понятие стойкости к атаке IND-CCA2, Раков и Симон предложили криптосистемы, основанные на неинтерактивном доказательстве с нулевым разглашением (доказательство NIZK). Однако они рассмотрели доказательство NIZK с конкретным средством доказательства (specific prover). В их криптосистеме парой, состоящей из открытого и закрытого ключа, обладал не только получатель, но и отправитель сообщения. Более того, открытый ключ отправителя сертифицировался с помощью инфраструктуры сертификации открытых ключей (см. раздел 13.2). Для того чтобы зашифровать сообщение, отправитель использовал не только открытый ключ получателя, что вполне привычно, но и свой собственный закрытый ключ, позволяющий создать доказательство NIZK так, чтобы получатель зашифрованного текста мог проверить его, используя открытый ключ отправителя. Передача доказательства NIZK означала, что исходный текст был создан именно данным отправителем, а значит, возвращение исходного текста не дает ему никакой новой информации, позволяющей взломать криптосистему. Криптосистема Ракова и Симона также выполняет все операции побитово.