Предотвращение атак заражения в сетевом кодировании с несколькими источниками

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:20, 24 декабря 2015.
Предотвращение атак заражения в сетевом кодировании с несколькими источниками
Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA.png
Авторы Shweta Agrawal [@: 1]
Dan Boneh [@: 2]
Xavier Boyen [@: 3]
Опубликован 2010 г.
Перевели Максим Мисюра
Год перевода 2015 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Сетевое кодирование – метод достижения пропускной способности сетей. Ключевая идея метода – позволять роутерам линейно перемешивать пакеты, передающиеся по сети, таким образом, чтобы получатели принимали линейные комбинации пакетов. Системы сетевого кодирования уязвимы для «атак загрязнения», в которых один вредоносный узел отправляет в сеть большое количество плохих пакетов и не даёт получателю корректно декодировать принятое. Криптографическая защита от этой проблемы основана на гомоморфных подписях и МАКах. Эти предложения, однако, не могут обрабатывать смешивание пакетов из нескольких источников, что необходимо для достижения максимального результата сетевого кодирования. В данной работе мы обращаемся к целостности смешения множественных источников. Мы предлагаем модель безопасности и общее техническое устройство.

1. Введение

Сетевое кодирование [1] [2] – это изящная техника, которая заменяет традиционную парадигму сетевых маршрутизаторов «храни и пересылай» на метод, позволяющий трансформировать принятую информацию до повторной передачи. Установлено, что для определённых классов сетей случайное линейное кодирование достаточно для улучшения пропускной способности [3]. К тому же, линейные сетевые коды адаптивней и имеют множество практических применений (в беспроводных и сенсорных сетях) [4]. В связи с этими преимуществами сетевое кодирование стало очень популярным.

С другой стороны, сети, использующие сетевое кодирование, подвержены проблемам, которые не встречаются в традиционных сетях. Особенно важная из них проблема «загрязнения»: если некоторые маршрутизаторы в сети вредоносны и передают неправильные комбинации принимаемых пакетов, тогда эти пакеты смешаются с верными и быстро загрязнят всю сеть. Вдобавок получатель, принявший несколько пакетов, не знает точно, какие из них верные и какие следует декодировать. Действительно, используя даже один неправильный пакет в процессе декодирования, можно декодировать все сообщения неверно. Для детального обсуждения проблемы «загрязнения» мы отправляем читателя к [5] [6] [7]

Чтобы предотвратить поток поврежденных пакетов, желательно использовать «сдерживание от прыжка к прыжку». Это значит, что даже если плохой пакет будет внедрён в сеть, он будет обнаружен и извлечён на следующем прыжке. Таким образом, он будет удалён до соединения с другими пакетами, предотвращая загрязнение от его распространения.

«Сдерживание от прыжка к прыжку» не может быть достигнуто стандартными сигнатурами МАК. Как отмечено в [8], обозначение пакетов сообщения на поможет до тех пор, пока получатели не будут иметь оригинальное сообщение, чтобы проверить сигнатуры. Это не будет работать и при обозначении всего сообщения для работы передачи, потому что это потребует от получателя декодировать экспоненциально много подмножеств принятых пакетов для нахождения декодированного сообщения. Таким образом, требуются новые механизмы целостности.

Предыдущая работа

Безопасность сетевого кодирования была рассмотрена в перспективах как теории информации, так и криптографии. Формально противник моделировался имеющим контроль над ограниченным числом связей в сети. Такие подходы, используемые в кабельных сетях, имеют ограниченное применение в беспроводных сетях. Для детального рассмотрения этих техник смотрите [9][10][11][12]. Криптографические техники также рассматриваются в[13][14][6][5]. Авторы строят цифровые сигнатуры для обозначения линейного подпространства. Если – подпространство, и – его обозначение, то существует алгоритм верификации, принимающий пары для всех , но трудно построить вектор , для которого пары подходят. Альтернативный подход – использование МАК, для целостности линейного подпространства; смотрите [8][15].

