BC/NW 2008, №2 (13): 13.3

 

Предварительное распределение ключей В локальной компьютерной сети

 

Фролов А.Б., Щуров И.И.

 

(Москва, Московский энергетический институт (технический университет), Россия)

 

Работа выполнена при финансовой поддержке РФФИ, грант 08-01-00632-а.

 

1.Введение

Защите компьютерных сетей уделяется все возрастающее внимание [1,2]. Важнейшим аспектом при этом является проблема распределения ключей, используемых для обеспечения конфиденциальности и целостности передаваемой от одного участника сети другому участнику информации. Традиционное распределение ключей на основе, например, инфраструктуры сертификации открытых ключей, поддерживаемой технологиями Windows, предполагает необходимость аутентификации открытых ключей каждого пользователя, генерации и доставки секретных ключей с использованием аутентифицированного открытого ключа. Проблема генерации секретных ключей, в свою очередь, должна обеспечиваться доверенными центрами, отвечающими за их качество, целостность и конфиденциальность. Для упрощения технологических решений этапа сертификации был изобретен протокол Kerberos [1], позволяющий аутентификацию в пределах сегмента вычислительной сети осуществлять на основе единого сертифицированного открытого ключа сервера аутентификации. Но при этом необходимо формировать и распределять ключи для каждой пары абонентов сегмента, что практически не реализуемо, например, в сетях мобильной связи. В связи с этим актуальной задачей является обоснование возможности организации на базе протоколов типа Kerberos предварительного распределения ключевой информации, в соответствии с теми или иными схемами [1,3,4,5], а также возможности распараллеливания процессов генерации и доставки ключевой информации участникам больших, состоящих из сегментов или доменов, вычислительных сетей. В настоящей работе обоснованы обобщения некоторых схем предварительного распределения ключей, предполагающие меньший объем необходимой секретной ключевой информации, используемой участниками сети для вычисления рабочих ключей по сравнению прототипами таких схем.

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

 

2. Некоторые схемы предварительного распределения ключевой информации

Пусть P={P₁,…,P_l} и F ={F₁,…,F_s} - множества привилегированных и запрещенных коалиций участников компьютерной сети [3].

На этапе предварительного распределения ключей доверенный центр TA (Trusted Authority) генерирует некоторое множество M={M₁,…,M_q} единиц ключевой информации (двоичных слов подходящей длины), выполняющих роль базовых ключей, и распределяет их всем участникам сети по защищенным каналам.

Каждый из n участников получает свою долю в виде пакета , , i=1,…n, состоящего из базовых ключей, набор  номеров которых публикуется. Все единицы ключевой информации из пересечения пакетов, направленных участникам некоторой привилегированной коалиции P, позволяет вычислить ключ k_P для расшифрования информации, передаваемой от TA или для зашифрования и расшифрования при конфиденциальном информационном обмене между участниками коалиции в режиме конференц-связи.

С другой стороны, никакая запрещенная коалиция FÎ F, не имеющая с P общих элементов, не должна получать никакой информации о k_P.

Такие схемы предварительного распределения ключей обозначаются (P,F)-KDS, или (g,w)-KDS, если множества P и F состоят из всех g- и w-элементных подмножеств соответственно. Схема (2,1)-KDS, когда |M|=q и сеть состоит из n участников, обозначается KDP-(n,q) и называется KDP-(n,q) схемой [1].

KDP(n,q)-схема определяется как семейство подмножеств K_i, i=1,…,n, множества K из q элементов, обладающее свойством

                                                                                        

Известен ряд подходов к вычислению и оценкам сложности (P,F)-KDS, (g,w)-KDS и KDP-(n,q) схем предварительного распределения ключей [3].

Метод хеширования ключей предложен в работе [6] и применен в работе [7] при обосновании т.н. HARPS-схемы путем обобщения более раннего прототипа RPS [8] таких схем[1].

В [6] предложен метод хеширования при генерации пакетов ключевой информации на основе базового пакета ключей (S₁, S₂, …, S_k) (LM-схемы). Для формирования пакетов распределяемой участникам i=1, …, n сети ключевой информации используется односторонняя хеш-функция h.  Пакеты вычисляются в виде наборов

(M₁, …, M_t, …, M_k)=(, …, , …, )

