Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Пример 14.4. Для того чтобы организовать атаку на криптосистему BG во время ленча, Злоумышленник должен подобрать запрос в виде зашифрованного текста (с,т), где с — квадратичный вычет по модулю N, а \т\ = [log2log2J. Анализируя криптосистему BG, описанную в разделе 14.3.6, легко определить, что в ответ на свой запрос Злоумышленник получит следующую расшифровку.
т ® "[log2 log2 N\ младших битов квадратного корня числа с по модулю N".
Применяя к ответу побитовую операцию XOR, Злоумышленник получит [log2 log2 N\ младших битов квадратного корня числа с по модулю N. Напомним, что число с представляет собой модуль N, являющийся квадратичным вычетом. Учитывая замечание 9.1 (раздел 9.3.1), приходим к выводу, что знание |k)g2log2 N\ младших битов квадратного корня числа с по модулю N дает Злоумышленнику возможность разложить модуль N на простые множители за полиномиальное время! ?
Пример 14.4 демонстрирует, что курс криптоанализа, который проходит Злоумышленник, резко увеличивает вероятность взлома криптосистемы. Последствия взлома являются чрезвычайно тяжкими, поскольку Злоумышленник может раскрыть не просто отдельный шифрованный текст, но и разрушить всю криптосистему в целом.
Таким образом, нами абсолютно точно доказана нестойкость криптосистемы BG к атаке rND-CCA. Это напоминает нестойкость криптосистемы Рабина в рамках подхода "все или ничего" (теорема 8.2 в разделе 8.11).
Наор и Юнг предложили криптосистему, обладающую доказуемой стойкостью к атаке IND-CCA [210]. В этой криптосистеме исходное сообщение поби-тово шифруется в виде двух текстов с помощью двух разных ключей. Алгоритм шифрования содержит процедуру неинтерактивного доказательства с нулевым разглашением (non-interactive zero-knowledge — NIZK), позволяющую отправителю исходного сообщения доказать, что два зашифрованных текста действительно содержат один и тот же бит, зашифрованный разными открытыми ключами. (Считается, что алгоритм шифрования, на вход которого поступает исходный тест
540
Часть V. Методы формального доказательства стойкости
и случайное число, представляет собой NP-задачу (см. раздел 4.8.1)). Это доказательство проверяется во время расшифровки (например, оракулом О, принимающим участие в атаке во время ленча). Применение процедуры верификации во время расшифровки основано на предположении, что пара зашифрованных сообщений уже известна отправителю (например, Злоумышленнику в ходе атаки во время ленча). Таким образом, обслуживание Злоумышленника во время ленча не дает ему никаких новых знаний, облегчающих криптоанализ. Вследствие довольно высокой стоимости процедуры неинтерактивного доказательства с нулевым разглашением (верификации) и побитового шифрования (расшифровки) криптосистема Наора и Юнга не получила практического применения.
Атака во время ленча является довольно ограниченной моделью, поскольку помощь, получаемая Злоумышленником при расшифровке, доступна лишь в течение короткого периода. Это выглядит так, будто "блок расшифровки" по окончании ленча каждый раз отключается или Злоумышленник не может ничего поделать даже во время ленча на следующий день. Это совершенно нереалистичный сценарий. На практике наивные пользователи всегда остаются наивными, и Злоумышленник способен нанести ответный удар, даже если для этого придется использовать обеденный перерыв на следующий день! Таким образом, стойкость к атаке IND-CCA не является сильной.
14.5.2 Стойкость к атаке на основе адаптивно подобранных зашифрованных текстов
Рассмотрим атаку на основе неразличимых адаптивно подобранных зашифрованных текстов (IND-CCA2), предложенную Раковым (Rackoff) и Симоном (Simon) [241].
В этой атаке перед Злоумышленником стоит более простая задача. В атаке во| время ленча (см. протокол 14.3) помощь в расшифровке ("курс обучения криптоанализу") прекращалась, как только Злоумышленник посылал пару адаптивно подобранных исходных сообщений. Иначе говоря, атака во время ленча прекращалась сразу после завершения игры IND-CCA (т.е. протокола 14.1).
В новой модели это нереалистичное условие было снято. Теперь Злоумышленник может получать помощь при расшифровке сообщений как до, так и после атаки, организованной во время ленча. Таким образом, новый сценарий можно рассматривать как атаку во время очень долгого перерыва, например, ночью. По этой причине эту атаку называют атакой пополуночи (small-hours attack). Это название отражает реальный сценарий, в рамках которого Злоумышленник, например, обиженный сотрудник или конкурирующая фирма, остается на ночь и вступает в контакт с механизмом расшифровки сообщений. Следует заметить, что атака пополуночи отличается от полуночной атаки (midnight attack), кото-
Глава 14. Определения формальной и сильной стойкости криптосистем... 541
рая в литературе часто упоминается как синоним атаки во время ленча. Почему-то считается, что охранники должны ужинать в полночь.
Поскольку теперь Злоумышленник не ограничен во времени, он может организовать более сложную и интересную игру с механизмом расшифровки. Кроме того, что он мог делать в ходе атаки во время ленча (или в полночь), т.е. создавать адаптивно подобранные запросы, содержащие исходный текст, используя информацию, полученную в рамках курса обучения криптоанализу, и получать зашифрованный оклик, Злоумышленник теперь может посылать адаптивно подобранные зашифрованные сообщения после получения оклика. Следовательно, адаптивно подобранные зашифрованные сообщения могут быть каким-то образом связанными с окликом или соответствующим исходным текстом. Разумеется, механизм расшифровки достаточно разумен, чтобы не расшифровывать оклик, посланный Злоумышленнику! Это единственное и вполне обоснованное ограничение. Без него Злоумышленник мог бы просто попросить блок расшифровки расшифровать оклик и не организовывать сложную игру! С другой стороны, блок расшифровки достаточно глуп, чтобы расшифровать текст, связанный с окликом! Блок не распознает любое изменение оклика, например, умножение на два или добавление единицы, и расшифровывает измененное сообщение!
