3.5 Методы анализа стойкости схем аутентификации

Основные требования к стойкости схем аутентификации хорошо формализуются посредством понятия доказательства с нулевым разглашением (см. главу 15). Отметим, однако, что здесь, как и всюду в криптографии, формальное математическое понятие стойкости не обеспечивает защиту против всех мыслимых нарушений и злоупотреблений. Наиболее ярким примером злоупотреблений, возможных в схемах аутентификации, являющихся доказательствами с нулевым разглашением, служит возможность организации во многих таких схемах подпороговых каналов.

Понятие доказательства с нулевым разглашением включает в себя три требования. Требование полноты, с практической точки зрения, означает, что если оба участника протокола -- доказывающий и проверяющий -- честные, то доказывающий всегда пройдет аутентификацию.

Требование корректности обеспечивает стойкость схемы в том случае, когда противник выступает в роли доказывающего, и, не зная секретного ключа, пытается пройти аутентификацию.

Свойство нулевого разглашения защищает доказывающего от противника, который, выступая в роли проверяющего, пытается в результате выполнения протокола получить какую-либо информацию о секретном ключе.

В принципе любой из предложенных в литературе протоколов доказательства с нулевым разглашением может использоваться в качестве схемы аутентификации. Проблемы, однако, возникают с эффективностью: большая длина секретного ключа, значительное (или даже растущее с возрастанием параметров схемы) количество раундов, недопустимо высокая коммуникационная сложность протокола (количество информации, пересылаемой между участниками), а иногда и слишком высокая вычислительная сложность.

При разработке схем аутентификации, предназначенных для практического применения, разработчики основное внимание уделяют их эффективности. Но затем, при попытке доказать их стойкость, как правило, возникают существенные трудности. Полнота во всех таких схемах тривиальным образом следует из конструкции самого протокола. Но уже с корректностью дело обстоит значительно сложнее. Большинство попыток доказательства корректности строится по следующей схеме: утверждается, что единственная возможность для противника, не владеющего секретным ключом, обмануть проверяющего, это -- угадать его запрос (т. е. значение, посылаемое проверяющим доказывающему в каждом раунде) еще до посылки первого сообщения в данном раунде. Из этого делается вывод, что вероятность обмана в каждом раунде обратно пропорциональна мощности множества, из которого выбирается запрос. Но такая посылка, вообще говоря, неверна! (Это специально подчеркивают Десмедт и Бурместр в тезисах конференции [Ober].) Поэтому корректность многих схем остается недоказанной. Безусловно доказанной можно считать корректность только тех схем аутентификации, для которых это доказательство состоит в демонстрации сводимости какой-либо вычислительно трудной задачи к задаче, стоящей перед противником. Например, Шнорр [Sch] доказал, что если в его схеме противник может обманывать проверяющего, то применяемый противником алгоритм можно использовать для вычисления дискретных логарифмов.

Доказать свойство нулевого разглашения для какого-либо протокола -- вообще задача нетривиальная. Для этого надо построить моделирующую машину, доказать, что она работает за полиномиальное в среднем время и доказать неотличимость создаваемого ею распределения вероятностей от распределения вероятностей в самом протоколе. Уже задача построения моделирующей машины, работающей за полиномиальное время, вызывает значительные трудности. Такую машину легко построить, если сильно ограничить мощность того множества, из которого проверяющий выбирает свои запросы. Это, однако, сказывается на корректности: уверенность проверяющего в том, что его не обманывают, тем выше, чем больше мощность этого множества. Иными словами, разработчик протокола может упростить здесь свою задачу за счет либо снижения корректности либо увеличения количества раундов.

Многие схемы аутентификации, такие как схема Фиата -- Шамира, описаны как многократное повторение одного и того же элементарного протокола. Для таких схем в литературе имеются наброски доказательств свойства нулевого разглашения, по которым можно восстановить полные доказательства. Однако, последовательное выполнение элементарных протоколов с практической точки зрения неприемлемо. А при параллельной композиции возникает другая проблема: из теории доказательств с нулевым разглашением известно, что при параллельной композиции свойство нулевого разглашения, вообще говоря, теряется.

С практической точки зрения, идеальный вариант схемы аутентификации -- это протокол доказательства с нулевым разглашением, выполняемый за 1.5 раунда (3 сообщения). Но Гольдрайх и Кравчик [GKr] доказали, что протоколов доказательства с нулевым разглашением, выполняемых за 1.5 раунда, у которых свойство нулевого разглашения устанавливается с помощью универсальной моделирующей машины (методом "черного ящика"), не существует. Поскольку иных методов доказательства свойства нулевого разглашения, кроме метода "черного ящика", неизвестно, этот результат ставит разработчиков схем аутентификации перед дилеммой: либо искать решение среди многораундовых, а значит, менее эффективных протоколов, либо разрабатывать 1.5-раундовые протоколы, но отказаться при этом от попыток доказательства их стойкости.