Методы генерации стеганограмм

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

Пусть имеется файл А, который состоит из символьных строк. Обозначим через р(t, a, A) вероятность того, что символ а находится в строке t файла A, а через р(×, a, A) и p(t, ×, A) — независимые вероятности того, что символ а или строка t, соответственно, существуют в A. Два файла А и B будем считать статистически эквивалентными в пределах e, если |p(t, ×, A) – p(t, ×, B)| < e для всех строк t, длина которых меньше чем n.

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

Функцией имитации n-го порядка будем называть такую функцию f, которая в e-окрестности выполняет статистически эквивалентное преобразование файла А в файл В.

Таким образом, если p(t, A) — вероятность появления некоторой строки t в файле А, то функция f преобразует файл А в файл В так, что для всех строк t длиной меньше n выполняется соотношение |p(t, f(A)) –p(t, B)| < e.

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

Регулярные функции имитации можно смоделировать с помощью схемы кодирования по Хаффману. Известно, что любой язык обладает некоторыми статистическими свойствами. Этот факт используется многими методами сжатия данных. Если на алфавите S задано распределение вероятностей A, то можно воспользоваться схемой кодирования по Хаффману для создания функции сжатия с минимальной избыточностью f_A:S®{0,1}*, где символ * используется в смысле S*=È_i³0{x₁…x_i|x₁,…,x_iÎS}. Такую функцию можно построить на основе функции сжатия Хаффмана: G(x)=f_B(f_A(x)).

Таким образом, секретный файл можно сжать по схеме Хаффмана с распределением A, в результате чего получится файл двоичных строк, которые могут интерпретироваться как результат операции сжатия некоторого файла с распределением B. Этот файл может быть восстановлен с применением инверсной функции сжатия f_B к файлу двоичных строк и использоваться в дальнейшем как стеганограмма. Если функции f_A и f_B являются взаимно однозначными, то и созданная функция имитации будет также взаимно однозначна. Доказано, что построенная таким образом функция подобия оптимальна в том смысле, что если функция сжатия Хаффмана f_A является теоретически оптимальной и файл x состоит из случайных бит, то взаимно однозначная функция f_A(X) имеет наилучшую статистическую эквивалентность к А.

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

Контекстно-свободная грамматика определяется упорядоченной четверткой <V, SÍV, П, SÌV\S>, где V и S — соответственно множества переменных и терминальных символов, П — набор продукций (правил вывода), а S — начальный символ. Продукции подобны правилам подстановки, они преобразуют переменную в строку, состоящую из терминальных или переменных символов. Если с помощью правил вывода из стартового символа можно получить последовательность терминальных символов, то говорят, что последовательность получена грамматикой. Такие грамматики называются контекстно-свободными, т.к. любой символ можно заменить последовательностью символов, не обращая внимания на контекст, в котором он встретился. Если для каждой строки s существует только один путь, по которому s может быть порождена из начального символа, то такая грамматика называется однозначной.

Однозначные грамматики могут использоваться в качестве апарата для стеганографических преобразований. Рассмотрим грамматику

<{S,A,B,C},{A,…,Z, a,…,z},П,S>,

где каждой возможной продукции приписана некоторая вероятность: П={S®_0.5 Alice B, S®_0.3 Bob B, S®_0.1 Eve B, S®_0.1 I A; A®_0.3 am working, A®_0.4 am lazy, A®_0.4 am tired; B®_0.5 is С, B®_0.5 can cook; C®_0.5 reading, C®_0.1 sleeping, C®_0.4 working}.

Пусть П_Vi={p_i,1,…,p_i,n} — набор всех продукций, которые связаны с переменной V_i. Тогда для каждого набора П_i можно создать функцию сжатия Хаффмана f_Пi. На рис. 20.7 показаны возможные деревья для П_S и П_А, из которых может быть легко получена функция сжатия Хаффмана. Например, продукция Eve B будет кодироваться как 110, I am tired — как 11 и т.д.

Для стеганографических задач используется инверсная функция Хаффмана. На этапе сокрытия данных отправитель получает с помощью КСГ некоторую строку, которая считается стеганограммой. Стартуя с начального символа S, самая левая переменная V_i заменяется по соответствующей продукции. Эта продукция определяется в соответствии с секретным сообщением и функцией сжатия Хаффмана для П_Vi следующим образом. В соответствии с очередным битом секретного сообщения происходит просмотр дерева Хаффмана до тех пор, пока не будет достигнут лист в дереве, после чего начальный символ заменяется на значение, которое приписано данному листу. Этот процесс повторяется для всех битов сообщения. Результирующая строка состоит только из терминальных символов.

Рис. 20.7. Функция сжатия Хаффмана для П_S и П_А

Рассмотрим пример. Пусть секретное сообщение будет 11110. Тогда для указанной выше грамматики П на первом шаге просмотр дерева П_S с помощью трех первых битов сообщения достигнет листа I. Таким образом, начальный символ S будет заменен на I A. Затем, просматривая еще раз дерево, с помощью следующий двух секретных битов сообщения произойдет замена очередных символов на am working. В результате, конечная строка будет состоять только из терминальных символов. В итоге стеганограмме 11110 соответствует сообщение I am working.

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

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