Протокол совместной выработки ключа (Hjkmktkl vkfbyvmukw fdjgQkmtn tlZcg)

В криптографии, протокол совместной выработки ключа^[1] (англ. Key-agreement protocol) — метод установления секретного ключа шифрования, в котором каждый авторизированный пользователь канала влияет на его значение.

Для конфиденциального общения между пользователями необходимы секретные ключи шифрования и дешифрования сообщений. Протоколами обмена ключом называют алгоритмы, которые осуществляют защищенный обмен ключом шифрования. Протоколы обмена ключами делятся на два типа^[2]: протоколы передачи ключа и протоколы совместной выработки ключа. В протоколах передачи ключа используется симметричное шифрование, один из пользователей канала (сервер) генерирует ключ и передаёт его остальным участникам. Для этого необходим защищенный канал. Протоколы совместной выработки ключа используют асимметричное шифрование. Они организованы так, что открытый ключ передается по незащищенному каналу и используется для шифрования сообщений. Для дешифрования сообщений используется секретный ключ.

Появление протокола[править | править код]

Недостатком симметричных криптосистем является сложность передачи ключа. Необходим защищенный канал, по которому осуществится начальный обмен ключом. Если две стороны не могут установить безопасный начальный обмен, существует риск перехвата сообщений третьей стороной. Протокол совместной выработки ключа создавался для решения этой проблемы^[3], что привело к появлениюкриптографии с открытым ключом.

Первый протокол совместной выработки ключа был описан в работе «Новые направления в современной криптографии» Уитфилда Диффи и Мартина Хеллмана, опубликованной в 1976 году. Они предложили алгоритм получения секретных ключей, при помощи распространения открытых ключей через незащищенный канал^[4]/ В основе этого метода^[5] лежит экспоненциальный обмен ключами, известный как обмен ключами Диффи — Хеллмана. Экспоненциальный обмен ключами не требует предварительных соглашений между участниками, но в результате такого обмена каждая из сторон обладает секретным ключом.

Подход к созданию[править | править код]

После разработки Уитфилдом Диффи и Мартином Хеллманом алгоритма обмена ключами, появились и другие протоколы совместной выработки ключа. Их появление обосновано, например, желанием сократить объем вычислений, используя математические операции, отличные от возведения в степень^[6]. Можно выделить общий подход к созданию протоколов совместной выработки ключа.

Для начала, в криптографии с асимметричным шифрованием значение открытого ключа пользователя известно всем пользователям канала (и возможно стороннему наблюдателю), значение секретного ключа пользователя известно только самому пользователю и никому больше. Тогда любой протокол совместной выработки ключа должен обладать следующими свойствами^[7]:

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

Главным инструментом математического аппарата, который лежит в основе создания протоколов совместной выработки ключа, являются односторонние функции^[8]. Они из определения удовлетворяют свойствам, которые требует протокол, в том случае, если аргументом такой функции является секретный ключ, а выходным значением открытый ключ. Далее будут приведены задачи, основанные на односторонней сложности вычислений, и протоколы, в основе которых они лежат.

Задача дискретного логарифмирования[править | править код]

Односторонняя функция: возведение в степень по модулю большого простого числа $\leftrightarrow$ дискретное логарифмирование.

Пусть заданны некоторые натуральные числа $g$ и $a$ . Решение $x$ уравнения $g^{x}=a$ в некоторой конечной мультипликативной группе $G$ называется дискретным логарифмом элемента $a$ по основанию $g$ ^[9].

Пусть известны $g$ и $x$ и необходимо посчитать $g^{x}$ в кольце вычетов по модулю $m$ . Значение $a$ по заданным $g$ и $x$ в терминах теории сложности вычислений считается легко.

Пусть теперь известны $g$ и $a$ . Получение дискретного логарифма $x$ — значительно более трудоемкая задача и если числа $x$ и $m$ выбраны достаточно большие, то практически неразрешима за разумное время. Таким образом, $x$ в терминах теории сложности вычислений находится трудно.

На задаче дискретного логарифмирования основан протокол Диффи-Хеллмана^[4], где $x$ — это секретный сеансовый ключ пользователя, $a$ — открытый ключ пользователя, $g$ — генератор.

Задача факторизации[править | править код]

Односторонняя функция: умножение $\leftrightarrow$ факторизация.

Пусть задано некоторое натуральное число $n$ , факторизацией называется процесс разложения $n$ в произведение простых множителей. Существование и единственность (с точностью до порядка следования множителей) такого разложения следует из основной теоремы арифметики^[10]

Пусть известны два больших простых числа $p$ и $q$ . Результат их произведения $n=p\cdot q$ в терминах теории сложности вычислений считается легко.

Пусть известно большое натуральное число $n$ , которое является произведением некоторых больших простых чисел $p$ и $q$ . Факторизация $n$ в терминах теории сложности вычислений осуществляется трудно.

Примером криптосистемы, использующей эту идею, является RSA^[11]. Два больших простых числа $p$ и $q$ являются секретными ключами пользователей, $n=p\cdot q$ — открытым ключом.

Задача дискретного логарифмирования на эллиптической кривой[править | править код]

Односторонняя функция: умножение натурального числа на точку эллиптической кривой $\leftrightarrow$ дискретное логарифмирование на эллиптической кривой.

Рассмотрим выражение $Q=k\cdot P\mod p$ , где $Q$ и $P$ — точки эллиптической кривой.

Пусть известны $k$ , $P$ и $p$ . Результат $Q$ операции $k\cdot P\mod p$ в терминах теории сложности вычислений считается легко.

Пусть известны $Q$ , $P$ и $p$ . Задача поиска $k$ в терминах теории сложности вычислений осуществляется трудно.

Примером протокола, основанного на этой задаче, может служить Протокол Диффи — Хеллмана на эллиптических кривых, в котором $P$ — заранее определенная базовая точка, $p$ некоторое большое простое значение. Различные $k$ — секретные ключи пользователей, $Q$ — открытый ключ^[12].

Примеры[править | править код]

Атаки на протокол[править | править код]

При анализе протоколов, необходимо понимать, каким типам атак они могут подвергаться. Существует два типа атак на протоколы: пассивные и активные. Безопасный протокол способен противостоять обоим видам атак^[13].

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

Под этими двумя категориями существует довольно много методов атаки^[13].

Атака подслушиванием[править | править код]

Подслушивание^[14] — захват злоумышленником информации, отправляемой в протоколе. Способа предотвратить подслушивание нет, но есть возможность защитить содержимое сообщений с помощью шифрования. Это один из самых основных видов атак, и более сложные атаки могут включать в себя прослушивание. Подслушивание — вид пассивной атаки. Далее будут приведены активные атаки.

Атака модификацией[править | править код]

При атаке модификацией^[15] злоумышленник изменяет отправляемую информацию. Способ предотвращения такого рода атак — использование мер криптографической целостности.

Атака повтором[править | править код]

Атака повтором^[15] включают любую ситуацию, когда злоумышленник мешает выполнению протокола путем вставки сообщения или части сообщения, которое было отправлено ранее при любом запуске протокола. Атака повтором часто используется в сочетании с другими видами атак. Использование токенов сессии помогает избежать атак повтором.

Атака отражением[править | править код]

Атака отражением^[15] — способ атаковать систему, которая использует один и тот же ключ в обоих направлениях. Атака пытается обмануть цель и дать ответ на ее собственный запрос. Эта атака возможна только в том случае, если протокол допускает параллельные запуски. Чтобы предотвратить эту атаку, отправляющий может добавить свой идентификатор в ответ и отклонять ответы, в которых встречает свой идентификатор. Другим решением является требование, чтобы ключи были разными для каждого направления связи.

Атаки типа «отказ в обслуживании»[править | править код]

Во время DoS-атаки^[16] злоумышленники отправляют множество запросов на сервер, чтобы перегрузить его и мешать достоверным пользователям получить соединение с ним. Единственная защита состоит в том, чтобы сводить к минимуму число вычислений и количество значений, которые сервер должен хранить для каждого соединения.

Криптоанализ[править | править код]

Криптоанализ^[17] — получение зашифрованной информации без доступа к ключу дешифрования. В большинстве случаев такого рода атаки направлены на поиск секретного ключа.

Пересечение протоколов[править | править код]

Пересечение протоколов означает^[18], что злоумышленник использует ключ известного протокола для взаимодействия с новым протоколом. Большинство долгосрочных ключей предназначены для использования только для одного протокола. Несмотря на это, некоторые ключи используются одновременно в нескольких протоколах. Чтобы предотвратить атаку такого рода, нужно использовать разные ключи для каждого протокола и включать детали протокола,например, идентификатор и номер версии в аутентифицированную часть сообщений.

Таким образом:

Атака подслушиванием — злоумышленник перехватывает информацию, отправленную в протоколе.

Атака модификацией — информация, передаваемая в протоколе, изменяется злоумышленником.

Атака повтором — передача записывается, а затем повторно отправляется.

Атака отражением — отправка того же сообщения отправителю при запуске нового протокола.

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

Криптоанализ — изучение методов получения смысла зашифрованной информации.

Пересечение протоколов — использование ключа одного протокола для взаимодействия с другим протоколом.

Свойства надёжныx протоколов[править | править код]

Знание ключа безопасности: запуск протокола должен привести к уникальному секретному сеансовому ключу. Если этот ключ скомпрометирован, он не должен влиять на другие сеансовые ключи.

Совершенная прямая секретность: тот факт, что долгосрочные закрытые ключи скомпрометированы, не должен влиять на секретность ранее установленных сеансовых ключей.

Устойчивость к компрометированию ключей: если долгосрочный закрытый ключ объекта А скомпрометирован, злоумышленник может представиться, как А. Но это не должно позволить ему выдать себя за А другим лицам.

Устойчивость к обмену неизвестными ключами: если объект A хочет создать секретный ключ с B, не должно быть возможности, чтобы A обманом поделился ключом с объектом C.

Управление ключами: ни один из участников обмена не должен быть в состоянии принудительно установить сеансовый ключ на конкретное значение только по своему выбору^[19].

Аутентификация[править | править код]

Чтобы пользователь B при обмене информацией с А по заданному протоколу был аутентифицированным, протокол должен обладать одним из двух следующих свойств безопасности^[20]:

Неявное (слабое) подтверждение ключа: B уверен, что A — единственный другой объект, который может знать правильный ключ.
Явное (сильное) подтверждение ключа: B уверен, что A — единственный другой объект, который знает правильный ключ (B подтвердил, что A получил правильный ключ).

Чтобы обмен ключами в протоколе был аутентифицированным, должны быть выполнены два следующих требования^[20]:

Взаимная аутентификация: (аутентификация двух сторон) обе стороны аутентифицируют себя таким образом, чтобы каждая из сторон была уверена в идентичности другой стороны. B уверен, что A — единственный другой объект, который может знать правильный ключ. A уверен, что B — единственный другой объект, который может знать правильный ключ.
Защищенная связь: два взаимодействующих объекта устанавливают значения сеансовых ключей для защиты последующих передач.

Примечания[править | править код]

↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 13.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 137.
↑ Brita Vesterås: Analysis of Key Agreement Protocols, 2006, pp. 1—3.
↑ ¹ ² Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638
↑ Intellect. Как работает асимметричное шифрование понятным языком Архивная копия от 4 февраля 2018 на Wayback Machine. 20 мая 2012.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003.
↑ Brita Vesterås: Analysis of Key Agreement Protocols, 2006, p. 6.
↑ RSA Laboratories, 2000, p. 47.
↑ Buchmann J., Jacobson M. J., Teske E. On some computational problems in finite abelian groups (англ.) // Mathematics of Computation (англ.) (рус. : journal. — 1997. — Vol. 66. — P. 1663—1687. — doi:10.1090/S0025-5718-97-00880-6. Архивировано 4 марта 2016 года.
↑ RSA Laboratories, 2000.
↑ Rivest, Shamir, Adleman, 1978.
↑ Brita Vesterås: Analysis of Key Agreement Protocols, 2006, pp. 7—8.
↑ ¹ ² Brita Vesterås: Analysis of Key Agreement Protocols, 2006.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 24.
↑ ¹ ² ³ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 25.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 27.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 29.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 31.
↑ Chen, Kudla.
↑ ¹ ² Dent, Mitchell, 2004.

Литература[править | править код]

Colin Boyd, Anish Mathuria. Protocols for Authentication and Key Establishment. — International Standard, 2003. — ISBN 978-3-662-09527-0.
Dent A. W. and Mitchell C. J. User’s Guide to Cryptography and Standards. — ArtechHouse Computer Security Series, 2004. — P. 215-266. — ISBN 10: 1580535305.
Brita Vesterås. Online-Manuskript Analysis of Key Agreement Protocols (неопр.). Allen Institute for AI (2006).
L. Chen, C. Kudla. Online-Manuskript (PDF, 596 kB) Identity Based Authenticated Key Agreement Protocols from Pairings] (неопр.).
Rivest R., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems (англ.) // Communications of the ACM — New York City: Association for Computing Machinery, 1978. — Vol. 21, Iss. 2. — P. 120—126. — ISSN 0001-0782; 1557-7317 — doi:10.1145/359340.359342
Frequently Asked Questions About Today’s Cryptography (неопр.). RSA Laboratories (2000).

[_fcae0cd75b8146a1-1] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 13.

[_dd0672f07cab03a4-2] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 137.

[_3c35a63507cbbad4-3] Brita Vesterås: Analysis of Key Agreement Protocols, 2006, pp. 1—3.

[_ef6e2c33266405da-4] ¹ ² Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Transactions on Information Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638

[5] Intellect. Как работает асимметричное шифрование понятным языком Архивная копия от 4 февраля 2018 на Wayback Machine. 20 мая 2012.

[_6edcc1d6b237040d-6] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003.

[_878e9765eb34f4d6-7] Brita Vesterås: Analysis of Key Agreement Protocols, 2006, p. 6.

[_b9c535b5c7b99c1b-8] RSA Laboratories, 2000, p. 47.

[9] Buchmann J., Jacobson M. J., Teske E. On some computational problems in finite abelian groups (англ.) // Mathematics of Computation (англ.) (рус. : journal. — 1997. — Vol. 66. — P. 1663—1687. — doi:10.1090/S0025-5718-97-00880-6. Архивировано 4 марта 2016 года.

[_fc03b0495c7a9eb0-10] RSA Laboratories, 2000.

[_446f86ba7b0dd94d-11] Rivest, Shamir, Adleman, 1978.

[_f45bd265e6acb599-12] Brita Vesterås: Analysis of Key Agreement Protocols, 2006, pp. 7—8.

[_7e1f8046443807a0-13] ¹ ² Brita Vesterås: Analysis of Key Agreement Protocols, 2006.

[_fcae0bd75b8144eb-14] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 24.

[_fcae0bd75b8144ea-15] ¹ ² ³ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 25.

[_fcae0bd75b8144e8-16] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 27.

[_fcae0bd75b8144e6-17] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 29.

[_fcae0ad75b81431d-18] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment, 2003, p. 31.

[_69a28da5a0758960-19] Chen, Kudla.

[_d498f7b35b7b3222-20] ¹ ² Dent, Mitchell, 2004.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]