MAC.tex

\section{Имитовставка}\label{section-MAC}
\selectlanguage{russian}
\index{имитовставка}

Для обеспечения целостности и подтверждения авторства информации, передаваемой по каналу связи, используют \textbf{имитовставку} $\MAC$ (message authentication code).

Имитовставкой называется \emph{криптографическая хэш-функция} $\MAC(K,m)$, зависящая от передаваемого сообщения $m$ и секретного ключа $K$ отправителя $A$, обладающая свойствами цифровой подписи:
\begin{itemize}
    \item получатель $B$, используя такой же или другой ключ, имеет возможность проверить целостность\index{целостность} и доказать принадлежность информации $A$;
    \item имитовставку невозможно фальсифицировать.
\end{itemize}

Имитовставка может быть построена либо на симметричной криптосистеме (в таком случае обе стороны имеют один общий секретный ключ), либо на криптосистеме с открытым ключом, в которой $A$ использует свой секретный ключ, а $B$ -- открытый ключ отправителя $A$.

Наиболее универсальный способ аутентификации сообщений через схемы ЭП на криптосистемах с открытым ключом состоит в том, что сторона $A$ отправляет стороне $B$ сообщение
    \[ m ~\|~ \textrm{ЭП}(K, h(m)), \]
где $h(m)$ -- криптографическая хэш-функция в схеме ЭП и $\|$ является операцией конкатенации битовых строк. Для аутентификации большого объёма информации этот способ не подходит из-за медленной операции вычисления подписи. Например, вычисление одной ЭП на криптосистемах с открытым ключом занимает порядка 10 мс на ПК. При средней длине IP-пакета 1 Кб, для каждого из которых требуется вычислить имитовставку, получим максимальную пропускную способность в $\frac{1 ~ \text{Kб}}{10 ~ \text{мс}} = 100$ Кб/с.

Поэтому для большого объёма данных, которые нужно аутентифицировать, $A$ и $B$ создают общий секретный ключ аутентификации $K$. Далее имитовставка вычисляется либо с помощью модификации блочного шифра, либо с помощью криптографической хэш-функции.

Для каждого пакета информации $m$ отправитель $A$ вычисляет $\MAC(K,m)$ и присоединяет его к сообщению $m$:
    \[ m ~ \|~ \MAC(K,m). \]
Зная секретный ключ $K$, получатель $B$ может удостовериться с помощью кода аутентификации, что информация не была изменена или фальсифицирована, а была создана отправителем.

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

Стандартные способы использования имитовставки сообщения следующие.
\begin{itemize}
    \item Если шифрование данных не применяется, отправитель $A$ для каждого пакета информации $m$ отсылает сообщение
        \[ m ~\|~ \MAC(K, m) .\]
    \item Если используется шифрование данных симметричной криптосистемой с помощью ключа $K_e$, то имитовставка с ключом $K_a$ может вычисляться как до, так и после шифрования:
        \[ E_{K_e}(m) ~\|~ \MAC(K_a, E_{K_e}(m)) ~~ \text{ или } ~~ E_{K_e}(m ~\|~ \MAC(K_a, m)). \]

\end{itemize}
Первый способ, используемый в IPsec\index{протокол!IPsec}, хорош тем, что для проверки целостности достаточно вычислить только имитовставку, тогда как во втором случае нужно дополнительно вначале расшифровать данные. С другой стороны, во втором способе, используемом в системе PGP\index{протокол!PGP}, защищённость имитовставки не зависит от потенциальной уязвимости алгоритма шифрования.

Вычисление имитовставки от пакета информации $m$ с использованием блочного шифра $E$ осуществляется в виде:
    \[ \MAC(K, m) = E_K(H(m)), \]
где $H$ -- криптографическая хэш-функция.

Имитовставка на основе хэш-функции обозначается $\HMAC$ (Hash-based MAC)\index{HMAC} и стандартно вычисляется в виде
    \[ \HMAC(K, m) = H(K \| H(K \| m)). \]

Возможно также вычисление в виде:
    \[ \HMAC(K, m) = H(K \| m \| K). \]

В протоколе IPsec\index{протокол!IPsec} (который используется в протоколе IPv6\index{протокол!IPv6}) используется следующее вычисление кода аутентификации:
    \[ \HMAC(K, m) = H((K \oplus ~ \textrm{opad}) ~\|~ H((K \oplus ~ \textrm{ipad}) ~\|~ m)), \]
где $\textrm{opad}$ -- последовательность повторяющихся байтов
    \[ \text{\texttt{0x5C}}= [1011100]_2, \]
$\textrm{ipad}$ -- последовательность повторяющихся байтов
    \[ \text{\texttt{0x36}} = [00110110]_2, \]
которые инвертируют половину битов ключа. Считается, что использование различных значений ключа повышает криптостойкость.

В протоколе защищённой связи SSL/TLS\index{протокол!SSL/TLS}, используемом в интернете для инкапсуляции протокола HTTP\index{протокол!HTTP} в протокол SSL (HTTPS\index{протокол!HTTPS}), код $\HMAC$ определяется почти так же, как в IPsec. Отличие состоит в том, что вместо операции XOR для последовательностей $\textrm{ipad}$ и $\textrm{opad}$ осуществляется конкатенация:
    \[ \HMAC(K, m) = H((K ~\|~ \textrm{opad}) ~\|~ H((K ~\|~ \textrm{ipad}) ~\|~ m)). \]

Двойное хэширование\index{двойное хэширование} с ключом в
    \[ \HMAC(K, m) = H(K \| H(K \| m)) \]
применяется для защиты от атаки на расширение сообщений. Вычисление хэш-функции от сообщения $m$, состоящего из $n$ блоков $m_1 m_2 \dots m_n$, можно записать в виде
    \[ H_i = f(H_{i-1}, m_i), ~ H_0 \equiv IV = \textrm{const}, ~ H(m) \equiv H_n, \]
где $f$ -- известная сжимающая функция.

Пусть имитовставка использует одинарное хэширование с ключом:
    \[ \MAC(K, m) = H(K \| m) = H (m_0 = K \| m_1 \| m_2 \| \dots \| m_n). \]
Тогда криптоаналитик, не зная секретного ключа, имеет возможность вычислить имитовставку для некоторого расширенного сообщения $m \| m_{n+1}$:
\[
    \MAC(K, m \| m_{n+1}) = \underbrace{H \left( K \| m_1 \| m_2 \| \dots \| m_n \right.}_{\MAC(K, m)} \left. \| m_{n+1} \right) =
\] \[
    f(\MAC(K, m), m_{n+1}).
\]