Лекция: Компрометация криптопротоколов

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

Атака на протокол Диффи-Хеллмана методом «человек в середине». Алиса и Боб хотят договориться об общем секретном ключе, обмениваясь несекретной информацией. Они выбирают конечное поле и примитивный элемент. Алиса и Боб договариваются о способе представления элементов поля. Проще всего это делается в случае поля вычетов по простому модулю.

Следует отметить, что при этом информация, передаваемая по открытому каналу связи, должна быть подписана участниками протокола. Исходные данные для реализации протокола, то есть поле и образующий элемент g, могут предоставляться каким – либо центром сертификации ключей (ЦСК). Эта информация также должна быть подписана с помощью секретного ключа ЦСК. То есть в любом случае предполагается, что Алиса и Боб абоненты сети связи, в которой реализована какая – либо система электронной цифровой подписи. Пусть это будет протокол Диффи – Хеллмана.

1) Алиса выбирает случайное число s,, вычисляет и передает S Бобу.

2) Боб выбирает случайное число t,, вычисляет и передает T Алисе.

3) Получив T, Алиса вычисляет .

4) Получив S, Боб вычисляет .

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

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

Предположим теперь, что Алиса и Боб не подписывают сообщения, которыми они обмениваются по протоколу Диффи – Хеллмана. Рассмотрим вскрытие протокола методом «человек в середине». Условно метод можно изобразить на рисунке

Алиса Противник Боб

После реализации протокола есть общий секретный ключ Алисы и Противника, а есть общий секретный ключ Противника и Боба. Пусть Алиса передает Бобу шифртекст, полученный на ключе К1. Противник перехватывает шифртекст, расшифровывает его с помощью ключа К1, зашифровывает полученный открытый текст на ключе К2 и передает Бобу. Таким образом, Противник читает секретную переписку Алисы и Боба. Этот метод несложно реализовать там, где в канале связи происходят задержки с передачей сообщений от одного абонента к другому.

Возможности противника в протоколе связи абонентов с использованием RSA. Рассмотрим протокол связи абонентов сети А, А, …, А с использованием RSA. Пусть у каждого абонента есть справочник, в котором находятся все открытые ключи всех абонентов е, е, …, е. Соответственно, d, d, …, d -секретные ключи абонентов… Абонент А хочет послать зашифрованное сообщение абоненту А. Пусть х – это открытый текст. Тогда А вычисляет c = x (modn).

Затем

А А ,

что означает, что абонент Аi посылает сообщение с абоненту Аj.

Получив сообщение с абонент А вычисляет х = с (modn).

То, что описано выше – это протокол секретной связи в сети. Данный протокол определяется следующими элементами.

1. Участники протокола – абоненты А и А ;

2. Язык протокола – (множество понимаемых участниками слов) – блок длины £ log n или последовательность блоков (сообщение = слова);

3. Порядок обмена сообщениями. Любой обмен это трехэтапная процедура:

· формирование сообщения у абонента А (в нашем случае – это формирование сообщения с);

· передача сообщения абоненту А ;

· формирование исходных данных для следующего шага протокола или завершения протокола (в нашем случае – это формирование х).

Криптопротокол в отличие от обычного протокола характеризуется наличием у некоторых участников секретов, то есть информации, которая известна одному или группе участников и не должна попасть к не участникам группы (информация может быть измерена информационным потоком или возможностью за приемлемое время вычислить секрет или часть его).

В протоколе связи два секрета: d – секрет А и х – секрет для А и А .

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

c = x (modn).

А А ,

х = с (modn) является частью следующего протокола.

Предполагаем расширение числа участников протокола («пассивный» перехват) за счет добавления участника Е, который из канала связи получает сообщение c = x (modn), переданное А .

А А

х = с (modn).

Так как мы не знаем действий Е, то с получением с его участие в протоколе завершено.

Возможно активное изменение протокола, то есть имеется еще один (активный) участник М:

c с’

А М А

Если М играет роль транслятора или Е, то функция протокола выполняется, иначе выполняется другой протокол вместо исходного.

В нашем случае цель модификации протокола – компрометация секрета, то есть получение хотя бы частичной информации о секрете не членами группы.

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

c = x (modn)

А А

c = x (modn)

А А

Пусть Е перехватывает все сообщения, и предположим, что x для c и c одно и то же. Поскольку Е знает e и e, он может вычислить НОД(e, e ). Если НОД(e, e )= 1, то в указанных предположениях он может провести компрометацию протокола секретной связи. Так по обобщенному алгоритму Евклида существуют r и s, что re +se =1. Если r <0, то Е считает (c ), тогда (c ) c = m (modn) = x.

