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

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

Оказва се, че има известна полза. Именно затова днес ще сжимаме данни с помощта на методи за стеганография. А в края читателят ще може дори да използва своите ценни 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 в k-битово s;
- Ако s == 0, тогава няма нужда да се променя нищо и алгоритъмът преминава към следващите коефициенти;
- Намалете абсолютната стойност на коефициента, отговарящ за s-ия бит в словото a;
- Ако в резултат на намаляване е настъпило съкращаване (коефициентът е станал 0), повторете стъпката от начало;
Всички коефициенти се кодирани с RLE и Хаффман, записват се в изходните файлове;
В архива се записва параметър k;
От всеки файл L, в реда на оригиналното им местоположение, се изчислява MD5 хеш и се записва в архивния файл.

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

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

Крос-платформеността е постигната чрез използването на комбинация от библиотеки libjpeg, pcre и tinydir, за което им благодаря. По подразбиране всичко се компилира чрез обикновен направи, затова потребителите на 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.8с
Разпознат е малко гарантиран капацитет от 48439359 байта
Разпознат е възможен капацитет до 102618787 байта
Компресиране... завършено за 32.6с
Записване на архива... ок

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

$ 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