Wenn wir von Steganographie sprechen, denken die Leute an Terroristen, Pädophile, Spione – oder im besten Fall an kryptoanarchistische Wissenschaftler. Und tatsächlich, wer sonst könnte noch etwas von den Blicken der Außenwelt brauchen? standardmäßig den Subdomain "www" auszublenden und einen Mechanismus hinzuzufügen. Welchen Nutzen könnte das für den einfachen Menschen haben?
Es stellt sich heraus, dass es tatsächlich einen gibt. Aus diesem Grund werden wir heute Daten mithilfe von Steganographiemethoden komprimieren. Am Ende wird der Leser sogar in der Lage sein, seine wertvollen JPEG-Fotoarchive zu nutzen, um den freien Speicherplatz auf dem Dateisystem zu erhöhen.
Was?
Wenn sich der Leser erinnert, ist Steganographie eine seltsame Art von Algorithmus, der es ermöglicht, das Vorhandensein einer Information innerhalb einer anderen zu verbergen. Einfacher ausgedrückt: Bild + Datei = etwa dasselbe Bild, aber nicht ganz (anstatt Bilder kann alles Mögliche sein, aber bei Bildern ist es normalerweise verständlicher). Dabei sollte es keinen einfachen Weg geben, festzustellen, ob sich etwas im Inneren befindet oder nicht.
Aber wenn man das eine nicht vom anderen unterscheiden kann, gibt es dann überhaupt einen Unterschied? Aus der Sicht des Verbrauchers spielt die mathematische Genauigkeit (die durch einen bestimmten Bitensatz widergespiegelt wird) keine Rolle, sondern nur das, was wahrgenommen wird.
Betrachten wir zum Beispiel drei Bilder eines niedlichen Hundes:
Achtung, JPEG!
Trotz des enormen Größenunterschieds wird kaum jemand die dritte Version wählen. Im Gegensatz dazu ist der Unterschied zwischen den ersten beiden Fotos nicht so offensichtlich, und die Menge an Informationen darin könnte (meiner Meinung nach) als gleichwertig angesehen werden.
Dieses Prinzip ist bereits alt und wird seit vielen Jahren aktiv durch verlustbehaftete Komprimierungsmethoden verwendet. Aber brechen ist leichter als bauen, uns interessiert die fortgeschrittenere Seite der Frage. Ist es möglich, zusätzliche Informationsgröße N in die Datei einzubetten, so dass ihre Größe sich um M < N, erhöht, ohne dass der Benutzer die Änderungen bemerkt?
Natürlich ist das möglich. Es sei jedoch gleich zu Beginn erwähnt, dass einige Vorbehalte bestehen:
- Erstens muss die Methode universell sein und bei den meisten Eingabedaten positive Ergebnisse liefern. Das bedeutet, dass bei durchschnittlichen Eingaben eine tatsächliche Reduzierung der gespeicherten Informationsmenge erfolgen sollte. "Im Durchschnitt" bedeutet, dass gegenteilige Fälle auftreten können, 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 Menge von Bits im BMP-Bild mit der LSB-Methode einzufügen, ist keine steganographische Kompression, da das Originalbild nach einer DEFLATE-Verarbeitung wahrscheinlich deutlich kleiner sein wird.
- Drittens sollte das Ergebnis im Vergleich zu bereits mit klassischen Methoden komprimierten Daten durchgeführt werden. Dies ermöglicht es, den probabilistischen Effekt von deren Redundanz zu eliminieren und eine effizientere Kompression im Allgemeinen zu erreichen.
Wo?
Die Verwendung von Steganographie bedeutet, dass wir neben den zu komprimierenden Informationen auch Container benötigen, in die diese eingebettet wird. Die maximale Menge an einbettbaren Informationen hängt stark von den einzelnen Eigenschaften ab, lässt sich jedoch einfacher mit ihrer Anzahl skalieren. Daher sollte das Containerformat weit verbreitet sein, damit der Benutzer genügend davon hat, um überhaupt eine Rückmeldung von dem Prozess der "Kompression" zu erhalten.
In diesem Kontext eignen sich grafische, Audio- und Videodateien gut. Aufgrund der Vielzahl unterschiedlichster Formate, Codecs usw. bleibt uns in der Praxis jedoch nicht mehr als eine relativ kleine Auswahl zur Verfügung.
Angesichts all dessen fiel meine Wahl auf JPEG. Dieses Format ist nahezu jeder Person bekannt, wird sowohl im privaten als auch im geschäftlichen Bereich weit verbreitet und gilt de facto als das Standardformat für die meisten Bilder.
Wann?
Es folgen technische Schemata und Beschreibungen ohne besondere Erläuterungen, daher können Interessierte sie überspringen, indem sie bis zum Abschnitt "Hohe Technologie" blättern.
Gemeinsame Merkmale
Um Daten irgendwo einzufügen, muss zuerst bestimmt werden, wohin. Im Dateisystem können sich beliebig viele verschiedene Fotos befinden, von denen der Benutzer möglicherweise nur einige verwenden möchte. Diese gewünschte Menge an Containern nennen wir Bibliothek.
Sie wird in zwei Fällen gebildet: vor der Komprimierung und vor der Dekomprimierung. Im ersten Fall kann man einfach eine Menge von Dateinamen verwenden (besser wäre ein regulärer Ausdruck dafür), im zweiten Fall ist etwas Zuverlässigeres erforderlich: Der Benutzer kann sie innerhalb des Dateisystems kopieren und verschieben, wodurch eine korrekte Identifizierung erschwert wird. Daher ist es notwendig, ihre Hashwerte (md5 reicht aus) nach allen Modifikationen zu speichern.
Der ursprüngliche Suchvorgang mit einem regulären Ausdruck macht dabei keinen Sinn, wenn er über das gesamte FS durchgeführt wird; es reicht aus, ein gewisses Wurzelverzeichnis anzugeben. In diesem wird zudem eine spezielle Archivdatei gespeichert, in der sich die Hashwerte zusammen mit anderen Metainformationen befinden, die für die spätere Wiederherstellung der komprimierten Informationen erforderlich sind.
All dies gilt gleichermaßen für jede Implementierung eines Datenkompressionsteganografie-Algorithmus. Die Prozesse der Datenkompression und -wiederherstellung können als Packen und Entpacken bezeichnet werden.
F5
Jetzt, da klar ist, was wir tun und warum, bleibt nur noch der Algorithmus zur Zielerreichung zu beschreiben. Erinnern wir uns an den Prozess der JPEG-Dateikodierung (danke an die Wiki der Nationalbibliothek namens Bauman):
Wenn man darauf schaut, sollte man sofort einige Bemerkungen machen:
- Die Größe einer JPEG-Datei kann als optimal angesehen werden, selbst ohne es mit einem WinRAR oder ähnlichem zu komprimieren;
- Es darf nur die gespeicherte Information (die, die mit der diskreten Cosinus-Transformation, DCT, ausgegeben wird) geändert werden, um eine einigermaßen akzeptable Leistung zu gewährleisten.
- Um keine Daten in für den Benutzer merkbaren industriellen Maßstäben zu verlieren, ist es erforderlich, minimale Änderungen an jedem einzelnen Bild vorzunehmen;
Für diese Bedingungen eignet sich eine ganze Familie von Algorithmen, mit denen man sich vertraut machen kann. . Der fortschrittlichste von ihnen ist der Algorithmus verfasst von Andreas Westfeld, der mit DCT-Komponenten der Helligkeit arbeitet (das menschliche Auge reagiert am wenigsten empfindlich auf deren Veränderungen). Sein Gesamtschema bei der Arbeit mit einer bestehenden JPEG-Datei wird durch folgendes Schema dargestellt:
Der Block F5 verwendet eine fortschrittliche Einbettungsmethode, die auf der Codierung einer Matrix basiert. Weitere Informationen dazu und zu dem Algorithmus finden Sie unter dem oben stehenden Link. Besonders wichtig ist für uns der Fakt, dass durch ihn weniger Änderungen beim Einbetten derselben Informationsmenge erforderlich sind, je größer der verwendete Container ist. Für die Durchführung des Algorithmus sind lediglich einfache (De-)Kodierungsoperationen mit Huffman und RLE erforderlich.
Die Änderungen erfolgen an den ganzzahligen Koeffizienten und bestehen darin, ihren absoluten Wert um eins zu verringern. Dies ermöglicht es im Grunde, F5 zum Datenkomprimieren zu verwenden. Der Grund dafür ist, dass ein im absoluten Wert verringerter Koeffizient nach einer Huffman-Codierung aufgrund der statistischen Verteilung der Werte im JPEG wahrscheinlich weniger Bits beanspruchen wird.
Im Falle der Nullbildung (d. h. der Reduktion) 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 deren Kompression sind orthogonale Aufgaben, daher kann die geheime Passwortpermutation des ursprünglichen Algorithmus vernachlässigt werden. Darüber hinaus müssen wir genau wissen, wie man die Daten extrahiert, weshalb alle benötigten Informationen (welche Container verwendet wurden, in welcher Reihenfolge usw.) in einer separaten Datei erfasst werden sollten und für den Archivierungsprozess frei lesbar sein müssen.
Der originale Algorithmus ist darauf ausgelegt, geheime Nachrichten zu übertragen, weshalb er jeweils nur mit einem Container arbeitet. Der Benutzer muss ihn gegebenenfalls selbst in Teile aufteilen, wenn dies notwendig ist. Darüber hinaus erfordert die eigenständige Einbettung in jeden Container, dass im Voraus bekannt ist, wie viele Bits an Daten in jeden Container passen. Daher sollten die Koeffizienten jedes Bibliothekselements in einem großen abstrakten zusammengefasst werden, um mit dem ursprünglichen Algorithmus zu arbeiten.
Da das originale F5 die Nutzung von bis zu 12% der Containergröße erlaubt, erhöht diese Modifikation ebenfalls die maximale Kapazität: "bis zu 12%" der gesamten Bibliotheksgröße ist größer oder gleich der Summe von "bis zu 12%" von jedem ihrer Elemente.
Das kodifizierte Gesamtschema sieht folgendermaßen aus:
Der Algorithmus
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 von regulären Ausdrücken und dem Wurzelverzeichnis der Suche;
- In der Reihenfolge der Dateisystemelemente bilden die Bibliothekelemente MC:
- Aus der Datei wird eine Serie von Koeffizienten C dekodiert;
- MC <- MC | C;
- Der Parameter k wird basierend auf der schweren Ungleichheit bestimmt:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Es werden n = (1 << k) - 1
die niederwertigen Bits der Nicht-Null-Elemente aus MC entnommen und inEs wird eine magische Hash-Funktion berechnet,a:- die ein n-Bit-Wort
fin k-Bit umwandelt.as == 0s; - Wenn
, dann muss nichts geändert werden, und der Algorithmus fährt mit den nächsten Koeffizienten fort;Verringerung des Absolutwerts des Koeffizienten, der für - -e Bit im Wort verantwortlich ist.
sWenn durch die Verringerung eine Reduktion aufgetreten ist (der Koeffizient wurde 0), dann wiederhole den Schritt von Anfang an;a; - Alle Koeffizienten werden mit RLE und Huffman kodiert und in die ursprünglichen Dateien geschrieben;
- die ein n-Bit-Wort
- Die Parameter k werden in die Archivdatei geschrieben;
- Für jede Datei L wird in der Reihenfolge ihres ursprünglichen Erscheinens der MD5-Hash berechnet und in die Archivdatei geschrieben.
- От каждого файла L в порядке их исходного нахождения считается MD5-хэш и записывается в файл архива.
Hohe Technologie
Die naive Form des Algorithmus und dessen Implementierung in anderen Hochsprachen (insbesondere solchen mit Garbage Collection) würden eine katastrophale Leistung bringen. Daher habe ich all diese Komplexität 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). Trotzdem ließ die Ausführungsgeschwindigkeit anfänglich stark zu wünschen übrig, weshalb ich den gesamten Prozess und die verwendeten Methoden nicht im Detail beschreiben werde.
Die plattformübergreifende Unterstützung wurde durch die Verwendung einer Kombination aus den Bibliotheken libjpeg, pcre und tinydir erreicht, wofür ich ihnen dankbar bin. Standardmäßig wird alles über die übliche make, weshalb Windows-Benutzer sich Cygwin installieren oder selbstständig mit Visual Studio und den Bibliotheken auseinandersetzen möchten.
Die Implementierung ist als Konsolenanwendung und Bibliothek verfügbar. Interessierte können sich in der README-Datei im GitHub-Repository näher über die Verwendung der Bibliothek informieren; den Link dazu füge ich am Ende des Beitrags hinzu. Jetzt kommen wir zur Beschreibung und Demonstration der Funktionalität.
Wie verwendet man das?
Seien Sie vorsichtig. Verwendete Bilder können nach Belieben verschoben, umbenannt und kopiert werden. Dennoch sollte man äußerst vorsichtig sein und den Inhalt nicht verändern. Eine Änderung auch nur eines Bits führt zu einer Verletzung des Hashs und macht die Wiederherstellung der Informationen unmöglich.
Nach der Kompilierung haben wir die ausführbare Datei f5ar erhalten. Sie können die Größe der Bibliothek analysieren, um ihre Nutzbarkeit mit dem Flag zu berechnen. -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] [wiederhergestellter Dateiname].
Demonstration der Funktionsweise
Um die Effektivität der Methode zu zeigen, habe ich eine Sammlung von 225 völlig kostenlosen Hundebildern von einem Dienst hochgeladen . Jede dieser Dateien bietet eine leicht höhere Qualität als gewöhnliche Benutzerfotos, dennoch. Jede wurde mit libjpeg neu kodiert, um die Auswirkungen der Codierungseigenheiten auf die Gesamtgröße auszugleichen. Zur Bezeichnung des schlechtesten Beispiels komprimierter Daten wurde mit dd eine zufällige 36-Meter-Datei (etwas mehr als 5% der Gesamtgröße) mit gleichmäßiger Verteilung generiert.
Der Testprozess ist recht 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 komprimierende Datei... ok
Initialisiere das 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
Komprimiere... erledigt in 32,6s
Speichere das Archiv... ok
$ ./f5ar -u dogs/dogs.f5ar entpackt
Initialisiere das Archiv... ok
Lese die Archivdatei... ok
Fülle das Archiv mit Dateien... erledigt in 1,2s
Dekomprimiere... erledigt in 17,5s
Schreibe extrahierte Daten... ok
$ sha1sum binary_data entpackt
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 entpackt
$ du -sh dogs/
563M dogs/Oder ein Screenshot für die Liebhaber
Wie zu sehen ist, haben wir aus den ursprünglichen 633 + 36 == 669 Megabyte Daten auf der Festplatte eine angenehmere Größe von 563 erreicht, was uns einen Kompressionsfaktor von etwa 1,188 gibt. Diese radikale Differenz erklärt sich durch die sehr geringen Verluste, ähnlich denen, die bei der Optimierung von JPEG-Dateien mit klassischen Methoden (wie tinyjpg) auftreten. Natürlich wird bei der Verwendung von steganografischer Kompression die Information nicht einfach „verloren“, sondern für die Kodierung anderer Daten genutzt. Darüber hinaus ist die Anzahl der „optimierten“ Koeffizienten durch die Verwendung von F5 deutlich geringer als bei herkömmlicher Optimierung.
Egal welche Modifikationen vorgenommen wurden, für das Auge sind sie absolut nicht bemerkbar. Unter dem Spoiler unten kann der Leser den Unterschied sowohl visuell als auch durch das Abziehen der Werte der geänderten Komponente vom Original bewerten (je gedämpfter die Farbe, desto geringer ist der Unterschied):
Links zu Bildern, die nicht auf habrastorage gepasst haben
Original —
Modifiziert —
Unterschied —
Abschließend
Ich hoffe, ich konnte die Leser überzeugen, dass solche Methoden möglich und legitim sind. Dennoch kann der Kauf einer Festplatte oder eines zusätzlichen Kanals (für die Netzwerkübertragung) weit einfacher erscheinen als der Versuch, auf diese Weise zu sparen. Einerseits stimmt das, extensives Wachstum ist oft einfacher und zuverlässiger. Andererseits sollte man nicht das intensive Wachstum vergessen. Schließlich gibt es keine Garantie, dass man morgen einfach in ein Geschäft gehen und eine weitere Festplatte mit tausend Terabyte kaufen kann; stattdessen kann man immer auf die zurückgreifen, die bereits zu Hause liegen.
->
Quelle: habr.com