Изящные сигнатуры или МАКи [13][14][6][5][8] крайне ограничены: они позволяют маршрутизаторам комбинировать векторы только от одного источника. (Более того, конструкции в [13][14][6] требуют новый публичный ключ для каждого файла, это отражается на эффективности.) Традиционное сетевое кодирование представляет собой совокупность маршрутизаторов, линейно комбинирующих векторы из множественных источников. Эта идея показывает, что сетевое кодирование может улучшить эффективность 802.11 беспроводных сетей [16].

Наш вклад

Наша цель создать механизм сигнатур, обеспечивающий целостность комбинирования роутерами пакетов из многих источников. Это проблема ожидаемо серьёзнее, чем проблема одиночного источника. Во-первых, определение безопасности намного сложнее. Необходимо смоделировать атаки, когда атакующий контролирует роутеры так же хорошо, как и некоторые отправители. Цель атакующего сгенерировать верные сигнатуры для смешиваемых пакетов; после их декодирования получатели поверят в верность сообщения , которое отправитель никогда не посылал.

Более точно, если существуют s отправителей в сети, мы позволяем атакующему контролировать из них. Далее, атакующий может направить атаку на одного подлинного отправителя. Цель атакующего – создать пакет при смешении с верной сигнатурой, который после декодирования будет соответствовать существующей у одного подлинного отправителя.

В секции 3 мы показываем естественное обобщение модели безопасности с одним отправителем, в [5] – что для модели с несколькими отправителями эти результаты не могут быть достигнуты. Мы делаем это путем создания общей атаки на абстрактную модель сетевого кодирования с несколькими источниками. В секции 4 мы представляем модель безопасности, которая включает в себя ограничения модели с множеством источников. Наша модель сохраняет желаемые свойства модели с одним источником, такие как «сдерживание от прыжка к прыжку» создаваемых пакетов, и достигаема.

В секции 5 мы представляем конструкцию, удовлетворяющую нашей модели безопасности. Мы даем общую форму нового примитива, называемого хеш-вектор, содержащий свойства гомоморфного хеширования, необходимые для производства сигнатур безопасности. В полной версии этой статьи [17] мы показываем экземпляр конструкции, основанной на предположении дискретного логарифма. Также мы докажем нижнюю оценку, показывающую, что наша модель располагает относительно неэффективной конструкцией; желаемая схема асимптотически достигает этой нижней границы.

2. Сетевое кодирование

Мы советуем читателю [2] для полного представления о сетевом кодировании. Здесь же мы представим дополнительный обзор; этот раздел описывает операции системы сетевого кодирования и независимо от модели безопасности. Мы моделируем сеть как направленный граф, состоящий из ряда вершин и ряда рёбер . Подразумевается, что граф связный. Вершина, которая только передаёт данные, называется корнем. Мы начнём с базовой модели, в которой один источник будет передавать один файл по сети. Источник преобразует данные из файла в векторов – в -мерное векторное пространство в конечном поле ( фиксированные параметры системы). Мы иногда представляем отдельные векторы как блоки или пакеты. Далее источник преобразует один вектор длины в векторы для того чтобы получить

Дополненные векторы включают в себя данные для передачи по сети. Мы назовем первые вхождений вектора компонентой данных, а последние - компонентой дополнения.

Кодирование происходит следующим образом: промежуточная вершина сети принимает набор векторов , выбирает случайных элементов и передаёт вектор вдоль исходящих рёбер. Ключевое свойство дополнения в том, что его компонента содержит точную линейную комбинацию коэффициентов, используемых для получения . Поэтому мы знаем, что , даже если промежуточная вершина никогда не видела . Это свойство позволяет каждой вершине восстанавливать оригинальный . Если - матрица , в которой -ая строка состоит из компоненты данных , а - матрица , в которой -ая строка состоит из компоненты дополнения , то строки матрицы - исходные векторы . Так как сетевое кодирование состоит из линейных комбинаций векторов, подпространство, полученное при помощи дополнительных векторов файла неизменно для сетевых операций. Поэтому мы можем эквивалентно рассмотреть файл, представленный подпространством, полученным из векторов, включающих его.

