В статье рассмотрены распределенные системы с запрещенными каналами обмена информацией. Предложена модификация схемы Блома, позволяющая реализовать запрет на обмен информацией между заданными пользователями. Запрет реализуется с помощью обнуления парных ключей шифрования для запрещенных каналов. Многочлен схемы Блома строится на основе элементарных симметрических многочленов. Предложена реализация разработанной схемы для построения VPN.
Постановка задачи и схема Блома Пусть в распределенной системе имеется n узлов. Необходимо обеспечить защиту каналов обмена информации для каждой пары узлов и, кроме того, запретить обмен информации некоторым парам узлов. В начальной постановке задачи будем считать, что все каналы информации двухсторонние, то есть если соединение установлено, то оба узла могут получать и отправлять информацию беспрепятственно. Данная задача может быть изображена с помощью матрицы доступов, в ячейках которой расположены ключи для реализации криптографического протокола, если связь разрешена, и нули если канал связи запрещен политикой безопасности. Поставим задачу распределения между узлами некоторой информации, называемой ключевыми материалами, на основе которых каждый узел может либо вычислить необходимый ключ шифрования, либо определить, что данный канал ему запрещен. Пусть подсистема безопасности на каждом узле системы реализована, таким образом, что при нулевом значении ключа следует запрет на установление соединения. В дальнейшем будем считать, что все ключи имеют длину бит.
Схема Блома предварительного распределения ключей основывается на вычислении значений симметрического многочлена (, ) степени 2 над кольцом вычетов по модулю . Если число абонентов , то < . Многочлен (, ) хранится в секрете на сервере. Каждому участнику сопоставляется число (=1,...,). Таблица чисел хранится на сервере в открытом виде. Сервер передаёт каждому абоненту по защищенному каналу многочлен () = (, ). Общий ключ связи двух абонентов и формируется путем подстановки числа в многочлен () -ым абонентом ( = ()) и подстановкой числа в многочлен () -ым абонентом ( = ()). Так как многочлен (, ) симметричен, то будет выполняться равенство = .
Под компроментацией схемы Блома понимается возможность по известному набору ключей получить
остальные неизвестные ключи. Как показано в работе [
Модифицированная схема Блома с запрещенными каналами Осуществим модификацию схемы Блома таким образом, чтобы она позволяла реализовывать запреты на создание некоторых каналов связи. Пусть в системе наложены ограничения на возможность взаимодействия абонентов. То есть существуют пары абонентов, для которых запрещен обмен информацией. Потребуем, чтобы для разрешенных пар абонентов (, ) схема генерировала ключ обмена информацией ̸= 0, для запрещенных пар абонентов = 0. Если такая схема будет построена, то далее задача решается техническими средствами с помощью запрета шифрования нулевым ключом.
Будем считать, что в системе имеется абонентов и задан список пар номеров абонентов , для которых запрещен обмен информацией. Построим симметричный полином (, ), который будет храниться в секрете на сервере и иметь вид: (, ) = (, ) (, ). Здесь (, ) (как и в обычной схеме Блома) является симметричным многочленом степени 2. Многочлен (, ) необходим для формирования ключей обмена информацией. Он обеспечивает стойкость к компрометации ключей. Многочлен d(x,y) также является симметричным и обеспечивает обнуление ключей шифрования для запрещенных пар абонентов. Наложим требование (, ) = (, ) = 0, если (, ) ∈ , и (, ) = (, ) ̸= 0, если (, ) ̸∈ . Будем искать многочлен d(x,y) в виде произведения:
(, ) = ( + − − )2 + ( − )2.
∏︁ (( + − − )2 + ( − )2) Доказательство. Для компрометации списка запрещенных каналов, необходимо найти все корни многочлена (, ). Для этого надо вычислить все его коэффициенты. Данная задача равносильна полной компрометации всей схемы. Следовательно, согласно утверждению 1, требуется утечка + 2 ключевых материалов. Пример построения модифицированной схемы Блома с запрещенными каналами Рассмотрим пример построения схемы Блома с запрещенными каналами. Пусть задана матрица доступов для четырех участников 1, 2, 3, 4.
1 2 3 4 1 1 0 0 1
1 В матрице доступов 0 означает запрет на обмен информацией, 1 – обмен разрешен. Таким образом, в приведенной системе два запрещенных канала.
Для построения симметрического многочлена (, ) выберем = 1, тогда
(, ) = 2 = 2. Для упрощения расчетов будем проводить вычисления над кольцом 7. Коэффициенты многочлена (, ) выбираются произвольным образом и держатся в секрете на сервере. Пусть
(, ) = 3 + 2 + 2 + 4 + 52 + 52 ( 7). Выберем также произвольно значения хранящихся открыто чисел (=1,...,4):
1 = 2, 2 = 5, 3 = 3, 4 = 4. Построим симметричный многочлен (, ), реализующий запрещенные каналы обмена информацией между парами пользователей 1 = (2, 3), 2 = (1, 4). Найдем значения элементарных многочленов от двух переменных для пар 1 и 2: 1(1) = 1(2, 3) = 2 + 3 ( 7) = 1, 2(1) = 2(2, 3) = 2 · 3 ( 7) = 1, 1(2) = 1(1, 4) = 1 + 4 ( 7) = 6, 2(2) = 2(1, 4) = 1 · 4 ( 7) = 1. Следовательно 1(, ) = ( 1(, ) − 1(2, 3))2 + ( 2(, ) − 2(2, 3))2 = 22 + 2 + 2 + 5 + 5 + 2 ( 7), 2(, ) = ( 1(, ) − 1(1, 4))2 + ( 2(, ) − 2(1, 4))2 = 22 + 2 + 2 + 2 + 2 + 2 ( 7), (, ) = 1(, ) · 2(, ). (, ) = (, ) · (, ) = (22 + 2 + 2 + 5 + 5 + 2) · (22 + 2 + 2 + 2 + 2 + 2) · (3 + 2 + 2 + 4 + 52 + 52) ( 7). Найдем ключевые материалы для каждого из участников обмена информацией.
1() = (, 1) = 66 + 55 + 34 + 43 + 32 + 6 + 1, 2() = (, 2) = 66 + 45 + 64 + 33 + 42 + 2 + 2, 3() = (, 3) = 36 + 54 + 63 + 6 + 5, 4() = (, 4) = 36 + 5 + 24 + 43 + 32 + 4. Для обмена информацией участники будут вырабатывать парные ключи по правилу
, = (). Для рассматриваемого примера матрица ключей будет иметь вид: 1 2 3 4 3 1 0 0 3
2 1 2 3 3 1 0 4 0 3 2 Как видим, для запрещенных каналов ключи равны нулю, то есть обмен информацией невозможен. Следует отметить, что для малого количества участников обмена и большого количества запрещенных каналов схема не дает выигрыш в использовании памяти. В рассматриваемом примере вектор из коэффициентов многочлена () для каждого из участников содержит 7 координат, тогда как без использования схемы распределения ключей необходимо хранить всего три ключа. Однако это проблема снимается при большом количестве участников обмена. В заключение выделим основные результаты. Предложенная модификация схемы Блома позволяет реализовать дискреционное разделение доступа в распределенных системах методами симметричной криптографии. При этом учет запрещенных каналов в рамках схемы Блома приводит к росту объема ключевых материалов, которые необходимо хранить на каждом из узлов сети. Также можно отметить, что учет запрещенных каналов в рамках схемы Блома не приводит к дополнительным утечкам информации по сравнению с традиционной схемой Блома. Список литературы [1] R. Blom. An optimal class of symmetric key generation systems. Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques , 335–338, 1985. [3] W. Du, J. Deng, Y. Han, P. Varshney. A pairwise key pre distribution scheme for wireless sensor networks. In Proceedings of the Tenth ACM Conference on Computer and Communications Security (CCS 2003) , 42–51, 2003. [4] Du W., J. Deng, Y.S. Han, P. Varshney, J. Katz, A. Khalili. A pairwise key pre-distribution scheme for wireless sensor networks. ACM Transactions on Information and System Security (TISSEC) , 8(2):228–258, 2005. [5] D. Liu, P. Ning, R. Li. Establishing pairwise keys in distributed sensor networks. ACM Trans. Inf Syst.
Secur., 8:41–77, 2005. [6] A. Parakh, S. Kak. Eficient key management in sensor networks.
(GC workshops), 1539–1544, 2010.
[7] A. Parakh, S. Kak. Matrix based key agreement algorithms for sensor networks. Proceedings IEEE 5th
International Conference on Advanced Networks and Telecommunication Systems (ANTS) , 1–3, 2011.
The Blom’s Scheme Modification for Discretionary Access Control
In article the distributed systems with the forbidden channels of information exchange are considered. The Blom’s scheme modification, allowing to realize the ban on exchange of information between users is ofered. The ban is implemented by means of zeroing of pair keys for the forbidden channels. The Blom’s scheme polynomial is constructed on the basis of elementary symmetric polynomials. Implementation of the developed scheme for creation of VPN is suggested.