Реализация симплексных каналов в распределенных системах на основе схемы предварительного распределения ключей Блома С.В. Белим С.Ю. Белим belimsv@omsu.ru sbelim@mail.ru Омский государственный университет им. Ф.М. Достоевского, Омск, Россия Аннотация В статье рассмотрена возможность использования схемы предвари- тельного распределения ключей Блома для реализации симплекс- ных каналов в распределенных системах. Модификация схемы Бло- ма состоит в использовании асимметричной функции от трех пере- менных для формирования ключевых материалов. Предложенная схема не приводит к увеличению объема ключевых материалов. Трудоемкость вычисления парных ключей возрастает. Введение Схемы предварительного распределения ключей используются для организации взаимодействия пользо- вателей сети по защищенным каналам связи. Основная идея состоит в том, что каждый пользователь получает набор ключевых материалов, на основании которых он может вычислить общий ключ шифрова- ния с любым другим пользователем системы, используя открытую информацию. Схема предварительного распределения ключей Блома основана на модели взаимодействия «каждый с каждым». Однако такой подход оправдан только в сетях с доверенными пользователями. В современ- ных глобальных сетях все большее распространение получает подход, в котором вводится ограничение на полномочия отдельно взятых пользователей. Причем ограничения могут быть связаны как с действия- ми пользователя в сети в целом, так и с ограничением его доступа к ресурсам. Решение данных задач возможно несколькими способами. Один из подходов получил название ID-based криптографии [1]. На сегодняшний день задачи ID-based криптографии решаются с помощью ассиметричных алгоритмов шифрования. Основная идея состоит в выработке ключевой информации на основе идентификаторов [1] или атрибутов пользователя [2, 3, 4]. Основное направление развития ID-based криптографии состоит в развитии подхода, позволяющего связываться с любым абонентом сети только на основе открытой инфор- мации. При этом каждый пользователь сети должен получить некоторый сертификат от удостоверяющего центра. Во всех работах, опубликованных к настоящему времени решаются задачи отправки зашифрован- ных сообщений и электронной цифровой подписи с помощью криптографических алгоритмов с открытым ключом. Основным недостатком данного подхода является общая проблема использования ассиметричной криптографии - трудоемкость вычислений, приводящая к временным задержкам. В связи с чем акту- альной является проблема разработки алгоритмов ID-based криптографии, основанной на использовании многочленов. 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 Следует также учесть критерии, которым должна удовлетворять криптосистема на основе атрибутов, сформулированные в работе [5]: К1: Конфиденциальность данных. Данные должны быть зашифрованы владельцем перед отправкой их в облако. Неавторизованный участ- ник, включая облако не могут узнать о данных, которые были зашифрованы. К2: Детальный контроля доступа. В группе пользователей система предоставляет различные правила доступа для каждого отдельного участника группы. Таким образом, пользователи, которые находятся в одной группе могут иметь различ- ные правила доступа к данным. К3: Масштабируемость. Число зарегистрированных пользователей не должно влиять на производительность системы. К4: Контроль действий. Недопустима передача атрибутов секретного ключа авторизованного пользователя другим лицам. К5: Отзыв прав пользователя. Если пользователь выходит из системы, то система может отозвать права данного пользователя. Поль- зователь, чьи права были отозваны, уже не сможет получить доступ к данным. К6: Невозможность сговора. Пользователи не могут объединять свои атрибуты, чтобы расшифровать данные, поскольку каждый атрибут связан с многочленом или случайным числом. Таким образом, пользователи не могут вступать в сговор друг с другом. Также распределение ключей с ограничением на взаимодействие может быть реализовано с помощью хэш-функций [6]. Другой подход основан на модификации схем предварительного распределения ключей. В работе [7] предложена модификация схемы Блома, позволяющая реализовать запрет на отдельные каналы обмена информацией между пользователями. В статьях [8, 9] аналогичная задача решена на основе KDP-схемы предварительного распределения ключей. Однако в обоих случаях запрещен или разрешен полный обмен информацией между двумя пользователями. Тогда как в реальных системах актуальна проблема разгра- ничения доступа к ресурсам исходя из его типа. Таким образом, актуальной является задача модификации схем предварительного распределения ключей, учитывающая направление информационных потоков. Целью данной статьи является разработка схемы предварительного распределения ключей для системы с учетом типов доступов. 1 Постановка задачи Рассмотрим систему с двумя базовыми типами доступа: чтения (𝑟) и записи (𝑤). При инициализации ка- нала обмена информацией необходимо следить в каком направлении будут передаваться данные. Таким образом все каналы должны быть симплексными. Введем переменную 𝑝, показывающую направление пе- редачи данных. Если пользователь 𝑢 отправляет запрос на открытие канала по чтению, то есть получению информации, то 𝑠 = −1. Если пользователь открывает канал по записи, то есть передаче информации, то 𝑠 = 1. В схеме предварительного распределения ключей каждому пользователю по защищенному каналу вы- даются некоторые ключевые материалы, на основании которых с использованием открытой информации может быть сформирован общий ключ. В нашем случае симплексных каналов для пары пользователей 𝑢𝑖 и 𝑢𝑗 должны формироваться два ключа: 𝑘𝑖𝑗 – ключ для передачи информации от пользователя 𝑢𝑖 пользо- вателю 𝑢𝑗 , 𝑘𝑗𝑖 – ключ для передачи информации от пользователя 𝑢𝑗 пользователю 𝑢𝑖 . В случае обращения пользователя 𝑢𝑖 для чтения информации к пользователю 𝑢𝑗 или обращения пользователя 𝑢𝑗 к пользова- телю 𝑢𝑖 для записи используется ключ 𝑘𝑗𝑖 . В случае обращения пользователя 𝑢𝑗 для чтения информации к пользователю 𝑢𝑖 или обращения пользователя 𝑢𝑖 к пользователю 𝑢𝑗 для записи используется ключ 𝑘𝑖𝑗 . Потребуем, чтобы запрещенные каналы передачи информации имели нулевой парный ключ, а разрешен- ные – ненулевой. Схему предварительного распределения ключей, удовлетворяющую данным условиям, будем называть симплексной. 2 Алгоритм предварительного распределения ключей Реализуем мандатную схему предварительного распределения ключей на базе хорошо известной схемы Блома, проведя ее модификацию. В схеме предварительного распределения ключей Блома на сервере генерируется симметрический мно- гочлен от двух переменных 𝑓 (𝑥, 𝑦) над полем по модулю 𝑝. Каждому пользователю 𝑢𝑖 сопоставляется некоторое число 𝑟𝑖 . Далее для каждого пользователя формируются многочлены от одного переменного 𝑔𝑖 (𝑥) = 𝑓 (𝑥, 𝑟𝑖 ). Данные многочлены передаются по защищенным каналам пользователям и хранятся в секрете. При необходимости выработать общий ключ с пользователем 𝑢𝑗 пользователь 𝑢𝑖 извлекает из открытой базы элемент 𝑟𝑗 и вычисляет значение 𝑘𝑖𝑗 = 𝑔𝑖 (𝑟𝑗 ). Аналогичным образом поступает пользова- тель 𝑢𝑗 , вычисляя 𝑘𝑗𝑖 = 𝑔𝑗 (𝑟𝑖 ). Симметричность многочлена 𝑓 (𝑥, 𝑦) обеспечивает выполнение равенства 𝑘𝑖𝑗 = 𝑘𝑗𝑖 . Для реализации симплексной схемы предварительного распределения ключей необходимо учесть на- правления информационных потоков. Для учета направления потоков будем генерировать на сервере многочлен от трех переменных 𝐹 (𝑥, 𝑦, 𝑠) над полем по модулю 𝑝, в котором переменная 𝑠 может при- нимать два значения (+1 или -1) и определяет направление потока информации. Каждому пользователю 𝑢𝑖 как и в обычной схеме Блома сопоставим некоторое число 𝑟𝑖 , которое хранится в открытом виде и защищено от изменений. Для каждого пользователя сервер распределения ключей формирует многочлен 𝐺𝑖 (𝑥, 𝑠) = 𝐹 (𝑥, 𝑟𝑖 , 𝑠) и передает его по защищенному каналу. Многочлен 𝐹 (𝑥, 𝑦, 𝑠) должен иметь такой вид, чтобы на основе функции 𝐺𝑖 (𝑥, 𝑠) и чисел 𝑟𝑖 для разрешенного обмена информации генерировался ключ 𝑘𝑖𝑗 ̸= 0, а для запрещенных каналов 𝑘𝑖𝑗 = 0. При этом оба участника обмена должны вырабатывать одинаковый ключ на основе собственных секретных ключевых материалов и открытой информации друг о друге. Рассмотрим два вида взаимодействия пользователей при передаче информации. Во-первых, остановим- ся на случае, в котором пользователь 𝑢𝑖 инициирует получение информации от пользователя 𝑢𝑗 , то есть обращается к нему с запросом на чтение. Пользователь 𝑢𝑗 отправляет информацию предварительно за- шифровав ее ключом 𝑘𝑗𝑖 = 𝐺𝑗 (𝑟𝑖 , 1) = 𝐹 (𝑟𝑖 , 𝑟𝑗 , 1). Параметр 𝑠 = 1, так как для 𝑢𝑗 информационный поток исходящий. Пользователь 𝑢𝑖 получает сообщение и расшифровывает его тем же ключом, вычисляемым на основе своих ключевых материалов: 𝑘𝑗𝑖 = 𝐺𝑖 (𝑟𝑗 , −1) = 𝐹 (𝑟𝑗 , 𝑟𝑖 , −1). Параметр 𝑠 = −1, так как для 𝑢𝑖 информационный поток входящий. Второй случай состоит в том, что пользователь 𝑢𝑖 инициирует отправку информации пользователю 𝑢𝑗 , то есть обращается к нему с запросом на запись. Пользователь 𝑢𝑖 отправляет информацию предварительно зашифровав ее ключом 𝑘𝑖𝑗 = 𝐺𝑖 (𝑟𝑗 , 1) = 𝐹 (𝑟𝑗 , 𝑟𝑖 , 1). Параметр 𝑠 = 1, так как для 𝑢𝑖 информационный поток исходящий. Пользователь 𝑢𝑗 получает сообщение и расшифровывает его тем же ключом, вычисляемым на основе своих ключевых материалов: 𝑘𝑖𝑗 = 𝐺𝑗 (𝑟𝑖 , −1) = 𝐹 (𝑟𝑗 , 𝑟𝑖 , −1). Параметр 𝑠 = −1, так как для 𝑢𝑗 информационный поток входящий. Из рассмотрения этих двух случаев вытекает три требования, накладываемых на функцию 𝐹 (𝑥, 𝑦, 𝑠): 1. 𝐹 (𝑥, 𝑦, 1) ̸= 𝐹 (𝑦, 𝑥, 1), 2. 𝐹 (𝑥, 𝑦, −1) ̸= 𝐹 (𝑦, 𝑥, −1), 3. 𝐹 (𝑥, 𝑦, 1) = 𝐹 (𝑦, 𝑥, −1). Первые два требования сводятся к несимметричности функции 𝐹 (𝑥, 𝑦, 𝑠) к перестановке первых двух ар- гументов при любом значении третьего аргумента. Для криптографической стойкости также необходимо потребовать, чтобы вычисление 𝐹 (𝑥, 𝑦, 𝑠) было невозможно на основании известного значения 𝐹 (𝑦, 𝑥, 𝑠). Будем задавать 𝐹 (𝑦, 𝑥, 𝑠) в следующем виде: {︂ ℎ(𝑦) 𝑥 , 𝑖𝑓 𝑠 = 1, 𝐹 (𝑥, 𝑦, 𝑠) = 𝑦 ℎ(𝑥) , 𝑖𝑓 𝑠 = −1. Здесь ℎ(𝑥) некоторый многочлен от одной переменной. Очевидно, что данная функция удовлетворяет всем трем требованиям, перечисленным выше. Криптографическая стойкость данной функции обеспечивается трудоемкостью задач линейного логарифмирования и вычисления корня в конечных полях. Рассмотрим схему распределения ключей на основе данной функции. Каждому пользователю переда- ются ключевые материалы, необходимые для вычисления функции от двух переменных: {︂ ℎ(𝑟𝑖 ) 𝑥 , 𝑖𝑓 𝑠 = 1, 𝐺𝑖 (𝑥, 𝑠) = 𝐹 (𝑥, 𝑟𝑖 , 𝑠) = ℎ(𝑥) 𝑟𝑖 , 𝑖𝑓 𝑠 = −1. Для вычисления значений функции 𝐺𝑖 (𝑥, 1) пользователю 𝑢𝑖 необходимо знать одно число ℎ𝑖 = ℎ(𝑟𝑖 ), которое сервер передает ему по защищенному каналу. Рассмотрим более сложный случай вычисления 𝐺𝑖 (𝑥, −1). Пусть ℎ(𝑥) представляет собой многочлен степени 𝑚: ℎ(𝑥) = 𝑎𝑚 𝑥𝑚 + 𝑎𝑚−1 𝑥𝑚−1 + ... + 𝑎1 𝑥 + 𝑎0 . Тогда значение функции: 𝑎 𝑥𝑚 +𝑎𝑚−1 𝑥𝑚−1 +...+𝑎1 𝑥+𝑎0 𝐺𝑖 (𝑥, −1) = 𝑟𝑖 𝑚 = 𝑚 𝑚−1 𝑥 𝑎 𝑥 𝑥 = (𝑟𝑖𝑎𝑚 ) ... (𝑟𝑖𝑎1 ) (𝑟𝑖𝑎0 ) = (︀ )︀ 𝑟𝑖 𝑚−1 (︁ )︁𝑥𝑚 (︁ )︁𝑥𝑚−1 (︁ )︁𝑥 (𝑖) (𝑖) (𝑖) = 𝑏(𝑖) 𝑚 · 𝑏𝑚−1 · ... · 𝑏1 · 𝑏0 , (𝑖) где 𝑏𝑘 = 𝑟𝑖𝑎𝑘 (𝑘 = 1, ..., 𝑚). Таким образом сервер в качестве ключевых материалов высылает пользователю 𝑢𝑖 по защищенному каналу вектор: (︁ )︁ (𝑖) (𝑖) (𝑖) 𝑔𝑖 = ℎ𝑖 , 𝑏(𝑖) 𝑚 , 𝑏𝑚−1 , ..., 𝑏1 , 𝑏0 . Этих данных достаточно для вычисления значений функции. При этом, задача определения коэффициен- тов многочлена ℎ(𝑥) по координатам вектора 𝑔𝑖 сводится к дискретному логарифмированию. Следует отметить, что данная схема незначительно увеличивает объем ключевых материалов, храня- щихся у пользователя в сравнении с традиционной схемой Блома – добавляется одно число. Однако про- цедура нахождения парного ключа значительно более трудоемкая, так как требует возведения в степень больших чисел. Заключение Таким образом, модификация схемы Блома позволяет организовать обмен сообщениями по симплексным каналам. При этом приходится отказаться от идеи использования симметрических многочленов. Такой отказ обусловлен тем, что сам обмен информацией становится несимметричным. Список литературы [1] A. Shamir. Identity-Based Cryptosystems and Signature Schemes. Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, 7:47–53, 1984. [2] A. Sahai, B. Waters. Fuzzy Identity-Based Encryption. Cryptology ePrint Archive, Report 2004/086, 2004. [3] D. Boneh, M. Franklin. Identity-based encryption from the weil pairing. In CRYPTO ’01: Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, 213–229, 2001. [4] C. Cocks. An identity based encryption scheme based on quadratic residues. Proceedings of the 8th IMA International Conference on Cryptography and Coding, 360–363, 2001. [5] C.-C. Lee, P.-S. Chung, M.-S. Hwang. A Survey on Attribute-based Encryption Schemes of Access Control in Cloud Environments. International Journal of Network Security, 15(4):231–240, 2013. [6] S.V. Belim, N.F. Bogachenko. Distribution of Cryptographic Keys in Systems with a Hierarchy of Objects. Automatic Control and Computer Sciences, 50(8):773–776, 2016. [7] 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. [8] 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. [9] S.V. Belim, S.Yu. Belim. The VPN Implementation on Base of the KDP-Scheme. CEUR Workshop Proceedings, 1732, 2016. URL: http://ceur-ws.org/Vol-1732/paper3.pdf. Realization of Simplex Channels in the Distributed Systems on the Basis of the Blom’s Preliminary Distribution of Keys Scheme Sergey V. Belim, Svetlana Yu. Belim In article the possibility of use of the Blom’s keys preliminary distribution scheme for simplex channels realization in the distributed systems is considered. The Blom’s schem modification includes use asymmetrical function of three variables for key materials calculation. The suggested scheme doesn’t increase the key materials volume. The calculation’s difficulty for pair keys increases.