Замечание

Мы используем для обозначения размерности пространства данных и для обозначения размерности векторного подпространства, представляющего одиночный файл. Множество файлов в системе обозначается . Для мы будем использовать для обозначения компоненты данных , а - для компоненты дополнения. Когда мы используем векторное пространство в качестве входных или выходных данных алгоритма, мы подразумеваем полный базис .

Мы будем предполагать что векторы дополнения передаются источником как примитивные, то есть не перемешиваются с другими. Их дополнительные компоненты - одиночные векторы. С другой стороны, составные векторы - те, которые являются результатом линейной комбинации примитивных.

2. Множественные источники, множественные файлы.

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

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

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

К примеру, допустим, что вершина принимает два вектора с идентификаторами соответственно. Разделив на данные и компоненты подтверждения, мы запишем . Если , тогда векторы пришли от одного файла, ситуация аналогична таковой с одним источником – дополнительных действий не требуется. Но если нет, тогда векторы принадлежат различным файлам, и мы должны предоставить дополнительное расширение до того, как мы их скомбинируем. В этом случае мы определим и , где обозначает нулевой вектор длины . Таким образом мы вычисляем линейную комбинацию , компоненты данных смешаны, но компоненты дополнения разделены. Теперь мы можем использовать идентификатор для обозначения соответствия дополнения файлу.

В более общем смысле мы определяем алгоритм Слияния, который соединяет список идентификаторов, заключенных в составном векторе и добавляет дополнения векторов. Этот алгоритм применим в условиях множественных источников: он не комбинирует векторы, а подготавливает составные векторы (из разных источников) к смешиванию. Если - составной вектор, мы продолжаем обозначать первые переменных компонентой данных; мы называем остальные компонентой дополнения и делим ее на блоков дополнения длины . (Здесь и далее мы подразумеваем для простоты, что размерность для каждого файла одинакова и известна; перейти к переменной размерности просто.)

Алгоритм 1 (Слияние).

Входные данные: список идентификаторов длины соответственно, без повторяющихся переменных и векторы для .

Выходные данные: векторы и список идентификаторов длины .

  1. Пусть - список элементов , записанных в лексикографическом порядке. Длина .
  2. Для определяем , в котором компонента данных равна таковой в , и для в -ый блок дополнения равен:
    • Если -ый блок элемента является -ым блоком элемента , - -ому блоку .
    • Если -ый блок элемента не является -ым блоком элемента , - нулю.
  3. На выход подается список и векторы .

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

Алгоритм 2 (СлияниеПространства).

Входные данные: список идентификаторов и два векторных пространства и .

Выходные данные: подпространство и идентификатор .

  1. Пусть ненулевые векторы, полученные:
СлияниеСлияние
СлияниеСлияние
  1. Пусть будет идентификатором выходных данных для каждого вызова Слияния в шаге 1.
  2. Выходные данные и .

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

3. Сигнатуры и идентификаторы файлов

Для одиночных источников схема сигнатур сетевого кодирования состоит из трёх алгоритмов: Установка, Обозначение и Подтверждение, которые функционально соответствуют обычным сигнатурным схемам. В данном случае алгоритм Обозначения создает сигнатуры в векторном пространстве, а алгоритм Подтверждения проверяет сигнатуры на соответствие данному вектору. Также Обозначение и Подтверждение принимают в качестве дополнительных входных данных идентификатор , который привязывает сигнатуру к файлу. Проще говоря, состояние является корректным тогда, когда существует сигнатура в векторном пространстве с идентификатором , тогда для всех Подтверждение на выходе будет «разрешено». (Определения находятся в [5], Секции 3.1)

Для нескольких источников нам требуется добавить дополнительный алгоритм Комбинирование, который будет использоваться роутерами для создания сигнатур на векторах, которые являются линейными комбинациями векторов из различных файлов. Комбинирование принимает на вход для , где это векторы, это идентификаторы, – сигнатуры, и – сетевые коэффициенты кодирования. Алгоритм выводит сигнатуру .

Для случая с одним источником Обозначение принимает на вход . Далее вектор делает пару (is, \sigma), в которой файловый идентификатор выбирается однажды, и Обозначение генерирует . В случае нескольких источников отправителям разрешается помечать идентификаторы, давая им возможность ограничивать остальных пользователей в системе. Таким образом Боб может поверить в то, что пользователь Алиса прислал ему пакет, который в действительности не отправлял. В большинстве системах сетевого кодирования, таких как BitTorrent[18] , атаки извне вполне реальны, поэтому такие атаки имеют значительное практическое применение. К счастью, атака может быть отражена, если идентификаторы будут криптографически подтверждаемы. В следующей подсекции мы формализуем эти утверждения. Сперва мы опишем атаки, а затем используем интуицию для создания фреймворка, который сможет отражать их.

3.1. Основная атака

Здесь мы рассмотрим атаку на абстрактную схему сигнатур сетевого кодирования с несколькими источниками, включающими в себя алгоритмы Установки, Обозначения, Комбинирования и Подтверждения, описанные выше. Мы не делаем никаких предположений по поводу этих алгоритмов. Мы покажем, что невозможно достичь пошагового соотношения, если идентификатор выбран отправителем и дан на вход алгоритму Обозначения. Мы создаём основную атаку, в которой средние узлы принимают неверные пакеты в качестве верных. Как было сказано выше, это атака «извне», где один из отправителей мошенник. Такой отправитель может дать двум разным векторным пространствам один идентификатор и отметить оба, используя свой секретный ключ. У узла нет возможности когда-либо обнаружить это, так как оба пакета создаются при помощи двух векторных пространств, каждое из которых верно, но вместе они некорректны и могут привести к некорректному декодированию верного пользовательского сообщения. Мы имеем в виду атаку с размерностью подпространства ; атака просто делает с определенным . В нашей системе честный отправитель Алиса, получатель Боб и нечестный пользователь Маллет.

Честный пользователь Алиса

Алиса желает отправить файл, описанный как одиночный ненулевой вектор. Она задаёт вектор, выбирает идентификатор и использует свой секретный ключ для создания сигнатуры в полученном одномерном подпространстве. Затем она передает пакет

Злоумышленник Маллет

Маллет предает и делает следующее:

  1. Создает пару ключей.
  2. Подбирает два вектора таким образом, чтобы набор был линейно независимым. Пусть - подпространства, построенные на этих векторах.
  3. Выбирает идентификатор и использует ключ для получения сигнатур на этих подпространствах. Создает пакеты и
  4. Запускает алгоритм Слияния для и .
  5. Запускает алгоритм Комбинирование для получения сигнатуры на векторе . Пусть
  6. Отправляет Бобу.

В атаке, описано выше, Маллет мог создать для Алисы секретно используемый идентификатор для двух разных векторных пространств. Обратите внимание, что эта атака является более коварной, чем просто помещение данных с идентификатором. Мы видим, что произвольные идентификаторы файла дают злоумышленнику слишком много власти. Поэтому необходимо, чтобы идентифиаторы криптографически привязывались к файлам, и то проверялось на каждой вершине. На практике алгоритм Обозначение должен давать на выходе оба идентификатора и сигнатуру. Для подтверждения идентификатора мы используем алгоритм ИдТест, который принимает открытый ключ, вектор и список идентификаторов, а выводит разрешение, если вектор в подпространстве идентифицируется. Для того чтобы избежать обеих атак, для Маллета должны быть недостижимы две задачи:

  1. Нахождение верного идентификатора, с которым алгоритм даст разрешение.
  2. Нахождение векторного пространства, публичного ключа, для которых ИдТест выдаст разрешение.

