F5 (Стеганографический алгоритм)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 00:15, 18 ноября 2016.


F3 - один из алгоритмов стеганографии для встраивания данных в изображения JPEG.

Разнесенная перестановка

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

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

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

Рис. 1. При последовательном встраивании изменения (они обозначены ) сосредотачиваются в начале файла
Рис. 2. Перестановка распределяет изменения (они обозначены ) по всему файлу

Кодирование матрицы

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

Пусть есть равномерно распределенное сообщение и равномерно распределенные значения на позициях, которые должны быть изменены. Половина сообщения осуществляет изменения, вторая нет. Без использования кодирования матрицы, эффективность встраивания будет равна 2 битам на 1 изменение. Учитывая сокращения, производимые алгоритмом F4, эффективность встраивания даже меньше, т.е. примерно составляет 1.5 бита на 1 изменение.

Например, если мы встраиваем сообщение длиной 217 байт (1736 бит), F4 изменяет 1157 позиций в тестовом изображении. F5 встраивает то же сообщение, используя кодирование матрицы, с 459 изменениями (т.е. с эффективностью встраивания 3.8 бита на изменение).

Следующий пример детально показывает, что происходит. Нам необходимо внедрить 2 бита в три изменяемых позиции , изменяя не более одной позиции. Могут возникнуть следующие 4 случая:

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

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

А коэффициент встраивания

где логарифм по основанию 2.

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

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

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

Измененный код принимает следующий вид

Структура алгоритма F5

В упрощенном виде алгоритм F5 имеет следующую структуру:

  1. Начать сжатие JPEG. Остановиться после квантования коэффициентов.
  2. Инициализировать криптографически стойкий генератор случайных чисел с помощью ключа, полученного из пароля.
  3. Создать перестановку с двумя параметрами – генератор случайных чисел и количество коэффициентов (включая нулевые коэффициенты).
  4. Определить параметр , который зависит от емкости несущей среды, а также от длины секретного сообщения.
  5. Вычислить длину кодового слова .
  6. Вставить секретное сообщение, используя кодирование матрицы.
    1. Заполнить буфер ненулевыми коэффициентами.
    2. Хешировать буфер (сгенерированное значение хеш-функции состоит из бит). (См. формулу )
    3. Добавить следующие битов сообщения к значению хеша (побитно с помощью операции XOR). (См. формулу )
    4. Если сумма равна 0, то буфер остается неизменным. В противном случае, сумма указывает на элемент буфера, абсолютное значение которого нужно уменьшить на единицу. (См. формулу )
    5. При получении нуля проверяется сокращение. Если сокращение имеет место, то настроить буфер (исключить 0, прочитав еще один ненулевой коэффициент, т. е. повторить шаг 6.1, начиная с того же коэффициента). Если сокращения не произошло, осуществляется переход к новым коэффициентам фактического буфера. Если еще есть данные сообщения, перейти к шагу 6.1.
  7. Продолжить сжатие JPEG (кодирование Хаффмана и т.д.).

См. также

Литература

  1. Andreas Westfeld. F5 – A Steganographic Algorithm: High Capacity Despite Better Steganalysis / In Ira S. Moskowitz, editor, Information Hiding, 4th International Workshop, volume 2137 of Lecture Notes in Computer Science, pages 289-302. Springer, 2001.