Эта статья входит в число хороших статей

Протокол Нидхема — Шрёдера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Криптографические обозначения, используемые в протоколах проверки подлинности и обмена ключами
A Идентифкаторы Алисы (Alice), инициатора сессии
B Идентифкатор Боба (Bob), стороны, с которой устанавливается сессия
T Идентифкатор Трента (Trent), доверенной промежуточной стороны
K_A, K_B, K_T Открытые ключи Алисы, Боба и Трента
K_A^{-1}, K_B^{-1}, K_T^{-1} Секретные ключи Алисы, Боба и Трента
E_A, \left\{...\right\}_{K_A} Шифрование данных ключом Алисы, либо совместным ключом Алисы и Трента
E_B, \left\{...\right\}_{K_B} Шифрование данных ключом Боба, либо совместным ключом Боба и Трента
\left\{...\right\}_{K_B^{-1}}, \left\{...\right\}_{K_A^{-1}} Шифрование данных секретными ключами Алисы, Боба (цифровая подпись)
I Порядковый номер сессии (для предотвращения атаки с повтором)
K Случайный сеансовый ключ, который будет использоваться для симетричного шифрования данных
E_K, \left\{...\right\}_{K} Шифрование данных временным сеансовым ключом
T_A, T_B Метки времени, добавляемые в сообщения Алисой и Бобом соответственно
R_A, R_B Случайные числа (nonce), которые были выбраны Алисой и Бобом соответственно

Протокол Нидхема — Шрёдера — общее название для симметричного и асимметричного протоколов аутентификации и обмена ключами. Оба протокола были предложены Майклом Шрёдером (англ.)русск. и Роджером Нидхемом[1]. Вариант, основанный на симметричном шифровании, использует промежуточную доверенную сторону. Этот протокол стал основой для целого класса подобных протоколов. Например, Kerberos является одним из вариантов симметричного протокола Нидхема — Шрёдера. Вариант, основанный на асимметричном шифровании, предназначен для взаимной аутентификации сторон. В оригинальном виде оба варианта протокола являются уязвимыми[2][3].

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

Протокол для аутентификации с симметричным ключом, вероятно являющийся самым знаменитым протоколом аутентификации и установления ключа, был сформулирован Майклом Шрёдером и Роджером Нидхемом в 1978 году[1]. Однако, он уязвим для атаки, изобретенной Дороти Деннинг (англ. Dorothy E. Denning) и Джованни Марией Сакко (англ. Giovanni Maria Sacco) в 1981 году[2]. Несмотря на это, он стал основой для целого класса подобных протоколов. В частности, протокол Kerberos является одним из вариантов Нидхем-Шрёдер-протокола аутентификации на основе доверенной третьей стороны и его модификациях, предложенных Деннинг и Сакко[2]. Протокол Нидхема-Шрёдера для аутентификации с открытым ключом также является уязвимым. В 1995 году Лоу (англ. Gavin Lowe) описал возможную атаку на протокол[3].

Протокол Нидхема-Шрёдера для аутентификации с симметричным ключом[править | править вики-текст]

Протокол Нидхема-Шрёдера для аутентификации с симметричным ключом

При схеме шифрования с симметричным ключом, предполагается, что секретный ключ известен и серверу аутентификации T (Трент) и обоим субъектам обмена: A (Алиса) и B (Боб). Изначально оба субъекта имеют секретные ключи: K_A и K_B, известные только им и некоторой доверенной стороне - серверу аутентификации. В ходе выполнения протокола Алиса и Боб получают от сервера новый секретный сессионный ключ для шифрования взаимных сообщений в данном сеансе связи, т.е. сообщения от Алисы к Бобу дешифровать может только Боб, сообщения от Боба к Алисе дешифровать может только Алиса. Кроме того субъекты обмена должны быть уверены, что пришедшее сообщение было отправлено именно тем, с кем должен произойти обмен. Боб должен быть уверен, что получил сообщение именно от Алисы и наоборот. Это также обеспечивается протоколом. Предположим, что обмен инициирует Алиса. Будем полагать, что сервер аутентификации у них общий. Рассмотрим реализацию протокола[4]:

  1. Alice \to A, B, R_A \to Trent
  2. Trent \to \left\{ R_A, B, K, \left\{ K, A \right\}_{K_B} \right\}_{K_A} \to Alice
  3. Alice \to \left\{ K, A \right\}_{K_B} \to Bob
  4. Bob \to \left\{ R_B \right\}_{K} \to Alice
  5. Alice \to \left\{ R_B - 1 \right\}_{K} \to Bob