где A_i,t, t=1, …, k, i=1, …, n – публикуемая таблица натуральных чисел A_i,t{0, …, L},  – есть результат A_i,t-кратного применения хеш-функции h к значению элемента S_t набора базовых ключей. Число L определяет глубину хеширования.

На основе выделенных пакетов участники i и j имеют возможность вычислить общий ключ:

,

где | – знак конкатенации.

Предложенные на основе метода хеширования базовых ключей схемы HARPS [7] отличаются от LM-схем тем, что рассматривается в общем случае большее число базовых ключей S₁,…,S_P, а распределяемые пакеты образуются методом хеширования из k, k£ P ключей.

Участникам j, j=1,… n сети распределяются случайно выбираемые k-подмножества совокупности случайным образом хешированных базовых ключей

.

Имея в составе пакетов хеш-образы базовых ключей , использованных для их порождения в пакетах пользователей i и j, эти пользователи имеют возможность вычислить общий ключ

k(i,j)=.

Схемы (P,k,L)-HARPS при P=k являются рассмотренными выше LM-схемами.

Предполагается [7], что схемы HARPS решают проблему масштабирования сети.

 

3. KDP-схемы с хешированием

Для совершенствования и обобщения известных схем предварительно распределения ключей используем прием хеширования, описанный выше применительно к по обобщению других схем. При этом обоснуем схемы KDP-(n,q) и (P,F) -KDS с хешированием.

Применяя рассмотренный в предыдущем разделе метод хеширования базовых ключей, обоснуем теперь понятие KDP-схемы с хешированием (HAKDP-схемы).

Дадим определение HAKDP-(n,q,L) схемы.[2]

Определение. Пусть K={1,2,…,q} - множество номеров базовых ключей и D={0,1,…,L}, LÎN. HAKDP(n,q,L) схема есть семейство пар (K₁,D₁),...,(K_n,D_n), где первые элементы являются упорядоченными подмножествами множества K, содержащими C₁,…,C_n элементов, а вторые элементы суть слова длины C_i в алфавите D. Обозначим D_i,j набор значений max(D_i(t),D_j(t)) соответствующих совпадающим элементам множеств K_i, K_j и D_r,i,j набор значений D_r(t), соответствующих совпадающим элементам тех же множеств K_i и K_j. Описанное множество пар образует HAKDP(n,q) схему, если

 или не выполняется D_r,i,j £ D_i,j,                 (1)

где £ есть отношение частичного порядка на множестве числовых наборов.

В качестве примеров в табл.1 приведены KDP(4,4)-схема HAKDP-(4,3,1)-схема.

Как видим, понятие HAKDP-(n,q,L) схемы обобщает понятие KDP-(n,q) схемы, позволяя рассматривать последние как HAKDP-(n,q,0) схемы. В то же время HAKDP схемы образуют специальный класс схем HARPS, изучавшихся в [7], включающий схемы, безопасные относительно одного нечестного участника.

 

Таблица 1. KDP(4,4)-схема и HAKDP-(4,3,1)-схема.

KDP(4,4)-схема	HAKDP(4,3,1)-схема
K1={1,2,3}	K1={1,2,3} A1=(1,1,1),
K2={1,2,4}	K2={1,2}, A2=(0,0),
K3={1,3,4}	K3={1,3}, A3=(0,0),
K4={2,3,4}	K4={2,3}, A4=(0,0),

 

Элементы схемы HAKDP являются открытой информацией участников сети, на основе которой доверенный центр вычисляет пакеты ключевой информации для каждого участника, используя совокупность M₁,M₂,…,M_q базовых ключей.

Если K_i=(i₁,…, ) и D_i=(i₁,…, ), то соответствующий пакет вычисляется как

.                                          

Заметим, что если свойство (1) не выполняется, то участник r сможет вычислить ключ, используемый для конфиденциальной коммуникации между участниками i и j.

Обобщая, можем обосновать понятие схемы (P,F)-KDS с хешированием (P,F)-HAKDS как пары (K_i,D_i), i=1,…,n, таких, что каждая пара (P,F) непересекающихся множеств PÎ P и FÎ F не удовлетворяет следующему условию:

и ,

