Протокол Ву — Лама

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

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

Протокол Ву — Лама — протокол аутентификации и обмена ключами. Как и в случае протокола DASS промежуточная сторона — Трент — поддерживает базу данных всех ключей.

Симметричный вариант протокола

Протокол был описан Томасом Ву и Саймоном Ламом в 1992 году.

Алиса отправляет Бобу свой идентификатор:

[math]\displaystyle{ (1)\ Alice \to \{A\} \to Bob }[/math]

Боб отправляет Алисе случайное число:

[math]\displaystyle{ (2)\ Bob \to \{R_B\} \to Alice }[/math]

Алиса отправляет Бобу это число, зашифровав его на общем ключе её и Трента:

[math]\displaystyle{ (3)\ Alice \to \{E_{K_A}(R_B)\} \to Bob }[/math]

Боб отправляет Тренту сообщение, зашифрованное на его с Трентом ключе, в котором содержатся идентификатор Алисы и её сообщение, полученное Бобом на 3-м проходе:

[math]\displaystyle{ (4)\ Bob \to \{E_{K_B}(A, E_{K_A}(R_B))\} \to Trent }[/math]

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

[math]\displaystyle{ (5)\ Trent \to \{E_{K_B}(R_B)\} \to Bob }[/math]

Асимметричный вариант протокола

Алиса отправляет Тренту сообщение со своим идентификатором и Боба:

[math]\displaystyle{ Alice \to \left\{ A, B \right\} \to Trent }[/math]

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

[math]\displaystyle{ Trent \to \left\{ S_T \left( K_B \right) \right\} \to Alice }[/math]

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

[math]\displaystyle{ Alice \to \left\{ E_{K_B} \left( A, R_A\right) \right\} \to Bob }[/math]

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

[math]\displaystyle{ Bob \to \left\{ A, B, E_{K_T} \left( R_A\right) \right\} \to Trent }[/math]

Трент отправляет Бобу два сообщения. В первом содержится открытый ключ Алисы, подписанный ключом Трента. Во втором — случайное число Алисы, случайный сеансовый ключ и идентификаторы Боба и Алисы. Второе сообщение подписывается ключом Трента и шифруется открытым ключом Боба:

[math]\displaystyle{ Trent \to \left\{ S_T \left( K_A \right), E_{K_B} \left( S_T \left( R_A, K, A, B \right) \right) \right\} \to Bob }[/math]

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

[math]\displaystyle{ Bob \to \left\{ E_{K_A} \left( S_T \left( R_A, K, A, B \right) , R_B \right) \right\} \to Alice }[/math]

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

[math]\displaystyle{ Alice \to \left\{ E_K \left( R_B\right) \right\} \to Bob }[/math]

Боб расшифровывает число и убеждается, что оно не изменилось.

Протокол взаимной аутентификации и распределения ключей

Этот протокол, основанный на симметричной криптографии, был описан Ву и Ламом в 1994 году.

Алиса генерирует случайное число [math]\displaystyle{ R_A }[/math] и отправляет Бобу свой идентификатор и это число:

[math]\displaystyle{ (1)\ Alice \to \{A, R_A\} \to Bob }[/math]

Боб тоже генерирует случайное число [math]\displaystyle{ R_B }[/math] и отправляет Алисе свой идентификатор и это число:

[math]\displaystyle{ (2)\ Bob \to \{B, R_B\} \to Alice }[/math]

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

[math]\displaystyle{ (3)\ Alice \to \{E_{K_A}(A, B, R_A, R_B)\} \to Bob }[/math]

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

[math]\displaystyle{ (4)\ Bob \to \{E_{K_A}(A, B, R_A, R_B), E_{K_B}(A, B, R_A, R_B)\} \to Trent }[/math]

Трент расшифровывает сообщения от Боба, узнаёт идентификаторы и случайные числа участников, после чего генерирует сессионный ключ [math]\displaystyle{ K }[/math] и отправляет Бобу два сообщения. В первом сообщении содержатся идентификатор Боба, оба случайных числа и сессионный ключ, зашифрованные на ключе Алисы. Во втором сообщении содержатся идентификатор Алисы, оба случайных числа и сессионный ключ, зашифрованные на ключе Боба:

[math]\displaystyle{ (5)\ Trent \to \{E_{K_A}(B, R_A, R_B, K), E_{K_B}(A, R_A, R_B, K)\} \to Bob }[/math]

