Как стать автором
Обновить

Знакомьтесь: Хеш-стеганография. Очень медленная, но совершенно секретная

Время на прочтение 5 мин
Количество просмотров 33K
Да, уважаемый читатель, вы правильно прочитали: совершенно секретная. Причем, прошу заметить, совершенно секретная в самом строгом математическом смысле: совершенно секретная по Кашену, ибо расстояние Кульбака — Лейблера в моей математической конструкции будет равно нулю; причем не «почти нулю», а всамделишному нулю, без всяких «бесконечно малых» и иных вульгарных приближений!

Каким образом? А очень просто — я вообще не буду ничего вкраплять в стегоконтейнер. Действительно, если мы ничего не вкрапляем, то пустой контейнер неотличим от стегоконтейнера, верно?

«Подождите, но ведь если мы совсем ничего не вкрапляем, то мы совсем ничего не передаем!!!» — разумно поспорит со мной читатель.

Абсолютно верно! Вкраплять мы и не будем! Есть способ, не искажая контейнер, тем не менее передать информацию. Как?

Cхематично Хеш-стеганографию ɔ⃝
можно представить так:


Текстовое пояснение к картинке под катом.



Хеш-стеганография



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

Теперь берем некую хорошую хеш-функцию. Из всех свойств «хорошести» хеш-функции нас интересует только равновероятность; то есть можно даже взять (с криптографической точки зрения) не самое лучшее хеш-преобразование, например MD5, справедливо потерявший доверие общественности.

Прогоняем все картинки через хеш-функцию, данные заносим в таблицу:
картинка --> хеш

Например:
  • котик1.jpg --> 0xd131dd02c5e6eec4693d9a0698aff95c
  • котик2.jpg --> 0x55ad340609f4b30283e488832571415a


Фиксируем некое целое число n.
Например n=2.

Составляем новую табличку, выбирая первые (или последние, кто как любит) n нибблов(полубайтов) из хеш'а.
Для нашего примера:
  • котик1.jpg --> 0xd1
  • котик2.jpg --> 0x55
  • ...


Так как без определений уже не обойтись, введем понятие хеш-кода.
Хеш-код — это первые n нибблов хеш'а изображения.
Фунцию вычисления обозначим за H(...).
Для примера: H(котик1.jpg) = 0xd1; H(котик2.jpg) = 0x55

