11.3. «Криптосистемы-протоколы»

Как и создатели трёхпроходных протоколов из раздела 11.2, авторы следующих алгоритмов считали их не просто математическими конструкциями, обеспечивающие некоторую элементарную операцию (например, шифрование с открытым ключом), но пытались вокруг одной-двух математических конструкций построить законченную систему распространения ключей. Некоторые из этих конструкций, преобразовавшись, используются до настоящего времени (например, протокол Диффи-Хеллмана), некоторые – остались только в истории криптографии и защиты информации.

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

11.3.1. Протокол Диффи — Хеллмана

Первый алгоритм с открытым ключом был предложен Диффи и Хеллманом в работе 1976 года «Новые направления в криптографии» (англ. Bailey Whitfield Diffie, Martin Edward Hellman, ``New directions in cryptography'', [30]). Данный протокол, который также можно назвать схемой Диффи — Хеллмана, стал первым, позволивший уменьшить требования к каналу связи для установления защищённого соединения без предварительного обмена ключами.

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

Пусть $p$ – большое простое число, $g$ – примитивный элемент группы ${{\mathbb{Z}}}_p^*$, $y = g^x \bmod p$, причём $p, y, g$ известны заранее. Функцию $y=g^{x} \bmod p$ считаем однонаправленной, то есть вычисление функции при известном значении аргумента является лёгкой задачей, а её обращение (нахождение аргумента) при известном значении функции – трудной.

Обратную функцию $x = \log_g y \bmod p$ называют функцией дискретного логарифма. В настоящий момент не существует быстрых способов вычисления такой функции для больших простых $p$.

Протокол обмена состоит из следующих действий.

sequencediagram AliceAlice 2.5BobBob Alice$ A = g ^ a \bmod p $Bob Bob$ B = g ^ b \bmod p $Alice
Рис. 11.14 — Протокол Диффи — Хеллмана
samepage==
  • Алиса выбирает случайное $2 \leq a \leq p - 1$
  • $Alice \to \left\{ A = g ^ a \bmod p \right\} \to Bob$
  • Боб выбирает случайное $2 \leq b \leq p-1$
  • Боб вычисляет сеансовый ключ $K = A ^ b \bmod p$
  • $Bob \to \left\{ B = g ^ b \bmod p \right\} \to Alice$
  • Алиса вычисляет $K = B ^ a \bmod p$

Таким способом создан общий секретный сеансовый ключ $K$. За счёт случайного выбора значений $a$ и $b$ в каждом новом сеансе будет получен новой сеансовый ключ.

Протокол обеспечивает только генерацию сеансового ключа. Выбор нового «мастер»-ключа любой из сторон гарантирует (с вероятностью $1 - 1/p$) для неё формирование нового сеансового ключа (цель G10). В отсутствие третей доверенной стороны протокол не обеспечивает аутентификацию сторон (цель G1), а из-за отсутствия проходов с подтверждением владения ключом отсутствует аутентификация ключа (цель G8). Так как протокол не использует длительные «мастер»-ключи, можно говорить о том, что он обладает свойством совершенной прямой секретности (цель G9).

Протокол можно использовать только с такими каналами связи, в которые не может вмешаться активный криптоаналитик. В противном случае протокол становится уязвим к простой атаке «человек посередине».

sequencediagram AliceAlice 2.5MelloryMellory 2.5BobBob Alice$ A = g ^ a \bmod p $Mellory Mellory$ M = g ^ m \bmod p $Bob Bob$ B = g ^ b \bmod p $Mellory Mellory$ M = g ^ m \bmod p $Alice
Рис. 11.15 — Атака «человек посередине» на протокол Диффи — Хеллмана
samepage==
  • Алиса выбирает случайное $2 \leq a \leq p - 1$
  • $Alice \to \left\{ A = g ^ a \bmod p \right\} \to Mellory~(Bob)$
  • Меллори выбирает случайное $2 \leq m \leq p-1$
  • Меллори вычисляет сеансовый ключ для канала с Алисой
    $$K_{AM} = A ^ m \bmod p = g ^ {am} \bmod p$$
  • $Mellory~(Alice) \to \left\{ M = g ^ m \bmod p \right\} \to Bob$
  • $Mellory~(Bob) \to \left\{ M = g ^ m \bmod p \right\} \to Alice$
  • Алиса вычисляет сеансовый ключ для канала с Меллори (думая, что Меллори это Боб)
    $$K_{AM} = M ^ a \bmod p = g ^ { am } \bmod p$$
  • Боб выбирает случайное $2 \leq b \leq p-1$
  • Боб вычисляет сеансовый ключ для канала с Меллори (думая, что Меллори это Алиса)
    $$K_{BM} = M ^ b \bmod p = g ^ { bm } \bmod p$$
  • $Bob \to \left\{ B = g ^ b \bmod p \right\} \to Mellory~(Alice)$
  • Меллори вычисляет сеансовый ключ для канала с Бобом
    $$K_{BM} = B ^ m \bmod p = g ^ { bm } \bmod p$$

