=Paper=
{{Paper
|id=Vol-1965/paper16
|storemode=property
|title=
О применении
политики разграничения
доступа к
предварительному распределению
ключей на основе
векторной схемы
разделения секрета
(On the Application of the Access Control Policy to the Threshold Key Exchange Protocol Based on the Blakley's Scheme of Secret Sharing)
|pdfUrl=https://ceur-ws.org/Vol-1965/paper16.pdf
|volume=Vol-1965
|authors=Sergey Usov
}}
==
О применении
политики разграничения
доступа к
предварительному распределению
ключей на основе
векторной схемы
разделения секрета
(On the Application of the Access Control Policy to the Threshold Key Exchange Protocol Based on the Blakley's Scheme of Secret Sharing)
==
https://ceur-ws.org/Vol-1965/paper16.pdf
О применении политики разграничения доступа к
предварительному распределению ключей на основе
векторной схемы разделения секрета
С.В. Усов
raintower@mail.ru
Омский государственный университет им. Ф.М. Достоевского, Омск, Россия
Аннотация
Традиционные алгоритмы предварительного распределения клю-
чей игнорируют политику безопасности системы. В данной работе
удалось предложить основанный на схеме Блэкли подход к распре-
делению ключей, нивелирующий этот недостаток. В предложенной
схеме получение общего ключа возможно лишь для пар участников
схемы, обмен информацией между которыми разрешен политикой
безопасности. При этом учитывается направление потока данных и
тип доступа, как, например, на чтение и на запись.
1 Схемы предварительного распределения ключей, учитывающие ограниче-
ния на доступ, предопределенные политикой безопасности
Схемы предварительного распределения ключей и политики разграничения доступа принято рассмат-
ривать независимо друг от друга. Все схемы предварительного распределения ключей подразумевают
возможность связи каждого абонента сети с каждым. Однако в реальных системах существует необходи-
мость согласования между механизмами обеспечения информационной безопасности. Базовой политикой
безопасности является дискреционное разделение доступа, заданное в виде матрицы доступов, определя-
ющих разрешенные каналы передачи информации.
Если обмен информацией между двумя выбранными пользователями является нежелательным, необхо-
димо построить схему, в которой выработка общего ключа этими пользователями была бы невозможной.
С этой целью в работах [1, 2, 3] были предложены схемы предварительного распределения ключей (в
частности, модифицированная схема Блома), учитывающие дискреционную политику безопасности. Од-
нако в представленных алгоритмах выработанный общий ключ подразумевал доступ к симметричному
каналу связи между пользователями, то есть обмен информацией происходил в обоих направлениях, что,
например, невозможно при применении мандатной политики разграничения доступа. В данной работе мы
предложим схему, подходящую для более общего случая.
Пусть в распределенной системе имеется множество S = {𝑠1 . . . 𝑠𝑁 } субъектов (пользователей, участни-
ков схемы). Необходимо обеспечить защиту каналов обмена информации для каждой пары субъектов и,
кроме того, запретить обмен информации некоторым парам субъектов. Поставим задачу распределения
между субъектами некоторой информации, называемой ключевыми материалами, на основе которых каж-
дый субъект может либо вычислить необходимый ключ шифрования, либо определить, что данный канал
c by the paper’s authors. Copying permitted for private and academic purposes.
Copyright ○
In: Sergey V. Belim, Nadezda F. Bogachenko (eds.): Proceedings of the Workshop on Data, Modeling and Security 2017 (DMS-2017),
Omsk, Russia, October 2017, published at http://ceur-ws.org
ему запрещен. Пусть подсистема безопасности для каждого субъекта системы реализована таким образом,
что при невозможности вычисления ключа следует запрет на установление соединения.
Учитывая вышесказанное, разумно выделить два класса политик безопасности разной степени общно-
сти. Будем называть политику разграничения доступа симметричной, если субъект 𝑠𝑖 обладает доступом
к субъекту 𝑠𝑗 одновременно с тем, что субъект 𝑠𝑗 обладает доступом к субъекту 𝑠𝑖 . Политику, в которой
данное ограничение отсутствует, назовем асимметричной.
Для начала будем считать политику разграничения доступа симметричной.
2 Модификация векторной схемы разделения секрета до схемы предваритель-
ного распределения ключей
В схеме Блэкли [4] каждый участник схемы в качестве своей доли секрета получает уравнение (𝑛 − 1)-
мерной плоскости в 𝑛-мерном пространстве. Все эти гиперплоскости имеют одну общую точку, которая и
является хранимым секретом, для получения которого каждый участник схемы должен, очевидно, ском-
прометировать свою долю секрета. Мы также будем работать в 𝑛-мерном пространстве. Предложим сле-
дующую модификацию векторной схемы разделения секрета до схемы предварительного распределения
ключей.
Долю секрета пользователя 𝑠𝑖 , а в модифицированной схеме – его долю ключевых материалов, состав-
ляет множество точек 𝑋(𝑖) в 𝑘 -мерном подпространстве 𝐿(𝑖). В открытом доступе хранится 𝑚-мерное
подпространство 𝑌 (𝑖), сопоставленное 𝑖-тому пользователю, причем 𝐿(𝑖) является подпространством 𝑌 (𝑖),
то есть 𝑘 < 𝑚 < 𝑛.
Алгоритм выработки общего ключа между 𝑖-м и 𝑗 -м пользователями следующий:
Дано:
1) множество всевозможных ключей K,
2) размерности пространства и подпространств 𝑘 < 𝑚 < 𝑛;
для каждого пользователя 𝑠𝑖 :
3) его доля секрета 𝑋(𝑖),
4) секретное подпространство 𝐿(𝑖),
5) открытое подпространство 𝑌 (𝑖),
6) также для каждой пары пользователей 𝑠𝑖 и 𝑠𝑗 задана ключевая функция Φ𝑖,𝑗 : R
𝑘+𝑚
→ K* , помога-
ющая выработать общий ключ.
Получить: для каждой пары пользователей (𝑠𝑖 , 𝑠𝑗 ) ключевые множества 𝐾(𝑖, 𝑗), 𝐾(𝑗, 𝑖) ⊂ K, имеющие
общий элемент, который и будет являться общим ключом пользователей 𝑠𝑖 и 𝑠𝑗 , либо установить, что
получение таких множеств невозможно (а значит, обмен информацией между 𝑠𝑖 и 𝑠𝑗 запрещен).
1. Пользователь 𝑠𝑖 находит пересечение множеств 𝐿(𝑖) и 𝑌 (𝑗). Если пересечение пусто, выработка общего
ключа невозможна. Это значит, что обмен информации между 𝑖-м и 𝑗 -м пользователями запрещен
политикой безопасности.
2. Если 𝐿(𝑖) ∩ 𝑌 (𝑗) содержит непустое множество точек, то пользователь 𝑠𝑖 вычисляет определенную
функцию Φ𝑖,𝑗 от координат этих точек. Результатом вычисления функции является некоторое множе-
ство. Если оно пусто, либо бесконечно, выработка общего ключа невозможна.
3. В противном случае результат вычисления функции Φ𝑖,𝑗 (𝑋(𝑖) ∩ 𝑌 (𝑗)) обозначим через 𝐾(𝑖, 𝑗).
4. Симметричные действия предпринимает пользователь 𝑠𝑗 по отношению к 𝑠𝑖 . Его результат обозначим
через 𝐾(𝑗, 𝑖).
5. Пользователи сравнивают результаты. Если 𝐾(𝑖, 𝑗) ∩ 𝐾(𝑗, 𝑖) ̸= ∅ (если у каждого пользователя полу-
чилось некоторое множество результатов, то должен совпадать хотя бы один элемент этих множеств),
то элемент из 𝐾(𝑖, 𝑗) ∩ 𝐾(𝑗, 𝑖) является общим ключом связи между пользователями.
6. Если же результаты не совпадают, то обмен информации между 𝑖-м и 𝑗 -м пользователями запрещен
политикой безопасности.
Пример 1. 𝑘 = 1, 𝑋(𝑖) = 𝐿(𝑖) (прямая), 𝑚 = 𝑛 − 1. Пользователь 𝑠𝑖 ищет множество точек пересечения
своей (секретной) прямой и подпространства 𝑌 (𝑗) пользователя 𝑠𝑗 , которое находится в открытом доступе.
С учетом размерностей, возможны четыре варианта:
а) Точек пересечения нет, то есть прямая 𝑋(𝑖) параллельна подпространству 𝑌 (𝑗). Доступ запрещен.
б) Точек пересечения бесконечно много, то есть прямая 𝑋(𝑖) целиком лежит в подпространстве 𝑌 (𝑗).
Доступ запрещен.
в) Прямая 𝑋(𝑖) и подпространство 𝑌 (𝑗) пересекаются в единственной точке. Однако прямые 𝑋(𝑖) и 𝑋(𝑗)
не имеют общих точек (скрещиваются). В этом случае точка, полученная пользователем 𝑠𝑖 не совпадет с
точкой, полученной пользователем 𝑠𝑗 . Доступ запрещен.
г) Прямая 𝑋(𝑖) и подпространство 𝑌 (𝑗) пересекаются в единственной точке. Причем эта точка лежит
на 𝑋(𝑗). Такая точка пересечения прямых – единственная, поэтому пользователь 𝑠𝑗 получит ту же точку.
Общим ключом может служить, например, 𝑛-я координата точки. Доступ разрешен.
Итак, мы построили схему предварительного распределения ключей с разграничением доступа. Теперь
рассмотрим ее недостатки.
Во-первых, если три пользователя 𝐴, 𝐵 и 𝐶 обладают взаимным доступом, то схема легко компромети-
руется. Действительно, ведь тогда их прямые лежат в одной двумерной плоскости, а открытые 𝑛−1-мерные
пространства этих пользователей, пересеченные с уравнением общей плоскости, позволяют злоумышлен-
нику получить секрет каждого из пользователей 𝐴, 𝐵 , 𝐶 . Одним из решений данной проблемы может
стать запрет на циклы длины 3 в графе доступов системы, что накладывает существенные ограничения
на область применения данной схемы.
Во-вторых, раскрытие секретов только двух участников схемы компрометирует всю схему. Достаточно
найти точки пересечения прямых пользователей 𝐴 и 𝐵 с прямой третьего участника С, и восстановить его
прямую по двум точкам.
Предложим и два способа исправления недостатков.
1. Секретом каждого участника будет 𝑘 -мерное пространство, а в качестве открытой информации об
участнике на сервере будет предоставляться 𝑛 − 𝑘 -мерное подпространство, причем 𝑛 ≥ 2𝑘 .
2. Секретом каждого участника будет не прямая, а некоторое множество точек (например, кривая или
поверхность), которое легко задается аналитически. Более того, в качестве открытой информации на сер-
вере можно также использовать 𝑛 − 1-мерные поверхности, а не плоскости.
Результатом исправления недостатков может стать, например, следующая модель:
Пример 2. 𝑘 = 2, 𝑋(𝑖) – кривая (например, окружность) в плоскости 𝐿(𝑖), 𝑚 = 𝑛 − 2. Пользователь
𝑠𝑖 ищет множество точек пересечения своей (секретной) кривой и подпространства 𝑌 (𝑗) пользователя 𝑠𝑗 ,
которое находится в открытом доступе. С учетом размерностей, возможны несколько вариантов:
а) Кривая 𝑋(𝑖) не пересекается с подпространством 𝑌 (𝑗). Доступ запрещен.
б) Кривая 𝑋(𝑖) вместе с плоскостью 𝐿(𝑖) целиком лежит в подпространстве 𝑌 (𝑗). Доступ запрещен.
в) Подпространства 𝐿(𝑖) и 𝑌 (𝑗) пересекаются по прямой. Однако кривые 𝑋(𝑖) и 𝑋(𝑗) не имеют об-
щих точек. В этом случае точка, полученная 𝑖-м пользователем не совпадет с точкой, полученной 𝑗 -м
пользователем. Доступ запрещен.
г) Подпространства 𝐿(𝑖) и 𝑌 (𝑗) пересекаются по прямой. Кривая 𝑋(𝑖) и подпространство 𝑌 (𝑗) пере-
секаются в единственной точке. Причем эта точка лежит на 𝑋(𝑗). Такая точка пересечения прямых –
единственная, поэтому пользователь 𝑠𝑗 получит ту же точку. Общим ключом может служить, например,
𝑛-я координата точки. Доступ разрешен.
д) Подпространства 𝐿(𝑖) и 𝑌 (𝑗) пересекаются по прямой. Прямая 𝑋(𝑖) и подпространство 𝑌 (𝑗) пересека-
ются в нескольких точках. Правило вычисления ключа 𝐾(𝑖, 𝑗) позволяет определить его точное значение,
либо выдает конечный (небольшой) набор возможных значений, которые можно перебрать. Пользователь
𝑠𝑗 также смог получить свой конечный набор значений 𝐾(𝑗, 𝑖), причем 𝐾(𝑖, 𝑗) ∩ 𝐾(𝑗, 𝑖) ̸= ∅. Пользователям
осталось перебрать элементы своих ключевых множеств, чтобы найти общий ключ. Доступ разрешен.
е) Подпространства 𝐿(𝑖) и 𝑌 (𝑗) пересекаются по прямой. Прямая 𝑋(𝑖) и подпространство 𝑌 (𝑗) пере-
секаются в нескольких точках. Правило вычисления ключа 𝐾(𝑖, 𝑗) не позволяет определить его точное
значение, либо выдает большой (бесконечный) набор возможных значений, которые нет возможности пе-
ребрать за разумное время. Либо подобная ситуация произошла с пользователем 𝑠𝑗 . Доступ запрещен.
Еще несколько вариантов событий, симметричных описанным с точки зрения пользователя 𝑠𝑗 , рассмат-
риваются аналогично.
Приведем, наконец, еще один простой пример схемы предварительного распределения ключей, на этот
раз с определенными значениями всех множеств и функций.
Пример 3. Пусть 𝑛=4, 𝑚= 3, 𝑘 =2. Значения 𝑋(𝑖), 𝐿(𝑖) и 𝑌 (𝑖) для каждого участника схемы (𝑖 = 1 . . . 4)
занесем в таблицу 1. Координаты точек 4-мерного пространства будем обозначать через 𝑥, 𝑦, 𝑧, 𝑡.
Таблица 1: Исходные данные к схеме предварительного распределения ключей
𝑖 𝑌 (𝑖) 𝐿(𝑖) 𝑋(𝑖)
1 {𝑥 = 0} {𝑥 = 0, 𝑦 = 0} {𝑥2 + 𝑡2 = 1} ∩ 𝐿(1)
2 {𝑦 = 0} {𝑦 = 0, 𝑧 = 0} {−𝑦 2 + 𝑡2 = 1} ∩ 𝐿(2)
3 {𝑧 = 0} {𝑧 = 0, 𝑡 = 0} {𝑥2 + 𝑦 2 + 𝑡2 = 1} ∩ 𝐿(3)
3 {𝑡 = 0} {𝑡 = 0, 𝑥 = 0} {𝑦 2 + 𝑦𝑧 = 1} ∩ 𝐿(4)
Теперь для каждой пары участников (𝑠𝑖 , 𝑠𝑗 ) вычислим и занесем в таблицу 2 пересечения 𝑋(𝑖) ∩ 𝑌 (𝑗).
Таблица 2: Промежуточный этап попытки вычисления общих ключей для каждой пары участников
𝑖, 𝑗 1 2 3 4
1 {(0, 0, 𝑧, ±1)} {(0, 0, 0, ±1)} ∅
2 {(0, 0, 0, ±1)} {(𝑥, 0, 0, ±1)} ∅
3 {(0, ±1, 0, 0)} {(0, 0, 𝑧, ±1)} {𝑥2 + 𝑦 2 = 1, 𝑧 = 𝑡 = 0}
3 {𝑦 2 + 𝑦𝑧 = 1, 𝑡 = 𝑥 = 0} ∅ {(0, ±1, 0, 0)}
Уже на этом этапе становится понятным, что выработка общего ключа для пар участников (𝑠1 , 𝑠4 ) и
(𝑠2 , 𝑠4 ) невозможна, то есть взаимный доступ этих участников друг к другу запрещен, поскольку пересе-
чения 𝑋(1) ∩ 𝑌 (4) и 𝑋(2) ∩ 𝑌 (4) пусты.
Для построения ключевых множеств 𝐾(𝑖, 𝑗) остальных пар участников нам потребуется ключевая функ-
ция Φ𝑖,𝑗 . Здесь мы будем считать, что значением Φ𝑖,𝑗 (𝑋(𝑖)∩𝑌 (𝑗)) (а значит, возможным ключом) будет одна
или несколько точек из множества 𝑋(𝑖) ∩ 𝑌 (𝑗). На самом деле, конечно, можно задать ключевую функцию
и другим способом. Например, использовать только одну координату из четырех, или сумму координат, и
т.д. Такие способы задания ключевой функции позволяют выработать общий ключ пользователям 𝑠𝑖 и 𝑠𝑗
даже в том случае, когда множества 𝑋(𝑖) и 𝑋(𝑗) не имеют общих точек. Однако в этом случае сложнее
будет доказать, что такой же ключ не сможет получить кто-нибудь еще из участников схемы, и тем самым
выдать себя за другого. Да и в целом лучше свести роль ключевой функции к минимуму. Кроме того,
будем считать, что Φ𝑖,𝑗 = Φ𝑗,𝑖 , хотя это условие также не выглядит обязательным.
В рамках введенных нами предположений становится ясно, что какую бы мы ни выбрали ключевую
функцию, 𝐾(1, 3) ∩ 𝐾(3, 1) = ∅. Если бы в качестве Φ1,3 = Φ3,1 мы выбрали сумму координат точки,
результат был бы иным. Аналогичная ситуация возникает между вторым и третьим пользователями.
Итак, пусть Φ1,2 = Φ2,1 выбирает точку с суммой всех координат, равной единице. Тогда 𝐾(1, 2) =
{(0, 0, 2, −1), (0, 0, 0, 1)}, 𝐾(2, 1) = {(0, 0, 0, 1)}, и общим ключом первого и второго участников является
(0, 0, 0, 1). Как только первый участник выберет подходящий ключ, они смогут обмениваться информацией
друг с другом.
Далее, пусть Φ3,4 = Φ4,3 выбирает точку с наибольшей координатой по 𝑦 . Тогда 𝐾(3, 4) = {(0, 1, 0, 0)} =
𝐾(4, 3) = {(0, 1, 0, 0)}, и эти два участника также смогут обмениваться информацией друг с другом.
Приведенная в примере схема согласована с дискреционной политикой безопасности с матрицей до-
ступов, представленной в таблице 3 (0 означает отсутствие взаимного доступа, то есть запрет на обмен
информацией, 1 – наличие взаимного доступа, то есть разрешение на информационный обмен).
Однако, на практике более важной является обратная задача: по данной матрице доступов построить
схему предварительного распределения ключей, удовлетворяющую задаваемой матрицей дискреционной
политике разграничения доступа. К сожалению, в случае, когда секретные доли ключей участников за-
даются сложными множествами (такими, как кривые или поверхности), решить эту задачу становится
довольно сложно.
Таблица 3: Матрица доступов для участников схемы предварительного распределения ключей
𝑖, 𝑗 1 2 3 4
1 1 0 0
2 1 0 0
3 0 0 1
3 0 0 1
3 Схема предварительного распределения ключей с учетом асимметричной
политики безопасности
Ранее мы провели адаптацию схемы Блэкли разделения секрета к схеме предварительного распределения
ключей для симметричных политик безопасности. Теперь наша цель – расширить упомянутую конструк-
цию на более широкий класс асимметричных моделей. Считая саму схему векторного разделения секрета
широко известной, опишем только построенную на ее основе асимметричную политику разграничения
доступа.
Долю секрета пользователя 𝑠𝑖 по праву доступа 𝑟 составляет множество точек 𝑋(𝑖, 𝑟) в 𝑘 -мерном под-
пространстве 𝐿(𝑖). Здесь под 𝑟 может пониматься, например, право на чтение субъектом 𝑠𝑖 объектов,
принадлежащих другому субъекту, который, в свою очередь, не получает права чтения объектов, принад-
лежащих субъекту 𝑠𝑖 . То есть в описании права доступа обязательно указывается, исходящее это право,
либо входящее. В открытом доступе хранится 𝑚-мерное подпространство 𝑌 (𝑖), сопоставленное пользова-
телю 𝑠𝑖 , причем 𝐿(𝑖) является подпространством 𝑌 (𝑖), то есть 𝑘 < 𝑚 < 𝑛.
Алгоритм выработки общего ключа между 𝑖-м и 𝑗 -м пользователями следующий:
Дано:
1) множество всевозможных ключей K,
2) множество прав доступа R (причем для каждого права в процессе выработки ключа дополнительно
указывается, исходящее оно или входящее для участвующего в выработке ключа пользователя),
3) размерности пространства и подпространств 𝑘 < 𝑚 < 𝑛;
для каждого пользователя 𝑠𝑖 : 4) его доли секрета 𝑋(𝑖, 𝑟 _𝑖𝑛), 𝑋(𝑖, 𝑟 _𝑜𝑢𝑡) относительно каждого права
𝑟 ∈ R,
5) секретное подпространство 𝐿(𝑖),
6) открытое подпространство 𝑌 (𝑖);
7) также для каждой пары пользователей (𝑠𝑖 , 𝑠𝑗 ) и права 𝑟 задана ключевая функция Φ𝑖,𝑗,𝑟 : R
𝑘+𝑚
→ K* ,
помогающая выработать общий ключ.
Здесь постфикс 𝑜𝑢𝑡 в названии права показывает, что право доступа принадлежит пользователю 𝑠𝑖 по
отношению к другому пользователю, а постфикс 𝑖𝑛 – что другой пользователь применяет право доступа
по отношению к пользователю 𝑠𝑖 .
Получить: для каждой пары пользователей (𝑠𝑖 , 𝑠𝑗 ) ключевые множества 𝐾(𝑖, 𝑗, 𝑟), 𝐾(𝑗, 𝑖, 𝑟) ⊂ K, име-
ющие общий элемент, который и будет являться общим ключом пользователей 𝑠𝑖 и 𝑠𝑗 , либо установить,
что получение таких множеств невозможно (а значит, 𝑠𝑖 не обладает правом доступа 𝑟 по отношению к
𝑠𝑗 ).
1. Пользователь 𝑠𝑖 находит пересечение множеств 𝑋(𝑖, 𝑟 _𝑜𝑢𝑡) и 𝑌 (𝑗). Если пересечение пусто, выработка
общего ключа невозможна. Это значит, что пользователь 𝑠𝑖 не обладает правом доступа 𝑟 к объектам
пользователя 𝑠𝑗 в рамках применяющейся политики безопасности.
2. Если 𝑋(𝑖, 𝑟 _𝑜𝑢𝑡) ∩ 𝑌 (𝑗) содержит непустое множество точек, то пользователь 𝑠𝑖 вычисляет ключевую
_
функцию Φ𝑖,𝑗,𝑟 𝑜𝑢𝑡 от координат этих точек. Результатом вычисления функции является некоторое
множество. Если оно пусто, либо бесконечно, выработка общего ключа невозможна (пользователь
𝑠𝑖 не обладает правом доступа 𝑟 к объектам пользователя 𝑠𝑗 в рамках применяющейся политики
безопасности).
_
3. Если Φ𝑖,𝑗,𝑟 𝑜𝑢𝑡 (𝑋(𝑖, 𝑟 _𝑜𝑢𝑡) ∩ 𝑌 (𝑗)) непусто и конечно, обозначим это множество через 𝐾𝑖 (𝑖, 𝑗, 𝑟).
4. Пользователь 𝑠𝑗 находит пересечение множеств 𝑋(𝑗, 𝑟 _𝑖𝑛) и 𝑌 (𝑖). Если пересечение пусто, выработка
общего ключа невозможна. Это значит, что пользователь 𝑠𝑖 не обладает правом доступа 𝑟 к объектам
пользователя 𝑠𝑗 в рамках применяющейся политики безопасности.
5. Если 𝑋(𝑗, 𝑟 _𝑖𝑛) ∩ 𝑌 (𝑖) содержит непустое множество точек, то пользователь 𝑠𝑗 вычисляет ключевую
_
функцию Φ𝑗,𝑖,𝑟 𝑖𝑛 от координат этих точек. Результатом вычисления функции является некоторое
множество. Если оно пусто, либо бесконечно, выработка общего ключа невозможна (пользователь
𝑠𝑖 не обладает правом доступа 𝑟 к объектам пользователя 𝑠𝑗 в рамках применяющейся политики
безопасности).
_
6. Если Φ𝑗,𝑖,𝑟 𝑖𝑛 (𝑋(𝑗, 𝑟 _𝑖𝑛) ∩ 𝑌 (𝑖)) непусто и конечно, обозначим это множество через 𝐾𝑗 (𝑖, 𝑗, 𝑟).
Стоит обратить внимание на порядок параметров множеств 𝐾𝑖 и 𝐾𝑗 , который показывает, что право
𝑟 рассматривается как право субъекта 𝑠𝑖 в отношении субъекта 𝑠𝑗 , но не в обратную сторону (то есть
право 𝑟 является исходящим), что учитывает асимметричность распределения прав доступа в системе.
Однако если для всех субъектов и прав доступа системы выполнено равенство 𝐾𝑖 (𝑖, 𝑗, 𝑟) = 𝐾𝑗 (𝑗, 𝑖, 𝑟),
получаем симметричную политику безопасности в качестве частного случая.
7. Пользователи сравнивают результаты. Если 𝐾𝑖 (𝑖, 𝑗, 𝑟)∩𝐾𝑗 (𝑖, 𝑗, 𝑟) непусто (если у каждого пользователя
получилось некоторое множество результатов, то должны совпадать хотя бы какие-то элементы этих
множеств), то элемент из 𝐾𝑖 (𝑖, 𝑗, 𝑟) ∩ 𝐾𝑗 (𝑖, 𝑗, 𝑟) является общим ключом связи между пользователями,
то есть субъект 𝑠𝑖 получает право доступа 𝑟 в отношении субъекта 𝑠𝑗 .
8. Если же пересечение пусто, то 𝑖-й пользователь не обладает правом доступа 𝑟 к объектам 𝑗 -го поль-
зователя в рамках применяющейся политики безопасности.
Поскольку состояние подсистемы безопасности изменяется со временем, то субъекты в процессе функ-
ционирования системы могут получать новые права доступа, а также лишаться старых. В случае дискре-
ционной политики безопасности, например, происходит модификация матрицы доступов. Чтобы данные
изменения нашли отражение в схеме распределения ключей, достаточно переслать по защищенному ка-
налу каждому пользователю, которого коснулись соответствующие изменения, новую версию множеств
𝑋(𝑖, 𝑟).
Приведенная схема хорошо согласуется не только с дискреционными политиками разграничения доступа
наподобие HRU, базирующимися на матрицах доступа, но и с мандатными политиками безопасности.
Рассмотрим пример применение схемы к мандатной политике разграничения доступа с линейным порядком
на уровнях доступа (как правило, более сложные частичные порядки редко применяются на практике).
Пусть мандатная политика безопасности подразумевает три уровня секретности (упорядоченные ли-
нейно):𝐴 – секретная информация, 𝐵 – информация с ограниченным доступом, 𝐶 – информация
для свободного доступа. Заодно метки 𝐴, 𝐵 , 𝐶 будем использовать для индексации субъектов, нахо-
дящихся на соответствующих уровнях доступа. Множество прав доступа рассмотрим следующее: R =
{𝑟𝑒𝑎𝑑_𝑜𝑢𝑡, 𝑟𝑒𝑎𝑑_𝑖𝑛, 𝑤𝑟𝑖𝑡𝑒_𝑜𝑢𝑡, 𝑤𝑟𝑖𝑡𝑒_𝑖𝑛}.
Пример 4. Пусть 𝑘 =2, 𝑋(𝑖, 𝑟) – круг в плоскости 𝐿(𝑖) радиуса 1, 2 или 3, 𝑚 = 𝑛 − 2. Функция Φ𝑖,𝑗,𝑟 будет
возвращать упорядоченный набор координат концов отрезка, по которому пересекутся круг и плоскость,
и пустое значение, если пересечение пусто, либо не является отрезком.
Рассмотрим пользователя 𝑠𝐴 . Он обладает четырьмя секретными множествами 𝑋(𝐴, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡),
𝑋(𝐴, 𝑤𝑟𝑖𝑡𝑒_𝑖𝑛), 𝑋(𝐴, 𝑟𝑒𝑎𝑑_𝑖𝑛) и 𝑋(𝐴, 𝑤𝑟𝑖𝑡𝑒_𝑜𝑢𝑡), первые два – круги радиуса 3, последние два – ра-
диуса 1 (в данном примере будем считать все круги концентрическими). Радиусы кругов определены в
соответствии с принципами мандатной политикой безопасности «нет чтения вверх» и «нет записи вниз».
Так, например, плоскость 𝐿(𝐶) пользователя, находящегося на уровне доступа 𝐶 , будет пересекаться с
плоскостью 𝐿(𝐴) по прямой, расстояние до которой от общего центра кругов лежит в интервале от 2 до
3. Таким образом, в пересечение попадут точки кругов 𝑋(𝐴, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡) и 𝑋(𝐴, 𝑤𝑟𝑖𝑡𝑒_𝑖𝑛), но пользователь
𝑠𝐶 не получить права читать информацию пользователя 𝑠𝐴 , в то время как пользователь 𝑠𝐴 не сможет
писать информацию в объекты пользователя 𝑠𝐶 .
Далее, 𝐿(𝐵) в пересечении с 𝐿(𝐴) пройдет на расстоянии от 1 до 2 от центра кругов пользователя 𝑠𝐴 .
*
Наконец, плоскость пользователя 𝑠𝐴 , обладающего тем же правом доступа, что и 𝑠𝐴 , пересечется с 𝐿(𝐴)
по прямой, расстояние до которой от центра кругов не будет превышать 1, то есть пользователи одного
уровня могут получить полный доступ друг к другу.
Теперь рассмотрим пользователя 𝑠𝐵 . Все его секретные множества 𝑋(𝐵, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡), 𝑋(𝐵, 𝑤𝑟𝑖𝑡𝑒_𝑖𝑛),
𝑋(𝐵, 𝑟𝑒𝑎𝑑_𝑖𝑛) и 𝑋(𝐵, 𝑤𝑟𝑖𝑡𝑒_𝑜𝑢𝑡) – круги радиуса два. Правила пересечения с плоскостями других поль-
зователей – те же. Таким образом, 𝑠𝐵 не сможет читать информацию из объектов 𝑠𝐴 и писать информацию
в объекты 𝑠𝐶 , и наоборот, 𝑠𝐴 не сможет писать в объекты 𝑠𝐵 , а 𝑠𝐶 – читать из объектов 𝑠𝐵 .
У пользователя 𝑠𝐶 ситуация аналогичная, только теперь круги 𝑋(𝐶, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡) и 𝑋(𝐶, 𝑤𝑟𝑖𝑡𝑒_𝑖𝑛) имеют
радиус 1, а 𝑋(𝐶, 𝑟𝑒𝑎𝑑_𝑖𝑛) и 𝑋(𝐶, 𝑤𝑟𝑖𝑡𝑒_𝑜𝑢𝑡) – радиус 3.
В результате 𝑋(𝐴, 𝑟𝑒𝑎𝑑_𝑖𝑛) и 𝑋(𝐵, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡) будут пересекаться по пустому множеству, и выработка
общего ключа на чтение пользователем 𝑠𝐵 материалов пользователя 𝑠𝐴 невозможна. Напротив, пересече-
ния 𝑋(𝐵, 𝑟𝑒𝑎𝑑_𝑖𝑛) с 𝐿(𝐴) и 𝑋(𝐴, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡) с 𝐿(𝐵) непусты, пусть это отрезки. Если в рамках мандатной
политики безопасности нет дополнительных ограничений на потоки информации, то эти отрезки совпада-
ют, а значит совпадают и наборы координат их концов, что приводит к выработке общего ключа на чтение
пользователем 𝑠𝐴 материалом пользователя 𝑠𝐵 : 𝐾𝐴 (𝐴, 𝐵, 𝑟𝑒𝑎𝑑) = 𝐾𝐵 (𝐴, 𝐵, 𝑟𝑒𝑎𝑑).
Необходимо сразу заметить, что требования на концентричность всех кругов одного пользователя, на
радиус этих кругов и расстояние от центра кругов до прямой пересечения серьезно усложняют построе-
ние действующей модели, но не являются обязательными. Более того, не обязательно выбирать именно
круги в качестве секретных множеств: это было сделано исключительно ради примера. Реализовать схему
разделения секрета с учетом мандатной политику безопасности можно и менее строгим способом.
Приведем еще один пример, на этот раз для дискреционной политики безопасности.
Пример 5. В условиях примера 3 рассмотрим множество прав R = {𝑟𝑒𝑎𝑑_𝑜𝑢𝑡, 𝑟𝑒𝑎𝑑_𝑖𝑛}. Секретные
множества 𝑋(𝑖, 𝑟𝑒𝑎𝑑_𝑖𝑛) = 𝑋(𝑖, 𝑟𝑒𝑎𝑑_𝑜𝑢𝑡) примем совпадающими с исходными 𝑋(𝑖) для каждого пользо-
вателя 𝑠𝑖 , так чтобы пересечения 𝑋(𝑖, 𝑟) ∩ 𝑌 (𝑗) по каждому праву доступа 𝑟 ∈ R совпадали с занесенными
в таблицу 2. Наконец, переопределим ключевые функции следующим образом:
Φ1,2,𝑟𝑒𝑎𝑑_𝑖𝑛 , Φ2,1,𝑟𝑒𝑎𝑑_𝑜𝑢𝑡 и Φ2,1,𝑟𝑒𝑎𝑑_𝑖𝑛 выбирают точку с суммой всех координат, равной едини-
це, а Φ1,2,𝑟𝑒𝑎𝑑_𝑜𝑢𝑡 выбирает точку с суммой всех координат, равной нулю. Тогда 𝐾1 (1, 2, 𝑟𝑒𝑎𝑑) =
{(0, 0, 1, −1), (0, 0, −1, 1)}, 𝐾2 (1, 2, 𝑟𝑒𝑎𝑑) = {(0, 0, 0, 1)}, 𝐾1 (2, 1, 𝑟𝑒𝑎𝑑) = {(0, 0, 2, −1), (0, 0, 0, 1)},
𝐾2 (2, 1, 𝑟𝑒𝑎𝑑) = {(0, 0, 0, 1)}. Поскольку 𝐾1 (1, 2, 𝑟𝑒𝑎𝑑) ∩ 𝐾2 (1, 2, 𝑟𝑒𝑎𝑑) = ∅, первый участник схемы не по-
лучит права читать информацию второго участника. Однако второй получит право читать информацию
первого, так как будет выработан общий ключ 𝐾1 (2, 1, 𝑟𝑒𝑎𝑑) ∩ 𝐾2 (2, 1, 𝑟𝑒𝑎𝑑) = {(0, 0, 0, 1)}.
_ _
Далее, пусть Φ3,4,𝑟𝑒𝑎𝑑 𝑖𝑛 , Φ4,3,𝑟𝑒𝑎𝑑 𝑜𝑢𝑡 выбирают точки с наибольшей координатой по 𝑦 , а Φ3,4,𝑟𝑒𝑎𝑑 𝑜𝑢𝑡 _
и Φ4,3,𝑟𝑒𝑎𝑑_𝑖𝑛 выбирает точки с положительным значением координаты 𝑦 . Тогда 𝐾3 (4, 3, 𝑟𝑒𝑎𝑑) =
𝐾4 (4, 3, 𝑟𝑒𝑎𝑑) = {(0, 1, 0, 0)}, и четвертый участник получит право читать информацию третьего. Однако,
вычислить 𝐾3 (4, 3, 𝑟𝑒𝑎𝑑) не удается, и третий участник схемы не сможет читать информацию четвертого.
Приведенная в примере схема согласована с дискреционной политикой безопасности со следующей мат-
рицей доступов (0 на пересечении 𝑖-той строки и 𝑗 -го столбца означает отсутствие права доступа участника
𝑠𝑖 к участнику 𝑠𝑗 , заполненная правом 𝑟 ячейка – наличие соответствующего права участника 𝑠𝑖 по отно-
шению к участнику 𝑠𝑗 ):
Таблица 4: Матрица доступов для участников асимметричной схемы предварительного распределения
ключей
𝑖, 𝑗 1 2 3 4
1 0 0 0
2 read 0 0
3 0 0 0
3 0 0 read
Список литературы
[1] S.V. Usov. On the possibility of implementation of the threshold key exchange protocol with discretionary
access control based on Blakley”s secret sharing scheme. Shestoj tehnologicheskij uklad: mehanizmy i perspektivy
razvitija. Chast’ 1. Sbornik materialov III Mezhdunarodnoj nauchno-prakticheskoj konferencii, Hanty-Mansijsk:
JuGU, 58–59, 2015 (In Russian).
[2] S.V. Belim, S.Yu. Belim, S.Yu. Polyakov. The implementanion of discretionary access separation using a
modified Blom’s scheme of key distribution. Information Security Problems. Computer Systems, 3:72–76, 2015
(In Russian).
[3] S.V. Belim, S.Yu. Belim. KDP Scheme of Preliminary Key Distribution in Discretionary Security Policy.
Automatic Control and Computer Sciences, 50(8):777–786, 2016.
[4] G.R. Blakley. Safeguarding cryptographic keys. Proceedings of the 1979 AFIPS National Computer
Conference. Monval, NJ, USA: AFIPS Press, 313–317, 1979.
On the Application of the Access Control Policy to the Threshold Key Exchange
Protocol Based on the Blakley’s Scheme of Secret Sharing
Sergey V. Usov
Traditional pre-distribution algorithms ignore the security policy of the system. In this paper, we succeeded
in proposing an approach based on the Blackley’s scheme for the distribution of keys, leveling this shortcoming.
In the proposed scheme, obtaining a public key is only possible for those pairs of participants in the scheme, the
exchange of information between which is allowed by the security policy. Moreover, the proposed scheme takes
into account the direction of the data flow and the type of access, such as read and write.