Если Маллет сможет преуспеть в этих задачах, тогда Боб поверит, что вектор принадлежит файлу, посланному Алисой, когда на самом деле это не так.

Эти две задачи довольно близки: это аналоги двух путей взлома сети с одним источником [5]. Этот анализ ведет к нашему ключевому выводу: идентификатор файла, сделанный алгоритмом Обозначение, должен быть сигнатурой в векторном пространстве. Из этого следует, что все свойства системы заключены в идентификаторе, таким образом мы можем сделать часть сигнатуры равной идентификатору. Мы формализуем эти идеи в следующей секции.

Ремарка 3.

Можно показать ,что использование произвольных идентификаторов не только делает пошаговое сравнение невозможным, но еще заставляет принимающего решать проблему корректного декодирования. В частности, существует формальное сокращение проблемы декодирования в сетях с множественными источниками; детали в статье[17].

4. Сигнатуры сетевого кодирования.

Мы формально определяем схему сигнатур сетевого кодирования с несколькими источниками. Алгоритм Обозначения генерирует сигнатуру, используемую, и как идентификатор, и как сигнатура. Алгоритм Подтверждения выполняет функцию алгоритма ИдТест из предыдущего раздела и позволяет каждой вершине проверять идентификатор/подпись входящего пакета. Так как сигнатуры и идентификаторы играют одну и ту же роль, алгоритм Комбинирование обеспечивает ту же функцию, что и алгоритм Слияние. Заметим, что в сравнении с традиционными сигнатурами, алгоритм Подтверждения не принимает на вход оригинальное сообщение (т.е. векторное пространство)

Определение 4.

Схема сигнатур сетевого кодирования с несколькими источниками основана на пяти алгоритмах: Установка, КейГен, Обозначение, Комбинирование и Подтверждение со следующими свойствами:

Установка(): на вход подаются унарное представление параметра безопасности , размерность пространства данных n и размерность подпространства m, на выходе - описание системы параметров params. Описание включает в себя параметр p, используемый для определения поля над векторным пространством.

КейГен(params): на выходе - случайно генерируемая пара ключей .

Обозначение(params, sk, ): на входе секретный ключ sk, и подпространство , на выходе сигнатура .

Комбинирование(params, ): принимает на вход два вектора , два списка сигнатур, два списка открытых ключей и два коэффициента . На выходе - список сигнатур и список открытых ключей .

Подтверждение(params, , v, ): на входе список открытых ключей, вектор и список сигнатур, на выходе - разрешение или запрещение .

Уточнение.

Нам требуется для любых параметров системы придерживаться следующего:

  1. Для простых сигнатур: пусть пара ключей КейГен(params) и векторное пространство . Пусть это выходные данные Обозначение(params, sk, V). Пусть . Тогда для всех нам потребуется чтобы Подтверждение.
  2. Рекурсивно для составных сигнатур: пусть есть два списка открытых ключей, два списка сигнатур, два вектора, такие, что ПодтверждениеПодтверждение.

Пусть - на выходе Слияние. Для любых нам потребуется чтобы, если - выходные данные алгоритма Комбинирование, тогда:

(а) , (б) j-ый элемент является k-ым элементом , тогда j-ый элемент pk является k-ым элементом (в) Подтверждение/

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

4.1. Безопасность

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

Определение 5

Преимущество NC-ADV[A,S] для А это вероятность, с которой А выиграет состязание безопасности. Схема сетевого кодирования с несколькими источниками S является безопасной, если для всех вероятностей и полиномиальном времени преимущество NC-ADV[A,S] является незначительным по параметру безопасности .

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

Предполагаемые свойства

Модель безопасности подразумевает, что даже получив секретный ключ, ни один состязующийся не сможет построить такие векторные пространства , чтобы ОбозначениеОбозначение. Заметим, что это не свойство сопротивления коллизиям. В течение подтверждения сигнатуры, векторное пространство не доступно, поэтому алгоритм Подтверждения должен принять сигнатуру .

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

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