Обмен начинается с того, что Алиса генерирует некоторое случайное число R_A (идентификатор), использующееся один раз. Первое сообщение от Алисы к Тренту содержит в себе имена участников предстоящего обмена и генерированное Алисой случайное число:

Alice \to A, B, R_A \to Trent

Данное сообщение посылается открытым текстом, но может быть зашифровано ключом Алисы K_A:

Alice \to \left\{ A, B, R_A \right\}_{K_A} \to Trent

При получении этого сообщения Трент извлекает из базы данных секретные ключи Алисы и Боба: K_A и K_B, а также вычисляет новый сессионный ключ K. Далее Трент посылает Алисе следующее сообщение:

Trent \to \left\{ R_A, B, K, \left\{ K, A \right\}_{K_B} \right\}_{K_A} \to Alice

Алиса может дешифровать и прочесть сообщение от Трента. Она проверяет наличие своего идентификатора R_A в сообщении, что подтверждает то, что данное сообщение является откликом на ее первое сообщение Тренту. Также она проверяет имя субъекта, с которым собирается обмениваться данными. Эта проверка обязательна, так как если бы не было этого имени, Злоумышленник мог бы заменить имя Боба на свое в первом сообщении, и Алиса, ничего не подозревая, в дальнейшем бы взаимодействовала со Злоумышленником. Часть сообщения Алиса прочитать не может, так как эта часть зашифрована ключом Боба. Алиса пересылает Бобу зашифрованный его ключом фрагмент:

Alice \to \left\{ K, A \right\}_{K_B} \to Bob

Дешифровать его может только Боб, так как оно зашифровано его секретным ключом. После дешифровки Боб тоже владеет сессионным ключом K. Имя Алисы в сообщении подтверждает факт, что сообщение от неё. Далее при обмене данными будет использоваться сессионный ключ. Чтобы сделать схему симметричной и уменьшить вероятность атаки воспроизведения, Боб генерирует некоторое случайное число R_B (идентификатор Боба) и посылает Алисе следующее сообщение, зашифрованное сессионным ключом:

Bob \to \left\{ R_B \right\}_{K} \to Alice

Алиса дешифрует его и посылает отклик, который ожидает Боб, также зашифрованный сессионным ключом:

Alice \to \left\{ R_B - 1 \right\}_{K} \to Bob

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

Атака на протокол Нидхема-Шрёдера для аутентификации с симметричным ключом[править | править вики-текст]

Атака на протокол Нидхема-Шрёдера для аутентификации с симметричным ключом

Протокол Нидхема-Шрёдера уязвим для атаки с повторной передачей сообщения, изобретённой Дороти Деннинг (англ. Dorothy E. Denning) и Джованни Марией Сакко (англ. Giovanni Maria Sacco) в 1981 году[2]. В ходе атаки Злоумышленник перехватывает и заменяет сообщения из пунктов 3,4,5 протокола. Злоумышленник перехватывает сообщение от Алисы к Бобу на третьем шаге протокола и блокирует Алису. Потом заменяет актуальное сообщение Алисы на другое из старого сеанса между Алисой и Бобом. Исходя из предположения об уязвимости старого сеансового ключа, Злоумышленник может узнать его значение и начать обмен данными с Бобом под видом Алисы[4].

В результате Боб думает, что имеет новый сеансовый ключ с Алисой, но на самом деле ключ старый и известен Злоумышленнику.

