Протоколы, основанные на тождествах

Многие протоколы идентификации/аутентификации и ЭЦП основываются на проверке некоторого тождества в модульной арифметике. Если идентификационные данные, предъявляемые пользователем по каналу связи, и данные, выбираемые проверяющим из справочника, удовлетворяют проверочному равенству, то делается вывод, что пользователь есть тот, за кого себя выдает. Однако проверочное равенство обычно имеет гораздо больше решений, чем может быть получено по протоколу. Это позволяет подобрать числа, удовлетворяющие проверочному равенству, не зная секретных данных пользователя или сервера. Предъявляя эти числа в качестве идентификационных данных, можно в ряде случаев ввести в заблуждение проверяющего.

Для примера рассмотрим две модификации протокола односторонней идентификации. Предварительно сервер S выбирает надлежащим образом значения системных параметров (Р, clip_image002), генерирует от ДСЧ свой секретный ключ х, вычисляет соответствующий открытый ключ clip_image004 и рассылает всем пользователям постоянные (Р, clip_image002[1], y) по достоверному каналу. Далее, для каждого пользователя, например, для А сервер генерирует от ДСЧ случайное секретное число “К”, вычисляет открытый идентификатор r=ak (mod p), находит секретный идентификатор S=K-1(A+xclip_image007r)mod(p-1) и по безопасному каналу передает А его идентификационные данные (A, r, S), например, А получает их в ЦГРК при регистрации вместе с системными константами Р, clip_image002[2], y. Заметим, что секретный идентификатор S является функцией неизвестного числа “К”, которое стирается, и секретного ключа х сервера S, а также функцией адреса А и открытого идентификатора “r”.

7.1. Двухшаговый протокол односторонней идентификации

В этом протоколе пользователь В, желая идентифицировать А, посылает “вопрос” (случайное число Z) и проверяет правильность “ответа” А (Рис.11).

Формальная запись протокола:

В: ДСЧ(В) clip_image009Z clip_image011А

А: ДСЧ(А) clip_image009[1]t; rt(modp)=u; (S+tz)mod(p-1)=V; [AIIrIIuIIv] clip_image011[1] B

B: clip_image013; A – аутентифицирован.

clip_image015

Рис.11

Заметим, что если какие-то числа А, r, u, v при заданных clip_image002[3], y, z удовлетворяют уравнению (*)clip_image017 в обычной арифметике (без mod p), то они удовлетворяют такому же уравнению по любому модулю.

Положим rij=clip_image019, clip_image021 где i, j, l, m – целые. Тогда уравнение (*) удовлетворяется, если iclip_image007[1]v= A+lclip_image007[2]z; jclip_image007[3]v = rij + mclip_image007[4]z. Оба уравнения для всякого z дают одинаковые значения v, если пропорциональны их коэффициенты clip_image024

Отсюда следует, что А должно равняться clip_image026; clip_image028 (числа i, j удобно выбрать так, чтобы v было целым). Заметим, что поскольку равенство (*) будет проверяться по mod p, то систему уравнений относительно показателей (v, z) можно решать по mod(p-1), согласно теореме Эйлера. Числа Aij, rij, ulm, в общем случае, имеют разрядность значительно больше, чем разрядность clip_image030 модуля p. Поскольку число Aij участвует в уравнении (*) только в показателе, то вместо него можно использовать clip_image032 (числа v, z уже имеют разрядность clip_image030[1]). Число ulm участвует в уравнении (*) только в основании степени, поэтому его можно заменить на clip_image034. Наконец, число rij участвует в уравнении (*) как в показателе, так и в основании степени, а потому его можно заменить только на clip_image036 т.е. число разрядности 2clip_image030[2].

Атака. Противник Е, играющий роль clip_image038, перехватывает в канале связи “вопрос” Z и дает “ответ”: clip_image040clip_image042clip_image044clip_image046clip_image011[2]B, где число v находит из системы уравнений по mod (p-1). Если В не проверяет разрядность чисел в “ответе”, то у него уравнение (*) удовлетворяется. Если В проверяет наличие значения rij в справочнике открытых идентификаторов, то противник может заранее подобрать целые i, j так, чтобы значение rij в справочнике было.

7.2. Трехшаговый протокол односторонней идентификации

В данном протоколе пользователь А, желая идентифицировать себя В, посылает ему свои идентификационные данные А, r и синхроданные сеанса связи “u”. На “вопрос” Z от В он должен дать правильный “ответ” v такой, чтобы удовлетворилось проверочное равенство (*) (Рис.12).

clip_image048

Рис.12

Для авторизованного пользователя это сделать легко, поскольку он знает свой секретный идентификатор (S) и сам генерирует синхроданные (u) специальным образом. Для противника Е, не знающего ни одного секретного идентификатора, это также удалось сделать в протоколе 7.1. , но там “вопрос” Z был известен заранее. В протоколе 7.2. противник должен сначала предъявить какие-то идентификационные данные и только затем получает “вопрос” Z от В, на который он должен дать “правильный ответ”. Формальная запись протокола между А и В:

А: ДСЧ (А) clip_image009[2]t; rt (mod p) = u; [A║ r║ u] clip_image011[3]B

B: ДСЧ) clip_image009[3]Z; [BZ] clip_image011[4]A;

A: clip_image050; v = (S+tz) mod (p-1); [A v] clip_image011[5]B

B: clip_image052;clip_image054 A идентифицировался у В.

Атака. Противник Е, играющий роль clip_image056, посылает В сообщение clip_image057clip_image042[1]clip_image044[1]], где подбирает идентификационные данные, как в атаке п.7.1. В ответ на любой “вопрос” Z от В, противник решает систему уравнений относительно v по mod(p-1) и посылает clip_image059v]. Если В не проверяет разрядность чисел в “ответе”, то противник идентифицируется В под именем clip_image061, не зная секретного идентификатора этого пользователя.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100