среда, 12 сентября 2012 г.

Статистическая атака: анализ хи-квадрата

Эта статистическая атака на стегосистему была опубликована в 2000 году немецкой группой исследователей во главе с Андреасом Вестерфелдом. Точное название этой статьи: A. Westfeld and A. Pfitzmann, "Attack on Steganographic Systems", Lectures Notes in Computer Science, vol. 1768, Springer-Verlag, Berlin, 2000, pp. 61-75. Вы можете скачать текст статьи в формате PDF с его сайта .
Следует обратить внимание, что с тех пор были опубликованы более эффективные и надежные атаки на LSB вложения. Например, следует упомянуть нападения RS от лаборатории Джессики Фридрих :J. Fridrich, M. Goljan, R. Du, "Reliable Detection of LSB Steganography in Color and Grayscale Images", 2002.
Итак, почему я выбрана эту атаку несмотря на то, что она не самая на сегодняшний день эффективная? В качестве основного критерия для автора служила простота реализации и понятность математических выкладок. Более того, заниматься математикой на ​​чистом ассемблере, который используется для написания программы не так просто.
Эта программа и ее исходные коды доступны здесь .

 Как это работает?

Так как же это работает этот вид атак на стегосистему? Давайте попробуем объяснить это простыми словами.
Во-первых, давайте определим условия. У нас есть простое изображение. Как и в прошлом примере мы снова используем 24-битный BMP формат. Как уже доказывалось ранее, наименее значащие биты такого обычных изображений вовсе не являются случайными. Если вы посмотрите на Beat Girl не содержащий скрытой информации,из предыдущего примера,  то заметите, что существует большое количество наименее значащих бит установлено в 1 (поскольку фон у изображения белого цвета). Также есть большие блоки с другими значениями младших разрядов, часто черные (так много смежных младших разрядов установлены в 0). Так что, значения младших битов в общем обычно не являются случайными.
Наоборот, сообщение мы собираемся прятать в младших битах изображения случайны, например, зашифрованный текст - его биты принимают случайные значения.
Давайте возьмем простой пример - скрытие случайных сообщений в однотонное изображение, например черного цвета. Перед добавлением скрытого сообщения, все байты области изображения равны 0. Все младшие биты будут тоже равны нулю. После добавления случайного сообщения, распределение младших бит будет стремиться к распределению 50/50: половина младших бит будет 0, а половина будет 1. Назовем парой значений (PoV) значение  младшего бита 1-го байта и значение младшего бита 2-го байта.
Пойдем дальше. Вместо того чтобы рассматривать только LSB одного байта, мы можем анализировать больше байт, и проверять насколько близко распределение пары значений r 50/50. Давайте возьмем пример с 2 последних байта. Есть 4 возможных сочетания младших бит. Так, 2 различные пары значений. В этой паре значения будут отличаться только последний бит:


0 0 
0 1
Первая пара значений.
При наличии случайного сообщения, оба значения должны присутствовать с одинаковой частотой.
  1 0 
1 1
Вторая пара значений.При наличии случайного сообщения, они оба значения должны присутствовать с одинаковой частотой.


Теперь перечислим все PoV для 3 байтов. Всего есть 8 возможных  значений, из них 4 PoV могут указывать на наличие скрытого сообщения


0 0 0
0 0 1
Первая пара значений.
При наличии случайного сообщения, оба значения должны присутствовать с одинаковой частотой.
0 1 0 
0 1 1
Вторая пара значений.
При наличии случайного сообщения, оба значения должны присутствовать с одинаковой частотой.
1 0 0 
1 0 1
Третья пара значений.
При наличии случайного сообщения, оба значения должны присутствовать с одинаковой частотой.
1 1 0 
1 1 1
Четвертая пара значений.
При наличии случайного сообщения, оба значения должны присутствовать с одинаковой частотой.


Для анализа мы фактически будем рассматривать все 8 бит каждого скрытого байта. Таким образом, мы будем иметь 256 возможных значений, и 128 пар значений.
Итак, при помощи каких математических вычислений мы получим эти 128 PoV? Для этого мы должны измерять частоту встречаемости для каждой извлеченной из изображения пары значений. В качестве примера, скажем, что мы найдем, в наборе из 500 последовательностей, 100 значений 0101110 0 и 400 значений 0101110 1 . Сведем в таблицу эти реальные значения.

В то же время, мы вычисляем теоретическую частоту встречаемости этой пары значений, в случае если они представлены случайным образом (т.е. если есть случайные сообщения встроенные в последние LSB). Поскольку они случайны, то их встречаемость должны иметь частоту 50% каждый. Таким образом, для примера, приведенного выше, теоретическая значения встречаемости были бы 250  для значения 0101110 0 и 250 для значения 0101110 1 . Построим вторую таблицу на основе этих теоретических значений.
Затем мы сравним эти две таблицы из 128 PoVs при помощи критерия хи-квадрат. В основном, критерий отвечает на следующий вопрос: эти два набора данных (результаты эксперимента и теоретические) существенно отличаются ? Если они существенно различаются, то распределение младших разрядов не является случайным: велика вероятность того, что никаких скрытых случайных сообщений нет.Если они существенно близки, то распределение младших разрядов близка к случайной: велика вероятность того, что есть скрытые сообщения, встроенные в младших разряды.
Этот тест работает для блоков изображения BMP различных размеров. Каждую итерацию, мы добавляем байт, и достаточно хорошие результаты получаются на интервале от 0 до 128 байт. Каждое значение наносится на график. Тогда мы делаем те же тесты для интервала от 0 до 256, и выводим вторую точку кривой. И так далее.

     Первый пример работы метода

Приведем первый практический пример анализа изображения. Программа будет выводить график с двумя кривыми. 
Первый в красном цвете является результатом критерия хи-квадрат. Если она близка к единице, вероятность встроенного случайного сообщения высока. 
Второе множество реализует простую идею - добавить еще один уровень проверки: это среднее значение младших разрядов на текущий блок из 128 байт. Так что, если в изображении есть случайное сообщение, то зеленая кривая будет располагаться около значения 0,5.
На графике имеется сетка, которая оделяет вертикальной синей линией каждый 1 килобайт проанализированных данных.
Программа не может сохранять график, но вы можете сделать скриншот, если вы хотите его сохранить.
Построим график по описанной методики для  уже упоминавшегося изображения Beat Girl . Мы получаем это:


Что 
скрыто
Результат работы программы
Ничего
стеганография, статистический стеганализ
1 Kb случайных данных
стеганография, статистический стеганализ
5 кб случайных данных
стеганография, статистический стеганализ
"Если" Поэма, 1,5 Kb ASCII текст
стеганография, статистический стеганализ



Итак, что же мы видим? Во-первых, у нас немного больше, чем 8 блоков по 1 кБ. Это означает, что мы можем скрыть немного больше, чем 8 КБ данных. Почему это так?  Один пиксель может быть использован, чтобы скрыть три бита сообщения (один в LSB каждого тона цвета RGB). Поскольку изображение Beat Girl размером 98x225 пикселей, мы можем скрыть (98x225) x3 бит. Чтобы получить количество килобайт, мы делим на 8 и на 1024: ((98x225) x3) / (8x1024), что около 8,1 килобайта.
Далее посмотрим на графики. На первом графике, который построен для  Beat Girl без встроенных данных, хи-квадрат красного графика находится в нуле на всем протяжении в изображении нет ничего скрытого. Зеленый график среднего значения LSB очень изменчив, иногда он очень близок к 1, а иногда и очень близок к 0. Любопытно, что она идет вниз приблизительно после около 5,5 килобайт данных. На изображении этому участку соответствует горизонтальная зона между двумя руками, там, где нет белого фона: в этой области много черного, таким образом, LSB близко к 0.
Теперь давайте посмотрим на второй график. Красная кривая принимает максимальные значения в начале, а затем внезапно падает до нуля, как только мы достигаем одного килобайта скрытых данных. Мы можем заключить, что в исследуемом изображении существует скрытое сообщение одного килобайта. Посмотрите, как зеленый график средних значений на участке первого килобайта -  скрытые данные гораздо ближе к значению 0,5, нежели на других участках. Это один хороший признак случайности.
Это то же самое со следующим, третьим графиком, где изображение содержит 5 Kb скрытых данных. Красная кривая убывает сразу после достижения пятого килобайта, что видно по вертикальной разметке синего цвета.
Оказывается, что для таких неслучайных данных как изображение, даже текст считается сравнительно случайным. Поэтому на последнем графике можно четко определить встроенное 1,5 кб стихотворение.

     Второй пример работы метода

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


Скрыто
Изображение
Расширение LSBs
Хи-квадрат
Ничего
стеганография, статистический стеганализ
стеганография, статистический стеганализ
стеганография, статистический стеганализ
2 кб случайных данных
стеганография, статистический стеганализ
стеганография, статистический стеганализ
стеганография, статистический стеганализ



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

     Третий пример работы метода

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


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


Скрыто
Изображение
Расширение LSBs
Хи-квадрат
Ничего
стеганография, статистический стеганализ
стеганография, статистический стеганализ
стеганография, статистический стеганализ
1 кб случайных данных
стеганография, статистический стеганализ
стеганография, статистический стеганализ
стеганография, статистический стеганализ
2 кб случайных данных
стеганография, статистический стеганализ
стеганография, статистический стеганализ
стеганография, статистический стеганализ



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

Можно заметить то, что часто бывает в моих экспериментах с фотографиями: есть своего рода задержки в красной кривой. Даже без скрытых данных, она начинается на максимуме и остается там на некоторое время. Она близко к ложно положительному значению. Похоже, что LSB в этих изображения очень близки к случайным, и алгоритм нуждается в большом наборе данных (вспомним анализ делается на увеличивающееся количество пикселей) для достижения порога, где он может решить, что на самом деле они не являются случайными, после чего красная кривая начинает идти вниз. Такая же задержка происходит со скрытыми данными. Вы скрываете 1 или 2 кб, но красная кривая не спускается сразу после этого объема данных. Он ждет немного, в приведенных примерах соответственно, это около 1,3 кб и 2,6 кб.


P.S. По материалам сайта

2 комментария:

  1. Здравствуйте.
    Можете прояснить некоторые детали?
    Как именно изображение разбивается на блоки и строится ли для каждого блока гистограмма или берется гистограмма всего изображения?

    ОтветитьУдалить
  2. Все изображения в статье отвалились, перезалейте плиз.

    ОтветитьУдалить