Рассмотрим возможную реализацию атаки:

  • Обмен начинается так же, как и в протоколе. Алиса генерирует случайное число и посылает Тренту. Трент извлекает из базы данных секретные ключи Алисы и Боба, вычисляет новый сессионный ключ K и посылает ответ Алисе. Алиса расшифровывает сообщение, проверяет случайное число и имя субъекта, с которым собирается обмениваться данными. Отправляет сообщение Бобу.
Alice \to A, B, R_A \to Trent
Trent \to \left\{ R_A, B, K, \left\{ K, A \right\}_{K_B} \right\}_{K_A} \to Alice
Alice \to \left\{ K, A \right\}_{K_B} \to Bob
  • После этого в ход протокола вмешивается Злоумышленник. Сначала он перехватывает сообщение Алисы Бобу, потом полностью блокирует канал связи Алисы. Исходя из предположения об уязвимости старого сеансового ключа, Злоумышленник может узнать его значение. Кроме значения старого ключа у Злоумышленника есть материал старого сеанса между Алисой и Бобом: Alice \to \left\{ K_P, A \right\}_{K_B} \to Bob, где  K_P (previous key) — старый ключ. Выдавая себя за Алису, он посылает Бобу сообщение со старым ключом:
Alice(Attacker) \to \left\{ K_P, A \right\}_{K_B} \to Bob
  • Боб расшифровывает сообщение и убеждается, что оно от Алисы, не подозревая, что подвергся атаке и общается уже со Злоумышленником. Он посылает "Алисе" свое случайное число:
Bob \to \left\{ R_B \right\}_{K_P} \to Alice(Attacker)
  • Злоумышленник, зная значение старого ключа, расшифровывает сообщение Боба. Он, как и положено, уменьшает на единицу значение случайного числа Боба, шифрует результат с помощью того же старого сессионного ключа и отправляет сообщение Бобу:
Alice(Attacker) \to \left\{ R_B - 1 \right\}_{K_P} \to Bob

В итоге Боб уверен, что установил сеанс связи с Алисой, так как все необходимые шаги протокола были проделаны верно и все сообщения оказались корректны.

Эта атака порождает более серьёзную опасность — отсутствие реальной связи между партнёрами. Злоумышленник не обязан ждать, когда Алиса запустит протокол. Поскольку он знает старый сеансовый ключ  K_P , он может сам начать атаку, начав протокол с этапа 3. Боб будет думать, что установил контакт с Алисой в то время как Алиса вообще не выходила на связь[6].

Исправление уязвимости[править | править вики-текст]

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

  1. Alice \to A, B, R_A \to Trent
  2. Trent \to \left\{ R_A, A, B, \left\{ K \right\}_{K_A} \right\}_{K_A}, \left\{ t, A, B, \left\{ K \right\}_{K_B} \right\}_{K_B} \to Alice
  3. Alice \to \left\{ t, A, B, \left\{ K \right\}_{K_B} \right\}_{K_B} \to Bob
  4. Bob \to \left\{ R_B \right\}_{K} \to Alice
  5. Alice \to \left\{ R_B - 1 \right\}_{K} \to Bob

Получив протокольные сообщения от Трента, Алиса и Боб могут обнаружить, что их послания остались без ответа, проверив неравенство:

 t_{curr} - t < \Delta t_1 + \Delta t_2

где t_{curr} (current time) - текущее локальное время получателя; \Delta t_{1} - интервал, представляющий допустимую разницу между временем Трента и локальным временем; \Delta t_{2} - ожидаемая временная задержка. Отсюда они убеждаются в "свежести" сообщений и в частности сессионного ключа. Т.к. временная метка зашифрована секретными ключами Алисы и Боба, то в идеальной схеме шифрования имитация Трента невозможна[7].

Также в данной уточнённой спецификации протокола необходимость защиты целостности данных выделена явно. Если сообщения, которыми обмениваются участники протокола, не искажались в процессе передачи, то после процедуры верификации обе стороны могут быть уверены, что сеансовый ключ согласован как с пользователями, так и с идентификатором «свежести». Это должно убедить их в подлинности друг друга и в том, что не используется старый сеансовый ключ[8].

Случай разных серверов аутентификации[править | править вики-текст]

Случай разных серверов аутентификации

В реальной жизни Алиса и Боб могут оказаться на достаточно большом расстоянии, чтобы не существовало общего сервера аутентификации[5]. По этой причине в общем случае Алиса может иметь свой сервер аутентификации: T_A, а Боб свой: T_B. Так как и в этом случае перед Алисой стоит задача построить для Боба сообщение вида \left\{ K, A \right\}_{K_B}. Для его формирования будут задействованы оба сервера, так как только T_A умеет шифровать ключом Алисы K_A, и только T_B может использовать ключ Боба: K_B. При этом безопасность обмена между серверами предполагается обеспеченной. Рассмотрим пример для случая двух разных серверов, имеющих соединение друг с другом:

  1. Alice \to A, B, R_A \to Trent_A
  2. Trent_A \to A, B, R_A, K \to Trent_B
  3. Trent_B \to A, R_A, \left\{ K, A \right\}_{K_B} \to Trent_A
  4. Trent_A \to \left\{ R_A, B, K, \left\{ K, A \right\}_{K_B} \right\}_{K_A} \to Alice
  5. Alice \to \left\{ K, A \right\}_{K_B} \to Bob
  6. Bob \to \left\{ R_B \right\}_{K} \to Alice
  7. Alice \to \left\{ R_B - 1 \right\}_{K} \to Bob

Шаги 1, 4-7 соответстуют шагам 1-5 из описанного выше случая с общим сервером аутентификации. На втором шаге сервер Алисы, не найдя в списке своих клиентов Боба, обращается к серверу Боба. Тот знает ключ Боба и может выполнить необходимое шифрование. После чего зашифрованная информация передается обратно серверу аутентификации Алисы, который и посылает её Алисе[5].

Протокол с аутентификацией сущности[править | править вики-текст]

Механизм «отклика-отзыва»[9] из протокола обеспечивает так называемую аутентификацию сущности (entity authentication)[ISO 1]. Аутентификация сущности осуществляется с помощью проверки верифицирующим пользователем некоторой криптографической операции. В её ходе демонстрируется существование доказывающего пользователя, которое считается подтверждённым, если доказывающий пользователь выполнил некоторую криптографическую операцию после события, которое другой пользователь считает последним.

На втором этапе протокола Нидхема-Шрёдера Алиса расшифровывает одноразовое случайное число, которое сгенерировала она сама на первом этапе. Это подтверждает тот факт, что Трент выполнил шифрование после получения сообщения от Алисы. В итоге Алиса знает, что Трент существовал после этого события, то есть Трент прошел аутентификацию существования по отношению к Алисе. В то же время Боб, участвующий в том же протоколе, не может быть уверен в существовании Трента[7].

Протокол Нидхема-Шрёдера для аутентификации с открытым ключом[править | править вики-текст]

Криптосистемы с открытым ключом[править | править вики-текст]

Введём обозначения:

Причем секретный ключ знает только Алиса, а открытый ключ известен окружающим.

  • Mоткрытый текст;
  • \left\{M\right\}_{K_A} — текст зашифрован открытым ключом Алисы и может быть расшифрован только Алисой с помощью её секретного ключа;
  • \left\{M\right\}_{K_{A}^{-1}} — текст зашифрован секретным ключом Алисы и может быть расшифрован с помощью открытого ключа Алисы.

Это означает, что текст \left\{M\right\}_{K_{A}^{-1}} при идеальном шифровании гарантированно создан Алисой, потому что данным секретным ключом владеет только она. Именно поэтому зашифрованный текст \left\{M\right\}_{K_{A}^{-1}} называется цифровой подписью сообщения M. Его расшифровка с помощью открытого ключа называется верификацией подписи Алисы[10].

Протокол Нидхема-Шрёдера для аутентификации с открытым ключом[править | править вики-текст]

Протокол Нидхема — Шрёдера для аутентификации с открытым ключом

Асимметричный вариант (двух ключевая схема) протокола Нидхема — Шрёдера. Трент владеет открытыми ключами всех обслуживаемых им клиентов. Алиса имеет открытый ключ K_A и секретный ключ K_{A}^{-1}, Боб — K_B и K_{B}^{-1}, Трент — K_T и K_{T}^{-1}. Пусть Алиса инициирует новый сеанс связи с Бобом[11]:

  1. Alice \to A, B \to Trent
  2. Trent \to {\left\{ K_B, B \right\}}_{K_{T}^{-1}} \to Alice
  3. Alice \to T, \left\{ R_A, A \right\}_{K_B} \to Bob
  4. Bob \to B, A \to Trent
  5. Trent \to \left\{ K_A, A \right\}_{K_{T}^{-1}} \to Bob
  6. Bob \to \left\{ R_A, R_B \right\}_{K_A} \to Alice
  7. Alice \to \left\{ R_B \right\}_{K_B} \to Bob

Алиса — инициатор протокола — в первом сообщении запрашивает у Трента открытый ключ Боба:

Alice \to A, B \to Trent

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

Trent \to {\left\{ K_B, B \right\}}_{K_{T}^{-1}} \to Alice

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

Alice \to T, \left\{ R_A, A \right\}_{K_B} \to Bob

Только Боб может дешифровать данное сообщение, так как для этого необходим его секретный ключ K_{B}^{-1}. Из сообщения он узнаёт, что Алиса хочет начать обмен данными с ним. Следовательно, Бобу нужен открытый ключ Алисы и он делает операции, аналогичные проделанным Алисой:

Bob \to B, A \to Trent
Trent \to \left\{ K_A, A \right\}_{K_{T}^{-1}} \to Bob

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

Bob \to \left\{ R_A, R_B \right\}_{K_A} \to Alice
Alice \to \left\{ R_B \right\}_{K_B} \to Bob

Нидхем и Шрёдер предложили использовать числа R_A и R_B для инициализации общего секретного ключа[1], обеспечивающего секретную связь между Алисой и Бобом. Позже Деннинг и Сакко указали, что этот протокол не гарантирует, что открытые ключи являются новыми, а не повторами старых. Эту проблему можно решить разными способами, в частности используя временные метки[2] в сообщениях с ключами. Нидхем и Шрёдер также рассматривали возможность применения меток времени, но отвергли эту идею из-за отсутствия качественного эталона времени[12].

Атака на протокол Нидхема-Шрёдера для аутентификации с открытым ключом[править | править вики-текст]

Атака на протокол Нидхема-Шрёдера для аутентификации с открытым ключом

Атака на протокол была предложена Лоу (англ. Gavin Lowe)[3]. Он разделил протокол на две части, не связанные логически. Первая: 1, 2, 4, 5 этапы протокола — получение открытого ключа. Вторая: 3, 6, 7 этапы — аутентификация Алисы и Боба. Будем полагать, что первая часть состоялась и рассмотрим вторую:

3. Alice \to T, \left\{ R_A, A \right\}_{K_B} \to Bob
6. Bob \to \left\{ R_A, R_B \right\}_{K_A} \to Alice
7. Alice \to \left\{ R_B \right\}_{K_B} \to Bob

Пусть Злоумышленник (Аttacker) — лицо, являющееся законным пользователем системы. Он может проводить стандартные сеансы связи с остальными пользователями системы. Для атаки используется одновременный запуск двух протоколов: в первом Алиса проводит корректный сеанс со Злоумышленником, во втором Злоумышленник выдаёт себя за Алису при общении с Бобом[13].

1.3. Alice \to T, \left\{ R_A, A \right\}_{K_{At}} \to Attacker
2.3. Attacker(Alice) \to T, \left\{ R_A, A \right\}_{K_B} \to Bob
2.6. Bob \to \left\{ R_A, R_B \right\}_{K_A} \to Attacker(Alice)
1.6. Attacker \to \left\{ R_A, R_B \right\}_{K_A} \to Alice
1.7. Alice \to \left\{ R_B \right\}_{K_{At}} \to Attacker
2.7. Attacker(Alice) \to \left\{ R_B \right\}_{K_B} \to Bob

