Безопасное сетевое кодирование с помощью целых чисел

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:12, 17 декабря 2015.
Безопасное сетевое кодирование с помощью целых чисел
Авторы Rosario Gennaro[@: 1] and
Jonathan Katz[@: 2] and
Hugo Krawczyk[@: 3] and
Tal Rabin[@: 4]
Опубликован 2011 г.
Сайт IBM T.J. Watson Research Center
Перевели [Lukanin]
Год перевода 2015 г.
Скачать оригинал
Аннотация. Сетевое кодирование представляет возможность увеличить пропускную способность и улучшить устойчивость без какого-либо централизованного управления. К сожалению, сетевое кодирование очень восприимчиво к видам атак, в которых вредоносные узлы изменяют данные неправильно, чтобы помешать декодированию сообщения получателем. Такие виды атак невозможно предотвратить, используя стандартную сквозную аутентификацию, так как сетевое кодирование подразумевает изменение пакетов данных промежуточными узлами. Специальные «ключи сетевого кодирования», использующие гомоморфическое шифрование, были созданы недавно именно для решения этой проблемы. Мы сделали различные вклады в эту область:
  1. Показали первый алгоритм гомоморфического шифрования, основанный на RSA алгоритме.
  2. Мы предложили алгоритм гомоморфического хэширования более эффективный чем существующие и который предлагает ключи шифрования, основанные на устойчивости факторизации.
  3. Мы описали варианты существующих алгоритмов, которые уменьшают коммуникационные расходы для сетей небольших размеров, и улучшают вычислительную эффективность.

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

Введение

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

Конечный узел получает набор векторов, причем дополнительные координаты образуют матрицу полного ранга, которая позволяет восстановить исходный файл. Главный вопрос: какова вероятность расшифровки на узлах-получателях? Тоесть, какова вероятность того, что узел-получатель сможет восстановить исходный файл? В книгах по сетевому кодированию говорится, что небольшие поля, например F28, дают хорошую вероятность расшифровки для достаточно соединенных сетей.

Хотя сетевое кодирование позволяет увеличить пропускную способность и надежность по отношению к другим способам кодирования, она уязвима к видам атак, в которых вредоносные узлы вводят неправильные данные, чтобы помешать восстановлению файла на узлах-получателях (неправильные данные — любые данные, которые не входят в линейную оболочку начальных векторов, созданных узлом-источником). Благодаря тому, как вектора распространяются и объединяются в сети, единственный неправильный пакет данных может сделать недействительными все дальнейшие данные.

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

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

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

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

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

Структура. Часть 2 рассказывает про сетевое кодирование и существующие алгоритмы сетевого кодирования. В части 3 мы обсудим сетевое кодирование над целыми числами и как оно помогает улучшить существующие алгоритмы. Мы покажем наш гомоморфический алгоритм основанный на принципе RSA в части 4 и гомоморфический алгоритм хэширования, основанный на факторизации, в части 5.

Общие понятия

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

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

Сначала источник создает расширенных векторов определенных как:

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

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

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

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

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

Ключи сетевого кодирования

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

Есть два вида данного алгоритма: основанный на гомоморфическом ключе и на гомоморфическом хэшировании. Далее рассмотрим подробно каждый.

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

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

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

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

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

  1. проверит эти ключи
  2. вычислит новые ключи для каждого исходящего вектора

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

Наглядным примером алгоритма гомоморфического ключа является BFKV алгоритм, предложенный Даном Боуни. Алгоритм основан на вычислительной проблеме Диффи-Хеллмана. В начале источник устанавливает открытый ключ следующим образом:

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

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

После получения векторов с правильными ключами промежуточный узел сможет вычислить новый ключ для любой линейной комбинации таким образом:

Сетевое кодирование с помощью целых чисел

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

  1. IBM T.J. Watson Research Center, Hawthorne, NY, E-mail: [{rosario,talr}@us.ibm.com]
  2. Department of Computer Science, University of Maryland, E-mail: [jkatz@cs.umd.edu]
  3. IBM T.J. Watson Research Center, Hawthorne, NY, E-mail: [{rosario,talr}@us.ibm.com]
  4. IBM T.J. Watson Research Center, Hawthorne, NY, E-mail: [{rosario,talr}@us.ibm.com]

== Примечание ==ое сетевое кодирование

Литература