Wenn wir von Steganographie sprechen, denken die Menschen an Terroristen, Pädophile, Spione und im besten Fall an Krypto-Anarchisten und andere Wissenschaftler. Und tatsächlich, wer könnte sonst etwas von den Blicken der Außenwelt brauchen? standardmäßig das Subdomain „www“ zu verbergen und einen Mechanismus Welchen Nutzen kann das für eine ganz gewöhnliche Person haben?
Tatsächlich gibt es einige. Genau deshalb werden wir heute Daten mit Hilfe von Steganographie komprimieren. Am Ende wird der Leser sogar in der Lage sein, seine wertvollen JPEG-Fotobestände zu nutzen, um die Anzahl der freien Gigabyte auf dem Dateisystem zu erhöhen.
Was?
Wenn sich der Leser erinnert, dann ist Steganographie eine Art merkwürdiger Algorithmen, die es ermöglichen, das Vorhandensein einer Information in einer anderen zu verbergen. Einfacher gesagt: Bild + Datei == ungefähr dasselbe Bild, aber nicht ganz (anstatt Bildern kann es alles Mögliche sein, aber normalerweise ist es bei Bildern verständlicher). Dabei sollte es keinen einfachen Weg geben festzustellen, ob etwas darin enthalten ist oder nicht.
Aber wenn man das eine vom anderen nicht unterscheiden kann, gibt es dann überhaupt einen Unterschied? Aus Sicht des Verbrauchers kümmert die mathematische Genauigkeit (die durch einen konkreten Satz von Bits widergespiegelt wird) nicht, sondern nur das, was er wahrnimmt.
Schauen wir uns zum Beispiel drei Bilder von einem süßen Hund an:
Vorsicht, JPEG!
Trotz des enormen Größenunterschieds wird nur selten die dritte Version gewählt. Auf der anderen Seite ist der Unterschied zwischen den ersten beiden Fotos nicht so offensichtlich, und die Menge an Informationen in ihnen (meiner Meinung nach) könnte gleichauf sein.
Dieses Prinzip selbst ist bereits alt und wird seit vielen Jahren aktiv in Methoden zur verlustbehafteten Daten kompression ausgenutzt. Aber brechen ist nicht gleich bauen, uns interessiert die fortgeschrittenere Seite der Frage. Ist es möglich, zusätzliche Informationen von der Größe N in eine Datei einzufügen, sodass ihre Größe um M < Nerhöht wird, ohne dass die Änderungen für den Benutzer sichtbar sind?
Natürlich ist das möglich. Aber gleich zu Beginn sollte ich ein paar Vorbehalte machen:
- Erstens, die Methode sollte universell sein und bei den meisten Eingabedaten positive Ergebnisse liefern. Das bedeutet, dass im Durchschnitt die tatsächlich gespeicherte Informationsmenge reduziert werden sollte. "Im Durchschnitt" bedeutet, dass gegenteilige Fälle möglich sind, aber nicht überwiegen sollten.
- Zweitens sollte die Größe des komprimierten Containers vor der Einbettung von Informationen größer sein als die komprimierte, entsprechend modifizierte Version. Einfach eine Vielzahl von Bits mithilfe der LSB-Methode in BMP-Bilder einzubetten, stellt keine steganographische Kompression dar, da das originale Bild nach einer DEFLATE-Wandlung wahrscheinlich deutlich kleiner sein wird.
- Drittens müssen die Ergebnisse relativ zu bereits mit klassischen Methoden komprimierten Daten durchgeführt und verglichen werden. Dies ermöglicht es, den scheinbaren Effekt ihrer Redundanz zu eliminieren und eine effektivere Kompression im Allgemeinen durchzuführen.
Wo?
Die Verwendung von Steganographie setzt voraus, dass wir neben den komprimierten Informationen Container benötigen, in die sie eingebettet werden. Die maximale Menge an einbettbaren Informationen hängt stark von den spezifischen Eigenschaften ab, lässt sich jedoch viel einfacher skalieren, je mehr Container vorhanden sind. Daher sollte das Containerformat verbreitet sein, damit der Benutzer genügend davon hat, um eine gewisse Rendite aus dem "Kompressionsprozess" zu erhalten.
In diesem Kontext eignen sich Grafik-, Audio- und Videodateien gut. Aufgrund der Vielfalt verschiedener Formate, Codecs usw. bleibt uns in der Praxis jedoch eine nicht allzu große Auswahl.
In Anbetracht all dessen fiel meine Wahl auf JPEG. Es ist praktisch überall vorhanden, wird sowohl für private als auch geschäftliche Zwecke weit genutzt und ist beinahe das De-facto-Format für die meisten Bilder.
Wann?
Darauf folgen annähernd technische Diagramme und Beschreibungen ohne große Erklärungen, daher können Interessierte diese überspringen, indem sie zum Abschnitt "Hohe Technologie" scrollen.
Allgemeine Merkmale
Um Daten irgendwo einzubetten, muss zuerst definiert werden, wo. Auf dem Dateisystem können beliebig viele verschiedene Fotos vorhanden sein, von denen der Benutzer möglicherweise nur einige verwenden möchte. Diese wünschenswerte Menge an Containern nennen wir Bibliothek.
Es bildet sich in zwei Fällen: vor der Kompression und vor der Dekompression. Im ersten Fall kann man einfach eine Menge von Namen (besser ein regulärer Ausdruck dafür) von Dateien verwenden, aber im zweiten Fall ist etwas Zuverlässigeres erforderlich: Der Benutzer kann sie innerhalb des Dateisystems kopieren und verschieben und somit die korrekte Identifizierung verhindern. Daher müssen ihre Hashes (md5 reicht) nach allen Änderungen gespeichert werden.
Der ursprüngliche Suchvorgang anhand eines regulären Ausdrucks macht in diesem Fall keinen Sinn, wenn man das gesamte FS durchsucht; es reicht aus, ein gewisses Stammverzeichnis anzugeben. In diesem wird auch eine spezielle Archivdatei gespeichert, in der sich die Hashes zusammen mit anderen Metainformationen befinden, die für die spätere Wiederherstellung der komprimierbaren Informationen erforderlich sind.
All dies ist gleichermaßen auf jede Implementierung jedes Algorithmus der steganografischen Datenkompression anwendbar. Die Komprimierungs- und Wiederherstellungsprozesse können Verpackung und Entpackung genannt werden.
F5
Jetzt, wo verständlich geworden ist, was wir tun und warum, bleibt es, den Algorithmus zur Zielerreichung zu beschreiben. Erinnern wir uns an den Prozess der Kodierung einer JPEG-Datei (danke der Wiki der Nationalbibliothek Bauman):
Schaut man sich das an, ist es besser, sofort einige Anmerkungen zu machen:
- Die Größe der JPEG-Datei kann als optimal angesehen werden, selbst wenn man nicht versucht, sie mit irgendeinem WinRAR zu komprimieren;
- Es kann nur die gespeicherte Information (die, die aus der diskreten Kosinustransformation (DCT) kommt) geändert werden, um eine einigermaßen akzeptable Leistung zu gewährleisten.
- Um zu vermeiden, dass Daten in nennenswertem Umfang für den Benutzer verloren gehen, müssen die Modifikationen an jedem einzelnen Bild minimal sein;
Unter solchen Bedingungen passt eine ganze Familie von Algorithmen, mit denen man sich vertraut machen kann . Der fortschrittlichste von ihnen ist der Algorithmus von Andreas Westfeld, der mit den DCT-Koeffizienten der Helligkeitskomponente arbeitet (das menschliche Auge ist am wenigsten empfindlich gegenüber ihren Änderungen). Sein allgemeines Schema bei der Arbeit mit einer bestehenden JPEG-Datei wird durch das folgende Schema dargestellt:
Block F5 verwendet eine fortschrittliche Einbettungsmethode, die auf der Codierung von Matrizen basiert. Der Leser kann sich näher mit ihr und dem Algorithmus selbst über den obenstehenden Link vertraut machen; uns interessiert in erster Linie die Tatsache, dass man mit ihrer Hilfe umso weniger Änderungen beim Einbetten der gleichen Datenmenge vornehmen kann, je größer der verwendete Container ist. Für die Durchführung des Algorithmus sind lediglich einfache (de)kodierungsoperationen von Huffman und RLE erforderlich.
Die Änderungen selbst werden an den ganzzahligen Koeffizienten vorgenommen und bestehen darin, ihren Absolutwert um eins zu verringern, was es ermöglicht, F5 tatsächlich zur Datenkompression zu verwenden. Der Grund dafür ist, dass ein verringerten absoluten Wert das betreffende Koeffizient wahrscheinlich weniger Bits nach der Huffman-Codierung beanspruchen wird, aufgrund der statistischen Verteilung der Werte in JPEG.
Im Falle der Bildung einer Null (sogenannte Reduzierung) wird die Menge der gespeicherten Informationen um deren Größe verringert, da der zuvor eigenständige Koeffizient Teil der codierten RLE-Sequenz von Nullen wird:
Modifikationen
Datenschutz und Datenkompression sind orthogonale Aufgaben, daher kann man auf die geheime Passwortpermutation des Originalalgorithmus verzichten. Darüber hinaus müssen wir genau wissen, wie man die Daten extrahiert; daher müssen alle dafür benötigten Informationen (welche Container verwendet wurden, in welcher Reihenfolge usw.) in einer separaten Datei festgehalten und für den Archivator zur freien Lesung geöffnet werden.
Der ursprüngliche Algorithmus ist für die Übertragung geheimer Nachrichten ausgelegt und funktioniert daher jeweils nur mit einem Container, wobei angenommen wird, dass der Benutzer ihn bei Bedarf selbst aufteilt, falls dies überhaupt erforderlich ist. Darüber hinaus muss man beim unabhängigen Einbetten in jeden Container im Voraus wissen, wie viele Bits an Daten in jeden Platzieren werden sollen. Daher empfiehlt es sich, die Koeffizienten jedes Elements der Bibliothek in einen abstrakten großen zu bündeln und mit diesem nach dem ursprünglichen Algorithmus zu arbeiten.
Da das ursprüngliche F5 bis zu 12 % der Containergröße verwenden kann, wird eine solche Modifikation auch die maximale Kapazität erhöhen: „bis zu 12 %“ der gesamten Bibliotheksgröße ist größer oder gleich der Summe „bis zu 12 %“ jedes ihrer Elemente.
Das codierte allgemeine Schema sieht folgendermaßen aus:
Der Algorithmus selbst
Jetzt ist es an der Zeit, den Algorithmus von Anfang bis Ende zu beschreiben, um den Leser nicht im Ungewissen zu lassen:
- Der Benutzer definiert die binären komprimierbaren Daten M und die Bibliothek L mithilfe regulärer Ausdrücke und des root-Verzeichnisses für die Suche;
- In der Reihenfolge des FS bilden die Elemente der Bibliothek MC:
- Eine Serie von Koeffizienten C wird aus den Daten der Datei dekodiert;
- MC <- MC | C;
- Der Parameter k wird anhand der schrecklichen Ungleichung bestimmt:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Es wird n genommen
n = (1 << k) - 1die niederwertigsten Bits der von MC nicht nullen Elemente und in geschriebena:- Die magische Hash-Funktion wird berechnet
f, die ein n-bit-Wortain k-bits; - Wenn
s == 0, dann muss nichts geändert werden und der Algorithmus wechselt zu den nächsten Koeffizienten; - Die absolute Größe des Koeffizienten, der für
s-ten Bit im Wort verantwortlich ist, verringerna; - Wenn durch die Verringerung eine Reduzierung (der Koeffizient wird 0) stattgefunden hat, dann den Schritt von vorne wiederholen;
- Die magische Hash-Funktion wird berechnet
- Alle Koeffizienten werden mit RLE und Huffman kodiert und in die ursprünglichen Dateien geschrieben;
- Der Parameter k wird in die Archivdatei geschrieben;
- Für jede Datei L wird in der Reihenfolge ihres ursprünglichen Vorkommens der MD5-Hash berechnet und in die Archivdatei geschrieben.
Hohe Technologie
Die naive Form des Algorithmus und Implementierungen in anderen hochgradig (insbesondere mit Garbage Collection) Programmiersprachen würden eine schreckliche Leistung zeigen, deshalb habe ich all diese Komplexitäten in reinem C umgesetzt und eine Reihe von Optimierungen sowohl in Bezug auf die Ausführungsgeschwindigkeit als auch auf den Speicher vorgenommen (Sie können sich nicht vorstellen, wie viel diese Bilder ohne Kompression sogar bis zu DCT wiegen). Aber auch so ließ die Geschwindigkeit zu Beginn stark zu wünschen übrig, weshalb ich den gesamten Prozess und die verwendeten Methoden nicht beschreiben werde.
Die Plattformunabhängigkeit wurde durch die Kombination der Bibliotheken libjpeg, pcre und tinydir erreicht, wofür ihnen gedankt sei. Standardmäßig wird alles über die übliche kompiliert make, daher möchten Windows-Benutzer sich irgendein Cygwin installieren oder selbst mit Visual Studio und den Bibliotheken auseinandersetzen.
Die Implementierung ist in Form eines Konsolenwerkzeugs und einer Bibliothek verfügbar. Weitere Informationen zur Verwendung der Bibliothek können Interessierte im README des Repositories auf GitHub finden, dessen Link ich am Ende des Beitrags bereitstelle. Lassen Sie uns hier zur Beschreibung und Demonstration der Funktionalität übergehen.
Wie verwendet man das?
Mit Vorsicht. Verwendete Bilder können nach Belieben verschoben, umbenannt und kopiert werden. Allerdings ist große Vorsicht geboten, und der Inhalt darf in keiner Weise verändert werden. Eine Änderung eines einzigen Bits führt zur Verletzung des Hashs und macht eine Wiederherstellung der Informationen unmöglich.
Angenommen, nach der Kompilierung haben wir die ausführbare Datei f5ar erhalten. Die Größe der Bibliothek kann zur Berechnung ihrer Verwendungsmöglichkeiten mit dem Flag analysiert werden. -a: .\/f5ar -a [Suchordner] [Perl-kompatibler regulärer Ausdruck]. Die Verpackung erfolgt mit dem Befehl .\/f5ar -p [Suchordner] [Perl-kompatibler regulärer Ausdruck] [zu verpackende Datei] [Archivname], und die Entpackung erfolgt mit .\/f5ar -u [Archivdatei] [Name der wiederhergestellten Datei].
Demonstration der Arbeit
Um die Effektivität der Methode zu zeigen, habe ich eine Sammlung von 225 absolut kostenlosen Fotos von Hunden von dem Dienst hochgeladen . Jede von ihnen hat eine etwas bessere Qualität als gewöhnliche Benutzerfotos, jedoch. Jede von ihnen wurde mit libjpeg neu kodiert, um den Einfluss der Kodierungseigenschaften der Bibliothek auf die Gesamtgröße zu neutralisieren. Für das schlechteste Beispiel komprimierbarer Daten wurde mit dd eine zufällige Datei von 36 Metern (etwas mehr als 5 % der Gesamtgröße) gleichmäßig verteilt generiert.
Der Testprozess ist ziemlich einfach:
$ 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
Lese komprimierte Datei... ok
Initialisiere Archiv... ok
Analysiere Bibliothekskapazität... erledigt in 16,8s
Erkannte garantierte Kapazität von 48439359 Bytes
Erkannte mögliche Kapazität von bis zu 102618787 Bytes
Komprimieren... erledigt in 32,6s
Speichern des Archivs... ok
$ .\/f5ar -u dogs/dogs.f5ar entpackt
Initialisiere Archiv... ok
Lese Archivdatei... ok
Fülle das Archiv mit Dateien... erledigt in 1,2s
Dekomprimieren... erledigt in 17,5s
Schreibe extrahierte Daten... ok
$ sha1sum binary_data entpackt
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 entpackt
$ du -sh dogs/
563M dogs/Oder mit einem Screenshot für die Liebhaber
Wie zu sehen ist, sind wir von den ursprünglichen 633 + 36 == 669 Megabyte Daten auf der Festplatte auf angenehmere 563 gekommen, was uns einen Kompressionsfaktor von ~1,188 gibt. Dieser radikale Unterschied erklärt sich durch die äußerst geringen Verluste, die analog zu denen auftreten, die bei der Optimierung von JPEG-Dateien mit klassischen Methoden (wie tinyjpg) erzielt werden. Natürlich wird bei der Verwendung von steganografischer Kompression die Information nicht einfach „verloren“, sondern wird zur Kodierung anderer Daten verwendet. Darüber hinaus ist die Anzahl der „optimierten“ Koeffizienten durch den Einsatz von F5 deutlich geringer als bei der herkömmlichen Optimierung.
Egal welche Modifikationen vorgenommen werden, sie sind für das Auge absolut nicht wahrnehmbar. Unter dem Spoiler unten kann der Leser den Unterschied sowohl visuell als auch durch die Subtraktion der Werte der veränderten Komponente vom Original bewerten (je gedämpfter die Farbe, desto geringer der Unterschied):
Links zu Bildern, die nicht auf habrastorage passen
Original —
Modifiziert —
Unterschied —
Zum Abschluss
Ich hoffe, ich konnte den Leser überzeugen, dass solche Methoden möglich sind und das Recht auf Existenz haben. Dennoch kann es viel einfacher erscheinen, eine Festplatte zu kaufen oder einen zusätzlichen Kanal (für die Netzübertragung) zu nutzen, als auf diese Weise zu sparen. Auf der einen Seite ist das wirklich so, der extensive Ausbau ist oft einfacher und zuverlässiger. Auf der anderen Seite sollte man jedoch das Intensive nicht vergessen. Denn es gibt keine Garantie, dass man morgen in den Laden gehen und sich eine weitere Festplatte mit tausend Terabyte kaufen kann, während man die bereits zu Hause liegenden immer nutzen kann.
->
Quelle: habr.com
