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

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

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

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

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

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

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

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

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

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

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

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

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

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

Затем

c

А А ,

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

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

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

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

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

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

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

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

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

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

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

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

c = x (modn).

c

А А ,

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

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

c

А А

с

Е

х = с (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

А А

c

А А

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

e e ’

А М А

c’ c

А М А

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

c’ = x (modn),

c = x (modn).

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

А А

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

А А

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

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

/2

А А

/2

А А

по половинке ключа, они попадут к противнику и М, сочинив свои половинки, создает свои ключи 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).

c

А S

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

g

S B

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

c

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), когда

c

B S

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

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

c

E S

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

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

вызов

S D

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

c

D S

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

c

S E

6. Так как Е и Д в сговоре, то Е знает r . Тогда Е вычисляет r из уравнения

(r + r r)(modn)= c .

Именно r = (c -r )r (modn).