В результате Алиса и Боб получили новые сеансовые ключи, но «защищённый» канал связи установили не с друг с другом, а со злоумышленником, который теперь имеет возможность ретранслировать или изменять все передаваемые сообщения между Алисой и Бобом.

Протокол Диффи — Хеллмана отличается от большей части протоколов распространения ключей из-за того, что не использует другие криптографические примитивы (функции шифрования, электронно-цифровой подписи или хеширования), но сам по себе является в некотором смысле криптографическим примитивом для построения более сложных протоколов. Он обеспечивает генерацию случайного числа в распределённой системе без доверенного центра. Причём ни одна из сторон не может заставить другую сторону использовать старый сессионный ключ, в отличие от, например, протокола Yahalom из раздела 11.1.2.

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

samepage==
  • Стороны договорились о группе точек эллиптической кривой ${\mathbb{E}}$, её циклической подгруппе ${\mathbb{G}}$ мощности $n = \| {\mathbb{G}} \|$ и генераторе $G$ группы ${\mathbb{G}}$ (или хотя бы достаточно большой подгруппы группы ${\mathbb{G}}$).
  • Алиса выбирает случайное $2 \leq a \leq n - 1$
  • $Alice \to \left\{ A = a \times G \right\} \to Bob$
  • Боб выбирает случайное $2 \leq b \leq n - 1$
  • Боб вычисляет точку $K = b \times A$
  • $Bob \to \left\{ B = g \times G \right\} \to Alice$
  • Алиса вычисляет точку $K = a \times B$

В качестве нового сессионного ключа стороны могут выбрать, например, первую координату найденной точки $K$.

11.3.2. Протокол Эль-Гамаля

sequencediagram AliceAlice 2.5BobBob Alice$ g^x \bmod p $Bob
Рис. 11.16 — Протокол Эль-Гамаля

Протокол Эль-Гамаля (рис. 11.16, [35, 36]) за счёт предварительного распространения открытого ключа одной из сторон обеспечивает аутентификацию ключа для этой стороны. Можно гарантировать, что только владелец соответствующего закрытого ключа сможет вычислить сеансовый ключ. Однако подтверждение факта получение ключа (выполнение целей G1 и G8) не является частью протокола.

samepage==
  • Алиса и Боб выбирают общие параметры $p$ и $g$, где $p$ – большое простое число, а $g$ – примитивный элемент поля ${{\mathbb{Z}}}_p^*$.
  • Боб создаёт пару из закрытого и открытого ключей $b$ и $K_B$:
    $$\begin{array}{l} b: 2 \leq b \leq p - 1, \\ K_B = g^b \bmod p. \end{array}$$
  • Открытый ключ $K_B$ находится в общем открытом доступе для всех сторон. Криптоаналитик не может подменить его – подмена будет заметна.
  • Алиса выбирает секрет $x$ и вычисляет сеансовый ключ $K$
    $$ K = K_B^{x} = g^{bx} \bmod p. $$
    $$ Alice \to \left\{ g^x \bmod p \right\} \to Bob$$
  • Боб вычисляет сеансовый ключ
    $$ K = (g^x)^{b} = g^{bx} \bmod p. $$

Протокол не обеспечивает гарантию выбора нового сессионного ключа в каждом сеансе протокола (G10), а использование «мастер»-ключа $K_B$ для передачи сеансового ключа позволяет злоумышленнику вычислить все сессионные ключи из прошлых сеансов при компрометации закрытого ключа $b$ (цель G9).