Каким образом Е находит одинаковые x по c и c это другая проблема.

Протокол атаки «человек по середине». Существуют универсальные атаки. Пусть справочника открытых ключей RSA в сети нет. Протокол связи выглядит следующим образом:

А А

Модифицированный протокол, компрометирующий исходный протокол, носит название «человек по середине».

e e ’

А М А

c’ c

А М А

Здесь М передает А свой открытый ключ e ’ вместо полученного от А ключа e. Тогда

c’ = x (modn),

c = x (modn).

Защита от атаки «человек по середине». А и А обмениваются ключами и договариваются о передачи части сообщения. При этом оставшуюся часть посылают только после получения подтверждения о получении первой части сообщения. Такой способ защиты не всегда защищает секрет, но иногда позволяет выявить наличие «человека по середине». А именно, А вычисляет c =x (modn)

А А

А вычисляет c = у (modn).

А А

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

Иногда указанный метод не защищает. Пусть А и А создают ключ k для сеанса по правилу k = k + k. Тогда послав друг другу

А А

по половинке ключа, они попадут к противнику и М, сочинив свои половинки, создает свои ключи k’ и k».

Атака на протокол Фиата-Шамира.Напомним сначала этот протокол.Пусть, где — простые числа. Пара, где s принадлежит мультипликативной группе кольца вычетов есть секретный ключ А, а пара, где и, есть открытый ключ для А. Открытый ключ А хранится в памяти компьютера. А является законным пользователем компьютера и хочет получить к нему доступ. Следующие шаги повторяются раз.

1) А генерирует случайный секретный вычет, вычисляет и передает на компьютер,

2) компьютер генерирует случайный бит и передает объекту А,

3) А вычисляет и передает компьютеру,

4) компьютер проверяет сравнение

Если все сравнений из п.4) выполнены, то А получает доступ.

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

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

Противник может попытаться выдать себя за А, не зная. Он может действовать так:

1) выбирает случайный бит, случайный вычет, вычисляет и передает на компьютер,

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

Очевидно, вероятность успеха таких попыток за итераций равна, т.к. в силу того, что, тогда и только тогда, когда .

Протокол Фиата-Шамира есть пример протокола с нулевым раскрытием. Смысл этого понятия заключается в следующем. Рассмотрим запись протокола Фиата-Шамира. Это тройки чисел такие, что, а и выбираются случайно и независимо. Противник может получить сколько угодно таких троек самостоятельно без участия А, исходя лишь из знания открытого ключа объекта А. Действительно, противник может выбрать случайно и независимо, и вычислить тройку. Таким образом, запись этого протокола не предоставляет противнику никакой новой информации о секретном ключе .

Атака на протокол распределения ключей TMN. Рассмотрим менее примитивный пример атаки на протокол распределения ключей TMN (Tatebayashi-Matsuzakai-Newman) [1]. Пусть имеется мобильная сеть. Любая мобильная информация ограничена по вычислительным возможностям и по криптографии. Есть сервер с хорошими вычислительными возможностями и криптографией. Предположим, что сервер безопасен при хранении и использовании своего ключа (а не всех в сети). Любой терминал имеет алгоритм шифрования (DES) и систему с открытым ключом типа RSA: n=pq, c= x (modn). Сервер знает p и q и, следовательно, быстро вычисляет (modn). Пусть абоненты А и В хотят обменяться ключом k для DES, используя сервер S, которому доверяют. Протокол выглядит следующим образом.

Протокол 1.

1. А вычисляет случайное число r длиной 64 бит и вычисляет

c = (r ) (modn).

А S

2. S вычисляет r зная p и q и S генерирует g

S B

3. В вычисляет сеансовый ключ для DES r. В вычисляет c = (r ) (modn).

B S

4. S вычисляет r. S вычисляет E(r, r ) = r Å r .

E(r, r )

S А

5. А вычисляет E(r, r ) Å r = r — ключ сеанса.

Компрометация протокола. Е подслушивает все, что ему надо. Д – сообщник Е, Д и Е легальные пользователи сети. Цель Е – узнать секрет r (а затем открытый текст). Опираясь на свои возможности, Д и Е дополняют протокол 1.

1. Е подслушивает c = (r ) (modn), когда

B S

2. Е выбирает случайное число r (64 бит). Вычисляет r (modn). Вычисляет

c = (r ) r (modn) =(r r) (modn)

E S

с просьбой организовать связь с Д.

3. S вычисляет (modn) = r r(modn) и

вызов

S D

4.Д вычисляет c = (r ) (modn).

D S

5. S вычисляет r. S вычисляет (r + r r)(modn)= c