Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
В' = (bi,b'2, ...,Ь'е),
где blt — дополнение к биту bj, г = 1,2,..., ?
Алисе этот результат расшифровки покажется набором случайных чисел, поэтому она вернет текст В' Злоумышленнику, который, в свою очередь, определит по нему текст В.
Используя вместо вектора (у,у,...,у) множитель Y = (у\,у2,...,уе), где Y — результат шифрования ^-битового кортежа Z — (zi, z2,..., ze) G [/{0,1}е с помощью алгоритма GM и открытого ключа Алисы, Злоумышленник может сделать текст В' не просто случайным, но и равномерно распределенным. Легко проверить, что
В = (bi © zi, Ь'2 © z2,..., Ь'е © ze) . п
В ходе этой атаки Алиса предоставляет Злоумышленнику "услуги оракула", помогая ему расшифровывать текст. Обратите внимание на то, что услуги оракула могут быть неявными. В примере 14.1 показано, что Алисе не следует отвечать на запросы Злоумышленника.
Пример 14.3. Допустим, что Алиса теперь не должна возвращать Злоумышленнику сообщения, которые выглядят как набор случайных цифр. Получив зашифрованное сообщение (ci, с2,..., q), посланное Бобом Алисе, Злоумышленник по-прежнему может распознать исходный текст бит за битом.
Например, для того, чтобы определить, какую цифру, 0 или 1, шифрует блок с\, Злоумышленник может послать Алисе зашифрованный вопрос, требующий однозначного ответа (ДА или НЕТ). Первую половину вопроса Злоумышленник может зашифровать, как обычно, а вторую — используя блок с\ вместо множителя у в алгоритме 14.1.
Если с\ б QRn, Алиса только первую половину сообщения расшифрует правильно, а вторая половина вопроса будет содержать одни нули. Следовательно, она будет вынуждена спросить у Злоумышленника, почему он послал неполное сообщение. Тогда Злоумышленник узнает, что блок с\ шифрует нуль. С другой стороны, если Алиса правильно отвечает на вопрос, Злоумышленник знает, что блок с\ является невычетом, и, следовательно, шифрует единицу.
Следует отметить, что в этой атаке Злоумышленник может даже сопровождать цифровой подписью все свои сообщения, направленные Алисе, чтобы убедить ее в своем авторстве. Иначе говоря, Злоумышленника невозможно обвинить в нарушении правил! ?
Анализ двух описанных выше атак показывает, что криптосистема GM безнадежно уязвима для активных атак, а семантическая стойкость является слабой.
536
Часть V. Методы формального доказательства стойкости
14.5 За рамками семантической стойкости
Эволюция принципа "все или ничего" (свойство 8.2 в разделе 8.2) до семантической стойкости (определение 14.1) представляет собой лишь первый шаг на пути усиления понятия стойкости криптосистем.
В разделе 14.4 было показано, что понятие семантической стойкости является недостаточно сильным для реальных приложений, в которых пользователи могут прибегать к услугам оракулов расшифровки. Действительно, трудно ожидать, что наивный пользователь реальных криптографических систем будет проявлять бдительность и отказываться отвечать на подозрительные запросы. Следовательно, необходимо предложить понятие более сильной стойкости.
Рассмотрим атаку на основе неразличимых подобранных зашифрованных текстов (indistinguishable chosen-ciphertext attack — IND-CCA). В рамках этой модели Злоумышленнику еще легче взломать атакованную криптосистему: кроме помощи при шифровании, предоставляемой в рамках протокола 14.1, Злоумышленник может прибегать к услугам оракула расшифровки. Формальное описание атаки IND-CCA основано на игре Наора (Naor) и Юнга (Yung) [210]. Эта игра называется атакой во время ленча (lunchtime attack) или атакой на основе индифферентных подобранных зашифрованных текстов (indifferent chosen-ciphertext attack).
14.5.1 Стойкость к атакам на основе подобранных зашифрованных текстов
Атака "во время ленча" описывает реальный сценарий, в котором Злоумыш-J ленник в отсутствие остальных сотрудников организации (например, во время ленча) посылает службе расшифровки сообщений запросы, надеясь таким образом пройти "курс обучения криптоанализу". Поскольку ленч проходит быстро, у Злоумышленника недостаточно времени для подготовки зашифрованных текстов так, чтобы ответы на запросы оказались связанными с определенной функцией. Следовательно, все шифрованные запросы, которые он посылает во время ленча, Злоумышленник должен приготовить заранее.
Этот реальный сценарий можно описать с помощью игры, в которой участвую^ те же персонажи, что и в игре IND-CPA (протокол 14.1): Злоумышленник (обиженный сотрудник организации) и оракул О — механизм расшифровки (и шифрования), обслуживающий организацию. Эта игра называется атакой на основе неразличимых подобранных зашифрованных текстов (IND-CCA).
На первый взгляд, атака во время ленча не слишком реалистична. Где найти такого простака, который согласился бы отвечать на запросы Злоумышленника? Ответить на этот вопрос можно следующим образом.
Глава 14. Определения формальной и сильной стойкости криптосистем... 537
Протокол 14.3. "Атака во время ленча" (атака на основе неадаптивно подобранных неразличимых зашифрованных текстов)
ПРЕДВАРИТЕЛЬНЫЕ УСЛОВИЯ:
а) Как и в протоколе 14.1, Злоумышленник и оракул О используют криптосистему ?, для которой оракул О имеет фиксированный ключ шифрования;
