Kiedy mówimy o steganografii, ludzie wyobrażają sobie terrorystów, pedofilów, szpiegów, no w najlepszym przypadku kryptoanarchistów i innych uczonych. I rzeczywiście, kto inny mógłby potrzebować ukrywać coś przed wzrokiem innych? Jaką w ogóle korzyść może z tego mieć przeciętny człowiek?
Okazuje się, że jakaś jest. Dlatego dzisiaj będziemy kompresować dane przy użyciu metod steganografii. A na końcu czytelnik nawet będzie mógł wykorzystać swoje cenne archiwa zdjęć w formacie JPEG, aby zwiększyć ilość wolnych gigabajtów w systemie plików.
Co?
Jeśli czytelnik pamięta, steganografia to takie dziwaczne algorytmy, które pozwalają ukryć istnienie jednej informacji w drugiej. Mówiąc bardziej przystępnym językiem: obrazek + plik == mniej więcej ten sam obrazek, ale nie do końca (zamiast obrazków może być cokolwiek, ale na nich wszystko jest bardziej zrozumiałe). Przy tym nie powinno być prostego sposobu na określenie, czy coś jest w środku, czy nie.
Ale jeśli nie można odróżnić jednego od drugiego, to czy w ogóle jest jakaś różnica? Z punktu widzenia konsumenta użytkownika nie interesuje go matematyczna precyzja (odzwierciedlona konkretnym zestawem bitów), tylko to, co postrzega.
Na przykład przyjrzyjmy się trzem zdjęciom uroczego psa:
Uwaga, JPEG!
Pomimo ogromnej różnicy w rozmiarze, mało kto wybierze trzecią wersję. Z drugiej strony, różnica między pierwszymi dwoma zdjęciami nie jest tak zauważalna, a ilość informacji w nich (z mojego punktu widzenia) można przyrównać.
Sam w sobie ten zasada jest już stara i od wielu lat aktywnie wykorzystywana w metodach kompresji informacji z utratą. Ale łamać to nie to samo co budować, interesuje nas bardziej zaawansowana strona problemu. Czy można wbudować dodatkową informację wielkości N do pliku tak, aby jego rozmiar zwiększył się o M < N, a zmiany były niewidoczne dla użytkownika?
Oczywiście, że można. Ale warto od razu wprowadzić kilka zastrzeżeń:
- Po pierwsze, metoda powinna być uniwersalna i przynosić pozytywny wynik w większości danych wejściowych. To znaczy, średnio, dla dowolnego wejścia, powinno nastąpić faktyczne zmniejszenie przechowywanej ilości informacji. „Średnio” oznacza, że przeciwne przypadki mogą występować, ale nie powinny dominować.
- Po drugie, rozmiar skompresowanego kontenera przed osadzeniem informacji musi być większy niż skompresowana w ten sam sposób jego modyfikacja. Po prostu osadzenie w BMP obrazka metodą LSB wielu bitów — to nie jest steganograficzne kompresowanie, ponieważ po przetworzeniu przez jakikolwiek DEFLATE, oryginalny obraz najprawdopodobniej będzie znacznie mniejszy.
- Po trzecie, należy przeprowadzić oraz porównać wyniki w odniesieniu do danych już skompresowanych klasycznymi metodami. Umożliwi to usunięcie probabilistycznego efektu różnicy ich nadmiarowości i przeprowadzenie bardziej efektywnego kompresowania w ogólnym przypadku.
Gdzie?
Użycie steganografii oznacza, że oprócz kompresowanej informacji, potrzebne będą kontenery, w które zostanie ona osadzona. Maksymalna ilość osadzonej informacji w dużej mierze zależy od poszczególnych właściwości, ale znacznie łatwiej skalować ją z ich liczbą. Dlatego też format kontenerów powinien być powszechny, aby użytkownik miał ich wystarczającą ilość, by uzyskać jakąkolwiek korzyść z procesu „kompresji”.
W tym kontekście dobrymi kandydatami stają się pliki graficzne, audio i wideo. Jednak ze względu na różnorodność różnych formatów, kodeków itd., w praktyce pozostaje nam wybór spośród nie tak wielu opcji.
Biorąc to wszystko pod uwagę, mój wybór padł na JPEG. Jest on praktycznie dostępny dla wszystkich, szeroko stosowany zarówno w celach osobistych, jak i biznesowych, stanowiąc niemal format de facto dla większości obrazów.
K̶o̶g̶d̶a̶ Jak?
Następnie pojawiają się schematy około- i techniczne oraz opisy bez szczególnych wyjaśnień, więc chętni mogą je pominąć, przewijając do sekcji „Zaawansowane technologie”.
Ogólne cechy
Aby osadzić dane gdzieś, najpierw należy ustalić, gdzie. Na systemie plików może znajdować się dowolna liczba różnych zdjęć, z których użytkownik może chcieć wykorzystać tylko niektóre. Taki pożądany zbiór kontenerów będziemy nazywać biblioteką.
Powstaje w dwóch przypadkach: przed kompresją i przed dekompresją. W pierwszym przypadku można po prostu użyć zestawu nazw (a lepiej, wyrażenia regularnego dla nich) plików, ale w drugim potrzeba czegoś bardziej niezawodnego: użytkownik może kopiować i przenosić je w obrębie systemu plików, co uniemożliwia ich poprawne zidentyfikowanie. Dlatego konieczne jest przechowywanie ich hashy (md5 wystarczy) po przeprowadzeniu wszystkich modyfikacji.
Początkowe wyszukiwanie za pomocą wyrażenia regularnego nie ma sensu przeprowadzać w całym systemie plików, wystarczy wskazać pewien katalog główny. Tam również będzie przechowywany specjalny plik-archiwum, w którym będą zawarte te hashe, obok innych metainformacji niezbędnych do późniejszego przywrócenia kompresowanej informacji.
Wszystko to dotyczy w równym stopniu każdej realizacji dowolnego algorytmu steganograficznej kompresji danych. Same procesy kompresji i przywracania danych można nazwać pakowaniem i rozpakowywaniem.
F5
Teraz, gdy stało się jasne, co robimy i po co, pozostało opisać sam algorytm osiągnięcia celu. Przypomnijmy sobie proces kodowania pliku JPEG (dziękuję wikipedii Narodowej Biblioteki im. Bauman):
Patrząc na to, lepiej od razu poczynić kilka uwag:
- Rozmiar pliku JPEG można uznać za optymalny, nawet nie próbując go skompresować żadnym winrarem;
- Można zmieniać tylko przechowywane informacje (te, które są na wyjściu z dyskretnego przekształcenia kosinusowego, DCT), aby zapewnić akceptowalną wydajność.
- Aby nie tracić danych w zauważalnych dla użytkownika wielkościach przemysłowych, konieczne jest wprowadzenie minimalnych modyfikacji w każdym pojedynczym obrazie;
Do takich warunków pasuje całe rodzinę algorytmów, z którymi można się zapoznać . Najbardziej zaawansowanym z nich jest algorytm autorstwa Andreasa Westfelda, działającego z współczynnikami DCT komponentu jasności (ludzkie oko jest najmniej wrażliwe na jej zmiany). Jego ogólny schemat przy pracy z istniejącym plikiem JPEG przedstawia się następująco:
Blok F5 wykorzystuje zaawansowaną metodę osadzania opartą na kodowaniu macierzy. Szczegóły na ten temat oraz samego algorytmu można znaleźć w podanym powyżej linku, nas jednak interesuje przede wszystkim fakt, że dzięki niego można wykonać tym mniej zmian podczas osadzania tej samej ilości informacji, im większy jest rozmiar używanego kontenera, a do przeprowadzenia samego algorytmu wystarczy wykonać jedynie proste operacje (de)kodowania Huffmana i RLE.
Zmiany te polegają na modyfikacji całkowitych współczynników i sprowadzają się do zmniejszenia ich wartości bezwzględnej o jeden, co pozwala w ogóle używać F5 do kompresji danych. Chodzi o to, że zmniejszony współczynnik, jego wartość absolutna, prawdopodobnie zajmie mniej bitów po przeprowadzeniu kodowania Huffmana z powodu statystycznego rozkładu wartości w JPEG.
W przypadku powstania zera (tzw. skrócenia), ilość przechowywanych informacji zmniejszy się o jego rozmiar, ponieważ wcześniej samodzielny współczynnik stanie się częścią zakodowanej sekwencji RLE zer:
Modyfikacje
Ochrona danych i ich kompresja to zadania ortogonalne, dlatego można zignorować tajną permutację hasła z oryginalnego algorytmu. Co więcej, musimy dokładnie wiedzieć, jak wydobywać dane, więc wszelkie niezbędne informacje (jakie kontenery zostały użyte, w jakiej kolejności itp.) powinny być zapisywane w osobnym pliku i być dostępne do swobodnego odczytu przez archiwizator.
Oryginalny algorytm jest zaprojektowany do przesyłania tajnych wiadomości, dlatego działa w danym momencie tylko z jednym kontenerem, zakładając, że użytkownik sam podzieli go na części w razie potrzeby, jeśli w ogóle zajdzie taka konieczność. Co więcej, przy niezależnym osadzaniu w każdym kontenerze należy wcześniej wiedzieć, ile bitów danych umieścić w każdym. Dlatego współczynniki każdego elementu biblioteki warto połączyć w jeden abstrakcyjny duży i pracować z nim według oryginalnego algorytmu.
Ponieważ oryginalny F5 pozwala na wykorzystanie do 12% rozmiaru kontenera, ta modyfikacja również zwiększy maksymalną pojemność: „do 12%” od rozmiaru całej biblioteki jest większe lub równe sumie „do 12%” od każdego z jej elementów.
Skodowana ogólna schemat wygląda następująco:
Sam algorytm
Teraz czas opisać sam algorytm od początku do końca, aby nie trzymać czytelnika w niepewności:
- Użytkownik definiuje binarne dane do kompresji M i bibliotekę L za pomocą wyrażenia regularnego oraz korzennej lokalizacji wyszukiwania;
- W kolejności na systemie plików elementy biblioteki formują MC:
- Z danych pliku dekoduje się serię współczynników C;
- MC <- MC | C;
- Określa się parametr k w oparciu o straszne nierówności:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Kolejno bierze się
n = (1 << k) - 1najmniejsze bity niezerowych elementów z MC i zapisuje się je wa:- Liczy się magiczna funkcja haszująca
f, przekształcająca n-bitowe słowoaw k-bitowes; - Jeśli
s == 0, więc nic nie trzeba zmieniać, a algorytm przechodzi do następnych współczynników; - Zmniejszyć absolutną wartość współczynnika odpowiadającego za
s-ty bit w słowiea; - Jeśli w wyniku zmniejszenia nastąpiło skrócenie (współczynnik stał się 0), należy powtórzyć krok od początku;
- Liczy się magiczna funkcja haszująca
- Wszystkie współczynniki są kodowane RLE i Huffmanem, zapisywane w plikach źródłowych;
- Do archiwum zapisuje się parametr k;
- Z każdego pliku L w kolejności ich początkowego wystąpienia obliczany jest hash MD5 i zapisywany w archiwum.
Wysokie technologie
Naivna forma algorytmu oraz implementacje w innych językach wysokiego poziomu (zwłaszcza z automatycznym zarządzaniem pamięcią) dałyby straszną wydajność, dlatego wszystkie te złożoności zrealizowałem w czystym C i przeprowadziłem szereg optymalizacji zarówno pod względem szybkości wykonania, jak i pamięci (nie możesz sobie wyobrazić, ile te obrazki ważą bez kompresji nawet do DCT). Ale nawet wtedy, na początku, szybkość wykonania pozostawiała wiele do życzenia, więc nie będę opisywać całego procesu i użytych metod.
Wieloplatformowość osiągnięto dzięki wykorzystaniu kombinacji bibliotek libjpeg, pcre i tinydir, za co im dziękuję. Domyślnie wszystko kompilowane jest przez zwykły make, dlatego użytkownicy Windows powinni zainstalować sobie jakiegoś Cygwina albo samodzielnie zająć się Visual Studio i bibliotekami.
Realizacja jest dostępna w formie narzędzia konsolowego i biblioteki. Osoby zainteresowane wykorzystaniem tej drugiej mogą zapoznać się z dokumentacją w repozytorium na GitHubie, którego link zamieszczę na końcu postu. A teraz przejdźmy do opisu i demonstracji działania.
Jak z tego korzystać?
Z zachowaniem ostrożności. Użyte obrazy można przenosić, zmieniać ich nazwy i kopiować według uznania. Należy jednak być bardzo ostrożnym i nie zmieniać ich zawartości. Zmiana jednego bitu spowoduje naruszenie hasha i uniemożliwi odzyskanie informacji.
Niech po kompilacji otrzymamy plik wykonywalny f5ar. Można analizować rozmiar biblioteki, aby oszacować jej możliwości wykorzystania za pomocą flagi -a: .\/f5ar -a [folder wyszukiwania] [wyrażenie regularne zgodne z Perl]. Spakowanie odbywa się poleceniem .\/f5ar -p [folder wyszukiwania] [wyrażenie regularne zgodne z Perl] [plik do spakowania] [nazwa archiwum], a dekompresja za pomocą .\/f5ar -u [plik archiwum] [nazwa odzyskanego pliku].
Prezentacja działania
Aby pokazać skuteczność metody, załadowałem kolekcję 225 całkowicie darmowych zdjęć psów z serwisu . Każde z nich ma nieco wyższą jakość niż zwykłe zdjęcia użytkowników, ale mimo to. Każde z nich zostało przetworzone za pomocą libjpeg, aby zminimalizować wpływ cech kodowania biblioteki na całkowity rozmiar. Aby przedstawić najgorszy przykład kompresji danych, za pomocą dd wygenerowano losowy plik o wielkości 36 metrów (nieco ponad 5% całkowitego rozmiaru), o równomiernym rozkładzie.
Proces testowania jest dość prosty:
$ 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
Odczytywanie kompresowanego pliku... OK
Inicjalizacja archiwum... OK
Analiza pojemności biblioteki... zakończono w 16.8s
Wykryta nieco gwarantowana pojemność 48439359 bajtów
Wykryta możliwa pojemność do 102618787 bajtów
Kompresowanie... zakończono w 32.6s
Zapisywanie archiwum... OK
$ .\/f5ar -u dogs\/dogs.f5ar unpacked
Inicjalizacja archiwum... OK
Odczytywanie pliku archiwum... OK
Wypełnianie archiwum plikami... zakończono w 1.2s
Dekompresja... zakończono w 17.5s
Zapisywanie wyodrębnionych danych... OK
$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs\/
563M dogs\/Lub zrzut ekranu dla miłośników
Jak widać, z początkowych 633 + 36 == 669 megabajtów danych na dysku twardym osiągnęliśmy bardziej przyjemne 563, co daje nam współczynnik kompresji ~1,188. Taka radykalna różnica wynika z bardzo niewielkich strat, podobnych do tych uzyskiwanych podczas optymalizacji plików JPEG za pomocą tradycyjnych metod (np. tinyjpg). Oczywiście, przy użyciu kompresji steganograficznej informacje nie są po prostu "utracone", ale służą do kodowania innych danych. Co więcej, liczba "optymalizowanych" współczynników dzięki użyciu F5 jest znacznie mniejsza niż w przypadku tradycyjnej optymalizacji.
Jakiekolwiek byłyby modyfikacje, dla oka są zupełnie niewidoczne. Pod spoilerem poniżej czytelnik może ocenić różnicę zarówno wizualnie, jak i za pomocą obliczenia różnicy wartości zmienionej komponenty z oryginalną (im bardziej stłumiony kolor, tym mniejsza różnica):
Linki do obrazów, które nie zmieściły się na habrastorage
Oryginał —
Zmodyfikowany —
Różnica —
Zamiast zakończenia
Mam nadzieję, że udało mi się przekonać czytelnika, że takie metody są możliwe i mają prawo do istnienia. Niemniej jednak zakup dysku twardego lub dodatkowego kanału (do transmisji sieciowej) może wydawać się znacznie prostszym rozwiązaniem niż próba oszczędzania w ten sposób. Z jednej strony, rzeczywiście tak jest, rozwój ekstensywny często jest prostszy i bardziej niezawodny. Z drugiej strony, nie należy zapominać o intensywnym. Nie ma żadnych gwarancji, że jutro będzie można pójść do sklepu i kupić dysk twardy o pojemności tysiąca terabajtów, a już używane w domu można zawsze wykorzystać.
->
Źródło: habr.com
