Коли ми говоримо про стеганографію, люди репрезентують терористів, педофілів, шпигунів, ну в кращому разі криптоанархістів та інших вчених. Кому ще може знадобитися приховувати щось від зовнішніх поглядів? Яка взагалі від цього може бути користь звичайній людині?
Виявляється, якась є. Саме тому ми сьогодні стискатимемо дані за допомогою методів стеганографії. А наприкінці читач навіть зможе використовувати свої дорогоцінні фотоархіви в JPEG для збільшення кількості вільних гігабайт на файловій системі.
Що?
Якщо читач пам'ятає, то стеганографія це такі дивні алгоритми, що дозволяють приховати наявність однієї інформації всередині іншої. Ще більш простою мовою: картинка + файл == приблизно та ж картинка, але не зовсім (замість картинок може бути будь-що, але зазвичай на них все зрозуміліше). При цьому не повинно бути простого способу визначення, чи є щось усередині чи ні.
Але якщо відрізнити одне від іншого не можна, чи взагалі є різниця? З погляду споживача, користувача хвилює математична точність (відбита конкретним набором біт), лише сприймається ним.
Наприклад, подивимося на три зображення милого собаки:
Обережно, JPEG!
Незважаючи на колосальну різницю у розмірі, мало хто обере третю версію. З іншого боку, між першими двома фотографіями різниця не така помітна, і кількості інформації в них (на мій погляд) можна прирівняти.
Сам собою цей принцип вже старий і багато років активно експлуатується методами стиснення інформації з втратами. Але ламати — не будувати, нас цікавить більш просунута сторона питання. Чи можна вбудувати додаткову інформацію розміру N у файл так, щоб його розмір збільшився на M < N, а зміни не були помітні користувачеві?
Звісно ж, можна. Але варто відразу зробити пару застережень:
- По-перше, метод має бути універсальним і давати позитивний результат більшості вхідних даних. Тобто, в середньому, для довільного входу має відбуватися фактичне зменшення кількості інформації, що зберігається. "У середньому" означає, що протилежні випадки відбуватися можуть, але не повинні переважати.
- По-друге, розмір стисненого контейнера до вбудовування інформації повинен бути більшим, ніж стислий аналогічним чином його модифікація. Просто вбудувати в BMP картинки методом LSB купу біт — не стеганографічне стискування, оскільки, будучи прогнаним через якийсь DEFLATE, оригінальне зображення, швидше за все, буде помітно менше.
- По-третє, проводити та порівнювати результат потрібно щодо вже стислих класичними методами даних. Це дозволить усунути ймовірнісний ефект відмінності їх надмірності і провести більш ефективне стиснення в загальному випадку.
Де?
Використання стеганографії передбачає, що, крім інформації, що стискається, нам знадобляться контейнери, в які вона буде вбудована. Максимальна кількість інформації, що вбудовується, багато в чому залежить від окремих властивостей, але куди простіше масштабується з їх кількістю. Тому формат контейнерів може бути поширеним, щоб у користувача було достатньо їх кількість щоб одержати будь-якої віддачі від процесу «стискування».
У такому контексті хорошими кандидатами стають графічні, аудіо- та відеофайли. Але, через різноманітність різних форматів, кодеків та ін, на практиці нам залишається вибір з не такого вже й великого числа варіантів.
Враховуючи все це, мій вибір ліг на JPEG, він є практично у всіх, широко використовується як в особистих, так і в цілях бізнесів, будучи чи не форматом де-факто для більшості зображень.
Коли як?
Далі йдуть навколо- та технічні схеми та описи без особливих пояснень, тому бажаючі можуть їх пропустити, промотавши до розділу «Високі технології».
Загальні риси
Щоб вбудувати дані кудись, треба спочатку визначити, куди. На файловій системі може бути скільки завгодно різних фотографій, серед яких користувач може хотіти використовувати лише деякі. Таку бажану кількість контейнерів будемо називати бібліотекою.
Вона формується у двох випадках: до стиснення та до розпакування. У першому випадку можна просто використовувати набір імен (а краще, регулярне вираження для них) файлів, але в другому потрібно щось надійніше: користувач може копіювати та переміщати їх у межах файлової системи, тим самим не даючи коректно їх визначити. Тому потрібно зберігати їх хеш (md5 вистачить) після проведення всіх модифікацій.
Початковий пошук за регулярним виразом при цьому немає сенсу проводити по всій ФС, достатньо вказати деяку кореневу директорію. У ній буде зберігатися спеціальний файл-архів, у якому будуть ті хеші, поруч із інший мета-інформацією, яка потрібна подальшого відновлення стисливої інформації.
Все це застосовно однаково до будь-якої реалізації будь-якого алгоритму стеганографічного стиснення даних. Самі процеси стиснення та відновлення даних можна називати упаковкою та розпакуванням.
F5
Тепер, коли стало зрозуміло (її), що робимо і навіщо, залишилося описати сам алгоритм досягнення мети. Згадаймо процес кодування JPEG-файлу (спасибі вікі національної бібліотеки ім. Баумана):
Дивлячись на нього, краще відразу зробити кілька зауважень:
- Розмір JPEG-файлу можна вважати оптимальним, навіть не пробуючи стиснути якимось вінраром;
- Змінювати можна лише збережену інформацію (ту, що у виході дискретно-косинусоидального перетворення, DCT), щоб забезпечити хоч скільки-небудь прийнятну продуктивність.
- Щоб не втрачати дані у помітних користувачеві промислових масштабах, потрібно вносити мінімум модифікацій у кожне окреме зображення;
Під такі умови підходить ціла родина алгоритмів, з якими можна ознайомитись. . Найбільш просунутим є алгоритм за авторством Андреаса Вестфелда, що працює з коефіцієнтами 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-хеш і записується у файл архіву.
Високі технології
Наївна форма алгоритму та реалізації іншими високорівневими (особливо, зі складанням сміття) мовами дали б жахливу продуктивність, тому всі ці складності я реалізував на чистому Сі і провів ряд оптимізацій як за швидкістю виконання, так і по пам'яті (ви не уявляєте, скільки ці картинки важать без стиску навіть до DCT). Але і так, спочатку швидкість виконання залишала бажати сильно кращого, тому я не описуватиму весь процес і використані методи.
Крос-платформність досягнута використанням комбінації бібліотек libjpeg, pcre і tinydir, за що їм дякую. За замовчуванням все компілюється через звичайний make, тому користувачі Windows хочуть встановити собі якийсь Cygwin, або розбиратися з Visual Studio і бібліотеками самостійно.
Реалізація доступна у формі консольної утиліти та бібліотеки. Докладніше про використання останньої бажаючі можуть ознайомитись у рідмі у репозиторії на гітхабі, посилання на який я докладу наприкінці посту. А тут перейдемо до опису та демонстрації роботи.
Як використовувати?
З обережністю. Використані зображення можна переміщувати, перейменовувати та копіювати за бажанням. Однак, варто бути вкрай обережним і ніяк не змінювати їх вміст. Зміна одного біта призведе до порушення хешу та неможливості відновлення інформації.
Нехай після компіляції ми отримали файл f5ar. Можна аналізувати розмір бібліотеки для розрахунку можливостей її використання за допомогою прапора -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Упаковка проводиться командою ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], а розпакування за допомогою ./f5ar -u [файл архива] [имя восстановленного файла].
Демонстрація роботи
Щоб показати ефективність роботи методу, я завантажив колекцію із 225 абсолютно безкоштовних фотографій собак із сервісу . Кожна з них має трохи вищу якість, ніж звичайні користувацькі фотографії, але тим не менш. Кожна з них була перекодована за допомогою 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
Reading compressing file... ok
Initializing the archive... ok
Analysing library capacity... done in 16.8s
Detected somewhat guaranteed capacity of 48439359 bytes
Detected possible capacity of upto 102618787 bytes
Compressing... done in 32.6s
Saving the archive... ok
$ ./f5ar -u dogs/dogs.f5ar unpacked
Initializing the archive... ok
Reading the archive file... ok
Filling the archive with files... done in 1.2s
Decompressing... done in 17.5s
Writing extracted data... ok
$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs/
563M dogs/Або скріншотом для аматорів
Як видно, з вихідних 633 + 36 == 669 мегабайт даних на жорсткому диску ми дійшли більш приємних 563, що дає нам коефіцієнт стиснення ~1,188. Така радикальна різниця пояснюється вкрай невеликими втратами, аналогічними класичними методами (типу tinyjpg), що отримуються при оптимізації JPEG-файлів. Природно, при використанні стеганографічного стиснення інформація не просто «губиться», але використовується для кодування інших даних. Більше того, кількість «оптимізованих» коефіцієнтів за рахунок використання F5 значно менше, ніж при традиційній оптимізації.
Які модифікації не були, для ока вони не помітні абсолютно. Під спойлером нижче читач може оцінити різницю як на око, так і отриману віднімання значень зміненої компоненти з оригінальної (чим більш приглушений колір, тим менша різниця):
Посилання на зображення, що не помістилися на habrastorage
Оригінал
Модифікований -
Різниця
Замість висновку
Сподіваюся, я зміг переконати читача, що такі методи можливі та мають право на життя. Тим не менш, купити жорсткий диск або додатковий канал (для мережевої передачі) може здатися набагато простішим виходом, ніж намагатися заощаджувати таким чином. З одного боку, це і справді так, екстенсивний розвиток часто простіший і надійніший. Але з іншого, не варто забувати про та інтенсивне. Адже немає жодних гарантій, що завтра можна буде прийти в магазин і купити собі черговий жорсткий диск на тисячу терабайт, а ось використовувати будинки, що вже лежать, можна завжди.
->
Джерело: habr.com