Список обозначений

Теория аутентификации Симмонса

simmons authentication theory

Теория аутентификации Симмонса (см. [1]) представляет собой теорию безусловно стойких протоколов аутентификации сообщений и является аналогом теории безусловно стойких систем секретной связи Шеннона.

В теории аутентификации Симмонса имеется три действующих лица: отправитель (transmitter), получатель (receiver) и противник (opponent). Изначально отправитель имеет некоторое случайное значение $s$ случайной величины $\widetilde s$ с конечным носителем $S$. Целью отправителя является передача значения $s$ получателю с обеспечением аутентичности. Для этого отправитель и получатель независимо от $s$ выбирают некоторое многозначное отображение $e\colon S\to M$ (где $M$ — некоторое конечное множество) такое, что $e^{-1}$ является однозначным отображением. Это отображение $e$ называется правилом кодирования (encoding rule); множество всех допустимых для выбора правил кодирования будет обозначаться через $E$. Кроме того, отправитель выбирает некоторое сообщение $m\in e(s)$ и посылает это сообщение получателю. Получатель признает полученное сообщение $m$ аутентичным, если и только если $m\in e(S)$. В этом случае он считает, что значение $s$, переданное ему отправителем, есть $e^{-1}(m)$.

Предполагается, что правило кодирования $e$ противнику неизвестно, а значение $s$ он может как знать, так и не знать. В первом случае мы получаем модель аутентификации без секретности, а во втором — аутентификации с секретностью. Противник может проводить два вида атак на описанную модель протокола аутентификации: имитацию (impersonation) и подмену (substitution). Имитация заключается в передаче противником сгенерированного им сообщения $m’\in M$ получателю в то время как отправитель не посылал никакого сообщения. При этом противник достигает своей цели в том и только том случае, когда сообщение $m’$ признается получателем аутентичным, т. е. $m’\in e(S)$. Подмена состоит в перехвате противником сообщения $m$ от отправителя к получателю, вычислении (вообще говоря, с использованием $m$) другого сообщения $m’\in M$ и передаче $m’$ вместо $m$ получателю. В этом случае противник достигает успеха тогда и только тогда, когда сообщение $m’$ признается получателем аутентичным (т. е. $m’\in e(S)$), причем при восстановлении получателем значения $s$ по $m$ и $m’$ получаются различные результаты (т. е. $e^{-1}(m)\ne e^{-1}(m’)$).

Обычно $e$, $m$ и $m’$ выбираются как случайные значения случайных величин $\widetilde e$, $\widetilde m$ и $\widetilde m’$ соответственно. При этом предполагается, что случайные величины $\widetilde s$ и $\widetilde e$ независимы.

Данная модель протокола аутентификации рассматривается в теории Симмонса как матричная игра между отправителем и получателем (с одной стороны) и противником (с другой стороны). Чистые стратегии отправителя и получателя заключаются в выборе $e$ и $m$, а чистые стратегии противника — в выборе $m’$. Если в некоторой чистой ситуации при фиксированном значении $s$ противник достигает успеха, то его выигрыш в этой ситуации считается равным $1$, а в противном случае — $0$. Как и всякая конечная матричная игра, эта игра имеет ситуацию равновесия в классе смешанных стратегий. Обозначим через $v_I$, $v_S$ и $v_G$ значение смешанного расширения данной игры при условии, что противник может выбирать только стратегию имитации, только стратегию подмены и произвольную стратегию этих двух видов соответственно (под стратегиями здесь понимаются, естественно, смешанные стратегии). Тогда $v_I$, $v_S$ и $v_G$ представляют собой вероятности успеха противника при соответствующих ограничениях на выбор стратегии и при оптимальном выборе смешанных стратегий.

В качестве примера приведем матрицу выигрышей $P_I$ рассматриваемой игры в модели аутентификации с секретностью при условии, что противник может выбирать только стратегию имитации. В этом случае чистые стратегии отправителя и получателя можно отождествить с элементами $E$, а чистые стратегии противника — с элементами $M$, так как успех противника не зависит от значений $s$ и $m$. Тогда строки матрицы $P_I$ индексированы элементами $E$, столбцы — элементами $M$, а на пересечении $\varepsilon$-й строки и $\mu$-го столбца ($\varepsilon\in E$, $\mu\in M$) стоит $1$, если $\mu\in\varepsilon(S)$, и $0$ в противном случае.

Основными результатами теории аутентификации Симмонса являются нижние оценки вероятностей успеха противника при оптимальном выборе смешанных стратегий (а также логарифмов этих вероятностей). Приведем такие оценки из работы [1]: \begin{align*} v_I&\geqslant\frac{\min_{\varepsilon\in E}\#\varepsilon(S)}{\#M}\geqslant\frac{\#S}{\#M};\\\log v_I&\geqslant H(\widetilde s,\widetilde e,\widetilde m)-H(\widetilde e)-H(\widetilde m). \end{align*} Здесь и далее в этой статье через $H$ обозначается энтропия, а через $\log$ — логарифм по тому же основанию, что используется в определении энтропии.

Приведенные выше оценки остаются справедливыми при замене $v_I$ на $v_G$, так как \[ v_G\geqslant\max(v_I,v_S). \] В той же работе [1] также получены следующие нижние оценки: \begin{align*} \log v_G&\geqslant\begin{cases} -H(\widetilde e)/2&\text{в модели с секретностью},\\-(H(\widetilde e)-H(\widetilde s\,|\,\widetilde m))/2&\text{в модели без секретности}; \end{cases}\\ v_G&\geqslant\frac1{\sqrt{\#E}}. \end{align*}

Литература

  • [1] Simmons, G. J. «Authentication theory/coding theory» 1985

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна