Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
544
Часть V. Методы формального доказательства стойкости
14.5.3 Строгая криптография
Строгая криптография (non-malleable cryptography — NM cryptography)! [100] — это криптография с открытым ключом, основанная на более сильных понятиях стойкости. Строгость является важным требованием, означающим, что Злоумышленник не должен иметь возможности легко модифицировать исходное сообщение, изменяя соответствующий зашифрованный текст. Долев (Dolev) с коллегами очень хорошо обосновали необходимость этого требования на примере аукциона.
Предположим, что муниципалитет пригласил строительные компании принять! участие в конкурсе на получение права построить новую школу. Городская администрация, широко применяющая электронные средства связи, обнародовала свой открытый ключ Е, используемый для шифрования заявок, и открыла свой почтовый ящик e-govGbid. for. it .gov. Компания А предложила 1 500000 долл., послав на почтовый ящик сообщение ?"(1 500000). Однако это электронное сообщение было перехвачено Злоумышленником, главой компании CheapSub, специализирующейся на заключении дешевых строительных контрактов. Если алгоритм шифрования является уязвимым, Злоумышленник может каким-либо образом трансформировать сообщение ?(1 500000) в ?(15 000000). Таким образом, шансы Злоумышленника на заключение контакта возрастают.
Простейшим примером уязвимого алгоритма шифрования является оцаорЛ вое заполнение (one-time pad). В части III показано, что все основные и nonynq ные функции шифрования с открытым ключом уязвимы.
В отличие от разнообразных атак на защиту неразличимости (IND), основан ных на задачах принятия решений, в основе гибких атак лежат вычислительны задачи.
Поскольку в ходе этой атаки целью Злоумышленника, получившего оклик с не является обучение, ему совершенно не обязательно знать параметр а. Однако для того, чтобы атака оказалась успешной, Злоумышленник должен вычислить "разумное" отношение R, связывающее расшифровки сообщений с* и с'.
Успех Злоумышленника выражается через преимущество. В работе [100] авторы для оценки преимущества использовали идею моделирования с нулевым разглашением.1 Во-первых, Злоумышленник, выполняющий РРТ-алгоритм, получает оклик с* = ?Pk(o>) и с определенной вероятностью вычисляет пару (?рк(Р), R Во-вторых, имитатор (simulator) ZK-Sim, представляющий собой РРТ-алгоритм, не получает оклик с*, но, как и Злоумышленник, вычисляет зашифрованный текст с с определенной вероятностью. (Имитатор даже игнорирует алгоритм шифрования и открытый ключ!) Преимущество Злоумышленника, организующего гибкук*
м,
'Доказательства с нулевым разглашением и полиномиальное моделирование таких доказательств будут рассмотрены в следующей главе.
Глава 14. Определения формальной и сильной стойкости криптосистем... 545
Протокол 14.5. Гибкая атака в режиме подбора исходных текстов
ПРЕДВАРИТЕЛЬНЫЕ УСЛОВИЯ:
Как и в протоколе 14.1, Злоумышленник и оракул О используют криптосистему ?, для которой оракул О имеет фиксированный ключ шифрования рк.
Злоумышленник и оракул О разыгрывают следующую атаку.
1. Злоумышленник посылает оракулу О вектор v, содержащий большое количество исходных текстов, и desc(u) — описание распределения исходных текстов v.
2. Оракул О создает правильный зашифрованный оклик с* = ?рк(а), где параметр а извлекается из генеральной совокупности исходных сообщений, подчиняющихся распределению текстов в векторе v. Оракул О посылает сообщение с* Злоумышленнику.
3. Получив сообщение с*, Злоумышленник должен вычислить "разумное" отношение R и другой корректный зашифрованный текст с1 — ?рк{13), удовлетворяющий условию R(a, j3) = 1.
атаку, оценивается следующим образом.
ATM — Adv — Prob[(?pfc(/3), R) <— Злоумышленник(?рд.(о!),р&, desc(u))]— - Prob[(c, R) <- ZK-Sim].
(14.5.3)
Криптосистема ?PkQ с параметром безопасности к называется строгой, если для всех полиномиально вычислимых отношений R и полиномиально ограниченных злоумышленников значение функции NM-Adv является пренебрежимо малой величиной по сравнению с числом к. В работе [100] это свойство называется "семантической стойкостью к атаке на основе подобранных открытых текстов с учетом отношений" ("semantic security with respect to relations under chosen-plaintext attack"). По этой причине оно сокращенно называется NM-CPA.
Свойство 14.2 (Стойкость NM-CPA). Преимущество Злоумышленника в ходе гибкой атаки на криптосистему NM-CPA на основе имеющегося зашифрованного текста по сравнению с имитацией этой атаки без такого текста увеличивается незначительно.
Поскольку обладание зашифрованным текстом не облегчает задачу взлома, Злоумышленнику следует пройти "курс обучения криптоанализу"! Как и атаки IND-CCA и IND-CCA2, гибкая атака также может быть облегченным вариантом атаки во время ленча и атаки пополуночи. В ходе гибкой атаки, организованной по
546
ЧИСТЬ V. теТОДЫ qjupiviculDnui и диг\аоатшчои ^..v.,,^,...
примеру атаки во время ленча, Злоумышленник может посылать оракулу О подобранные зашифрованные тексты для расшифровки, но эта возможность исчезает после запроса на получение оклика с*. В ходе гибкой атаки, организованной noi примеру атаки пополуночи, после получения оклика доступ к блоку расшифров-; ки не прекращается. Разумеется, Злоумышленник по-прежнему не имеет права пересылать оклик с* оракулу О для расшифровки.