Векторное пространство .Векторное пространство W † {\displaystyle W^{\dagger }} .

Напомним, что конструкция зависит от 4 параметров , где это вектор открытых ключей, содержащий открытый ключ состязания . Другие открытые ключи в векторе получены состязующимся, и поэтому возможно, что состязующийся знает подходящие закрытые ключи.

Вектор и сигнатура существующие данные оппонента. Предположим, что подходит в качестве верной пары вектор-сигнатура в отношении . Нам требуется, чтобы состязующийся передал векторное пространство для доказательства того, что он может использовать для ввода в заблуждение получателя, который принимает вектор от одного честного отправителя. Чтобы одурачить получателя, атакующий может генерировать верные пары вектор-сигнатура для всех базисных векторов из , используя секретный ключ. Так как все такие векторы будут иметь верные сигнатуры, получатель должен будет попробовать декодировать базис с вектором . Если , после декодирования набора векторов (т.е. после извлечения из проекции на ), получатель принимает вектор u, который, как он верит, пришел от честного отправителя, но который тот никогда не отправлял, так как u не присутствует в СлияниеПространств.

Таким образом, атакующий имеет возможность производить конструкции, для которых сохраняется требование (2), затем состязующийся может одурачить получателя, отправив ему последовательность верно обозначенных векторов. Нам следует потребовать, чтобы для схемы сигнатур безопасности было невозможно произвести подходящую конструкцию, где . К сожалению, столь жесткие требования, похоже, недостижимы. Мы можем требовать, чтобы , только в тех случаях, где возможно, чтобы векторы в были совместно декодированы с , то есть Подтверждение для всех базисных векторов . Это позволительная слабость для требований безопасности, так как декодер никогда не соберет вместе векторы с разными идентификаторами. В Секции 5 мы показываем, что этот результат достижим. Отметим, что требования состязующегося выводить аналог модели безопасности составных сигнатур [19],, где атакующий выводит составную сигнатуру из открытых ключей, где из них созданы атакующим. Более того, атакующий должен выводить список из сообщений, чтобы прийти к составной конструкции, для каждого из публичных ключей, им созданных. Наше векторное пространство играет ту же роль, что и сообщений в составной конструкции.

5. Конструкция схемы сигнатур с несколькими источниками

В этой секции мы строим полную схему сигнатур сетевого кодирования с несколькими источниками, достигнутую в Определении 4. Для того чтобы дать общую конструкцию, мы сперва определим вспомогательный вектор, называемый хэш-вектором. Этот примитив имеет свойства гомоморфных хэшей, использованный Кроном в [14], что необходимо для сигнатур безопасности.

5.1 Вектор Хэшей

Хэш-вектор состоит из трех алгоритмов, Установка, Хэш, Тест со следующими свойствами:

Установка(): на вход подаются унарное представление параметра безопасности , размерность пространства данных n, на выходе - открытый параметр pp.

Хэш(pp, v): на входе - открытый параметр pp и вектор , на выходе - хэш h вектора v. Алгоритм должен быть детерменированным.

Тест(pp, y, , h): на входе - открытый параметр pp, вектор , вектор коэффициентов и вектор m хэш значений h, на выходе - логическая единица или логический ноль .

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

Корректность.

Под корректностью мы подразумеваем , что для всех открытых параметров УстановкаХэшей:

  1. Для всех если Хэш, тогда Тест.
  2. Пусть , для некоторых , и пусть h список хэшей длины . Для фиксированных вектор с нулевой точкой между -ым и -ым местами, и - вектор с каким-либо значением хэша между -ым и -ым местами. Требуется, чтобы, если Тест, то Тест.
  3. Пусть , для некоторых , список хэшей длины . Пусть . Требуется, чтобы, если Тест для i = 1,2, то Тест.

Безопасность.

