vlsergey 16 ноя 2019 в 17:33

«Криптосистемы-протоколы»: Диффи—Хеллмана, Эль-Гамаля, MTI/A(0), STS

7 мин

28K

Информационная безопасность*Криптография*

Предисловие

Данный текст будет являться одной из переписанных глав для учебного пособия по защите информации кафедры радиотехники и систем управления, а также, с этого учебного кода, кафедры защиты информации МФТИ (ГУ). Полностью учебник доступен на github (см. также draft releases). На Хабре планирую выкладывать новые «большие» куски, во-первых, чтобы собрать полезные комментарии и замечания, во-вторых, дать сообществу больше обзорного материала по полезным и интересным темам. Предыдущие разделы главы «Криптографически протоколы»: 1, 2, 3

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

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

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

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

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

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

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

Взаимодействие участников в протоколе Диффи—Хеллмана

Алиса выбирает случайное $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$

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

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

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

Взаимодействие участников в протоколе Диффи—Хеллмана в модели с активным криптоаналитиком

Алиса выбирает случайное $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.

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

Стороны договорились о группе точек эллиптической кривой $\mathbb{E}$ , её циклической подгруппе $\mathbb{G}$ мощности $n = \| \mathbb{G} \|$ и генераторе $inline$ группы $\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$

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

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

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

Взаимодействие участников в протоколе Эль-Гамаля

Алиса и Боб выбирают общие параметры $inline$ и $inline$ , где $inline$ — большое простое число, а $inline$ — примитивный элемент поля $\mathbb{Z}_p^*$ .
Боб создаёт пару из закрытого и открытого ключей $inline$ и $inline$ :

$\begin{array}{l} b: 2 \leq b \leq p - 1, \\ K_B = g^b \bmod p. \end{array}$

Открытый ключ $inline$ находится в общем открытом доступе для всех сторон. Криптоаналитик не может подменить его — подмена будет заметна.
Алиса выбирает секрет $inline$ и вычисляет сеансовый ключ $inline$

$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), а использование «мастер»-ключа $inline$ для передачи сеансового ключа позволяет злоумышленнику вычислить все сессионные ключи из прошлых сеансов при компрометации закрытого ключа $inline$ (цель G9).

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

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

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

Взаимодействие участников в протоколе MTI/A(0)

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

$\begin{array}{ll} Alice: & ~ a, ~~ K_A = g^a \bmod p, \\ Bob: & ~ b, ~~ K_B = g^b \bmod p. \\ \end{array}$

Алиса сгенерировала случайное число $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$

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

$\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}$

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

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

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

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

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

Каждая из сторон $inline$ и $inline$ обладает долговременной парой ключей: закрытым ключом для расшифрования и создания электронной подписи $K_{\text{public}}$ и открытым ключом для шифрования и проверки подписи $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}}$ , а $inline$ — функция расшифрования с использованием закрытого ключа $K_{A, \text{private}}$ .

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

Взаимодействие участников в протоколе STS

Алиса выбирает случайное число $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$ .
Алиса проверяет подпись в сообщении $inline$ .
$Alice \to \left\{ A, B, E_K( S_A ( m_A, m_B ) ) \right\} \to Bob$
Боб проверяет подпись в сообщении $inline$ .

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

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

Взаимодействие участников в протоколе STS при атаке Лоу

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

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

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

Литература

[Diffie, Hellman 1976] Diffie W., Hellman M. E. New directions in cryptography // Information Theory, IEEE Transactions on. — 1976. — нояб. — т. 22, № 6. — с. 644—654. — ISSN 0018-9448. — DOI: 10.1109/TIT.1976.1055638.
[ElGamal, 1984] El Gamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // Proceedings of CRYPTO 84 on Advances in Cryptology. — Santa Barbara, California, USA: Springer-Verlag New York, Inc., 1985. — с. 10—18. — ISBN 0-387-15658-5. — URL: dl.acm.org/citation.cfm?id=19478.19480.
[ElGamal, 1985] El Gamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Transactions on Information Theory. — 1985. — июль. — т. 31, № 4. — с. 469—472. — DOI: 10.1109/TIT.1985.1057074.
[Matsumoto, Tsutomu, Imai 1986] Matsumoto T., Takashima Y., Imai H. On seeking smart publickey-distribution systems // Trans. Inst. Electron. Commun. Eng. Jpn. Sect. E. т. 69. вып. 2. — 02.1986. — с. 99—106.
[Diffie, Oorschot, Wiener 1992] Diffie W., Van Oorschot P. C., Wiener M. J. Authentication
and authenticated key exchanges // Designs, Codes and Cryptography. — 1992. — июнь. — т. 2, № 2. — с. 107—125. — ISSN 1573-7586. — DOI: 10.1007/BF00124891.
[Lowe 1996] Lowe G. Some new attacks upon security protocols // CSFW ’96 Proceedings of the 9th IEEE workshop on Computer Security Foundations. —Washington, DC, USA: IEEE Computer Society, 1996. — с. 162.
[Черёмушкин 2009] Черёмушкин А. В. Криптографические протоколы: основные свойства и уязвимости // Прикладная дискретная математика. — 2009. — нояб. — вып. 2. — с. 115—150. — URL: cyberleninka.ru/article/n/kriptograficheskieprotokoly-osnovnye-svoystva-i-uyazvimosti.pdf.

Послесловие

Автор будет благодарен за фактические и другие замечания к тексту.

Теги:

Хабы:

«Криптосистемы-протоколы»: Диффи—Хеллмана, Эль-Гамаля, MTI/A(0), STS

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

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

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

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

Литература

Публикации

Истории

Работа

Ближайшие события