Изобретение относится к устройствам для секретной или скрытной передачи информации в современных сетях связи, а более конкретно к системе распределения ключей для секретной связи.
Задача распределения ключей является важнейшей при решении ряда вопросов сетевой безопасности, а именно для обеспечения таких услуг, безопасности как конфиденциальность, подлинность и целостность информации при ее передаче между узлами сети. Основным механизмом обеспечения перечисленных услуг безопасности является криптографическое преобразование данных, которое осуществляется при помощи секретных ключей.
В симметричном криптографическом преобразовании один и тот же ключ используется в прямом (например, шифровании) и обратном преобразовании (например, дешифровании). При этом криптографические ключи распределяются исполнительной схемой процессора таким образом, что каждая пара узлов сети имеет общий секретный ключ (см., например, патент США №5150411 [1]).
В другом решении (например, по патенту США №4876716 [2]) приведено описание способа распределения ключей, формируемых при помощи генератора случайных чисел, между двумя системами по незащищенному каналу связи и вычисления общего секретного ключа исполнительной схемой процессора для передачи информации между этими системами.
Существует иной подход к решению задачи распределения ключей, который заключается в создании специализированной инфраструктуры, например инфраструктуры открытых ключей (см. А.П. Алферов, А.Ю. Зубков, А.С. Кузьмин, А.В. Черемушкин. Основы криптографии. М.: "Гелиос Ассоциация Российских вузов", 2002 [3]). Однако высокая стоимость развертывания такой инфраструктуры и последующего обслуживания ограничивает ее применение в современных ad hoc и mesh-сетях.
Задача, на решение которой направлено заявляемое изобретение, состоит в повышении сетевой безопасности за счет применения схемы предварительного распределения ключей с гарантированно высоким уровнем защищенности при межкластерном взаимодействии и допустимым уровнем защищенности при внутрикластерном взаимодействии, а также за счет разработки способа эффективного функционирования такой схемы.
Поставленная задача решена за счет разработки схемы распределения ключей EKSYD для обслуживания сети с кластерной организацией, при этом в такой схеме используется доверенный центр на этапе формирования и распределения ключевых блоков, что обеспечивает гарантированную защищенность при межкластерном взаимодействии и допустимый уровень защищенности при внутрикластерном взаимодействии узлов без участия доверенного центра, причем доверенный центр имеет исполнительную схему процессора и память, а каждый узел сети имеет исполнительную схему процессора, память и приемопередатчик, при этом:
- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора несущей матрицы инцидентности заданного размера с целью построения результирующей матрицы инцидентности;
- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора вложенных матриц инцидентности заданного размера с целью построения результирующей матрицы инцидентности;
- доверенный центр выполнен с возможностью формирования посредством исполнительной схемы процессора результирующей матрицы инцидентности путем объединения упомянутых несущей и вложенных матриц в соответствии с «гнездовым» принципом;
- доверенный центр выполнен с возможностью формирования ключевого пула сети при помощи генератора псевдослучайных чисел;
- доверенный центр выполнен с возможностью выделения посредством исполнительной схемы процессора ключевого пула каждого кластера из упомянутого ключевого пула сети;
- доверенный центр выполнен с возможностью выделения посредством исполнительной схемы процессора ключевого блока отдельного узла из упомянутого ключевого пула кластера, в который входит этот узел;
- доверенный центр выполнен с возможностью вычисления посредством исполнительной схемы процессора и генератора псевдослучайных чисел уникального идентификатора узла каждого кластера;
- доверенный центр выполнен с возможностью секретной передачи посредством каналов связи сформированных упомянутых ключевых блоков и их идентификаторов узлам каждого кластера, участвующим в межкластерном и внутрикластерном взаимодействии, которое заключается в обмене данными по открытым (незащищенным) каналам связи, причем каждому узлу передается один ключевой блок и идентификатор;
- узлы выполнены с возможностью вычисления посредством исполнительной схемы процессора столбца результирующей матрицы инцидентности произвольного узла по его идентификатору;
- узлы выполнены с возможностью формирования посредством исполнительной схемы процессора парного секретного ключа на основе упомянутого вычисленного столбца результирующей матрицы инцидентности узла-получателя и собственного ключевого блока;
- узлы выполнены с возможностью шифрования/дешифрования, а также проверки подлинности и целостности полезной информации при помощи упомянутого парного секретного ключа посредством исполнительной схемы процессора;
- узлы выполнены с возможностью передачи/приема сформированного сообщения посредством приемопередатчика.
Предполагается, что основной областью применения схемы распределения ключей, изложенной в настоящей патентной заявке, являются беспроводные mesh-сети (см. I.F. Akyildiz, X. Wang, W. Wang. Wireless mesh networks: a survey. http://www.sciencedirect.com/ [4]). Каждый узел в mesh-сети функционирует как маршрутизатор и способен адресно ретранслировать входящие пакеты в ситуации, когда узел-отправитель и узел-получатель не являются ближайшими соседями и, как следствие, не могут установить прямого соединения. Таким образом, отправитель и получатель связываются через цепочку промежуточных узлов. Для обозначения такого способа взаимодействия в англоязычной литературе используется термин «multi-hop connection». Соответственно термин «single-hop connection» используется для обозначения способа взаимодействия соседних узлов, когда прямое соединение возможно.
Как правило, топология mesh-сети изначально не задана и определяется в момент ее развертывания. Более того, топология может меняться с течением времени - особенно в тех случаях, когда узлы обладают мобильностью. Mesh-сети можно отнести к категории самоорганизующихся сетей. Идеологически mesh-сети близки ad hoc-сетям. Принципиальное отличие - существование внутри mesh-сети специальной управляющей инфраструктуры, состоящей из узлов с расширенной функциональностью (например, оснащенных несколькими беспроводными интерфейсами и дополнительной памятью для хранения данных).
Разбиение на кластеры - распространенный на практике способ организации современных сетей связи. В ряде случаев кластерный подход обусловлен привязкой отдельных сегментов сети к различным стационарным объектам, - например помещениям и зданиям. Принцип кластеризации хорошо согласуется с моделями использования mesh-сетей, детально описанных в документах стандарта IEEE 802.11s (см. Residential and Office usage models, IEEE P802.11-04/662r16, Jan 2005 [5]). Например, mesh-сеть может быть развернута на различных этажах здания, в котором располагается корпоративный офис. Виртуальная кластеризация также возможна. Выделенным сегментам сети могут быть сопоставлены виртуальные кластеры. Однако узлы из различных кластеров должны обладать возможностью установления защищенного режима взаимодействия аналогично тому, как если бы они находились в одном кластере.
Упомянутые выше модели использования mesh-сетей предполагают наличие периметра безопасности. Например, кластер корпоративной сети может быть развернут в офисном помещении на отдельном этаже. Помещение располагает несколькими входами и выходами, каждый из которых оснащен системой контроля доступа.
Кластерный подход позволяет повысить сетевую безопасность и снизить объем инвестиций в оборудование периметра безопасности. Затраты на оборудование нескольких ограниченных периметров безопасности для отдельных кластеров могут быть значительно ниже, чем затраты на оборудование общесетевого периметра безопасности.
Атака может развиваться по следующему сценарию. Вначале злоумышленник проникает внутрь периметра безопасности. Затем захватывает узел mesh-сети и покидает периметр безопасности тем же самым или иным путем. Основная цель злоумышленника - получить доступ к долговременным секретным ключам, которые хранятся в локальной памяти узла. Однако злоумышленник не способен достичь цели, находясь внутри периметра, - как правило, конструкция узла не позволяет выполнить копирование ключей за короткий промежуток времени. Таким образом, для снижения риска обнаружения, злоумышленник должен обеспечить оперативное внедрение, захват и выход за пределы периметра безопасности. Представим себе сеть, в которой для компрометации парного секретного ключа узлов, расположенных в двух различных кластерах, необходимо выполнить захват некоторого количества произвольных узлов из этих кластеров. Причем захват узлов из одного какого-то кластера не позволяет скомпрометировать ключ. Очевидно, что сеть с такими свойствами обладает повышенной сетевой безопасностью, так как для компрометации ключа необходимо осуществить проникновение внутрь периметров каждого из кластеров.
При кластерном подходе полезно различать внутрикластерное и межкластерное взаимодействие узлов. При внутрикластерном взаимодействии два узла из одного кластера устанавливают защищенный режим взаимодействия. При межкластерном взаимодействии отправитель и получатель находятся в различных, не обязательно смежных, кластерах. Соединение типа multi-hop возможно как при межкластерном, так и внутрикластерном взаимодействиях.
Рассмотрим возможные атаки. Далее под «компрометацией» будем понимать захват узла злоумышленником с последующим извлечением долговременных секретных ключей из его локальной памяти.
Под гарантированной защищенностью понимается следующее: раскрытие долговременных секретных ключей, которые хранятся в локальной памяти узла, не позволяет раскрыть парный секретный ключ отправителя и получателя. Гарантированная защищенность обеспечивается, если число скомпрометированных узлов не превышает некоторого порогового значения (порога компрометации), которое определяется параметрами действующей схемы.
1. Внутрикластерное взаимодействие. Цель атаки - компрометация парного секретного ключа отправителя и получателя из одного кластера S.
Возможные атаки:
- Скомпрометировать один или более узлов НЕПОСРЕДСТВЕННО из кластера S.
- Скомпрометировать один или более узлов из кластера ОТЛИЧНОГО от S.
- Скомпрометировать две группы узлов: первая группа принадлежит НЕПОСРЕДСТВЕННО кластеру S, а вторая принадлежит другому кластеру, ОТЛИЧНОМУ от S.
2. Межкластерное взаимодействие. Цель атаки - компрометация парного секретного ключа отправителя и получателя из различных кластеров S and T.
Возможные атаки:
- Скомпрометировать один или более узлов НЕПОСРЕДСТВЕННО из кластера S или/и T.
- Скомпрометировать один или более узлов из кластера ОТЛИЧНОГО от S или/и Т.
- Скомпрометировать две группы узлов: первая группа принадлежит НЕПОСРЕДСТВЕННО кластерам S или/и Т, а другая принадлежит другим кластерам, ОТЛИЧНЫМ от S или/и Т.
Заявляемое изобретение опирается на специальный «гнездовой» принцип. Согласно этому принципу схема предварительного распределения ключей строится на основе другой базовой схемы, которая «вкладывается» в специальную конструкцию. В заявленном изобретении в качестве базовой схемы предварительного распределения ключей выбрана схема KEDYS, описанная в патентной заявке РФ №2004103558 «Система распределения ключей и способ ее функционирования» [6], а также идеи, изложенные в выложенной патентной заявке США №20050177751 «Light-weight key distribution scheme in wireless network» [7]. Выбор данной схемы существенен, так как ее уникальные свойства позволяют эффективно реализовать распределенный метод управления ключами (см., например, способ, описанный автором ранее в патентной заявке РФ №2006114900 [8]). Объектом заявки [8] является способ распределенного управления ключами на основе схемы предварительного распределения ключей, включающий в себя следующие операции:
- формируют внешним центром регистрации уникальный идентификатор узла mesh-сети;
- записывают внешним центром регистрации уникальный идентификатор в локальную память узла mesh-сети;
- формируют доверенным центром матрицу инцидентности схемы KEDYS;
- формируют доверенным центром матрицу инцидентности тривиальной схемы;
- генерируют доверенным центром долговременные секретные ключи;
- записывают доверенным центром сформированный ключевой блок схемы KEDYS и соответствующий столбец матрицы инцидентности в локальную память узла mesh-сети;
- записывают доверенным центром сформированный ключевой блок схемы KEDYS и соответствующий столбец матрицы инцидентности в локальную память управляющего узла распределенного центра управления ключами;
- записывают доверенным центром сформированный ключевой блок тривиальной схемы и широковещательный ключ в локальную память управляющего узла распределенного центра управления ключами;
- генерируют доверенным центром стартовое значение хэш-цепочки;
- вычисляют доверенным центром финальное значение хэш-цепочки;
- записывают доверенным центром аутентификатор в локальную память узла mesh-сети;
- записывают доверенным центром стартовое значение хэш-цепочки в локальную память управляющего узла распределенного центра управления ключами;
- сверяют управляющим узлом распределенного центра управления ключами идентификатор отключаемого узла по базе данных и принимают решение об отключении;
- заносят управляющим узлом распределенного центра управления ключами идентификатор отключаемого узла в базу данных;
- генерируют управляющим узлом распределенного центра управления ключами сеансовый ключ;
- вычисляют управляющим узлом распределенного центра управления ключами матрицу инцидентности схемы KEDYS;
- вычисляют управляющим узлом распределенного центра управления ключами покрытие;
- шифруют управляющим узлом распределенного центра управления ключами сеансовый ключ на парных ключах тривиальной схемы или широковещательном ключе;
- рассылают управляющим узлом распределенного центра управления ключами шифротексты, которые есть суть сеансовый ключ, зашифрованный на парных ключах тривиальной схемы или широковещательном ключе;
- принимают управляющим узлом распределенного центра управления ключами шифротексты, которые есть суть сеансовый ключ, зашифрованный на долговременных ключах из покрытия;
- шифруют управляющим узлом распределенного центра управления ключами сеансовый ключ на ключах из покрытия, которые входят в его ключевой блок;
- формируют управляющим узлом распределенного центра управления ключами широковещательное сообщение для обновления ключевых блоков;
- рассылают управляющим узлом распределенного центра управления ключами широковещательное сообщение для обновления ключевых блоков;
- принимают узлом mesh-сети широковещательное сообщение от управляющего узла распределенного центра управления ключами;
- проверяют узлом mesh-сети подлинность широковещательного сообщения;
- дешифруют узлом mesh-сети широковещательное сообщение с целью получения сеансового ключа;
- обновляют узлом mesh-сети ключевой блок при помощи сеансового ключа;
- вычисляют узлом-отправителем столбец матрицы инцидентности узла-получателя по его идентификатору;
- формируют узлом-отправителем общий секретный ключ на основе столбца матрицы инцидентности узла-получателя и ключевого блока узла-отправителя;
- шифруют узлом-отправителем полезную информацию на общем секретном ключе;
- формируют узлом-отправителем сообщение на основе полученного шифротекста;
- отправляют узлом-отправителем сформированное сообщение по адресу узла-получателя;
- принимают узлом-получателем сформированное сообщение;
- вычисляют узлом-получателем столбец матрицы инцидентности узла-отправителя по его идентификатору;
- формируют узлом-получателем общий секретный ключ на основе столбца матрицы инцидентности узла-отправителя и ключевого блока узла-получателя;
- дешифруют узлом-получателем шифротекст из сообщения на общем секретном ключе.
Основные преимущества схемы KEDYS заключаются в следующем.
- Схема легко масштабируется и применима в mesh-сетях с произвольным числом узлов.
- Вычислительная трудоемкость построения схемы для сети с заданным числом узлов пропорциональна размеру сети. В ходе построения используются операции двоичной логики, а также арифметические операции над целыми числами ограниченной разрядности.
- Метод построения схемы детерминированный, т.е. время построения зависит только от числа узлов в mesh-сети и трудоемкости самого метода.
- Схема относится к классу субоптимальных - общее число долговременных ключей (далее ключевой пул), а также число ключей, которое хранится в локальной памяти отдельного узла (далее ключевой блок), значительно меньше, чем для других известных схем.
- Вычисление парного ключа осуществляется отправителем и получателем автономно и не требует исполнения специального протокола.
- Схема допускает обновление ключей. Необходимость в обновлении ключей возникает каждый раз, когда какие-то узлы mesh-сети скомпрометированы. Обновление возможно благодаря существованию так называемых покрытий. Покрытие - некоторое подмножество ключей, входящих в ключевые блоки всех узлов за исключением скомпрометированных. Покрытие имеет малый размер. Процедура поиска покрытия имеет невысокую вычислительную трудоемкость.
- Схема допускает распределенное управление ключами. Уникальное свойство схемы заключается в возможности выбора ключевых блоков для центра управления таким образом, что они способны образовывать коалиции с целью поиска покрытия. Конструктивный метод приемлемой трудоемкости позволяет построить распределенный центр управления ключами для заданного числа узлов с возможностью их объединения в коалиции определенной мощности.
Однако необходимо подчеркнуть, что вместо схемы KEDYS может быть выбрана любая другая схема предварительного распределения ключей с аналогичными свойствами.
Для полноты изложения необходимо предоставить некоторые дополнительные разъяснения относительно схем предварительного распределения ключей (СПРК) (см. A. Chmora and A. Ourivski, "Lightweight Key Pre-distribution Scheme for Sensor Networks", Tech. Rep., SAIT Communication&Network Lab, Security Team S/W SG CTL SRC, 15 Jan, 2004. [9]).
В СПРК доверенный центр распределяет секретную информацию (ключевой материал) среди совокупности узлов U={1, ..., N}. Порция информации ui передается узлу i по секретному каналу, например, во время создания сети. Переданный ключевой материал позволяет устанавливать общий секретный ключ для пары узлов (осуществление такой операции описано, например, в публикациях R. Blom. An Optimal Class of Symmetric Key Generation Systems. - In: Advances in Cryptology - EUROCRYPT'84, LNCS 209, 1985, 335-338. [10]; С.J. Mitchell, F.C. Piper - Key Storage in Secure Networks. Discrete Applied Mathematics, vol. 21(3), 1988, 215-228. [11]; L. Gong, D.J. Wheeler. A Matrix Key Distribution Scheme. - Journal of Cryptology, vol. 2(2), 1990, 51-59. [12]; M. Dyer, T. Fenner, A. Frieze, and A. Thomason - On Key Storage in Secure Networks. - Journal of Cryptology, vol.8(4), 1995, 189-199. [13]; С. Blundo, A. De Santis, A. Herzberg, S. Kutten, U. Vaccaro and M. Yung - Perfectly Secure Key Distribution for Dynamic Conferences. - In: Advances in Cryptology - CRYPTO'92, LNCS 740, 1993, 471-486. [14]; К. А. S. Quinn - Bounds for Key Distribution Patterns. - Journal of Cryptology, vol.12 (4), 1999, 227-240. [15]). Применение схем предварительного распределения ключей в ad hoc-сетях, а также сенсорных сетях, подробно обсуждается, например, в работах D. R. Stinson - On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption. - Designs, Codes and Cryptography, vol. 12(3), 1997, 215-243. [16]; L. Eschenauer, V.Gligor - A Key Management Scheme for Distributed Sensor Networks. - Proceedings of the 9-th ACM conference CCS2002, 2002, 41-47. [17]; J. Lee, D. Stinson - On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks using Combinatorial Designs. - Technical rep. CACR 2005-40, Centre for Applied Cryptographic Research, University of Waterloo, 2005. [18].
После распределения ключевого материала доверенный центр прекращает свою работу.
Существует две простейшие СПРК.
В первой схеме [10] доверенный центр выдает каждому узлу один и тот же ключ k. Поэтому фактически существует единственная разрешенная группа - вся сеть, которая включает в себя все попарные сочетания узлов, и общим ключом для каждой группы является k.
Эта схема имеет очевидный недостаток: компрометация хотя бы одного узла компрометирует всю сеть.
Во второй схеме (тривиальная СПРК) [10] у каждой пары узлов имеется свой уникальный ключ. Для сети из N узлов доверенный центр должен сгенерировать и распределить N(N-1)/2:N2/2 различных ключей - по одному для каждой пары. При этом каждый узел получит N-1 ключей. С ростом N объем данных, которые необходимо хранить в каждом узле, возрастает и, начиная с некоторого значения N, становится чрезмерно большим, что требует значительного объема памяти для хранения этих данных. С другой стороны, такая схема позволяет достичь максимального уровня защищенности: для компрометации всей сети необходимо захватить (скомпрометировать) не менее N-2 ключей.
СПРК, которые могут быть использованы в практических приложениях, расположены между двумя описанными схемами: ослабляя требования защищенности, зачастую удается снизить требования к объему памяти.
Дадим общее описание конструкции на основе «гнездового» принципа. Основная задача заключается в обеспечении гарантированной защищенности отдельного кластера, когда скомпрометированы узлы из других кластеров.
Для удобства изложения обозначим все узлы, входящие в кластер, как суперузел. Для простоты предположим, что защищенное взаимодействие между узлами одного кластера обеспечивается за счет единого секретного ключа, которым располагают все узлы этого кластера (очевидно, что защищенность кластера и отдельного узла эквивалентны и компрометация узла означает компрометацию кластера; далее будет показано, как заменить такую схему схемой с высоким порогом компрометации).
Соответственно защищенное взаимодействие суперузлов также возможно при наличии парного секретного ключа у отправителя и получателя.
Любая СПРК - это план распределения ключей между узлами. Двоичная матрица инцидентности - удобный способ представления такого плана. Каждая строка матрицы ассоциирована с долговременным секретным ключом, а каждый столбец- с узлом. Если на пересечении i-й строки и 7-го столбца расположена двоичная единица, то i-й ключ входит в ключевой блок j-го узла. Это означает, что каждый столбец матрицы инцидентности задает план формирования ключевого блока отдельного узла. Число ключей в ключевом пуле равно числу строк матрицы инцидентности. Тогда матрица инцидентности для суперузла выглядит как матрица инцидентности тривиальной СПРК, кроме этого каждый супер узел имеет свой собственный секретный ключ (для внутрикластерного взаимодействия).
Рассмотрим пример для пяти кластеров. Матрица инцидентности выглядит следующим образом.
Очевидно, что матрица F состоит из двух матриц - единичной матрицы наверху и матрицы тривиальной СПРК внизу. Таким образом, единичная матрица задает план распределения ключей для внутрикластерного взаимодействия, а матрица тривиальной СПРК - для межкластерного взаимодействия. Взаимодействие двух суперузлов означает, что обычный узел из первого суперузла, выступающий в роли отправителя, взаимодействует с обычным узлом из второго суперузла, выступающего в роли получателя. Назовем матрицу F несущей.
Напомним, что матрица инцидентности тривиальной СПРК имеет строго по две единицы в каждой строке - так как каждая пара узлов располагает уникальным секретным ключом.
Поскольку каждый суперузел - это множество узлов, то матрицу инцидентности для суперузлов не сложно представить в виде развернутой инцидентной структуры, в которой каждая двоичная единица заменена отдельной матрицей инцидентности меньшей размерности. Назовем такие матрицы вложенными. Число столбцов вложенной матрицы равно числу узлов соответствующего кластера, а число строк определяется размером ключевого пула соответствующей СПРК.
Тогда матрица F из (1) представима в следующем виде.
В результирующей матрице G матрица СS - это вложенная матрица инцидентности СПРК для S-го кластера. Матрицы 
и 
есть соответственно левая и правая части матрицы 
Причем DST - это вложенная матрица инцидентности СПРК, которая обеспечивает взаимодействие узлов из кластеров S и Т. Матрицы 0 - вложенные нулевые матрицы подходящей размерности.
«Гнездовой» принцип позволяет строить схемы для произвольного количества кластеров без ограничения на число узлов в отдельном кластере. При этом различные кластеры не обязательно должны быть равномощными (иметь одинаковое число узлов).
Оценим защищенность схемы, построенной по «гнездовому» принципу. Защищенность межкластерного и внутрикластерного взаимодействия зависит от того, каким СПРК соответствуют матрицы СS. и DST. Если СS - это матрица инцидентности kS - устойчивой (с порогом компрометации kS) СПРК, то обеспечивается гарантированная защищенность взаимодействия узлов внутри S-го кластера при условии, что в данном кластере скомпрометировано не более kS узлов. Кроме этого, допускается компрометация произвольного числа узлов в других кластерах. Аналогично, если DST - это матрица инцидентности wST - устойчивой СПРК, то обеспечивается гарантированная защищенность взаимодействия узлов из кластеров S и Т при условии, что в этих двух кластерах суммарно скомпрометировано не более wST узлов. Допускается также компрометация произвольного числа узлов в других кластерах.
Защищенность при компрометации узлов за пределами отдельного кластера или пары кластеров обеспечивается структурой матрицы (1). Тогда как защищенность внутри кластеров обеспечивается структурой матриц СS и DST.
Оценим объем памяти, который необходим для хранения ключевого блока и пула. Предположим, что имеется С кластеров размера ni, i=1,...,С. В кластере S развертывается kS - устойчивая СПРК с ключевым блоком из bS ключей и ключевым пулом из νS ключей. Для пары кластеров S и T развертывается wST - устойчивая СПРК с ключевым блоком из bST ключей и ключевым пулом из νST ключей. Заметим, что bST=bTS и νST=νTS.
Тогда ключевой блок узла из кластера S содержит
ключей.
Ключевой пул кластера, или общее количество различных ключей, входящих в ключевые блоки узлов кластера S, содержит
ключей.
Ключевой пул сети, или общее количество различных ключей в схеме, содержит 
ключей.
СПРК с хорошей защищенностью и приемлемым объемом памяти для хранения ключей можно построить, если воспользоваться схемой KEDYS. Иначе говоря, в конструкцию, построенную по «гнездовому» принципу, вкладывается схема KEDYS.
Такая конструкция получила название EKSYD, от Extended Key Distribution Scheme. Название произносится как "[ик'си:д]", аналогичным образом произносится английское слово "exceed".
Очевидно, что EKSYD превосходит (exceed) KEDYS по защищенности, однако расплата - рост числа ключей в ключевом блоке и пуле. Оценим этот рост. Предположим, что задана сеть из N узлов. Тогда ключевой пул схемы KEDYS содержит
ключей,
а ключевой блок - B(N)=V(N)/2 ключей.
Для простоты предположим, что сеть разбита на С кластеров и все кластеры равномощны. Защищенность в пределах одного кластера обеспечивается схемой KEDYS. Кроме этого, защищенность при межкластерном взаимодействии также обеспечивается соответствующей схемой KEDYS. Тогда ключевой блок содержит
ключей, ключевой пул кластера - VS=2BS ключей, а ключевой пул сети
ключей. Из приведенных выше формул следует, что размер ключевого блока возрастает линейно с ростом числа кластеров, тогда как размер ключевого пула сети возрастает квадратично, как в тривиальной схеме.
На Фиг.1 отражено изменение роста числа ключей в ключевом блоке с ростом числа кластеров (по оси X) для сети из N=65536 узлов.
Анализ размера ключевого блока показывает, что в схеме EKSYD с С кластерами по N/C узлов в каждом, размер ключевого блока приблизительно в С/2 раз больше, чем в схеме KEDYS для сети из N узлов. В схеме EKSYD ключевой пул сети приблизительно в С раз больше, чем ключевой блок. Однако размер ключевого пула сети важен только в момент формирования и распределения ключевых блоков, он устанавливается однократно на этапе развертывания сети. Размер ключевого пула кластера важнее, так как оказывает влияние на размер управляющей структуры внутри кластера (как следствие применения схемы KEDYS). Но размер ключевого пула кластера в схеме EKSYD в два раза больше, чем размер ключевого блока. Аналогичное соотношение справедливо для схемы KEDYS.
Если исходить из критерия объема памяти для хранения ключей, то для сетей с малым числом узлов, а именно при
схема EKSYD проигрывает тривиальной СПРК.
Необходимо отметить, что при увеличении числа кластеров от С=1 до C=N, можно построить семейство СПРК со схемой KEDYS для С=1 и тривиальной СПРК для C=N. Таким образом, можно утверждать, что схема EKSYD - это обобщение схемы KEDYS. Следуя «гнездовому» принципу, возможно построить схему с произвольными параметрами: от 1-устойчивой схемы с минимальным размером ключевого блока при С=1, до (N-2)-устойчивой схемы с ключевым блоком из N-1 ключей при С=N.
В основу заявленного изобретения поставлена задача повышения сетевой безопасности за счет применения схемы предварительного распределения ключей с гарантированно высоким уровнем защищенности при межкластерном взаимодействии и допустимым уровнем защищенности при внутрикластерном взаимодействии. Кроме этого, гарантированная защищенность обеспечивается всегда, когда компрометируются узлы из кластеров, отличных от тех, к которым относятся отправитель и получатель.
Поставленная задача решена путем создания схемы распределения ключей EKSYD для обслуживания сети с кластерной организацией, при этом схема включает в себя доверенный центр, который содержит исполнительную схему процессора (далее - «процессор») и блок памяти (далее - «память») и функционирует на этапе формирования и распределения ключевых блоков, причем каждый узел сети с кластерной организацией также содержит исполнительную схему процессора (процессор), блок памяти (память) и приемопередатчик, при этом:
- доверенный центр выполнен с возможностью формирования, посредством процессора, несущей матрицы инцидентности заданного размера для построения результирующей матрицы инцидентности;
- доверенный центр выполнен с возможностью формирования, посредством процессора, вложенных матриц инцидентности заданного размера для построения результирующей матрицы инцидентности;
- доверенный центр выполнен с возможностью формирования, посредством процессора, результирующей матрицы инцидентности путем объединения упомянутых несущей и вложенных матриц в соответствии с «гнездовым» принципом;
- доверенный центр выполнен с возможностью формирования ключевого пула сети при помощи генератора псевдослучайных чисел;
- доверенный центр выполнен с возможностью выделения, посредством процессора, ключевого пула каждого кластера из упомянутого ключевого пула сети;
- доверенный центр выполнен с возможностью выделения, посредством процессора, ключевого блока отдельного узла из упомянутого ключевого пула кластера, в который входит этот узел;
- доверенный центр выполнен с возможностью вычисления, посредством процессора и генератора псевдослучайных чисел, уникального идентификатора узла каждого кластера;
- доверенный центр выполнен с возможностью секретной передачи, посредством каналов связи, сформированных ключевых блоков и их идентификаторов узлам каждого кластера, участвующим в межкластерном и внутрикластерном взаимодействии, которое заключается в обмене данными по открытым (т.е. незащищенным) каналам связи, причем каждому узлу передают один ключевой блок и идентификатор;
- узлы выполнены с возможностью вычисления, посредством процессора, столбца результирующей матрицы инцидентности произвольного узла по его идентификатору;
- узлы выполнены с возможностью формирования, посредством процессора, парного секретного ключа на основе упомянутого вычисленного столбца результирующей матрицы инцидентности узла-получателя и собственного ключевого блока;
- узлы выполнены с возможностью шифрования/дешифрования, а также проверки подлинности и целостности полезной информации при помощи упомянутого парного секретного ключа посредством процессора;
- узлы выполнены с возможностью передачи/приема сформированного сообщения посредством приемопередатчика.
Таким образом, доверенный центр отвечает за формирование и распределение ключевых блоков на этапе развертывания сети. Взаимодействие узлов осуществляется без участия доверенного центра.
Предварительно выполняют:
- анализ защищенности внутрикластерного и межкластерного взаимодействия при разбиении сети на кластеры и выбор оптимального порога компрометации для каждого из кластеров;
- выбор параметров схемы EKSYD с учетом количества узлов в сети, количества кластеров, мощности каждого кластера, заданного порога компрометации для каждого кластера, а также наличия управляющей структуры внутри кластера;
- оценку объема локальной памяти узла для хранения ключевого блока, объема памяти доверенного центра для хранения ключевого пула сети.
Для функционирования схемы EKSYD необходимо, чтобы доверенный центр был выполнен с возможностью создания результирующей матрицы инцидентности.
Для функционирования схемы EKSYD существенно, чтобы доверенный центр был выполнен с возможностью создания несущей матрицы заданного размера.
Для функционирования схемы EKSYD существенно, чтобы доверенный центр был выполнен с возможностью создания вложенных матриц заданного размера.
Для функционирования схемы EKSYD существенно, чтобы доверенный центр был выполнен с возможностью секретной передачи ключевых блоков узлам каждого кластера на этапе развертывания сети.
Для функционирования схемы EKSYD существенно, чтобы узлы были выполнены с возможностью формирования парного секретного ключа на основе вычисленного столбца результирующей матрицы инцидентности узла-получателя и собственного ключевого блока узла-отправителя.
Поставленная задача решена также путем создания способа функционирования схемы EKSYD, состоящего из следующих операций:
- формируют, посредством процессора доверенного центра, несущую матрицу инцидентности заданного размера;
- формируют, посредством процессора доверенного центра, вложенные матрицы инцидентности заданного размера;
- формируют, посредством процессора доверенного центра, результирующую матрицу инцидентности схемы EKSYD путем объединения упомянутых несущей и вложенных матриц в соответствии с «гнездовым» принципом;
- формируют, посредством генератора псевдослучайных чисел доверенного центра, ключевой пул сети;
- выделяют, посредством процессора доверенного центра, ключевой пул каждого кластера из упомянутого ключевого пула сети;
- выделяют, посредством процессора доверенного центра, ключевой блок отдельного узла из упомянутого ключевого пула кластера, в который входит этот узел;
- вычисляют, посредством процессора и генератора псевдослучайных чисел доверенного центра, уникальный идентификатор узла для каждого кластера;
- секретно передают, посредством каналов связи доверенного центра, упомянутые ключевые блоки и их идентификаторы узлам каждого кластера;
- вычисляют, посредством процессора узла, столбец результирующей матрицы инцидентности произвольного узла по его идентификатору;
- формируют, посредством процессора узла, парный секретный ключ на основе упомянутого вычисленного столбца результирующей матрицы инцидентности узла-получателя и ключевого блока узла-отправителя;
- шифруют/дешифруют, а также проверяют подлинность и целостность полезной информации на упомянутом парном секретном ключе, посредством процессора узла;
- передают/принимают сформированное сообщение посредством приемопередатчика узла.
Для реализации способа функционирования схемы EKSYD важно, чтобы несущая матрица для сети из N узлов и С кластеров формировалась процессором доверенного центра, следующим образом:
- формируют, посредством процессора доверенного центра, единичную матрицу, у которой число строк и столбцов равно числу кластеров С;
- формируют, посредством процессора доверенного центра, матрицу инцидентности тривиальной СПРК, у которой число столбцов равно числу кластеров С, а число строк равно 
и в каждой строке имеется ровно по две двоичных единицы, а каждом столбце ровно по (N-1) двоичных единиц;
- формируют, посредством процессора доверенного центра, несущую матрицу путем объединения упомянутых единичной матрицы и матрицы инцидентности тривиальной СПРК.
Для реализации способа функционирования схемы EKSYD существенно, чтобы вложенные матрицы заданного размера формировались процессором доверенного центра в соответствии с конструкцией схемы KEDYS.
Для реализации способа функционирования схемы EKSYD существенно, чтобы номер столбца был ассоциирован с уникальным идентификатором узла на этапе развертывания сети.
Для функционирования схемы EKSYD существенно, чтобы парный секретный ключ формировался процессором узла следующим образом:
- вычисляют процессором узла пересечение ключевых блоков узла-отправителя и узла-получателя (общие ключи) путем применения операции AND (логическое И) к столбцам результирующей матрицы инцидентности для узла-отправителя и узла-получателя - двоичные единицы на соответствующих позициях столбца-результата указывают на ключи из пересечения;
- вычисляют процессором узла-отправителя парный секретный ключ путем применения однонаправленной хэш-функции к упомянутому набору ключей из пересечения (общих для ключевых блоков узла-отправителя и узла-получателя);
- вычисляют процессором узла-получателя парный секретный ключ путем применения однонаправленной хэш-функции к упомянутому набору ключей из пересечения (общих для ключевых блоков узла-отправителя и узла-получателя).
Для реализации способа функционирования схемы EKSYD существенно, чтобы применение однонаправленной хэш-функции сводилось к следующим операциям:
- осуществляют конкатенацию ключей из пересечения, которые являются общими для двух различных ключевых блоков, принадлежащих соответственно узлу-отправителю и узлу-получателю;
- устанавливают порядок конкатенации (т.е. последовательность расположения ключей), который должен совпадать как у отправителя, так и получателя;
- вычисляют значения однонаправленной хэш-функции от конкатенации этих ключей.
Таким образом, техническим результатом заявленного изобретения является создание схемы EKSYD, которая масштабируется для сети с произвольным числом узлов и кластеров произвольной мощности, не требует большого объема памяти для хранения ключевого блока, гарантирует низкую вычислительную трудоемкость, как при построении результирующей матрицы инцидентности, так и при вычислении парного ключа в ходе взаимодействия узлов, обеспечивает гарантированную защищенность при межкластерном взаимодействии и допустимый уровень защищенности при внутрикластерном взаимодействии. Кроме этого, гарантированная защищенность обеспечивается всегда, когда компрометируются узлы из кластеров отличных от тех, к которым относятся отправитель и получатель.
Для обеспечения более глубокого понимания функционирования схемы EKSYD далее приводится подробное описание ее работы и чертежи.
Фиг.1 - график изменения роста числа ключей в ключевом блоке с ростом числа кластеров для сети из N=65536 узлов (по схеме EKSYD и KEDYS).
Фиг.2 - график зависимости роста числа ключей в ключевом блоке (в тыс.) с ростом числа кластеров для сети из N=65536 узлов (по схеме EKSYD и по тривиальной СПРК).
Фиг.3 - блок-схема СПРК EKSYD согласно изобретению.
Фиг.4 - схема последовательных операций для способа формирования СПРК EKSYD согласно изобретению.
Фиг.5 - схема последовательных операций для способа взаимодействия узлов в СПРК EKSYD согласно изобретению.
Схема EKSYD предназначена для развертывания в сети с кластерной структурой и состоит из доверенного центра 2, каналов 3 связи. При этом доверенный центр 2 содержит процессор 4, память 5 и генератор 6 псевдослучайных (или случайных) чисел, а каждый узел 7 сети содержит процессор 8, память 9 и приемопередатчик 10 (см. Фиг.3).
На этапе развертывания сети (см. Фиг.4) посредством процессора 4 доверенного центра 2 формируют несущую матрицу инцидентности заданного размера (шаг 1), затем посредством процессора 4 доверенного центра 2 формируют вложенные матрицы инцидентности заданного размера (шаг 2), после чего посредством процессора 4 доверенного центра 2 формируют результирующую матрицу инцидентности на основе матриц, полученных на шаге 1 и 2 (шаг 3). Генерируют посредством генератора 6 псевдослучайных чисел доверенного центра 2 ключевой пул сети (шаг 4). Выделяют посредством процессора 4 доверенного центра 2 ключевой пул каждого кластера из ключевого пула сети (шаг 5). Выделяют посредством процессора 4 доверенного центра 2 ключевой блок отдельного узла из ключевого пула кластера, в который входит этот узел (шаг 6). Вычисляют посредством процессора 4 и генератора 6 псевдослучайных чисел доверенного центра уникальный идентификатор для каждого узла каждого кластера (шаг 7). Секретно передают узлам каждого кластера посредством каналов 3 связи доверенного центра 2 ключевые блоки и идентификаторы (шаг 8).
В ходе межкластерного и внутрикластерного взаимодействия (см. Фиг.5) вычисляют посредством процессора 8 узла 7 столбец результирующей матрицы инцидентности произвольного узла, выбранного в качестве узла-получателя (шаг 1). Формируют посредством процессора 8 узла 7 парный секретный ключ на основе вычисленного на шаге 1 столбца результирующей матрицы инцидентности узла-получателя и ключевого блока узла-отправителя, который хранится в памяти 9 (шаг 2). Шифруют/дешифруют данные, а также проверяют их подлинность и целостность при помощи парного секретного ключа посредством процессора 8 узла 7 (шаг 3). Передают/принимают сформированное сообщение посредством приемопередатчика 10 (шаг 4).
Далее рассмотрим построение заявленной схемы EKSYD на конкретном примере.
Для примера выберем сеть с пятью кластерами и 25 узлами. Будем исходить из предположения, что все кластеры имеют различную мощность. А именно, n1=3, n2=4, n3=5, n4=6, n5=7 и 
узлам.
Запишем матрицу G в явном виде.
В начале формируются матрицы Сi. Воспользовавшись матрицей инцидентности схемы KEDYS для четырех узлов [2] получим матрицы
.
Причем матрица С1 получена из С2 отбрасыванием двух последних столбцов, а затем строк, содержащих только одну единицу или не содержащих ни одной единицы.
Воспользовавшись матрицей инцидентности схемы KEDYS для восьми узлов
построим следующий набор матриц
Причем матрица С3 построена из матрицы С отбрасыванием трех последних столбцов, а затем строк, содержащих только одну единицу, или не содержащих ни одной единицы. Матрицы С4 и С5 построены аналогичным образом.
Построим матрицы DST. Матрица D12 - это первые семь столбцов матрицы С и D13=С. Тогда
Для построения остальных матриц воспользуемся матрицей инцидентности схемы KEDYS для шестнадцати узлов
Матрицы D14 и D23 - это первые девять столбцов D, D15, и D24 - первые десять столбцов D, D25, и D34 - первые одиннадцать столбцов D, и матрица D35 - первые двенадцать столбцов D. В итоге получаем
При взаимодействии узлов из кластеров «четыре» и «пять» используется один и тот же групповой ключ, общий для всех узлов (данное предположение преследует исключительно иллюстративные цели). Тогда
.
Полная матрица инцидентности представлена ниже (6). Используются следующие обозначения •=1 и o=0.
Еще раз подчеркнем, что настоящий пример приведен для иллюстрации «гнездового» принципа построения и свойств схемы EKSYD. Размер ключевого блока изменяется в зависимости от количества узлов в кластере и его защищенности (определяется используемой СПРК). Минимальный размер ключевого блока - тридцать четыре ключа (узлы из кластера «пять»), максимальный ключевой блок состоит из тридцати девяти ключей (узлы из кластера «три»). В тривиальной СПРК с аналогичными параметрами каждый узел располагал бы ключевым блоком из двадцати четырех ключей. Таким образом, справедливо утверждение о том, что для сетей с малым числом узлов, схема EKSYD проигрывает тривиальной СПРК по размеру ключевого блока. Однако ситуация меняется для сетей с большим числом узлов, как это следует из представленного ниже рисунка, на котором отражена зависимость роста числа ключей в ключевом блоке (в тыс.) с ростом числа кластеров (по оси X) для сети из N=65536 узлов (см. Фиг.2).
Хотя указанные выше варианты выполнения изобретения были изложены для целей иллюстраций, специалистам ясно, что возможны разные модификации, добавления и замены, не выходящие из объема и смысла настоящего изобретения, раскрытого в описании, чертежах и формуле изобретения.
Изобретение относится к области сетей передачи данных. Технический результат заключается в повышении сетевой безопасности. Сущность изобретения заключается в том, что схема распределения ключей EKSYD для обслуживания сети с кластерной организацией, включает в себя доверенный центр, который содержит процессор и память, и функционирует на этапе формирования и распределения ключевых блоков, причем каждый узел сети с кластерной организацией также содержит процессор, память и приемопередатчик. Также согласно предлагаемому способу функционирования схемы распределения ключей, состоящему из ряда операций, включающих, в том числе формирование несущей матрицы инцидентности заданного размера, матрицы инцидентности заданного размера, матрицы инцидентности схемы EKSYD, а также формирование ключевого пула сети и ключевого пула каждого кластера. 2 н. и 6 з.п. ф-лы, 5 ил.
доверенный центр выполнен с возможностью формирования посредством процессора несущей матрицы инцидентности заданного размера для построения результирующей матрицы инцидентности;
доверенный центр выполнен с возможностью формирования посредством процессора вложенных матриц инцидентности заданного размера для построения результирующей матрицы инцидентности;
доверенный центр выполнен с возможностью формирования посредством процессора результирующей матрицы инцидентности путем объединения упомянутых несущей и вложенных матриц в соответствии с «гнездовым» принципом;
доверенный центр выполнен с возможностью формирования ключевого пула сети при помощи генератора псевдослучайных чисел;
доверенный центр выполнен с возможностью выделения посредством процессора ключевого пула каждого кластера из упомянутого ключевого пула сети;
доверенный центр выполнен с возможностью выделения посредством процессора ключевого блока отдельного узла из упомянутого ключевого пула кластера, в который входит этот узел;
доверенный центр выполнен с возможностью вычисления посредством процессора и генератора псевдослучайных чисел уникального идентификатора узла каждого кластера;
доверенный центр выполнен с возможностью секретной передачи посредством каналов связи сформированных ключевых блоков и их идентификаторов узлам каждого кластера, участвующим в межкластерном и внутрикластерном взаимодействии, которое заключается в обмене данными по открытым каналам связи, причем каждому узлу передают один ключевой блок и идентификатор;
узлы выполнены с возможностью вычисления посредством процессора столбца результирующей матрицы инцидентности произвольного узла по его идентификатору;
узлы выполнены с возможностью формирования посредством процессора парного секретного ключа на основе упомянутого вычисленного столбца результирующей матрицы инцидентности узла-получателя и собственного ключевого блока;
узлы выполнены с возможностью шифрования/дешифрования, а также проверки подлинности и целостности полезной информации при помощи упомянутого парного секретного ключа посредством процессора;
узлы выполнены с возможностью передачи/приема сформированного сообщения посредством приемопередатчика.
формируют посредством процессора доверенного центра несущую матрицу инцидентности заданного размера;
формируют посредством процессора доверенного центра вложенные матрицы инцидентности заданного размера;
формируют посредством процессора доверенного центра результирующую матрицу инцидентности схемы EKSYD путем объединения упомянутых несущей и вложенных матриц в соответствии с «гнездовым» принципом;
формируют посредством генератора псевдослучайных чисел доверенного центра ключевой пул сети;
выделяют посредством процессора доверенного центра ключевой пул каждого кластера из упомянутого ключевого пула сети;
выделяют посредством процессора доверенного центра ключевой блок отдельного узла из упомянутого ключевого пула кластера, в который входит этот узел;
вычисляют посредством процессора и генератора псевдослучайных чисел доверенного центра уникальный идентификатор узла для каждого кластера;
секретно передают посредством каналов связи доверенного центра упомянутые ключевые блоки и их идентификаторы узлам каждого кластера;
вычисляют посредством процессора узла столбец результирующей матрицы инцидентности произвольного узла по его идентификатору;
формирует посредством процессора узла парный секретный ключ
на основе упомянутого вычисленного столбца результирующей матрицы инцидентности узла-получателя и ключевого блока узла-отправителя;
шифруют/дешифруют, а также проверяют подлинность и целостность полезной информации на упомянутом парном секретном ключе, посредством процессора узла;
передают/принимают сформированное сообщение посредством приемопередатчика узла.
формируют единичную матрицу, у которой число строк и столбцов равно числу кластеров С;
формируют матрицу инцидентности тривиальной СПРК (схемы предварительного распределения ключей), у которой число столбцов равно числу кластеров С, а число строк равно 
и в каждой строке имеется ровно по две двоичных единицы, а каждом столбце ровно по (N-1) двоичных единиц;
формируют несущую матрицу путем объединения упомянутых единичной матрицы и матрицы инцидентности тривиальной СПРК.
вычисляют пересечение ключевых блоков узла-отправителя и узла-получателя (общие ключи) путем применения операции AND (логическое И) к столбцам результирующей матрицы инцидентности для узла-отправителя и узла-получателя - двоичные единицы на соответствующих позициях столбца-результата указывают на ключи из пересечения;
отправитель и получатель вычисляют парный секретный ключ путем применения однонаправленной хэш-функции к упомянутому набору ключей из пересечения, общих для ключевых блоков узла-отправителя и узла-получателя.
выполняют конкатенацию ключей из пересечения, которые являются общими для двух различных ключевых блоков, принадлежащих соответственно узлу-отправителю и узлу-получателю;
устанавливают порядок конкатенации, который должен совпадать как у отправителя, так и получателя;
вычисляют значение однонаправленной хэш-функции от конкатенации этих ключей.
| US 5150411, 22.09.1992 | |||
| RU 2005129254 А, 10.04.2006 | |||
| УСТРОЙСТВО ДЛЯ КОНТРОЛЯ ДОПУСКАЕМОГО ПЕРЕТОКА МОЩНОСТИ | 0 |
|
SU257585A1 |
| US 4200770, 29.04.1980. | |||
