Протокол совместной выработки ключа

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

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

Появление протоколаПравить

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

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

Подход к созданиюПравить

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

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

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

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

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

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

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

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

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

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

Задача факторизации^[11]Править

Односторонняя функция: умножение $\text{[math]}$ $\text{[math]}$ $\leftrightarrow$ факторизация.

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

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

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

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

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

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

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

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

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

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

ПримерыПравить

Атаки на протоколПравить

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

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

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

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

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

Атака модификациейПравить

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

Атака повторомПравить

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

Атака отражениемПравить

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

Атаки типа «отказ в обслуживании»Править

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

КриптоанализПравить

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

Пересечение протоколовПравить

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

АутентификацияПравить

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

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

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

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

ПримечанияПравить

↑ Colin Boyd, Anish Mathuria . 'Protocols for Authentication and Key Establishment', 2003. International Standard. — p.13, ISBN 13:978-3-662-09527-0.
↑ Colin Boyd, Anish Mathuria . 'Protocols for Authentication and Key Establishment', 2003. International Standard. — p.137, ISBN 13:978-3-662-09527-0.
↑ Brita Vesterås: Analysis of Key Agreement Protocols., — pp.1-3, 2006.
↑ ¹ ² Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Trans. Inf. 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.
↑ Colin Boyd, Anish Mathuria . 'Protocols for Authentication and Key Establishment', 2003. International Standard. ISBN 13:978-3-662-09527-0.
↑ Brita Vesterås: Analysis of Key Agreement Protocols., — p.6, 2006.
↑ RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, — p.47, 2000.
↑ RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, — p.54, 2000.
↑ 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.
↑ RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, — p.48, 2000.
↑ RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, 2000.
↑ Rivest, Shamir, Adleman, 1978.
↑ Brita Vesterås: Analysis of Key Agreement Protocols., — pp.7-8, 2006.
↑ ¹ ² Brita Vesterås: Analysis of Key Agreement Protocols., 2006.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.24, 2003 — ISBN 978-3-662-09527-0.
↑ ¹ ² ³ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.25, 2003 — ISBN 978-3-662-09527-0.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.27, 2003 — ISBN 978-3-662-09527-0.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.29, 2003 — ISBN 978-3-662-09527-0.
↑ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.31, 2003 — ISBN 978-3-662-09527-0.
↑ L. Chen and C. Kudla. Identity Based Authenticated Key Agreement Protocols from Pairings .
↑ ¹ ² Dent, Mitchell, 2004.

ЛитератураПравить

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: Analysis of Key Agreement Protocols. Online-Manuskript Архивная копия от 5 декабря 2019 на Wayback Machine (PDF, 416 kB) (2006)
L. Chen and C. Kudla. Identity Based Authenticated Key Agreement Protocols from Pairings . Online-Manuskript (PDF, 596 kB) (12 февраля 2003)
RSA Laboratories: Frequently Asked Questions About Today’s Cryptography , Version 4.1. (PDF, 1539 kB) (2000)

[_2e0334deceda7569-1] Colin Boyd, Anish Mathuria . 'Protocols for Authentication and Key Establishment', 2003. International Standard. — p.13, ISBN 13:978-3-662-09527-0.

[_8f3b38b614489a90-2] Colin Boyd, Anish Mathuria . 'Protocols for Authentication and Key Establishment', 2003. International Standard. — p.137, ISBN 13:978-3-662-09527-0.

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

[_24b4c4d14cbf686e-4] ¹ ² Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Trans. Inf. 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.

[_9af7135d9ef27f9d-6] Colin Boyd, Anish Mathuria . 'Protocols for Authentication and Key Establishment', 2003. International Standard. ISBN 13:978-3-662-09527-0.

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

[_5c0f298a774c9f6f-8] RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, — p.47, 2000.

[_4230e12236b460f3-9] RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, — p.54, 2000.

[10] 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.

[_09aaa743f9d42dda-11] RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, — p.48, 2000.

[_aa91f25bf1d38dbe-12] RSA Laboratories. Frequently Asked Questions About Today’s Cryptography, Version 4.1. http://www.rsasecurity.com/rsalabs, 2000.

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

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

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

[_0195edea58a11960-16] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.24, 2003 — ISBN 978-3-662-09527-0.

[_0a17d3674187e4a5-17] ¹ ² ³ C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.25, 2003 — ISBN 978-3-662-09527-0.

[_6effc151353d20a3-18] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.27, 2003 — ISBN 978-3-662-09527-0.

[_23fd03b7cec071a9-19] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.29, 2003 — ISBN 978-3-662-09527-0.

[_fc238d8977feaf9a-20] C. Boyd and A. Mathuria. Protocols for Authentication and Key Establishment. Springer Verlag, — p.31, 2003 — ISBN 978-3-662-09527-0.

[_84e2e441974911f3-21] L. Chen and C. Kudla. Identity Based Authenticated Key Agreement Protocols from Pairings .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]