Пусть – хэш-вектор. Пусть – алгоритм, который принимает открытые параметры УстановкаХэшей и выводит вектор , m-размерное векторное пространство представлено базисными векторами , m коэффициентов и вектор хэшей .

Определение 6.

При помощи записи выше мы говорим, что ломает хэш-схему , если , Тест и Тест. (Напомним, что – компонента данных ). Мы считаем, что преимущество ПреимуществоХэш – возможность сломать . Мы скажем, что вектор безопасный, если для всех алгоритмов ПреимуществоХэш ничтожно для параметра безопасности .

В статье [17] мы даем пример хэш-вектора, используя конечную циклическую группу порядка р. Этот хэш-вектор безопасный, если проблемы дискретного логарифмирования недостижимы в .

5.2 Конструкция

Для данной конструкции мы используем черный ящик, как определено в Секции 5.1

Сигнатурная схема :Сигнатурная схема N S {\displaystyle {\mathcal {NS}}}

пусть – хэш-вектор и пусть будет схемой сигнатур для обозначения сообщений в . Наша сеть имеет схему сигнатур кодирования подобного плана: Установка(): на вход подаются унарное представление параметра безопасности , размерность пространства данных n и размерность подпространства m, на выходе - описание системы параметров params. Описание включает в себя параметр p, используемый для определения поля над векторным пространством. КейГен(params): на выходе - случайно генерируемая пара ключей . Обозначение(params, sk, ): на входе секретный ключ sk, и подпространство , на выходе сигнатура . Комбинирование(params, ): принимает на вход два вектора , два списка сигнатур, два списка открытых ключей и два коэффициента . На выходе - список сигнатур и список открытых ключей . Подтверждение(params, , v, ): на входе список открытых ключей, вектор и список сигнатур, на выходе - разрешение или запрещение . Единственное отличие между алгоритмом Комбинирования в нашей схеме и алгоритмом Слияния в Секции 2.1 – Комбинирование сохраняет набор открытых ключей, присвоенных сигнатурам. Вместо отправки раздельных хэшей для каждой сигнатуры, мы можем объединить эти сигнатуры вместе для экономии места. В статье [17] мы описываем систему, в которой сигнатура файлов длины бит. Также мы доказываем нижнюю оценку, показывая, что для больших значений эта длина оптимальна.

Корректность.

Мы подтверждаем корректность условий Определения 4.

  1. Для примитивных сигнатур: пусть пара ключей и векторное пространство описаны базисом. Пусть будет выходными данными Алгоритма Обозначение.

Для примитивных сигнатур существует только один файл. Мы проверяем каждый шах Подтверждения:

    1. Так как Обозначение, мы имеем Подтверждение из-за корректности .
    2. Так как Хэш и – единичный вектор , так как мы использовали базис и состояние корректности (1) и (3) выполняется, то Подтверждение.
  1. Рекурсивно для составных сигнатур: пусть есть два списка открытых ключей, два вектора, два списка сигнатур, для которых: ПодтверждениеПодтверждение

Состояния (а) и (б) немедленно наступили. Для (в) отметим, что в нашей схеме . Пусть . Мы проверяем каждый шаг алгоритма Подтверждения:

  1. Из-за предположения (5.1) у нас есть соответствие между , поэтому Подтверждение для .
  2. Из-за предположения (5.1) мы знаем, что Тест для i = 1,2. Из-за свойства корректности (2) имеем Тест. Затем из-за свойства корректности (3) имеем Тест.

Таким образом, мы имеем Подтверждение. У нас имеется соответствующая теорема безопасности, доказательство в полной статье [17].

Теорема 7.

Схема сигнатур сетевого кодирования безопасна, если – хэш-вектор и безопасная схема сигнатур.

[8]

Контакты авторов материала

  1. University of Texas at Austin, USA E-mail: [shweta.a@gmail.com]
  2. Stanford University, USA E-mail: [fdabo,dfreemang@cs.stanford.edu]
  3. Universit�e de Li�ege, Belgium E-mail: [xb@boyen.org]