где D_P есть набор значений , соответствующих совпадающим элементам множеств K_i из P и D_F,P есть набор значений всех тех элементов из F, которые соответствуют совпадающим элементам множеств K_i из F.

Сравнение KDP-(10⁴,173) и HAKDP-(10⁴,114,10) дано в табл. 2.

 

Таблица 2. Сравнение KDP-(10⁴,173) и HAKDP-(10⁴,114,10).

	KDP(104,173)-схема	HAKDP(104,114,10)-схема
Средняя длина пакета	115	71
Число передаваемых ключей	1150000	710000

 

4. Модификация протокола Kerberos.

Предложим модификацию протокола Kerberos с целью организации предварительного распределения ключей в сети.

Абонент  A_i и сервер аутентификации AS имеют одноразовый пароль .

На этапе инициализации сервер аутентификации Authentication Server (сокращенно - AS) вычисляет ключи   для связи  сервера Ticket Granting Server сокращенно - TGS) и привязанных к нему абонентов A_i. Предполагается, что у AS есть ключ   для связи с TGS и TGS строит KDP(n,q)-схему (или HAKDP(n,q,L)-схему): для каждого абонента  A_i вычисляются пакеты K_i.

Теперь каждый участник A_i поддерживающий службу одноразового пароля с сервером аутентификации AS, может получить свой пакет K_i распределяемой ключевой информации, инициализируя и выполняя два протокола:

а) Протокол обмена с Сервером аутентификации (Authentication Service Exchange, сокращенно - AS Exchange);

б) Протокол обмена с сервером Ticket Granting Service Exchange, (сокращенно - TGS Exchange).

Для безопасного обмена информации между абонентами сети используется протокол

в) Протокол Client/Server Authentication Application Exchange (сокращенно - AP Exchange) обмена с сервером приложений.

 

По протоколу аутентификации AS_Exchange во взаимодействии с сервером AS клиент С получает мандат TGT - Ticket Granting Ticket  на получение билетов-аутентификаторов TKT (сокращение TicKeT).

По Протоколу TGS Exchange во взаимодействии с сервером TGS клиент C и получает билет-аутентификатор TKT на доступ к сетевому ресурсу, включающий пакет K_i.

Эти протоколы двухраундовые:

1.    C® AS: AS_REQUEST (запрос мандата TGT);

AS ® C: TGT;

2.    C® TGS: TGS_REQUEST (запрос билета-аутентификатора TKT);

TGS ®C: TKT;

По Протоколу AP Exchange клиент C взаимодействует с сервером S приложений, роль которого исполняет клиентская программа любого участника сети. При этом клиент С получает возможность конфиденциального обмена с клиентом S на ключе, вычисляемом на основе принадлежащих им обоим ключей из их пакетов.

3.     C® AP: AP_REQUEST (запрос сетевого ресурса);

AP ®C: AP_REPLY.

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

1.     AS_REQUEST={U,TGS, время действия заявки 1, случайное число N₁}. 

Клиент C от имени пользователя U (U включает одноразовый пароль пользователя) запрашивает у сервера AS на мандат на обращение к серверу TGS в течение времен действия заявки, сообщает свое случайное число N₁; 

2. TGT ={U, T_C,TGS , TGT_C }, T_C,TGS ={U,C,TGS, K_C,TGS, время начала действия, время окончания действия} - сообщение, зашифрованное на ключе K_AS,TGS; TGT_C={TGS, K_C,TGS, время начала действия, время окончания действия, N₁}- сообщение, зашифрованное на ключе K_U, извлеченном из разового пароля абонента;

AS генерирует новый ключ K_C,TGS (или использует заранее сформированный ключ) для обмена между C и TGS и затем шифрует его в составе TGT и посылает это сообщение серверу C на ключе K_U сервера C. Этот ключ извлекается из одноразового пароля пользователя U. Одновременно сообщается время начала и время окончания действия TGT и возвращается случайное число N₁; 

3. TGS_REQUEST= {S, время действия заявки N₂. T_C,TGS,A_C,TGS}, A_C,TGS={C, время действия клиента}- аутентификатор;

