Спестяваме място на твърдия диск с помощта на стеганография

Когато говорим за стеганография, хората си представят терористи, педофили, шпиони, а в най-добрия случай криптоанархисти и различни учени. И наистина, кой друг би имал нужда от скриване на нещо от външния свят? Каква полза би имал обикновеният човек от това?

Оказва се, че доста. Затова днес ще компресираме данни с помощта на методи на стеганография. А в края на статията читателят дори ще може да използва своите ценни JPEG архиви за увеличаване на свободното място на файловата система.

Какво?

Ако читателят помни, стеганографията — това са странни алгоритми, които позволяват да се скрие наличието на една информация в друга. С по-прости думи: картинка + файл == почти същата картинка, но не съвсем (вместо картинки може да има каквото и да е, но обикновено с тях е по-ясно). Важно е, че не трябва да има прост начин за определяне дали нещо е вътре или не.

Но ако едното не може да се отличи от другото, съществува ли разлика изобщо? От гледна точка на потребителя, на потребителя не му пука за математическата точност (отразена чрез конкретен набор от битове), а само за възприеманото.

Например, да разгледаме три изображения на сладко куче:

Внимание, JPEG!

Въпреки огромната разлика в размера, малко хора ще изберат третата версия. От друга страна, разликата между първите две снимки не е толкова очевидна и количеството информация в тях (от моята гледна точка) може да се приравни.

Самият принцип вече е стар и от много години активно се експлоатира с методи за компресия на информация с загуби. Но да разбиваш е различно от да строиш, интересува ни по-напредналата страна на въпроса. Може ли да се вгради допълнителна информация с размер N в файл така, че размерът му да се увеличи с M < N, а промените да не са видими за потребителя?

Разбира се, че може. Но е разумно веднага да направим няколко уточнения:

• Първо, методът трябва да бъде универсален и да дава положителен резултат при повечето входни данни. Тоест, в средно, за произволен вход, трябва да се наблюдава реално намаляване на хранимото количество информация. 'В средно' означава, че оплитането на противоположни случаи може да се случи, но не трябва да доминира.
• На първо място, размерът на компресирания контейнер преди вграждането на информацията трябва да бъде по-голям от компресирания аналогично модифициран. Просто да вградим в BMP изображения с метода LSB пакет от битове — не е стеганографското компресиране, тъй като, след като премине през някой DEFLATE, оригиналното изображение вероятно ще бъде значително по-малко.
• На трето място, необходимо е да се провеждат и сравняват резултатите по отношение на вече компресирани данни с класически методи. Това ще позволи да се елиминира вероятностният ефект от разликите в тяхната излишност и да се проведе по-ефективно компресиране в общия случай.

Къде?

Използването на стеганография предполага, че освен компресируемата информация, ще ни трябват контейнери, в които тя ще бъде вградена. Максималното количество вградена информация до голяма степен зависи от специфичните свойства, но по-лесно се мащабира с тяхното количество. Следователно форматите на контейнерите трябва да бъдат разпространени, за да има достатъчно от тях за потребителя, за да получи каквато и да е възвръщаемост от процеса на „компресиране“.

В такъв контекст добри кандидати стават графични, аудио- и видеофайлове. Но, поради разнообразието от различни формати, кодеци и т.н., на практика остава избор от не толкова много опции.

Взимайки предвид всичко това, моят избор падна на JPEG. Той е практически на разположение на всички, широко използван както в лични, така и в бизнес цели, като е почти формат де факто за повечето изображения.

Кога?

Следват около- и технически схеми и описания без особени обяснения, така че желаещите могат да ги пропуснат, прескачайки до раздела „Високи технологии“.

Общи черти

За да вградим данни някъде, първо трябва да определим къде. На файловата система може да има неограничен брой различни фотографии, сред които потребителят може да иска да използва само някои. Това желяно множество контейнери ще наречем библиотека.

Формира се в два случая: преди компресия и преди разархивиране. В първия случай може просто да се използва набор от имена (по-добре е да се използва регулярна експресия за тях) на файлове, но във втория е необходимо нещо по-надеждно: потребителят може да копира и премества файлове в рамките на файловата система, което да затрудни коректното им определяне. Затова е необходимо да се съхраняват техните хешове (md5 е достатъчен) след извършване на всички модификации.

Първоначалното търсене по регулярна експресия няма смисъл да се извършва в цялата файлова система, достатъчно е да се посочи определена коренова директория. В нея ще се съхранява и специален архивен файл, в който ще бъдат запазени хешовете, наред с друга метаинформация, необходима за последвачното възстановяване на компресирана информация.

Всичко това е приложимо в равна степен към всяка реализация на който и да е алгоритъм за стеганографска компресия на данни. Процесите на компресия и възстановяване на данни могат да се наричат опаковане и разопаковане.

F5

