Тайнопись
АрхивСлово «стеганография» наверняка знакомо многим, и многие помнят, что эта дисциплина занимается защитой информации, являясь, таким образом, родственницей криптографии.
Слово «стеганография» наверняка знакомо многим, и многие помнят, что эта дисциплина занимается защитой информации, являясь, таким образом, родственницей криптографии. Самые памятливые читатели, наверное, смогут даже назвать пару-тройку алгоритмов «скрытого письма» — именно так переводится слово «стеганография» с греческого. Однако в последний раз «КТ» рассказывала о стеганографии более двух лет назад, а с тех пор в этой области появились новые и, без преувеличения, революционные технологии.
От булыжника до спама
Нередко стеганографию считают частным разделом криптографии, что совершенно неверно. Криптография просто защищает данные, а задача стеганографии гораздо глубже — скрыть сам факт существования защищаемой информации. Это различие не менее принципиально, чем между бронежилетом и шапкой-невидимкой.
Можно предположить, что уже в каменном веке, задолго до появления первых шифров, люди могли договориться и особым образом поворачивать булыжник у входа в пещеру, тем самым подавая условные знаки соплеменникам. Примеры аналогичных тайных знаков каждый может вспомнить из собственного детства или прочитанных книг. Скажем, у Сергея Довлатова описано, как друзья будущего заключенного, провожая его в тюрьму и зная, что письма будут вымарываться цензурой, просили его по приезде выслать свою фотографию — если все хорошо, то обычную, а если плохо, то с сигаретой в руке. Через некоторое время им пришло фото, на котором друг был чисто выбрит, аккуратно одет и держал в руках две пачки «Беломора». Краткость — сестра таланта! Если добавить к этому цветок на окне из «Семнадцати мгновений весны» или утюги на подоконнике из анекдота о Штирлице (типичные примеры скрытого информирования), то становится очевидно, что стеганография может быть удивительно разнообразной.
Цифровой век подарил стеганографии второе дыхание. Все мы слышали о невидимых чернилах, проявляющихся на бумаге после нагревания. Казалось бы — сугубо шпионская амуниция, но сейчас любая секретарша, имеющая Word, может сделать себе такие «чернила» одним движением мыши — просто изменив цвет набранного текста. К примеру, вытряхните из мусорной корзины своей почтовой программы какое-нибудь спамерское сообщение. Как видите, абзацы в письме разделены пустой строкой. Скопируйте этот текст в Word и наберите в пустых строках между абзацами свое секретное донесение, допустим: «В Пхеньяне все спокойно». Выделите набранные слова и измените их цвет таким образом, чтобы он совпал с цветом фона (белый на белом). Ваш текст «исчезнет», а письмо приобретет вид обычного спама. Сохраните результат и отправьте письмо своим знакомым, например, в Белый Дом.
Черт в табакерке
В Интернете можно найти десятки программ для компьютерной тайнописи, от больших и дорогих пакетов до маленьких бесплатных утилит. Некоторые из них используют очень причудливые алгоритмы, но всегда неизменной остается суть: для скрытой передачи сообщения нужен подходящий носитель — «контейнер», который, во-первых, безобидно выглядит и, во-вторых, по размеру значительно больше скрытого сообщения (в пересчете на килобайты). Оба требования очевидны, и им подчиняются все программы — от Snow1, скрывающей данные в тексте с разной длинной пробелов, до файловой системы StegFS2, создающей во множестве подходящих файлов целый спрятанный раздел, который может работать как обычный диск.
Хотя «контейнерами» могут быть различные файлы — даже dll-библиотеки и XML-страницы, — чаще всего в этой роли выступают аудиофайлы или графика. Помимо того, что их легко пересылать, не вызывая подозрений, у звука и картинок есть уникальная особенность — они позволяют прятать в себя информацию, совершенно не увеличиваясь в размерах и почти не меняясь «в лице». С помощью простейшей утилиты можно вставить 10 Кбайт текста в 100-килобайтную картинку так, что на глаз она будет неотличима от прежней, а размер не изменится ни на бит. Думаю, стоит объяснить этот фокус, поскольку его используют примерно девять стеганографических программ из десяти.
Представим простейшую черно-белую картинку, в которой каждый пиксель описывается одним байтом. Допустим, байт кодирует яркость пикселя: ноль — черный, 255 — белый, все остальное — градации серого. Если мы изменим любой байт нашего файла или, что то же самое, отдельные биты этого байта, то соответствующий ему пиксель изменит яркость. При этом окажется, что изменение разных битов влияет на яркость пикселя по-разному: первый очень сильно, второй слабее, а последний, восьмой бит может добавить байту (а значит, и пикселю) только единицу. Заметит ли нормальный человек изменение серой точки на одну (1/255) градацию серого? Конечно, нет. А значит, для нашей картинки абсолютно не важно, каковы последние биты ее байтов. И что бы мы с ними ни делали — обнуляли, переставляли, заменяли на случайные, — картинка будет казаться одинаковой. Также не будет меняться и ее размер — ведь количество байтов мы не меняем. Таким образом, для размещения в картинке тайного сообщения достаточно превратить его в цепочку битов и записать их на место последних битов картинки3.
Описанный метод4 очень прост, применим к аудиофайлам так же, как и к картинкам, и в разных вариантах его используют почти все программы. Однако, при всей его элегантности, этим способом нельзя спрятать слишком много: алгоритм требует, чтобы соотношение скрываемой информации и файла-контейнера было не более 1:8. Если мы попытаемся изменять не только восьмые, но и седьмые и шестые биты, то картинка сильно и подозрительно исказится. По правде говоря, даже изменение последних битов бывает заметным на больших однотонных участках. Поэтому хорошие программы делают вставки только в самые надежные участки картинки. В результате для скрытой передачи средней величины текста с короткими аудиороликами общим размером, скажем, 300 Кбайт надо использовать огромное письмо-контейнер объемом 3 Мбайт. Помимо всего прочего, если за вашей почтой наблюдают (а иначе чего вы прячетесь?), то пересылка столь больших объемов может легко привлечь внимание кого-не-нужно.
Тайнопись украинская
Мне случается иногда заглядывать на сайты, посвященные стеганографии, и обычно я лишь пробегаю взглядом их ленты новостей. Однако в недавнем таком «пробеге» я по-настоящему споткнулся, чуть не упав от удивления. Вообразите себе анонс: «Windows-программа BMP Secrets обладает простым интерфейсом и способна незаметно скрывать в bmp-файлах информацию большого объема, размером до 65% от файла-контейнера». Далее шли подробности: встроенное шифрование, работа в произвольном сегменте картинки и т. д., но мое внимание было приковано к цифрам — 65%! Возможно ли это? В то время как обычные «пряталки» делают вставки максимум в 10–12%, неизвестная фирма обещает в шесть раз больше! В анонсе давалась ссылка для скачивания программы5.
На сайте компании Parallel Worlds, куда меня «сослали», рассказывалось, что при работе программы файл-контейнер визуально не меняется, размер его остается прежним и, главное, в картинку запросто входит (а затем выходит) что угодно размером до 2/3 от ее объема. Размер чудо-программы всего 2 Мбайт, и, второе чудо, она полностью freeware — только заполни анкету. Вконец заинтригованный, я заполнил что требовалось и вскоре уже разглядывал скачанный архив.
Лаконичный интерфейс BMP Secrets (рис. 1) кажется понятным с первого взгляда, и мне удалось поместить в картинку большой файл, даже не читая инструкций, — при этом я, конечно же, решил набить «контейнер» под завязку. В мегабайтную картинку программа согласилась спрятать rar-архив размером чуть более 600 Кбайт. После нажатия кнопки «Hide» рядом с оригинальным «контейнером» появилась его новая копия — уже с «закладкой», но при всем старании я не смог найти между ними разницы6.
Решив стать на место получателя послания, я закрыл программу, стер архив, снова запустил программу и попытался извлечь из картинки спрятанное. Не тут-то было! Кнопка «Unhide» не нажималась, а быстрый обзор подсказки ничего не дал. В «About» программы я увидел одни славянские имена, и у меня появилось предчувствие дурацкого розыгрыша. Приготовившись к худшему, стиснул зубы и перечитал весь Help.
Оказалось, чтобы извлечь файл из контейнера, надо указать программе имя этого файла. Пользователь должен догадаться об этом сам или проштудировать инструкцию. Вы спросите, а что делать, если контейнер пришел, но имя спрятанного в нем файла вы не знаете? К счастью, угадывать точное имя не нужно — подойдет любой набор символов, например АВС.xyz. Какое имя укажете, такой файл и появится на диске, после чего снова придется гадать (если не знаете заранее), что же это за файл — электронная таблица, архив, exe’шник или шифровка для PGP?
Впрочем, недоработка с именами — единственный минус, вполне допустимый для версии 1.0. В остальном BMP Secrets полностью оправдывает свои анонсы. Это единственная доступная программа, умеющая вставлять в несжатую картинку любой файл размером в 2/3 картинки. Вдумайтесь в эти цифры! В обои рабочего стола Windows
с разрешением 1024х768 и размером (в формате TrueColor) 2,3 Мбайт можно спрятать архив почти в полтора мегабайта — больше, чем на дискету! При этом обои визуально не изменятся, и на вашем мониторе по-прежнему будет красоваться фотография… Чья там у вас красуется?
1(назад) munkora.cs.mu.oz.au/~mkwan/snow, автор Matthew Knaw.
2(назад) ban.joh.cam.ac.uk/~adm36/StegFS, авторы Andrew D. McDonald и Markus G. Kuhn. Написана для Linux, но обещается и версия для Windows 2000.
3(назад) Можно дать и такое объяснение: если у нас есть 8 байт, которые можно слегка изменять, то мы можем спрятать в них один символ чередованием четных и нечетных байт. Например букву «Ы» (в ASCII-коде 10011011) может передать последовательность «н-ч-ч-н-н-ч-н-н». Поскольку для верной передачи важен только признак «чет-нечет», абсолютные значения байтов-носителей достаточно уменьшить или увеличить лишь на единицу. Что вполне допустимо для графики и аудио.
4(назад) Метод называется LSB — Least Significant Bits method, вставка замещением наименее значащих бит.
5(назад) www.pworlds.com/products/i_secrets.html.
6(назад) Разница видна только при вычитании картинок в «Фотошопе» или быстром переключении между ними, как между кинокадрами.
Разумеется, в этот тайный архив мы можем поместить что угодно, вплоть до копии самих обоев — даже примитивным Zip’ом они сжимаются достаточно, чтобы спрятаться самим в себя. Этот, в общем, бессмысленный трюк хорошо демонстрирует силу новой программы. Если же мы возьмем более мощный компрессор, например WinRar 3, то сможем спрятать и другие фотографии, по размеру больше, чем видимая картинка!
У вас на экране висит изображение, внутри которой есть другое изображение — тайное. Можно ли в то, тайное, вставить еще одно, так сказать, «более тайное»? Стеганография действительно позволяет создавать многослойные файлы-матрешки, но раньше они должны были многократно отличаться размером. Сейчас же мы можем взять какой-нибудь пейзаж, сжать его посильнее и с помощью BMP Secrets вставить в собственную копию. Эту копию опять сжать посильнее (без потерь!) и опять вставить в свою копию — получится тройная «матрешка». Если бы мы могли повторять эти операции бесконечно7, то у нас получился бы информационный аналог вечного двигателя — файл с бесконечной емкостью каждого из своих битов. Но реальность грубее, и я, применяя самый мощный известный мне «безпотерьный» компрессор графики8, смог сделать «матрешку» лишь из четырех копий одной картинки, вложенных друг в друга. Внешний файл-контейнер моей четвертой матрешки уже практически не поддавался сжатию без потерь — так туго он был набит данными9.
Тайнопись японская
В справке BMP Secrets нет даже намека на суть ее алгоритмов, как и в файле readme.txt. В разделе «О программе» с достоинством сказано: «Идея Виктора Чеха. Разработка и программирование Александра Грушецкого». Я решил изучить сетевые стегано-ресурсы повнимательнее. На Stegoarchive.com меня ждала аннотация (перевожу дословно): «Программа Digital Picture Envelop использует в своей работе принципы BPCS-стеганографии, изобретенные Eiji Kawaguchi в 1997 г. Эта программа, работая с bmp-файлами, может скрывать в них огромные объемы информации, составляющие до 50–100% от размера файла-контейнера, не увеличивая его размера и не внося заметных искажений». Далее шли подробности и давалась ссылка10.
Ссылка привела меня на сайт японского университета, к счастью, англоязычный. Кроме самой программы, на сайте были подробные описания ее алгоритмов, и уже через полчаса я был уверен, что новое слово в стеганографии довелось сказать не двум украинским программистам, а одному японскому профессору — Эйджи Кавагучи из Kyushu Institute of Technology.
Итак, что же придумал Кавагучи-сан? Судя по списку его научных работ, цифровой обработкой изображений профессор занимается почти тридцать лет, а в 1998 году им была опубликована статья, в которой ученый показал, что любые цифровые изображение состоят из фрагментов, несущих информацию, и фрагментов с бесполезным шумом11. Казалось бы — что тут такого?
Наше восприятие устроено так, что все хаотичное мы незаметно для себя игнорируем. Даже оказавшись в густом лесу и разглядывая беспорядочное переплетение веток, мы стараемся в первую очередь увидеть в них знакомые образы и закономерности — например, силуэт хищника. Фильтрация шумов, выделение образов из хаоса — важная, если не важнейшая, особенность нашего восприятия. И, как доказал Кавагучи, из-за этой особенности в графических файлах можно заменять целые куски изображения. Мы не заметим подмены, если вставляемые фрагменты будут (как и оригинальные) состоять из хаотично перемешанных пикселей.
Много ли шума в обычных фотографиях? Если рассматривать их «в лоб», то совсем мало. Однако цифровые изображения состоят из байтов и битов, и, как было сказано выше, младшие биты любой картинки не несут полезной информации. Мы можем провести эксперимент, взяв воображаемый рубанок и «срезав» с фотографии слой последних восьмых битов. В этом срезе мы увидим совершенно хаотичную кашу из черных и белых точек — нулей и единиц. Можно сказать, что весь слой последних битов является шумовым и не нужен нашему восприятию. Если мы продолжим «состругивать» с фотографии битовые слои и рассматривать их как двуцветные картинки (в них будут только две цифры — 1 и 0), то заметим, что чем ближе к первому биту, тем отчетливее видны контуры изображения. Согласно Кавагучи, зашумленность битовых слоев любого изображения монотонно увеличивается от первого слоя (самого информативного) к последнему.
Эта эволюция хорошо видна на примере разложения любой фотографии (рис. 2–6). Если первый битовый слой картинки является почти точной ее копией, то в шестом мы уже ничего не можем разобрать. Наиболее любопытны промежуточные слои — 3, 4 и 5-й, в которых информативные сегменты причудливо сочетаются с шумовыми. Очевидно, научиться обнаруживать в картинке местоположение шумов такого рода было, как минимум, интересной научной задачей. В процессе ее решения Кавагучи создал эффективный алгоритм, способный быстро сегментировать любую картинку.
Полагаю, читатели уже догадались, какие возможности дает этот алгоритм для стеганографии. Если прежде мы могли добавлять информацию только в последний битовый слой, то сейчас можем использовать все шумовые сегменты, то есть более половины изображения. Новизну метода хорошо понимал и его создатель, опубликовавший в том же году статью «Principle and applications of BPCS-Steganography»12. BPCS означает Bit-Plane Complexity Segmentation, что можно перевести как «разделение битовых слоев на сегменты по уровню сложности». Это официальное название нового метода, который активно развивается японским профессором: так, на нескольких научных симпозиумах Кавагучи уже демонстрировал применение своих алгоритмов в файлах типа GIF и JP2.
Программа, демонстрирующая BPCS-алгоритмы, выложена в Сеть, но в какой-то момент ее автор пожадничал и заблокировал функцию вставки сообщений. Сейчас публика может лишь извлекать «закладки» из набора фотографий, выставленных профессором на своем сайте. Это позволяет убедиться в эффективности технологии, но использовать ее в своих целях увы, невозможно.
Кстати, способность BPCS-алгоритмов скрывать информацию того же объема, что и файл-контейнер, — сильное преувеличение. Перед вставкой данных программа делает их шумоподобными (проводит рандомизацию), а проще говоря — сжимает данные простейшим архиватором. В результате некоторые файлы (например, тексты) уменьшаются в несколько раз, из-за чего и возникает иллюзия, что в картинку влезает больше килобайт, чем сама картинка занимает на диске. С готовыми архивами такой трюк, естественно, не проходит, и в действительности «закладка» может составлять около 60% от размера контейнера.
7(назад) С разными картинками это возможно: взять тысячу файлов, рассортировать по увеличению размера и вставлять (сжимая) маленькие в большие.
8(назад) В 1999 году Дмитрий Шкарин, автор одного из сильнейших текстовых компрессоров — PPMd.exe, создал BMF.exe — компрессор графики, на 10–30% лучший, чем PNG, JPEG2000, LuraWave и прочие. См. ftp.simtel.net/pub/simtelnet/win95/graphics/bmf_1_10.zip.
9(назад) О том, почему вечный двигатель невозможен даже в компьютере, а утрамбовка информации имеет свои пределы, «КТ» подробно рассказывала в прошлом году (см. #447, «Поделить и отнять»).
10(назад) www.know.comp.kyutech.ac.jp/BPCSe/BPCSe-intro.html.
11(назад) Eiji Kawaguchi and Michiharu Niimi. Modeling Digital Image into Informative and Noise-Like Regions by Complexity Measure. Information Modeling and Knowledge Bases IX, IOS Press, pp.255-265, April, 1998.
12(назад) Eiji Kawaguchi. Principle and applications of BPCS-Steganography. SPIE’s International Symposium on Voice, Video, and Data Communications, (1998-11); ftp://pckawa01. know.comp.kyutech.ac.jp/pdf-filesdown/ SPIE98.pdf.
| Мне очень хотелось узнать, как же создатели украинской программы объяснят очевидные параллели с японской разработкой, поэтому я разыскал e-mail Виктора Чеха, основателя компании Parallel Worlds, и у нас состоялась заочная беседа. Я недавно испытал вашу программу BMP Secrets и, восхищенный результатами, хочу спросить, на каких принципах она работает? — Эта программа — наш побочный продукт, появившийся почти между делом. Мы, среди прочего, занимаемся алгоритмами сжатия изображений, с потерями и без потерь, а идея BMP Secrets как бы зеркальна такому сжатию. Она использует алгоритмы компрессии для нахождения в картинке «лишней» информации, после чего замещает ее той информацией, которую надо спрятать. Вы знакомы с работами Эйджи Кавагучи? — Знаком, но мы использовали другой метод. Вы знаете, как происходит сжатие изображений? Вначале над картинкой проводится какое-либо преобразование — косинусное, как в JPEG, или, скажем, wavelet-преобразование. Суть последнего заключается в сравнении пикселей-соседей и выявлении между ними разницы. В обычных фотографиях соседние элементы похожи, за исключением границ контрастных элементов. Таких границ немного, поэтому wavelet-декомпозиция фотографии выглядит как ее серая копия, на которой видны лишь контрастные переходы. Частотное распределение пикселей в этой декомпозиции покажет довольно широкий график. Иначе говоря — сжимается она плохо, хотя и лучше, чем исходная картинка. Теперь представьте, что мы обедняем нашу декомпозицию. Например, все пиксели со значением между 0 и 8 приравняем нулю. Они станут одинаковыми, график распределения станет более узким, декомпозиция еще более серой, а картинка — менее разнообразной. Очевидно, теперь ее гораздо легче сжать. Самое интересное, что когда мы проведем обратное wavelet-преобразование, то увидим, что даже многократное обеднение декомпозиции не вызывает в сжатой картинке заметных искажений (сравните рис. 7 и 8. — Прим. ред.). Иначе говоря, wavelet-сжатие — прогрессивный метод. Но что насчет стеганографии? — Если вы рассмотрите несколько wavelet-декомпозиций, то увидите, как при усилении степени сжатия серые участки близких оттенков начинают сливаться друг с другом. Но, повторяю, это практически не ухудшает визуальное восприятие сжатых изображений. А раз так, то нельзя ли в эти серые участки добавить, скажем так, «очень легкую рябь»? Которая и будет невидимой «закладкой»? — Верно. И поскольку при сжатии мы можем выбросить из картинки много килобайт, то и вставить на их место тоже можем много. Но картинка с такой вставкой опять будет плохо сжиматься. — Конечно, ведь мы снова сделаем соседние пиксели немного разными. Тут надо выбирать — или сильное сжатие, или мощная стеганография. Wavelet-компрессор, например от LuraWave, сжимает картинку без сильных искажений более чем в сто раз. Другими словами, из нее можно выбросить 99% исходной информации. Почему же BMP Secrets может прятать файл размером только 2/3 от размера контейнера? — Не забывайте, что, прореживая пиксели, мы выбрасываем похожие на своих соседей. А когда замещаем их скрываемой информацией, приходится вставлять абсолютно случайные биты. Визуально они выглядят как шум, и начиная с некоторых значений его легко увидеть. Тут нельзя подходить механически — сколько выбросили, столько и вставили. Надо тщательно взвешивать степень искажения. Наверное, поэтому ваша программа практически не меняет картинку, в отличие от программы Кавагучи. Что ж, теперь мне ясно, что ничего японского в BMP Secrets нет… — Вы не первый, кто сомневается. Мне часто пишут с форума Watermarkingworld.org и тоже спрашивают о связях с Кавагучи. Но хотя мы с ним и пришли к схожим результатам, пути у нас были разные. Собственно, вам не нужно верить мне на слово — возьмите программу и посмотрите, как именно она меняет изображения, а потом сравните с алгоритмами Кавагучи. А почему вы сделали ее бесплатной? — Для нас она была развлечением. Я вообще узнал о стеганографии году в 98-м, когда прочел о ней в одном журнале, может быть, даже в «КТ»*. Наша компания тогда работала, с подачи американцев, над wavelet-сжатием, и я сразу понял, как можно использовать его элементы для вставки в изображение больших объемов данных. Сначала я проверил эту идею «руками» в MathCad, а потом выложил на нашем внутреннем сайте как перспективную технологию. Она довольно долго там лежала, пока Саша Грушецкий не написал на ее основе BMP Secrets. Он, кстати, значительно улучшил мой алгоритм, используя особенности цветового восприятия. На фоне остальных наших разработок эта штука, мягко говоря, не самая сложная, и мы оставили ее бесплатной в качестве рекламы. Может, тогда и исходный код выложите? — Надо подумать. Может, и выложим. Мне немного совестно за то, что подозревал талантливых ребят в списывании чужих алгоритмов. И хотя я не анализировал изменения, вносимые в изображение BMP Secrets, объяснения г-на Чеха кажутся более чем убедительными. Картинки, выдаваемые BMP Secrets, действительно сильно отличаются от представленных в галерее Кавагучи: у японского профессора очень много цветового шума и странной зернистости. Думаю, среди читателей «КТ» достаточно мастеров дебаггера и дизассемблера, поэтому при желании они всегда смогут провести и полный анализ украинской программы, и снятие блокировок с японской. Обе программы свободно лежат в Интернете, а сетевая общественность будет им за такой труд только благодарна. |