Клиент C запрашивает у сервера TGS распределенное ему подмножество системных ключей для связи с другими абонентами домена и с сервером приложений S на требуемое время, сообщает случайное число N₂, предназначенное TGS сообщение T_C,TGS от AS, а также свой аутентификатор A с меткой текущего времени на ключе K_C,TGS. Назначением аутентификатора является демонстрация того, что C использует TGT в пределах указанного в нем периода времени.

4. ТКТ={U, T_C,S , TKT_C}, T_C,S ={U,C, S, K_S, время начала действия, время окончания действия};  TKT_C={S, K_C, время начала действия, время окончания действия, N₂}.

Сервер TGS высылает клиенту C сообщение T_C,S  для сервера S, включающее имя пользователя, имя клиента С, имя сервера S, время начала и окончания действия этого ключа. Это все шифруется на ключе  K_S,TGS.

Сервер TGS высылает абоненту C сообщение TKT_C, включающее имя сервера S, время начала и окончания действия этого ключа. Это все шифруется на ключе  K_S,TGS.

5. AP_REQUEST={ T_C,S , A_C,S}; A_C,S={C, текущее время клиента } .

Клиент C запрашивает у сервера приложений S доступ к сетевому ресурсу. Для этого он пересылает к S предназначенное ему сообщение T_C,S сервера TGS, зашифрованное на ключе T_C,S , а также на ключе K_C,S  свой аутентификатор A_C,S, включающий имя клиента C и его текущее время; назначение этого аутентификатора такое же, как в п. 3.

6.AP_REPLY= {A_S,C}; A_S,C={ текущее время клиента}.

Сервер S возвращает текущее время клиента. С этого момента C может использовать ресурс сервера приложений S на ключе K_C,S в период от начала до окончания действия этого ключа сессии. Ключ K_C,S вычисляется как абонентом C, так и сервером S по предварительно полученной ключевой информации K_C или K_S соответственно. Использование ресурса заключается во взаимодействии с сервером S.

Разница между базовым и модифицированным протоколами Kerberos заключается в двух сообщениях протокола TGS, которые представлены в табл. 3.

 

 

Таблица 3. Модификация протокола Kerberos

сообщения базового протокола TGS	сообщения модифицированного протокола TGS
TC,S={U,C,S,KC,S, время начала действия, время окончания действия}	TC,S={U,C,S, время начала действия, время окончания действия}
TKTC={S,KC,S, время начала действия, время окончания действия, N2}	TKTC={S,KC, время начала действия, время окончания действия, N2}

 

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

 

Заключение

 Обоснованы новые схемы предварительного распределения ключей, полученные как обобщение KDP и KDS схем применение приема хеширования и позволяющие сократить объем ключевого материала, передаваемого от доверенного центра участникам сети. Предложена модификация протокола Kerberos, отражающая особенность предварительного распределения ключевой информации в локальной компьютерной сети, а также в доменах глобальной компьютерной сети.

 

 

ЛИТЕРАТУРА

1.     А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин. Основы криптографии. М.: Гелиос АРВ. 2005.

2.     П. Н. Девянин. Модели безопасности компьютерных систем. Серия: Высшее профессиональное образование. Издательство: Академия, 2005 г.

3.     D. R. Stinson. On some methods for unconditionally secure key.

Distribution and broadcast encryption. Nov. 1996,

4.     Blom R. Nopublic key distribution// Advances in Cryptology. -- Proceedinge of EURUCRYPT'82. Plenum. New York. 1983. pp. 231--236.

5.     Martin Dyer M., Fenner T., Frieze A., Thomason A. On key storage in secure networks// J. Cryptology . v. 8, 1995, pp. 189--200.

6.     Leighton L., Micali S. Secret-Key Agreement with out Public-Key Cryptography. Advances in Cryptology-CRYPTO-1993, 1994. pp. 456-478.

7.     Ramkumar M, Memon N. "An efficient key predistribution scheme for ad hoc network security". Selected Areas in Communications, IEEE Journal on Volume 23, Issue 3, March 2005, pp. 611 - 621.

8.     Ramkumar M., Memon N., Simha R. Pre-Loaded Key Based Multicast and broadcast Authentication in Mobile ad-Hoc Networks. Globecom-2003.

9.     Фролов А.Б., Щуров И.И. Защищенные коммуникации при нецентрализованном предварительном распределении ключей. Вестник МЭИ, № 4,2008 г. Принято в печать.