Сега, когато стана ясно какво правим и защо, остава да опишем самия алгоритъм за постигане на целта. Нека си спомним процеса на кодиране на JPEG файл (благодаря на националната библиотека им. Баумана):

Гледайки го, е добре да направим няколко забележки веднага:

• Размерът на JPEG файла може да се счита за оптимален, дори без да се опитваме да го компресираме с някой винрар;
• Може да се променя само съхраняваната информация (тази, която е на изхода от дискретно-косинусоидалното преобразуване, DCT), за да се осигури приемлива производителност.
• За да не се губят данни в забележими за потребителя индустриални мащаби, е необходимо да се внасят минимални модификации в всяко отделно изображение;

Под тези условия подхожда цялото семейство алгоритми, с които може да се запознаете в тази добра презентация. Най-напредналият от тях е алгоритъмът F5 авторство на Андреас Вестфелд, работещ с коефициентите DCT на компонента яркост (човешкото око е най-малко чувствително точно към измененията в него). Неговата обща схема при работа с съществуващ JPEG файл се изобразява с следната схема:

Блок F5 използва усъвършенствана методика за вграждане, основана на кодиране на матрица. Повече информация за нея и самия алгоритъм читателят може да намери на линка горе, но нас ни интересува най-вече фактът, че с нея е възможно да се направят по-малко изменения при вграждането на същото количество информация, отколкото е по-голям размерът на използвания контейнер, а за провеждането на самия алгоритъм е необходимо да се извършат само прости операции за (де)кодиране на Хъфман и RLE.

Самите изменения се извършват върху цели числа и се свеждат до намаляване на абсолютната им стойност с единица, което всъщност позволява използването на F5 за компресия на данни. Факт е, че намаленият по абсолютна стойност коефициент вероятно ще заема по-малко битове след извършване на кодиране чрез Хъфман поради статистическото разпределение на стойностите в JPEG.

В случай на образуване на нула (т.н. скъсяване), количеството съхранявана информация ще се намали с нейния размер, тъй като бившият самостоятелен коефициент ще стане част от кодираната RLE последователност от нули:

Модификации

Защитата на данни и тяхната компресия са ортогонални задачи, затова може да се пренебрегне секретното паролно разместване от оригиналния алгоритъм. Освен това, трябва точно да знаем как да извлечем данните, затова цялата необходима за това информация (какви контейнери са използвани, в какъв ред и т.н.) трябва да се записва в отделен файл и да бъде отворена за свободно четене от архиватора.

Оригиналният алгоритъм е предназначен за предаване на секретни съобщения, затова работи наведнъж само с един контейнер, предполагаща, че потребителят сам ще го раздели на части при необходимост, ако такава изобщо възникне. Освен това, при независимо вграждане в всеки контейнер, е необходимо предварително да се знае колко бита данни да се поместят в всеки. Затова коефициентите на всеки елемент от библиотеката трябва да се обединят в един абстрактно голям и да се работи с него по оригиналния алгоритъм.

Тъй като оригиналният F5 позволява използването на до 12% от размера на контейнера, тази модификация също ще увеличи максималния капацитет: „до 12%“ от размера на цялата библиотека е по-голямо или равно на сумата „до 12%“ от всеки от нейните елементи.

Кодифицираната обща схема изглежда по следния начин:

Самият алгоритъм

Сега е време да опишем самия алгоритъм от начало до край, за да не оставяме читателя в неведение:

• Потребителят определя бинарните сжимаеми данни M и библиотеката L с помощта на регулярни изрази и коренната директория за търсене;
• В реда на следване на ФС елементите на библиотеката формират MC:
  • От данните на файла се декодира серия от коефициенти C;
  • MC <- MC | C;
• Определя се параметърът k, основавайки се на страховитото неравенство: |M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1);
• Последователно се взема n = (1 << k) - 1 най-младшите битове на ненулевите елементи от MC и се записва в a:
  • Счита се магическата хеш-функция f, която отразява n-битно слово a ако s == 0 s;
  • Ако , не е нужно нищо да променяте и алгоритъмът преминава към следващите коефициенти;Намалете абсолютната стойност на коефициента, отговарящ за
  • -тия бит в словото sАко в резултат на намалението е настъпило съкращение (коэффициентът е станал 0), то повторете стъпката отначало; a;
  • Всички коефициенти се кодират с RLE и Хаффман, записват се в изходните файлове;
• В архива се записва параметърът k;
• От всеки файл L в реда на оригиналното им разположение се изчислява MD5 хеш и се записва в файла на архива.
• Най-простата форма на алгоритъма и реализациите на други високо ниво (особено с garbage collection) е довела до ужасна производителност, затова всичките тези сложности реализирах на чист C и проведох редица оптимизации както по скорост на изпълнение, така и по памет (не можете да си представите колко тежат тези картинки без компресия дори до DCT). Но и тогава, в началото скоростта на изпълнение оставяше много да се желае, затова няма да описвам целия процес и използваните методи.

Високи технологии

Крос-платформеността е постигната чрез комбинация от библиотеките libjpeg, pcre и tinydir, за което им благодаря. По подразбиране всичко се компилира чрез обикновен

make , затова потребителите на Windows трябва да инсталират Cygwin или да се справят сами с Visual Studio и библиотеките., затова потребителите на Windows трябва да инсталират Cygwin или да се справят с Visual Studio и библиотеките самостоятелно.

Реализация е достъпна под формата на конзолна утилита и библиотека. Повече информация относно използването на последната може да бъде намерена в ръководството в репозитория на GitHub, чиято връзка ще добавя в края на публикацията. А сега преминаваме към описанието и демонстрацията на работата.

Как да я използвате?

С внимание. Използваните изображения могат да бъдат преместени, преименувани и копирани по желание. Въпреки това, е необходимо да бъдете изключително внимателни и никога да не променяте тяхното съдържание. Промяната дори на един бит ще доведе до нарушаване на хеша и невъзможност за възстановяване на информацията.

Нека след компилирането получим изпълним файл f5ar. Можем да анализираме размера на библиотеката за двоично изчисление на възможностите за нейното използване с помощта на флага -a: .\/f5ar -a [папка за търсене] [регулярно изразение, съвместимо с Perl]. Опаковката става с команда .\/f5ar -p [папка за търсене] [регулярно изразение, съвместимо с Perl] [опакован файл] [име на архива], а разопаковането става с помощта на .\/f5ar -u [файл на архива] [име на възстановен файл].

Демонстрация работы

Чтобы продемонстрировать эффективность метода, я загрузил коллекцию из 225 абсолютно бесплатных фотографий собак с сервиса Unsplash. Всяка от тях притежава малко по-високо качество в сравнение с обикновени потребителски снимки, но все пак. Всяка от тях е била пре-кодирана с помощта на libjpeg, за да се неутрализира влиянието на особеностите на кодиране на библиотеката върху общия размер. За уточняване на най-лошия пример на компресируеми данни с помощта на dd е бил генериран случайно разпределен 36-метров файл (малко над 5% от общия размер).

Процесът на тестване е доста прост:

$ ls
binary_data dogs f5ar
$ du -sh dogs/
633M dogs/
$ du -h binary_data
36M binary_data

$ .\/f5ar -p dogs/ .*jpg binary_data dogs.f5ar
Четене на компресирания файл... успешно
Инициализиране на архива... успешно
Анализ на капацитета на библиотеката... завършено за 16.8s
Открит малко гарантиран капацитет от 48439359 байта
Открит възможен капацитет до 102618787 байта
Компресиране... завършено за 32.6s
Запазване на архива... успешно

$ .\/f5ar -u dogs/dogs.f5ar разопакован
Инициализиране на архива... успешно
Четене на файла на архива... успешно
Запълване на архива с файлове... завършено за 1.2s
Разопаковане... завършено за 17.5s
Запис на извлечените данни... успешно

$ sha1sum binary_data разопакован
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 разопакован
$ du -sh dogs/
563M dogs/

Или със скрийншот за любителите

Както се вижда, от първоначалните 633 + 36 == 669 мегабайта данни на твърдия диск, достигнахме до по-привлекателните 563, което ни дава коефициент на компресия ~1,188. Тази радикална разлика се обяснява с много малки загуби, подобни на тези, получени при оптимизация на JPEG файлове с класически методи (като tinyjpg). Естествено, при използване на стеганографска компресия информацията не просто "изчезва", а се използва за кодиране на други данни. Освен това, количеството на "оптимизирани" коефициенти благодарение на F5 е много по-малко в сравнение с традиционната оптимизация.

Каквито и модификации да са, за окото те абсолютно не са забележими. Под спойлера по-долу читателят може да оцени разликата както визуално, така и чрез изваждане на стойностите на променената компонента от оригиналната (колкото по-приглушен е цветът, толкова по-малка е разликата):

Линкове към изображения, които не намериха място на habrastorage

Оригинал — https://i.ibb.co/wNDLNcZ/1.jpg
Модифициран — https://i.ibb.co/qWvpfFM/1.jpg
Разлика — https://i.ibb.co/2ZzhHfD/diff.jpg

Вместо заключение

Надявам се, че успях да убедя читателя, че такива методи са възможни и имат право на съществуване. Все пак, купуването на твърд диск или допълнителен канал (за мрежова предаване) може да изглежда много по-прост изход, отколкото да се опитваш да спестяваш по този начин. От една страна, наистина е така, екстенсивното развитие често е по-просто и надеждно. Но от друга страна, не трябва да забравяме и интензивното. Няма гаранции, че утре ще можеш да отидеш в магазина и да си купиш поредния твърд диск от хиляда терабайта, а използването на тези, които вече имаш у дома, винаги е възможно.

-> GitHub

Източник: habr.com