Боб отправляет Алисе два сообщения. Первое — это первое сообщение, полученное на предыдущем проходе от Трента. Второе — оба случайных числа ([math]\displaystyle{ R_A }[/math] и [math]\displaystyle{ R_B }[/math]), зашифрованные на сессионном ключе:

[math]\displaystyle{ (6)\ Bob \to \{E_{K_A}(B, R_A, R_B, K), E_{K}(R_A, R_B)\} \to Alice }[/math]

Алиса расшифровывает первое сообщение, получает ключ [math]\displaystyle{ K }[/math], расшифровывает второе сообщение и отправляет Бобу его случайное число:

[math]\displaystyle{ (7)\ Alice \to \{E_K(R_B)\} \to Bob }[/math]

Атаки на протокол

Атака на симметричный вариант протокола

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

Мэллори является пользователем системы и имеет общий ключ с Трентом. Также ей требуется блокировать все сообщения, посланные Алисе, то есть Мэллори должна быть активным криптоаналитиком.

Мэллори начинает два сеанса — один от имени Алисы и один от своего имени — и отправляет Бобу два сообщения:

[math]\displaystyle{ (1)\ Mallory\ (Alice) \to \{A\} \to Bob }[/math]

[math]\displaystyle{ (1')\ Mallory\to \{M\} \to Bob }[/math]

Боб думает, что с ним хотят связаться Алиса и Мэллори, и отправляет каждой своё случайное число:

[math]\displaystyle{ (2)\ Bob \to \{R_B\} \to Mallory\ (Alice) }[/math]

[math]\displaystyle{ (2')\ Bob \to \{R_B'\} \to Mallory }[/math]

Мэллори игнорирует своё случайное число и в обоих сеансах отправляет Бобу одно и то же сообщение — случайное число [math]\displaystyle{ R_B }[/math], предназначенное Алисе, зашифрованное на общем ключе Мэллори и Трента [math]\displaystyle{ K_M }[/math]:

[math]\displaystyle{ (3)\ Mallory\ (Alice) \to \{E_{K_M}(R_B)\} \to Bob }[/math]

[math]\displaystyle{ (3')\ Mallory \to \{E_{K_M}(R_B)\} \to Bob }[/math]

Боб, следуя инструкциям протокола и не сравнивая сообщения между собой, пересылает их Тренту, добавив идентификаторы и зашифровав на их общем ключе [math]\displaystyle{ K_B }[/math]:

[math]\displaystyle{ (4)\ Bob \to \{E_{K_B}(A, E_{K_M}(R_B)\} \to Trent }[/math]

[math]\displaystyle{ (4')\ Bob \to \{E_{K_B}(M, E_{K_M}(R_B)\} \to Trent }[/math]

Трент в каждом сеансе расшифровывает сообщение с помощью ключа того участника, идентификатор которого он получил. Так как в первом сеансе он получил идентификатор Алисы, а число [math]\displaystyle{ R_B }[/math] было зашифровано на ключе Мэллори [math]\displaystyle{ K_M }[/math], при расшифровке получится другое число («мусор»).

[math]\displaystyle{ (5)\ Trent \to \{\text{''Мусор''}\} \to Bob }[/math]

[math]\displaystyle{ (5')\ Trent \to \{E_{K_B}(R_B)\} \to Bob }[/math]

Боб видит в одном из последних сообщений случайное число [math]\displaystyle{ R_B }[/math], которое он посылал Алисе (как он думает), а в другом — мусор. Из-за этого Боб считает, что он установил связь с Алисой, хотя Алиса вообще не участвовала в обмене сообщениями.

Последовательность сеансов в данном случае не важна — атака будет развиваться точно также.

Абади и Нидхем предложили защиту от этой атаки: в сообщение 5-го прохода Трент должен включить идентификатор Алисы. В этом случае Боб при получении идентификатора Мэллори и случайного числа [math]\displaystyle{ R_B }[/math] (которое он отправлял Алисе) отбросит такое сообщение, и атака сорвётся.

Атака на протокол взаимной аутентификации

На этот вариант протокола также существует атака с помощью параллельного сеанса.

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

Алиса начинает сеанс связи с Мэллори. Мэллори в ответ начинает сеанс связи с Алисой, отправляя ей то же случайное число, которое она получила:

[math]\displaystyle{ (1)\ Alice \to \{A, R_A\} \to Mallory }[/math]

[math]\displaystyle{ (1')\ Mallory \to \{M, R_A\} \to Alice }[/math]

После этого Мэллори дожидается, пока Алиса ответит на её сообщение из второго сеанса, достаёт из него случайное число и вставляет его в сообщение Алисе в первом сеансе.

[math]\displaystyle{ (2')\ Alice \to \{A, R_{A'}\} \to Mallory }[/math]

[math]\displaystyle{ (2)\ Mallory \to \{M, R_{A'}\} \to Alice }[/math]

После этого Алиса и Мэллори нормально завершают первый сеанс протокола:

[math]\displaystyle{ (3)\ Alice \to \{E_{K_A}(A, M, R_A, R_{A'})\} \to Mallory }[/math]

[math]\displaystyle{ (4)\ Mallory \to \{E_{K_A}(A, M, R_A, R_{A'}), E_{K_M}(A, M, R_A, R_{A'})\} \to Trent }[/math]

[math]\displaystyle{ (5)\ Trent \to \{E_{K_A}(M, R_A, R_{A'}, K), E_{K_M}(A, R_A, R_{A'}, K)\} \to Mallory }[/math]

[math]\displaystyle{ (6)\ Mallory \to \{E_{K_A}(M, R_A, R_{A'}, K), E_K(R_A, R_{A'})\} \to Alice }[/math]

[math]\displaystyle{ (7)\ Alice \to \{E_K{R_{A'}}\} \to Mallory }[/math]

Через некоторое время Мэллори продолжает установление второго сеанса связи:

[math]\displaystyle{ (3')\ Mallory \to \{E_{K_M}(M, A, R_A, R_{A'})\} \to Alice }[/math]

Алиса отправляет серверу сообщение, которое Мэллори перехватывает и блокирует.

[math]\displaystyle{ (4')\ Alice \to \{E_{K_M}(M, A, R_A, R_{A'}), E_{K_A}(M, A, R_A, R_{A'})\} \to Mallory\ (Trent) }[/math]

Мэллори от имени сервера посылает Алисе сообщение со старым сессионным ключом, просто поменяв местами части сообщения из 5-го прохода первого сеанса.

[math]\displaystyle{ (5')\ Mallory\ (Trent) \to \{E_{K_M}(A, R_A, R_{A'}, K), E_{K_A}(M, R_A, R_{A'}, K)\} \to Alice }[/math]

После этого Алиса с Мэллори завершают установление соединения.

[math]\displaystyle{ (6')\ Alice \to \{E_{K_M}(A, R_A, R_{A'}, K), E_K(R_A, R_{A'})\} \to Mallory }[/math]

[math]\displaystyle{ (7')\ Mallory \to \{E_K(R_{A'})\} \to Alice }[/math]

Литература

• Шнайер Б. Глава 3. Основные протоколы. Протокол Ву-Лама // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — С. 85. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• M. Abadi, R. Needham. Prudent engineering practice for cryptographic protocols (англ.) // IEEE Transactions on Software Engineering. — 1996. — Vol. 22, iss. 1. — P. 6—15. — doi:10.1109/32.481513.
• Венбо Мао. Современная криптография: теория и практика / пер. с англ. Д. А. Клюшина.. — М.: Издательский дом "Вильямс", 2005. — С. 423—425. — ISBN 5-8459-0847-7.
• T. Y. C. Woo, S. S. Lam. Authentication for Distributed Systems (англ.) // Computer. — Los Alamitos, CA, USA: IEEE Computer Society Press, 1992. — Vol. 25, iss. 1. — P. 39—52. — ISSN 0018-9162. — doi:10.1109/2.108052.
• T. Y. C. Woo, S. S. Lam. Authentication Revisited (англ.) // Computer. — Los Alamitos, CA, USA: IEEE Computer Society Press, 1992. — Vol. 25, iss. 3. — P. 10. — ISSN 0018-9162. — doi:10.1109/2.121502. Архивировано 24 мая 2010 года.
• T. Y. C. Woo, S. S. Lam. A lesson on authentication protocol design (англ.) // Association for Computing Machinery. — New York, NY, USA, 1994. — Vol. 28, no. 3. — P. 24—37. — ISSN 0163-5980. — doi:10.1145/182110.182113.
• J. Clark, J. Jacob. A Survey of Authentication Protocol Literature: Version 1.0 (англ.) // Citeseer. — 1997. — 17 November.