11.3.3. Протокол MTI/A(0)

В 1986 году Ц. Мацумото (англ. Tsutomu Matsumoto), И. Такашима (англ. Youichi Takashima) и Х. Имаи (англ. Hideki Imai) предложили несколько алгоритмов, позже названных семейством протоколов MTI ([68]). За счёт предварительного распространения открытых ключей обоих сторон они обеспечивали неявную аутентификацию ключа (цель G7). То есть сессионный ключ гарантированно мог получить только владельцы соответствующих открытых ключей. Мы рассмотрим одного из представителей данного семейства – протокол MTI/A(0) (рис. 11.17).

Предварительно стороны договорились об общих параметрах системы $p$ и $g$, где $p$ – большое простое число, а $g$ – примитивный элемент поля ${{\mathbb{Z}}}_p^*$.

Каждая из сторон (Алиса и Боб) сгенерировала пару из закрытого и открытого ключей:

$$\begin{array}{ll} Alice: & ~ a, ~~ K_A = g^a \bmod p, \\ Bob: & ~ b, ~~ K_B = g^b \bmod p. \\ \end{array}$$
sequencediagram AliceAlice 2.5BobBob Alice$ g^{R_A} \bmod p $Bob Bob$ g^{R_B} \bmod p $Alice
Рис. 11.17 — Протокол MTI/A(0)
samepage==
  • Алиса сгенерировала случайное число $R_A: ~ 2\leq R_A\leq p-1$
  • $ Alice \to \left\{ g^{R_A} \bmod p \right\} \to Bob$
  • Боб сгенерировал случайное число $R_B: ~ 2\leq R_B\leq p-1$
  • Боб вычислил сеансовый ключ $K = (g^{R_A})^b \cdot K_A^{R_B} \bmod p$
  • $ Bob \to \left\{ g^{R_B} \bmod p \right\} \to Alice$
  • Алиса вычислила сеансовый ключ $K = (g^{R_B})^a \cdot K_B^{R_A} \bmod p$

Если открытые ключи $K_A$ и $K_B$ соответствуют своим закрытым ключам $a$ и $b$, то вычисленные участниками сессионные ключи совпадают:

$$\begin{array}{lll} (g^{R_A})^b \cdot K_A^{R_B} \bmod p & = & g^{b R_A + a R_B} \bmod p, \\ (g^{R_B})^a \cdot K_B^{R_A} \bmod p & = & g^{a R_B + b R_A} \bmod p. \end{array}$$

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

Как и другие представители криптосистем-протоколов, MTI не разрабатывался с учётом возможности компрометации закрытых «мастер»-ключей $a$ и $b$ (цель G9).

11.3.4. Протокол Station-to-Station

Протокол STS (англ. Station-to-Station, [32]) предназначен для систем мобильной связи. Он использует идеи протокола Диффи — Хеллмана и криптосистемы RSA. Особенностью протокола является использование механизма электронной подписи для взаимной аутентификации сторон.

Предварительно стороны договорились об общих параметрах системы $p$ и $g$, где $p$ – большое простое число, а $g$ – примитивный элемент поля ${{\mathbb{Z}}}_p^*$.

Каждая из сторон $A$ и $B$ обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи $K_{\text{private}}$ и открытым ключом для шифрования и проверки подписи $K_{\text{public}}$.

$$\begin{array}{ll} A: K_{A,\text{private}}, K_{A,\text{public}}: \forall M : & \text{Verify}_A ( M, S_A( M ) ) = true, \\ & D_A ( E_A( M ) ) = M, \\ B: K_{B,\text{private}}, K_{B,\text{public}}: \forall M : & \text{Verify}_B ( M, S_B( M ) ) = true, \\ & D_B ( E_B( M ) ) = M. \\ \end{array}$$

Где $\text{Verify}_A(\dots)$ это функция проверки электронной подписи на открытом ключе $K_{A, \text{public}}$, а $D_A$ – функция расшифрования с использованием закрытого ключа $K_{A, \text{private}}$.

sequencediagram AliceAlice 2.5BobBob Alice$ A, m_A = g^{R_A} \bmod p $Bob Bob $ B, A, m_B = g^{R_B} \bmod p$, $E_K( S_B ( m_A, m_B )) $ Alice Alice$ A, B, E_K( S_A ( m_A, m_B ) ) $Bob
Рис. 11.18 — Протокол STS

Протокол состоит из четырёх проходов, три из которых включают передачу сообщений (рис. 11.18, [133]).

samepage==
  • Алиса выбирает случайное число $R_A: 2 \leq R_A \leq p-1$.
  • $Alice \to \left\{ A, m_A = g^{R_A} \bmod p \right\} \to Bob$
  • Боб выбирает случайное число $R_B: 2 \leq R_B \leq p-1$.
  • Боб вычисляет сессионный ключ $K = m_A^{R_B} \bmod p$.
  • $Bob \to \left\{ B, A, m_B = g^{R_B} \bmod p, E_K( S_B ( m_A, m_B )) \right\} \to Alice$
  • Алиса вычисляет сессионный ключ $K = m_B^{R_A} \bmod p$.
  • Алиса проверяет подпись в сообщении $E_K( S_B ( m_A, m_B ))$.
  • $Alice \to \left\{ A, B, E_K( S_A ( m_A, m_B ) ) \right\} \to Bob$
  • Боб проверяет подпись в сообщении $E_K( S_A ( m_A, m_B ))$.

Протокол обеспечивает гарантию формирования новых ключей (G10), но не совершенную прямую секретность (G9).

sequencediagram AliceAlice 2.75MelloryMellory 2.75BobBob Alice$ A, m_A = g^{R_A} \bmod p $Mellory Mellory$ M, m_A $Bob Bob$ B, M, m_B, E_K( S_B ( m_A, m_B )) $Mellory Mellory$ B, A, m_B, E_K( S_B ( m_A, m_B )) $Alice Alice$ A, B, E_K( S_A ( m_A, m_B ) ) $Mellory
Рис. 11.19 — Атака Лоу на протокол STS

Как показала атака Лоу 1996 года ([64], рис. 11.19), протокол не может гарантировать аутентификацию субъектов (цель G1), ключей (G7) и подтверждение владения сессионным ключом (G8). Хотя злоумышленник не может получить доступ к новому сессионному ключу, если протокол использовать только для аутентификации субъектов, Алиса может принять злоумышленника за Боба.

samepage==
  • Алиса выбирает случайное число $R_A: 2 \leq R_A \leq p-1$.
  • $Alice \to \left\{ A, m_A = g^{R_A} \bmod p \right\} \to Mellory~(Bob)$
  • $Mellory~(Alice) \to \left\{ M, m_A \right\} \to Bob$
  • Боб выбирает случайное число $R_B: 2 \leq R_B \leq p-1$ и вычисляет $m_B = g^{R_B} \bmod p$, а также сессионный ключ $K = m_A^{R_B} \bmod p$.
  • $Bob \to \left\{ B, M, m_B, E_K( S_B ( m_A, m_B )) \right\} \to Mellory$
  • $Mellory~(Bob) \to \left\{ B, A, m_B, E_K( S_B ( m_A, m_B )) \right\} \to Alice$
  • Алиса вычисляет сессионный ключ $K = m_B^{R_A} \bmod p$.
  • Алиса проверяет подпись в сообщении $E_K( S_B ( m_A, m_B ))$.
  • $Alice \to \left\{ A, B, E_K( S_A ( m_A, m_B ) ) \right\} \to Mellory~(Bob)$

После успешного завершения протокола Алиса уверена, что общается с Бобом.

Как и все остальные «криптосистемы-протоколы», протокол Station-to-Station основывается на некотором внешнем источнике информации об открытых ключах участников, не подвергая сомнению корректность и надёжность этого источника. Что, в общем случае, неверно. Если информацию о ключах участников нужно получать извне при каждом сеансе протокола (например, если участников много, и запомнить ключи всех возможности нет), то канал получения открытых ключей будет основной целью активного криптоаналитика для рассмотренных протоколов. Как от этого защититься с использованием примитивов асимметричной криптографии – в разделе 11.5.