Да, уважаемый читатель, вы правильно прочитали: совершенно секретная. Причем, прошу заметить, совершенно секретная в самом строгом математическом смысле: совершенно секретная по Кашену, ибо расстояние Кульбака — Лейблера в моей математической конструкции будет равно нулю; причем не «почти нулю», а всамделишному нулю, без всяких «бесконечно малых» и иных вульгарных приближений!
Каким образом? А очень просто — я вообще не буду ничего вкраплять в стегоконтейнер. Действительно, если мы ничего не вкрапляем, то пустой контейнер неотличим от стегоконтейнера, верно?
«Подождите, но ведь если мы совсем ничего не вкрапляем, то мы совсем ничего не передаем!!!» — разумно поспорит со мной читатель.
Абсолютно верно! Вкраплять мы и не будем! Есть способ, не искажая контейнер, тем не менее передать информацию. Как?
Cхематично Хеш-стеганографию ɔ⃝
можно представить так:
![](https://habrastorage.org/files/912/1c9/806/9121c9806ada40619a316812d823d5db.gif)
Текстовое пояснение к картинке под катом.
Идея очень проста. Берем большую кучу картинок. В современном мире переизбытка гаджетов, селфяшниц и дешевой памяти для хранения полученных фотографий, генерация большого количества картинок, я думаю, не составит особых проблем…
Если лень генерировать, существует множество сайтов, предоставляющие огромное количество фотографий (и других картинок).
Пишем простой скриптик на Python и выгружаем данные.
Теперь берем некую хорошую хеш-функцию. Из всех свойств «хорошести» хеш-функции нас интересует только равновероятность; то есть можно даже взять (с криптографической точки зрения) не самое лучшее хеш-преобразование, например MD5, справедливо потерявший доверие общественности.
Прогоняем все картинки через хеш-функцию, данные заносим в таблицу:
картинка --> хеш
Например:
Фиксируем некое целое число n.
Например n=2.
Составляем новую табличку, выбирая первые (или последние, кто как любит) n нибблов(полубайтов) из хеш'а.
Для нашего примера:
Так как без определений уже не обойтись, введем понятие хеш-кода.
Хеш-код — это первые 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 слов.
Далее мы делаем следующее.
Еще раз для понимания посмотрим на GIF'ку, в которой показан принцип передачи 3-х слов: 55 d1 34
![](https://habrastorage.org/files/912/1c9/806/9121c9806ada40619a316812d823d5db.gif)
Прошу заметить, что если мы возьмем произвольным образом картинку в базе данных, то вероятность того, что
её хеш-код будет совпадать с произвольно заданным словом равна (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 их исправит.
Ну и, конечно, разбивать можно не на нибблы, а на байты, на биты, на произвольные числа произвольной системы счисления.
Следует так же дать пояснение по поводу канала. Под каналом я подразумевал абстракцию в самом общем смысле этого слова. Самое главное — должен быть задан порядок следования одного слова после другого. В принципе можно просто поместить файлы скопом в папку, пронумеровав их. В этом случае папка с файлами будет каналом.
Навскидку несколько примеров конкретной реализации хеш-стеганографии.
По пунктам.
Каким образом? А очень просто — я вообще не буду ничего вкраплять в стегоконтейнер. Действительно, если мы ничего не вкрапляем, то пустой контейнер неотличим от стегоконтейнера, верно?
«Подождите, но ведь если мы совсем ничего не вкрапляем, то мы совсем ничего не передаем!!!» — разумно поспорит со мной читатель.
Абсолютно верно! Вкраплять мы и не будем! Есть способ, не искажая контейнер, тем не менее передать информацию. Как?
Cхематично Хеш-стеганографию ɔ⃝
можно представить так:
![](https://habrastorage.org/files/912/1c9/806/9121c9806ada40619a316812d823d5db.gif)
Текстовое пояснение к картинке под катом.
Хеш-стеганография
Идея очень проста. Берем большую кучу картинок. В современном мире переизбытка гаджетов, селфяшниц и дешевой памяти для хранения полученных фотографий, генерация большого количества картинок, я думаю, не составит особых проблем…
Если лень генерировать, существует множество сайтов, предоставляющие огромное количество фотографий (и других картинок).
Пишем простой скриптик на 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 слов.
Далее мы делаем следующее.
- Берем слово. Ищем картинку у которой хеш-код совпадает с нашим словом. Если таковых картинок несколько, берем любую из них.
- Передаем картинку в канал
- берем второе слово, ищем хеш-код совпадающий со вторым словом
- Передаем картинку в канал
- переходим к третьему слову… и так далее...
Еще раз для понимания посмотрим на GIF'ку, в которой показан принцип передачи 3-х слов: 55 d1 34
![](https://habrastorage.org/files/912/1c9/806/9121c9806ada40619a316812d823d5db.gif)
Прошу заметить, что если мы возьмем произвольным образом картинку в базе данных, то вероятность того, что
её хеш-код будет совпадать с произвольно заданным словом равна (1 / 2^(4*n)) (
Для 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 их исправит.
Ну и, конечно, разбивать можно не на нибблы, а на байты, на биты, на произвольные числа произвольной системы счисления.
Следует так же дать пояснение по поводу канала. Под каналом я подразумевал абстракцию в самом общем смысле этого слова. Самое главное — должен быть задан порядок следования одного слова после другого. В принципе можно просто поместить файлы скопом в папку, пронумеровав их. В этом случае папка с файлами будет каналом.
Примеры
Навскидку несколько примеров конкретной реализации хеш-стеганографии.
- Публикация изображений в социальной сети в определенной последовательности.
- Передача данных по протоколу BitTorrent в нужной последовательности (чтобы были нужные хеш-коды для передачи нужных слов)
- Если в протоколе X есть возможность кодирования одних и тех же данных различными способами, то выбор такого способа кодирования, чтобы передавать нужные слова. Например подойдет протокол ZIP
- Совершенно произвольная осмысленная замена в человеческом языке до тех пор, пока не получим нужных хеш-код. Например предложение «Я пошёл в лес и увидел серого волка» можно заменить на аналогичное осмысленное предложение «Я отправился в лес и увидел серого волка». Смысл одинаков, но хеш-код, возможно, окажется другим. Следует производить замену до тех пор, пока не получим нужный нам хеш-код.
Подведем итоги
По пунктам.
- Хеш-стеганография не искажает данные контейнера. Поэтому она совершенно секретна (по Кашену)
- Хеш-стеганография достаточно медленна. С ростом n увеличивается скорость линейно, а сложность экспоненциально.
- Хеш-стеганография не чувствительна к данным контейнера. Не существует LSB для MP3, нельзя применить стеганографию в просодиях для JPEG… Для хеш-стеганографии важно только то, что данные представимы в цифровом виде.
- По причине п.1, п.2, п.3 хеш-стеганография может быть неплохим решением для передачи коротких сообщений
- Так как хеш-стеганография — это pure стеганография (стеганография без ключа), то для защиты данных необходимо шифрование
- Хеш-стеганография может быть «подалгоритмом» другого алгоритма стеганографии. Правда в этом случае нам, скорее всего придется пожертвовать совершенностью. Напрмер в LSB можно изображение разбить на U частей. Берем часть и изменяем в ней 1 бит данных, высчитываем для этой части хеш-код. Если он совпал со словом, то переходим к следующей части и берем следующее слово. Если нет, то пытаемся изменить другой бит данных. Таким образом мы изменили всего U бит данных, но передали 4*U*n бит данных. Увеличивая n и U можно добиться весьма хороших результатов.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Как вы думаете, будет ли на практике использоваться хеш-стеганография
28.86% Только для передачи совсем небольших сообщений129
21.7% Да, но требуется еще большая исследовательская работа97
49.44% Мы за вами уже едем221
Проголосовали 447 пользователей. Воздержались 222 пользователя.