Протоколы MTI

Материал из Википедии — свободной энциклопедии
(перенаправлено с «MTI»)
Перейти к: навигация, поиск

Протоколы MTI — семейство протоколов распределения ключей, разработанные Т. Мацумото (T. Matsumoto), И. Такасита (Y. Takashita) и Х. Имаи (H. Imai) и названные по именам авторов. Протоколы MTI делятся на три класса протоколов: MTI/A, MTI/B, MTI/C.[1]

Протокол распределения ключей решает задачу распределения секретных ключей шифрования между общающимися сторонами. Множество таких протоколов делится на следующие три типа:[2]

  1. протоколы обмена уже сгенерированными ключами;
  2. протоколы совместной выработки общего ключа (открытое распределение ключей);
  3. протоколы предварительного распределения ключей.

Протоколы MTI относятся к протоколам открытого распределения ключей.

В основе протоколов открытого распределения ключей лежит обмен сообщениями между пользователями, по результатам которого каждый пользователь вычисляет секретный сеансовый ключ. При этом вычисление сеансового ключа до обмена сообщениями невозможно. Поэтому данные протоколы еще называют[3] динамическими протоколами распределения ключей в отличие от статических протоколов, в которых ключи известны еще до самого сеанса связи. Кроме того, создание сеансовых ключей в протоколах открытого распределения требует от пользователей знания только открытых ключей, т.е. позволяет паре пользователей системы выработать общий секретный ключ, не обмениваясь закрытыми ключами. Именно это привело к тому, что такие протоколы сразу же после своего появления в 1976 году привлекли к себе внимание международного сообщества.


История[править | править вики-текст]

Идея построения протоколов открытого распределения ключей была впервые высказана Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) на «Национальной Компьютерной Конференции» в июне 1976 года. И в ноябре 1976 года ими же в работе «Новые направления в криптографии» (англ. New Directions in Cryptography) был предложен первый протокол открытого распределения ключей[4], названный по именам авторов (протокол Диффи-Хеллмана).

Первый в своем роде, протокол Диффи-Хеллмана был уязвим к некотором типам атак, в частности, к атаке «человек посередине»[2]. Для решения данной проблемы необходимо было обеспечить пользователей механизмом аутентификации. Таким механизмом стал опубликованный в августе 1977 года в колонке «Математические игры» журнала Scientific American алгоритм асимметричного шифрования RSA[5], который позволил решить проблему общения через открытый канал.

В 1984 году Тахером Эль-Гамалем был предложен усовершенствованный протокол Диффи-Хеллмана с возможностью односторонней аутентификации, когда только одна из общающихся сторон может проверить подлинность другой[6]. В отличие от RSA протокол Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

В феврале 1986 года Т. Мацумото, И. Такашима и Х. Имаи представили решение проблемы взаимной аутентификации без использования RSA[7]. В разработанных ими протоколах MTI выражение для вычисления общего секретного ключа содержит как открытые, так и закрытые ключи легальных пользователей. Это решение позволяет провести аутентификацию одновременно с вычислением общего секретного ключа (нелегальный пользователь не может вычислить значение секретного ключа).

На настоящий момент протоколы MTI включены в стандарт ISO/IEC 11770-3[1].

Описание протоколов MTI[1][править | править вики-текст]

Рассмотрим процесс обмена информацией между сторонами A и B. Ниже представлены обозначения, которые будут использованы при описании работы протоколов MTI.

большое простое число (не менее 1024 бит).
простое число (порядка 160 бит), являющееся делителем числа .
подгруппа группы (обычно порядка , но иногда совпадает с )
порождающий элемент подгруппы
, закрытые ключи сторон A и B
, открытые ключи сторон A и B : , .
, случайные целые числа, обычно той же величины, что и порядок группы , выбираемые сторонами A и B соответственно
, сообщения, отправляемые от A к B и от B к A соответственно.
секретный сеансовый ключ, вычисленный сторонами A и B
элеменет выбирается случайно из множества
наибольший общий делитель чисел и

Все вычисления в дальнейшем проводятся в группе .

MTI/A(0)[8][править | править вики-текст]

Алгоритм работы

  1. Сторона выбирает случайное число и отправляет сообщение
  2. Сторона выбирает случайное число и отправляет сообщение
  3. Сторона вычисляет сеансовый ключ:
  4. Сторона вычисляет сеансовый ключ:


Проводимые вычисления

MTI/B(0)[править | править вики-текст]

Алгоритм работы

  1. Сторона выбирает случайное число и отправляет сообщение
  2. Сторона выбирает случайное число и отправляет сообщение
  3. Сторона вычисляет сеансовый ключ:
  4. Сторона вычисляет сеансовый ключ:


Прводимые вычисления


MTI/C(0)[8][править | править вики-текст]

Алгоритм работы

  1. Сторона выбирает случайное число и отправляет B сообщение
  2. Сторона выбирает случайное число и отправляет A сообщение
  3. Сторона вычисляет сеансовый ключ:
  4. Сторона вычисляет сеансовый ключ:


Проводимые вычисления

MTI/A(k)[править | править вики-текст]

Алгоритм работы

  1. Сторона выбирает случайное число и отправляет B сообщение
  2. Сторона выбирает случайное число и отправляет A сообщение
  3. Сторона вычисляет сеансовый ключ:
  4. Сторона вычисляет сеансовый ключ:


Проводимые вычисления

MTI/B(k)[править | править вики-текст]

Алгоритм работы

  1. Сторона выбирает случайное число и отправляет сообщение
  2. Сторона выбирает случайное число и отправляет сообщение
  3. Сторона вычисляет сеансовый ключ:
  4. Сторона вычисляет сеансовый ключ:


Проводимые вычисления

MTI/C(k)[править | править вики-текст]

Алгоритм работы

  1. Сторона выбирает случайное число и отправляет сообщение
  2. Сторона выбирает случайное число и отправляет сообщение
  3. Сторона вычисляет сеансовый ключ:
  4. Сторона вычисляет сеансовый ключ:


Проводимые вычисления

Анализ протоколов MTI[3][править | править вики-текст]

Таблица протоколов MTI
Протокол
MTI/A(0)
MTI/B(0)
MTI/C(0)
MTI/A(k)
MTI/B(k)
MTI/C(k)
  1. Протоколы MTI/A и MTI/B требуют от каждого пользователя вычисления трех экспонент, тогда как протоколы MTI/C требуют вычисления только двух экспонент. Протокол MTI/C(1) имеет также дополнительное преимущество, состоящее в том, что не требуется вычислять обратные элементы для и . С другой стороны эти значения не меняются в течение всего сеанса связи и поэтому могут быть рассчитаны заранее.
  2. Все стороны в протоколах MTI проводят аналогичные операции, причем работа протоколов не зависит от того, в каком порядке посылаются сообщения от одной стороны к другой.
  3. Протоколы MTI/B и MTI/C требуют знания открытых ключей других сторон, для чего может потребоваться дополнительным обмен сообщениями (если информация об открытых ключах не помещается в отправляемых по сети сообщениях). Протоколы MTI/A знания открытых ключей не требуют, что позволяет избежать дополнительных передач и временных задержек.
  4. Все три класса протоколов обеспечивают взаимную неявную аутентификацию ключей (mutual implicit key authentication), но не обеспечивают подтверждения правильности ключей (key confirmation) и аутентификацию сторон (entitiy authentication).
Сравнение протоколов распределения ключей
Протокол Аутентификация ключа Аутентификация источников Подтверждение ключа Число сообщений
протокол Диффи-Хеллмана отсутствует отсутствует отсутствует 2
протокол Эль-Гамаля односторонняя отсутствует отсутствует 1
MTI/A взаимная неявная отсутствует отсутствует 2
MTI/B,C взаимная неявная отсутствует отсутствует 2
STS взаимная явная взаимная отсутствует 3

Атаки на протоколы MTI[править | править вики-текст]

Протоколы MTI противостоят пассивным атакам, однако уязвимы к активным атакам[3]. Ниже представлены примеры активных атак на протоколы MTI.

Атака по малой подгруппе на протоколы MTI/C[1][править | править вики-текст]

Атака по подгруппе (Small Subgroup Attack) применяется к классу протоколов MTI/C в том случае, если группа совпадает с группой , как и предполагается в оригинальном протоколе. Предполагается, что криптоаналитику известно разложение числа на простые множители. Пусть — наименьший простой множитель в разложении числа . Обозначим . Атака заключается в возведении всех сообщений в степень , что переводит передаваемые элементы в малую подгруппу группы .

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

Ниже описан процесс атаки на протокол MTI/C(0). Криптоаналитик находится между сторонами и (man-in-the-middle).

  1. Сторона выбирает случайное число и отправляет сообщение
  2. Криптоаналитик перехватывает сообщение от и отправляет сообщение
  3. Сторона выбирает случайное число и отправляет сообщение
  4. Криптоаналитик перехватывает сообщение от и отправляет сообщение
  5. Сторона вычисляет сеансовый ключ:
  6. Сторона вычисляет сеансовый ключ:

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

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

Атака с неизвестным общим ключом[1][3][9][править | править вики-текст]

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

Атака с неизвестным общим ключом осуществляется путём выполнения следующей последовательности действий.

  1. Сторона выбирает случайное число и отправляет сообщение
  2. Криптоаналитик передает сообщение от к в неизменном виде.
  3. Сторона выбирает случайное число и отправляет сообщение
  4. Криптоаналитик получает сообщение от и отправляет сообщение
  5. Сторона вычисляет сеансовый ключ:
  6. Сторона вычисляет сеансовый ключ:

Секретные ключи, вычисленные сторонами и , одинаковы и равны . При этом считает, что разделяет его с , в то время как считает, что разделяет ключ с .

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

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

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

  1. 1 2 3 4 5 Colin Boyd, Anish Mathuria. 5.3 MTI Protocols // Protocols for Authentication and Key Establishment. — Springer, 2003. — С. 147-155. — 321 с. — ISBN 3540431071.
  2. 1 2 Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Глава 15. Протоколы распределения ключей // Основы криптографии. — 2-е, испр. — Москва: Гелиос АРВ, 2002. — С. 378, 387-396. — 480 с. — 3000 экз. — ISBN 5-85438-025-0.
  3. 1 2 3 4 Menezes, Oorschot, Vanstone, 1996.
  4. Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Trans. Inf. Theory / F. KschischangIEEE, 1976. — Vol. 22, Iss. 6. — P. 644–654. — ISSN 0018-9448doi:10.1109/TIT.1976.1055638
  5. Martin Gardner. Mathematical Games: A new kind of cipher that would take millions of years to break (англ.) // Scientific American. — 1977.
  6. Taher ElGamal (1985). «A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms». IEEE Transactions on Information Theory 31 (4): 469-472. DOI:10.1109/TIT.1985.1057074.
  7. Tsutomu Matsumoto, Youichi Takashima, and Hideki Imai. On seeking smart public-key-distribution systems. // Transactions of the IECE of Japan. — February 1986. — Т. E69. — С. 99–106.
  8. 1 2 Ratna Dutta, Rana Barua Overview of Key Agreement Protocols. — С. 9-10.
  9. Черемушкин А. В. Криптографические протоколы: основные свойства и уязвимости // Прикладная дискретная математика : Приложение. — 2009. — № 2. — С. 115-150. Архивировано 3 ноября 2013 года.

Литература[править | править вики-текст]