На этапе 1.3 Алиса посылает Злоумышленнику случайное число R_A, которое Злоумышленник тут же на этапе 2.3 другого протокола пересылает Бобу. Боб принимает это сообщение и на этапе 2.6 генерирует своё случайное число и отвечает, по его мнению, Алисе. Злоумышленник не может расшифровать это сообщение, поэтому он на этапе 1.6 пересылает его Алисе. Алиса получает сообщение, не вызывающее подозрений, расшифровывает и возвращает на этапе 1.7 Злоумышленнику случайное число Боба, зашифровав сообщение открытым ключом Злоумышленника. Теперь Злоумышленник знает случайное число Боба и может ответить ему на этапе 2.7. Боб уверен, что установил сеанс связи с Алисой, так как шифровал сообщение со случайным числом ее ключом и получил правильный ответ.

Ключевой момент атаки состоит в том, что Злоумышленник может заставить Алису расшифровать для него случайное число Боба. Алиса в данной атаке выступает оракулом — пользователем системы, который выполняет некоторую криптографическую операцию в интересах Злоумышленника[14].

Пример последствий[править | править вики-текст]

Рассмотрим пример последствий данной атаки. Пусть Боб — это некоторый банк. Тогда Злоумышленник, выдав себя за Алису, может воспользоваться её счетом и перевести с него деньги на свой. Банк будет уверен, что операция была выполнена Алисой[14].

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

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

2.6. Bob \to \left\{ B, R_A, R_B \right\}_{K_A} \to Attacker(Alice)

В этом случае Злоумышленник не сможет переслать сообщение Алисе, так как Алиса будет ждать от него соответственно следующее сообщение:

1.6. Attacker \to \left\{ At, R_A, R_B \right\}_{K_A} \to Alice

которое Злоумышленник не может получить ни пересылками сообщений Боба, ни собственными силами[14].

Исправление уязвимости[править | править вики-текст]

Первый вариант[править | править вики-текст]

3. Alice \to \left\{\left\{ R_A, A \right\}_{K_A^{-1}}\right\}_{K_B} \to Bob
6. Bob \to \left\{ R_A, \left\{ R_B \right\}_{K_B^{-1}} \right\}_{K_A} \to Alice
7. Alice \to \left\{\left\{ R_B \right\}_{K_A^{-1}}\right\}_{K_B} \to Bob

В уточнённой спецификации \left\{ R_A, A \right\}_{K_A^{-1}} — это сообщение, для верификации которого необходимо использовать открытый ключ Алисы, то есть это подпись Алисы. В этой спецификации случайные числа сначала подписываются, а потом шифруются открытым ключом другого пользователя. Из-за того, что на этапе 6 Боб подписывает своё число, атака Лоу становится невозможной. Если Злоумышленник перешлёт сообщение Алисе, то она заметит ошибку при верификации[15].

Второй вариант[править | править вики-текст]

С помощью метода «зашифруй и подпиши» можно уточнить следующим образом:

3. Alice \to \left\{\left\{ R_A\right\}_{K_B}, A \right\}_{K_A^{-1}} \to Bob
6. Bob \to \left\{\left\{ R_A, R_B \right\}_{K_A}\right\}_{K_B^{-1}} \to Alice
7. Alice \to \left\{\left\{ R_B \right\}_{K_B}\right\}_{K_A^{-1}} \to Bob

Теперь Злоумышленник даже не в состоянии запустить протокол связи с Бобом от имени другого лица[15].

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

Для решения проблемы аутентификации сетевых пользователей предназначен протокол Kerberos. Его основная идея заключается в использовании доверенной третьей стороны, предоставляющей пользователю доступ к серверу с помощью общего сеансового ключа, разделённого между пользователем и сервером. В основе данного протокола лежит вариант протокола Нидхема — Шрёдера с использованием временной метки[16][1].

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

Стандарты[править | править вики-текст]

  1. ISO 9798-2: Information technology — Security technicues — Entity authentication mechanisms — Part 2: Entity authentication using symmetric techniques.

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

Ссылки[править | править вики-текст]