Литература

  1. R. Ahlswede, N. Cai, S. Li, and R. Yeung. Network information flow. IEEE Transactions on Information Theory, 46(4):1204-1216, 2000.
  2. 2,0 2,1 2,2 R. Koetter and M. M�edard. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, pages 782-795, 2003.
  3. C. Fragouli and E. Soljanin. Network Coding Fundamentals. Now Publishers Inc.,Hanover, MA, USA, 2007.
  4. C. Fragouli, J.-Y. Le Boudec, and J. Widmer. Network coding: an instant primer. SIGCOMM Comput. Commun. Rev., 36(1):63-68, 2006.
  5. 5,0 5,1 5,2 5,3 5,4 5,5 D. Boneh, D. Freeman, J. Katz, and B. Waters. Signing a linear subspace: Signature schemes for network coding. In Public-Key Cryptography — PKC ’09, volume 5443 of LNCS, pages 68–87. Springer, 2009.
  6. 6,0 6,1 6,2 6,3 F. Zhao, T. Kalker, M. Medard, and K. Han. Signatures for content distribution with network coding. In Proc. Intl. Symp. Info. Theory (ISIT), 2007.
  7. K. Han, T. Ho, R. Koetter, M. Medard, and F. Zhao. On network coding for security. In Military Communications Conference (Milcom), 2007.
  8. 8,0 8,1 8,2 8,3 S. Agrawal and D. Boneh. Homomorphic MACs: MAC-based integrity for network coding. In Proceedings of ACNS ’09, volume 5536 of LNCS. Springer, 2009.
  9. N. Cai and R. Yeung. Secure network coding. Proceedings of the 2002 IEEE International Symposium on Information Theory., 2002.
  10. J. Feldman, T. Malkin, C. Stein, and R. Servedio. On the capacity of secure network coding. Proc. 42nd Annual Allerton Conference on Communication, Control, and, Computing, 2004.
  11. T. Ho, B. Leong, R. Koetter, M. Medard, M. Effros, and D. Karger. Byzantine modification detection in multicast networks using randomized network coding. In Proceedings of the 2004 IEEE International Symposium on Information Theory (ISIT), June 2004.
  12. S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, M. Medard, and M. Effros. Resilient network coding in the presence of Byzantine adversaries. IEEE Trans. on Information Theory, 54(6):2596-2603, 2008.
  13. 13,0 13,1 13,2 D. Charles, K. Jain, and K. Lauter. Signatures for network coding. In 40th Annual Conference on Information Sciences and Systems (CISS ’06), 2006.
  14. 14,0 14,1 14,2 14,3 M. Krohn, M. Freedman, and D. Mazieres. On the-fly verification of rateless erasure codes for efficient content distribution. In Proc. of IEEE Symposium on Security and Privacy, pages 226-240, 2004.
  15. Y. Li, H. Yao, M. Chen, S. Jaggi, and A. Rosen. Ripple authentication for network coding. To appear in IEEE INFOCOM, 2010. Available at http://home.ie.cuhk. edu.hk/~mhchen/papers/ripple.infocom10.pdf.
  16. S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. XORs in the air: practical wireless network coding. IEEE/ACM Trans. Netw., 16(3):497-510, 2008.
  17. 17,0 17,1 17,2 17,3 17,4 S. Agrawal, D. Boneh, X. Boyen, and D. M. Freeman. Preventing pollution attacks in multi-source network coding. Cryptology ePrint Archive, 2010. Full version of this paper, available at http://eprint.iacr.org.
  18. B. Cohen. Incentives build robustness in BitTorrent, 2003. Available at http: //www.bittorrent.org/bittorrentecon.pdf.
  19. D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably en¬crypted signatures from bilinear maps. In Advances in Cryptology — Eurocrypt 2003, volume 2656 of LNCS, pages 416-432. Springer, 2003.