Составляем индекс по хеш-коду в нашей таблице. Это необходимо, чтобы мы достаточно быстро (а именно за O(log(M), где M — количество картинок в базе) могли найти нужную строку в базе данных по хеш-коду.

Предположим, что мы хотим передать сообщение (в шестнадцатиричном виде): 55d134237598. Разобъем его по n нибблов. В качестве примера мы выбрали n=2, значит следует сообщение 55d134237598 разбить по 2 ниббла. Если «разбивать» будем пробелами, то выглядить это будет так: 55 d1 34 23 75 98. Полученные «кусочки», каждый из которых содержит n нибблов будем называть словами. То есть всего у нас получилось 6 слов.

Далее мы делаем следующее.
  1. Берем слово. Ищем картинку у которой хеш-код совпадает с нашим словом. Если таковых картинок несколько, берем любую из них.
  2. Передаем картинку в канал
  3. берем второе слово, ищем хеш-код совпадающий со вторым словом
  4. Передаем картинку в канал
  5. переходим к третьему слову… и так далее...


Еще раз для понимания посмотрим на GIF'ку, в которой показан принцип передачи 3-х слов: 55 d1 34


Прошу заметить, что если мы возьмем произвольным образом картинку в базе данных, то вероятность того, что
её хеш-код будет совпадать с произвольно заданным словом равна (1 / 2^(4*n)) (эх, почему на хабре до сих пор нет LaTeX'a).

Для n=1 эта величина равна 1/16, для n=2 эта величина равна уже 1/256.
Чем меньше эта вероятность, тем больше фотографий необходимо поместить в базу данных для удовлетворения наших стеганографических потребностей.

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

По этой причине хеш-стеганография очень медленна. Тем не менее, для передачи коротких сообщений, она вполне приемлима.

Формальное описание



Теперь давайте дадим формальное описание стегосистемы.

Определим стегосистему как множество объектов I.
Определим множество слов S
Определим функцию H(i), которое для каждого i из I ставит в соответсвие слово s из S.
Назовем эту функцию хеш-кодом.

Для передачи сообщения s1,s2,s3,...,sm следует найти такие i1, i2, i3, ..., im,
для которых справедливо: H(i1)=s1, H(i2)=s2, ..., H(im)=sm.

Вот собственно и вся математическая модель. Как видите — ничего сложного.

Для того, чтобы для каждого слова s не перебирать картинки, пока H(i) не станет равным s
разумно выбрать достаточно большое количество изображений, предварительно рассчитать их хеш-коды, записать в базу данных и построить индекс по хеш-кодам.

Сколько должно быть изображений, чтобы с вероятностью 99.999% можно было передать произвольное сообщение s1,s2,s3,...,sm длины m? Обозначим это число за M.

Для меня этот вопрос открытый… Никаких иных способов, кроме как методом Монте-Карло, для расчета M от m и n я не вижу.

Апгрейды



Заметим, что наша хеш-стеганография, это типичная pure-стеганография, поэтому было бы неплохо сами данные зашифровать. Например, можно использовать потоковый шифр; в этом случае, перед тем как подать искомое стегосообщение на вход стегосистемы, его следует просуммировать с некой гаммой. К примеру искомое сообщение 55 d1 34 23 75 98 можно зашифровать шифром Вернама и уже шифрованную последовательность подавать на вход стегосистемы.

Другой, на мой взгляд важный апгрейд — это удаление картинки из базы данных после её использования; чтобы после использования картинки её повторно не использовать.

Так же можно попытаться поиграть с вероятностями и с надежностью системы. Например что будет, если мы хотим передать слово 0x55, но у нас в базе данных уже закончились изображения с хеш-кодом 0x55?
Пока варианта два: либо передать с ошибкой, либо каким-либо способом нагенерировать много новых фотографий в надежде, что среди них окажется хотя бы одна с хеш-кодом равным 0x55

Однако можно придумать и другой вариант: использовать помехоустойчивое кодирование. Тогда у нас есть возможность совершить несколько ошибок и ECC их исправит.

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

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

Примеры




Навскидку несколько примеров конкретной реализации хеш-стеганографии.
  1. Публикация изображений в социальной сети в определенной последовательности.
  2. Передача данных по протоколу BitTorrent в нужной последовательности (чтобы были нужные хеш-коды для передачи нужных слов)
  3. Если в протоколе X есть возможность кодирования одних и тех же данных различными способами, то выбор такого способа кодирования, чтобы передавать нужные слова. Например подойдет протокол ZIP
  4. Совершенно произвольная осмысленная замена в человеческом языке до тех пор, пока не получим нужных хеш-код. Например предложение «Я пошёл в лес и увидел серого волка» можно заменить на аналогичное осмысленное предложение «Я отправился в лес и увидел серого волка». Смысл одинаков, но хеш-код, возможно, окажется другим. Следует производить замену до тех пор, пока не получим нужный нам хеш-код.


Подведем итоги



По пунктам.
  1. Хеш-стеганография не искажает данные контейнера. Поэтому она совершенно секретна (по Кашену)
  2. Хеш-стеганография достаточно медленна. С ростом n увеличивается скорость линейно, а сложность экспоненциально.
  3. Хеш-стеганография не чувствительна к данным контейнера. Не существует LSB для MP3, нельзя применить стеганографию в просодиях для JPEG… Для хеш-стеганографии важно только то, что данные представимы в цифровом виде.
  4. По причине п.1, п.2, п.3 хеш-стеганография может быть неплохим решением для передачи коротких сообщений
  5. Так как хеш-стеганография — это pure стеганография (стеганография без ключа), то для защиты данных необходимо шифрование
  6. Хеш-стеганография может быть «подалгоритмом» другого алгоритма стеганографии. Правда в этом случае нам, скорее всего придется пожертвовать совершенностью. Напрмер в LSB можно изображение разбить на U частей. Берем часть и изменяем в ней 1 бит данных, высчитываем для этой части хеш-код. Если он совпал со словом, то переходим к следующей части и берем следующее слово. Если нет, то пытаемся изменить другой бит данных. Таким образом мы изменили всего U бит данных, но передали 4*U*n бит данных. Увеличивая n и U можно добиться весьма хороших результатов.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Как вы думаете, будет ли на практике использоваться хеш-стеганография
28.92% Только для передачи совсем небольших сообщений 129
21.75% Да, но требуется еще большая исследовательская работа 97
49.33% Мы за вами уже едем 220
Проголосовали 446 пользователей. Воздержались 222 пользователя.
Теги:
Хабы:
+18
Комментарии 128
Комментарии Комментарии 128

Публикации

Истории

Работа

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн