Схема аутентификации Шнорра

Одним из наиболее эффективных практических протоколов аутентификации считаеся протокол Шнорра.

Пусть

Ø р и q — простые числа такие, что q делит р -1.

(Шнорр предлагает использовать р длины порядка 512 бит и q — длины порядка 140 битов.)

Ø g ÎZ _p таково, что g^q = 1 mod р, g ¹ 1.

Ø х ÎZ _q — секретный ключ

Ø у = g^x mod p — открытый ключ.

Определение х по у - это задача дискретного логарифмирования, для которой на данный момент не известны эффективные алгоритмы.

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

В протоколе Шнорра количество раундов равно трем. Приведем алгоритм протокола по шагам:

1. В качестве секретного ключа схемы аутентификации Алиса выбирает случайное число k из множества {1,..., q — 1}, вычисляет открытый ключ r = g^k mod p и посылает r Бобу.

2. Боб выбирает случайный запрос е из множества {0,..., 2^t - 1}, где t — некоторый параметр, и посылает е Алисе.

3. Алиса вычисляет s = k + хе mod q и посылает s Бобу.

Боб проверяет соотношение r = g^sy^e mod p и, если оно выполняется, принимает доказательство, в противном случае — отвергает.

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

Несложный анализ показывает, что корректность протокола Шнорра зависит от выбранного значения параметра t. В самом деле, если t невелико, то противник имеет хорошие шансы просто угадать тот запрос е, который он получит от Боба на шаге 2.

Пусть для простоты t = 1. Тогда противник, не знающий секретного ключа х, может действовать следующим образом. Подбросив монету, он выби­рает равновероятным образом одно из значений 0 или 1. Обозначим его через е'. Далее противник выбирает произвольное s из {0 ,..., q- 1}, вы­чис­ляет  mod p и посылает r Бобу. Ясно, что запрос е, полученный от Боба на шаге 2, совпадет с е' с вероятностью 1/2, и именно с такой вероятностью противник пройдет аутентификацию. Если же значение t достаточно велико, то шансы угадать запрос е малы. Шнорр [1] рекомендует t = 72. Вероятность простого угадывания будет 2^-72, ее можно считать пренебрежимо малой.

Если в схеме Шнорра Алиса является противником, то на шаге 1 вместо действий, предписанных протоколом, она может выбирать r произвольным (но эффективным) образом. Иными словами, Алиса ис­пользует некоторый полиномиальный вероятностный алгоритм, кото­рый для каждого конкретного значения r определяет вероятность его выбора.

Пусть r — некоторое значение, которое Алиса передала Бобу на шаге 1. Предположим, что нам удалось найти два запроса

e₁,e₂ Î {0,...,2^t-1}, e₁¹e₂,

такие, что Алиса может для каждого из них найти соответствую­щие значе­ния s, для которых проверка на шаге 4 даст положительный результат. Обоз­начим эти значения s через s₁ и s₂ соответственно. Мы имеем:

r = g^sly^el mod p,

r = g^s2y^e2 mod p.

Отсюда

(g^sly^el = g^s2y^e2 ) mod p, или (g^sl-s2 = g^e2-el  ) mod p.

Поскольку e₁ ¹ е₂, существует (е₁ – e₂)^-1 mod q и, следовательно,

(s₁-s₂)(e₂-e₁) ^-1 mod q = х — дискретный логарифм у.

Таким образом, либо запросы e₁ ¹ е₂, такие, что Алиса может ответить надлежащим образом на оба из них (при одном и том же r) на шаге 3 про­токола, встречаются «достаточно редко», и это означает, что атака Алисы успешна лишь с пренебрежимо малой вероятностью, либо такие значения попадаются «достаточно часто», и тогда тот алго­ритм, который применяет Алиса, можно использовать для вычисления дискретных логарифмов.

Эта неформально изложенная идея была использована Шнорром [1] для доказательства полиномиальной сводимости задачи дискретного логариф­мирования к задаче, стоящей перед пассивным противником, т. е. таким, который пытается пройти аутентификацию, зная лишь откры­тый ключ. Иными словами, доказано, что в предположении трудности задачи диск­рет­ного логарифмирования схема аутентифи­кации Шнорра является стойкой против пассивного противника, т. е. корректной.

Активный противник может провести некоторое количество сеан­сов выполнения протокола в качестве проверяющего с честным доказыва­ющим (или подслушать такие выполнения) и после этого попытаться ата­ковать схему аутентификации. Для стойкости против активного против­ни­ка достаточно, чтобы протокол аутентификации был доказательством с ну­левым разглаше­нием. Однако свойство нулевого разглашения для схемы Шнорра до сих пор никому доказать не удалось. Более того, на данный мо­мент известен единственный метод доказательства свойства нулевого раз­гла­шения — так называемый метод «черного ящика». В этом методе моде­ли­рующая машина использует алгоритм проверяющего лишь в ка­честве оракула, то есть, не анализируя сам этот алгоритм, подает ему на вход любые значения по своему выбору и получает соответст­вующие выходные значе­ния.

Доказано, что трехраундовые доказатель­ства с нулевым разглаше­нием, в которых последнее свойство уста­навливается методом «черного ящика», существуют лишь в тривиаль­ном случае, т. е. когда проверяющий может самостоятельно, без всякой помощи доказывающего, проверить истинность утверждаемого. В отношении схемы Шнорра из этого резуль­тата следует, что либо существует эффективный алгоритм дискретного логарифмирования, либо свойство нулевого разглашения этого протокола не может быть доказано методом «черного ящика». Вопрос о существова­нии доказательств с нулевым разглашением, для которых свойство нуле­вого разглашения не может быть доказано методом «черного ящика», остается открытым.

Нетрудно показать, что схема Шнорра обладает несколько более слабым свойством — свойством нулевого разглашения относительно чест­ного проверяющего. В этом случае достаточно построить моделирующую машину только для честного проверяющего, который на шаге 2 и в самом деле выбирает случайный запрос е из множества {0,..., 2^t -1}.

Свойства нулевого разглашения относительно честного проверяю­щего может оказаться достаточно, если схема аутентификации исполь­зуется, например, для контроля за доступом в охраняемое помещение. В этом случае Алиса — это пропуск, выполненный в виде интеллек­туальной карточки, а Боб — компьютер охраны. В такой ситуации главная задача — обеспечить корректность схемы аутентификации, а защищаться от нечестного проверяющего бессмысленно. Что же касается свойства нулевого разглашения относительно честного проверяющего, то оно представляется далеко не лишним, так как позволяет обезопаситься от противника, который может попытаться подслушивать сеансы выполнения протокола с целью изготовления фальшивого пропуска.

Прежде чем завершить разговор о протоколах аутентификации, необходимо подчеркнуть, что никакое математически строго доказанное свойство криптографи­ческого протокола не может гаранти­ровать его безопасности во всех случаях жизни. В самом деле, даже протокол доказательства с нулевым разглашением не защищает от следующей атаки на схему аутентификации, известной в криптографи­ческой литературе под названием «мафиозная угроза». В данном сце­нарии имеются четыре участника: А, В, С и D. Предположим, что А зашел в кафе выпить чашечку кофе и расплачивается с помощью кре­дитной карточки. Для выполнения любой банковской операции карточ­ка должна идентифицировать себя, т. е. выполнить протокол аутенти­фикации. Но владелец кафе, В, — мафиози, сообщник которого С в тот же самый момент находится в магазине ювелира D и пытается купить бриллиант, также с помощью кредитной карточки. При этом С «пред­ставляется» как А, а D просит доказать это с помощью протокола аутентификации. Устройство считывания для карточек у В и карточка у С — это специально изготовленные приемо-передающие устройства, которые лишь пересылают сообщения между А и D. В результате А, обмениваясь сообщениями с В, на самом деле идентифицирует себя для D. Следовательно, только математического обоснования стойкости того или иного криптографического протокола недостаточно. Для практичес­кого применения конкретного протокола требуются еще усилия специ­алистов в области информаци­онной безопасности по анализу условий его применения.