Аппаратно-эффективный алгоритм формирования маркера начала сообщения

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

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

Рассмотрим поток данных, состоящий из бит, полученных или с помощью физического генератора псевдослучайных чисел, или с помощью программного датчика псевдослучайных чисел. Задача состоит в том, чтобы встроить в этот поток маркер сообщения, который будет содержать само сообщение. Схожая задача была рассмотрена в работе [5], но там маркер предваряет сообщение и зависит от него, как хэш-код, что представляется не совсем эффективным, т.к. требует офф-лайн обработки больших объёмов данных.

Рассмотрим последовательность байтов Q ¹,.., Q^N , каждый из которых состоит из K бит, и соответствующий им кортеж бит q ¹,..., q^N . Будем называть объединение этих кортежей мастер-ключом.

Передающая сторона, или Алиса, генерирует кортеж X ¹, … , X^N с условиями:

X^j >  Q* если q^j = 0,                       (1)

X^j <  Q j если q j = 1.

И маркирует н ачало сообщения операцией побитового сложения байтов.

X^j , Q^j :

Z{ = X i © Q i i = 1,.. K .

Получатель сообщения, или Боб, производит аналогичную операцию XOR над байтом Z j и бай- том Q , получая в итоге X . Если некоторая после- довательность битов X ,.., X       удовлетворяет условиям (1), тот Боб делает вывод о том, что с вероятностью 1–2–N эта последовательность байтов маркирует начало сообщения.

Но заметим, что Алиса может специально генерировать некоторые из X j так, что условия (1) для них не будут выполняться. Если число таких «ошибок» будет относительно мало, например, не более четверти, и окаймлено заранее заданным числом не «ошибок», то Боб, проверяя входной поток, может сделать хорошо обоснованный вывод о наличии специально встроенных Алисой символов «ошибки». Боб должен выбрать из двух гипотез: он получает случайный поток данных или поток данных, созданный Алисой. Учитывая, что случайный поток данных, например, созданный с помощью генератора псевдослучайных чисел BBS, хорошо описывается схемой Бернулли, а при увеличении Nхорошо описывается нормальным законом, то выде ление кортежа X ,.., X не представляет большого труда, с учётом, например, того, что доверенное лицо проводит тест на открытый текст для наиболее вероятного фрагмента потока данных.

В этом случае Боб может интерпретировать маркер как битовую строку qj, j = 1,..N, где нулями яв-jj ляются те из q , которые совпадают с q , а единицами – места «ошибок». Длина слова в этом случае будет равна N, а «полезное пространство сообщений» 2N-1, где l сравнимо с N.

Насколько стойкой является предложенная схема шифрования?

Предположим, что аналитик каким-то образом смог выделить несколько кортежей Z^j , j = 1,.., N , s = 1,.., MM >  2, отвечающих маркерам, и ему известно, что в маркерах нет «ошибок».

С учётом независимости блоков аналитик может рассматривать только один блок j и отвечающие ему неизвестные q^j , Q^j , X ^{j 1},.. X ^jM .

В этом случае мы получаем систему линейных уравнений в Z 2 и неравенств в R :

z^j i = x^js i © Q^j i i = 1,.. K , s = 1,.., M

j

( X j - Q^] )( - 1) q >  0

Предполагая, что, например, q s = 0, получим:

( X^]s - Q j ) >  0.

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

Предположим, что мы точно знаем расположение M кортежей Z ^j в потоке данных и тем самым знаем z ji = x j, ® Q ji i = 1,.. K , s = 1,.., M , ] = 1,.., N для каждых j , s . Зафиксируем некоторое j и оценим трудоёмкость определения битов Q ₁ ^j ,..., Q_K^j при неизвестном q .

Оказывается, что в этом случае верна след ующая лемма.

Лемма 1:

В наилучшем для атакующего случае трудоёмкость определения мастер-ключа Q1j,..., QNj и q1,..., qN не меньше, чем CNK2K .

Рассмотрим все возможные значения Q j, которые, возможно, являются битами маркера без ошибок. Очевидно, что их число оценивается величиной 2K. Для каждого такого Q j по известному Z j однозначно определяется X j и проверяется, например, условие (Xj - Q]) > 0. Заметим, что априори нельзя выделить множество таких пробных Q j, для которых всегда б удет выполняться только условие (Xj - Q]) > 0, кроме, конечно, тривиального слу- чая нулевого вектора. Поэтому мы вынуждены проверять условие в 2 -1 случаях.

По результатам проверки Q ^j заносится в одно из множеств A = { q ^j , X ^j - Q ^j >  0 } или B 'Q^r , X^] - Q^] <  0 } .

Выберем из M кортежей другой байт Q j и так же образуем множества A ={q], Xj 1 - Qj > 0}, B = {q] , Xj 1 - Qj < 0}. Предположим, что всё пересечение A ∩ A' состоит только из одного H j , а пе- ресечение B ∩ B' пусто.

В этом случае H ^j будет искомым байтом, а искомый бит q ^j будет определяться однозначно.

Даже в этом простейш ем случае мы вынуждены решить системы два раза, для каждого кортежа и число операций побитового сложения для определения X ^j пропорционально K , т.е. длине байта.

Циклический сдвиг кортежа q1,..., qN и встраивание «ошибок» или сообщения решает эту проблему практически, но лемма по существу остаётся верной. Мы с вероятностью 0,25 «успешно» попадаем в отрезок Голомба [6] длины больше, чем единица. Отметим, что мы рассматриваем идеальный слу- чай, в котором выборка и распределение данных в памяти производится мгновенно.

Из леммы след ует другой практический вывод о том, что гарантированная на сегодняшний день стойкость, равная 2⁸⁰, без учёта операций записи и считывания из памяти, б удет обеспечиваться выбором длины байта K большей или равной 64 .

Также можно сформулировать очевидную лемму о классе сложности, к которому принадлежит задача криптоанализа данного алгоритма.

Лемма 2:

Задача определения мастер-ключа при изв ест-ных кортежах Z j не принадлежит классу NP.

Допустим, что нам известны несколько кортежей Z j и необходимо проверить, что наборы Q1j ,..., QNj и q1,..., qN являются ключом. Покажем, что, даже если все Xj = Zj ® Qi i = 1,..K удовлетворяют (1), это не означает, что Q1j,..., QNj и q1,..., qN мастер-ключ. Допустим, что Z j и Q j на нескольких общих позициях имеют совпадающие нулевые биты. Тогда Q , полученное произвольной расстановкой единиц в этих позициях, так же позволит сгенерировать Xi = Z/ ® q] i = 1,..K , удовлетворяющие неравенствам (1). Единственный выход – это увеличени е числа M в общем случае до величины 2r , где r – это число нулевых бит, стоящих в общих позициях у Z j и Q j . Только в этом случае можно выбрать единственное Q из всех возможных Q . Доказательство завершено.

Заметим, что реализация кодирования информа- 1 N ции, или создание последовательности X ,... X , может быть осуществлена инвертированием бит, например, применением операций И, ИЛИ с битами байта Q и содержимым некоего регистра сдвига с линейной обратной связью. Если, например, q ^j =0, то некоторые нулевые биты Q ^j необходимо инвертировать на единичные (ИЛИ), если же q ^j =1, то наоборот, необходимо инвертировать единичные биты Q ^j (И).

Принимающая сторона может определить набор q ¹,.., q^N , пропуская его через регистр сдвига и тестируя байты на предмет проверки ( X^j - Q^j )( - 1) q >  0, так же с помощью автомата без памяти (конъюнктивную нормальную форму (КНФ)), предложенного в [7].

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

Заключение

Компьютерное моделирование формирования и распознавания маркера показало, что система работоспособна и не возникает гонок автоматов.

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