När vi talar om steganografi tänker folk på terrorister, pedofiler, spioner eller i bästa fall kryptoanarkister och andra vetenskapsmän. Och egentligen, vem mer kan behöva Dölj något från yttre ögon? Vad kan vara fördelen med detta för en vanlig människa?
Det visar sig att det finns en. Det är därför vi idag kommer att komprimera data med steganografimetoder. Och i slutändan kommer läsaren till och med att kunna använda sina värdefulla fotoarkiv i JPEG för att öka antalet lediga gigabyte i filsystemet.
Vad?
Om läsaren kommer ihåg är steganografi sådana konstiga algoritmer som gör det möjligt att dölja närvaron av en information inuti en annan. På ännu enklare språk: bild + fil == ungefär samma bild, men inte riktigt (istället för bilder kan det finnas vad som helst, men oftast är allt tydligare i dem). Det borde inte finnas ett enkelt sätt att avgöra om det finns något inuti eller inte.
Men om det ena inte kan skiljas från det andra, finns det någon skillnad alls? Ur konsumentens synvinkel bryr sig användaren inte om den matematiska precisionen (reflekteras av en viss uppsättning bitar), bara vad som uppfattas av honom.
Låt oss till exempel titta på tre bilder av en söt hund:
Akta dig, JPEG!
Trots den enorma skillnaden i storlek kommer få människor att välja den tredje versionen. Å andra sidan är skillnaden mellan de två första fotografierna inte så märkbar, och mängden information i dem (ur min synvinkel) kan vara lika stor.
Denna princip i sig är redan gammal och har aktivt utnyttjats av förlustbaserade informationskomprimeringsmetoder i många år. Men att bryta är inte att bygga, vi är intresserade av den mer avancerade sidan av frågan. Är det möjligt att bädda in ytterligare storleksinformation N till filen så att dess storlek ökar med M < N, men ändringarna var inte märkbara för användaren?
Såklart du kan. Men det är värt att göra ett par reservationer direkt:
- För det första måste metoden vara universell och ge ett positivt resultat på de flesta indata. Det vill säga, i genomsnitt, för en slumpmässig inmatning bör det finnas en faktisk minskning av mängden lagrad information. "I genomsnitt" betyder att motsatsen kan förekomma, men inte bör dominera.
- För det andra måste storleken på den komprimerade behållaren före inbäddning av information vara större än dess modifiering komprimerad på liknande sätt. Att helt enkelt bädda in ett gäng bitar i BMP-bilder med hjälp av LSB-metoden är inte steganografisk komprimering, eftersom den ursprungliga bilden troligen kommer att vara märkbart mindre efter att ha körts genom någon form av DEFLATE.
- För det tredje måste resultatet utföras och jämföras med avseende på data som redan komprimerats med klassiska metoder. Detta kommer att ta bort den probabilistiska effekten av skillnader i deras redundans och ge mer effektiv komprimering i det allmänna fallet.
Var?
Användningen av steganografi innebär att vi, förutom den komprimerade informationen, kommer att behöva behållare där den kommer att bäddas in. Den maximala mängden inbäddad information beror till stor del på enskilda egenskaper, men det är mycket lättare att skala med deras antal. Därför måste behållarformatet vara gemensamt så att användaren har tillräckligt med dem för att få någon nytta av "komprimeringsprocessen".
I detta sammanhang är grafik-, ljud- och videofiler bra kandidater. Men på grund av mångfalden av olika format, codecs, etc., har vi i praktiken ett val mellan inte så många alternativ.
Med tanke på allt detta föll mitt val på JPEG. Nästan alla har det, det används flitigt för både personliga och affärsändamål, och är nästan de facto-formatet för de flesta bilder.
Det beror på?
Därefter finns nära- och tekniska diagram och beskrivningar utan mycket förklaring, så de som är intresserade kan hoppa över dem genom att rulla till avsnittet "Högteknologi".
Vanliga funktioner
För att bädda in data någonstans måste du först bestämma var. Det kan finnas hur många olika fotografier som helst på filsystemet, av vilka användaren kanske bara vill använda ett fåtal. Vi kommer att kalla en sådan önskad uppsättning behållare för ett bibliotek.
Det bildas i två fall: före kompression och före dekompression. I det första fallet kan du helt enkelt använda en uppsättning filnamn (eller ännu bättre, ett reguljärt uttryck för dem) av filer, men i det andra krävs något mer tillförlitligt: användaren kan kopiera och flytta dem inom filsystemet , vilket förhindrar att de identifieras korrekt. Därför är det nödvändigt att lagra deras hash (md5 räcker) efter att alla ändringar har gjorts.
I det här fallet är det ingen idé att utföra den första sökningen med ett reguljärt uttryck i hela filsystemet, det räcker med att ange en viss rotkatalog. En speciell arkivfil kommer att sparas i den, som kommer att innehålla dessa hash, tillsammans med annan metainformation som behövs för efterföljande återställning av komprimerad information.
Allt detta gäller lika för alla implementeringar av alla steganografiska datakomprimeringsalgoritmer. Själva processerna för datakomprimering och återställning kan kallas packning och uppackning.
F5
Nu när det har blivit klart vad vi gör och varför återstår det att beskriva algoritmen för att nå målet. Låt oss komma ihåg processen att koda en JPEG-fil (tack vare wikin för Bauman National Library):
När man tittar på det är det bättre att omedelbart göra några kommentarer:
- Storleken på en JPEG-fil kan anses vara optimal utan att ens försöka komprimera den med någon form av Winrar;
- Endast den lagrade informationen (den som matas ut från den diskreta cosinustransformen, DCT) kan modifieras för att tillhandahålla åtminstone acceptabel prestanda.
- För att inte förlora data i industriell skala som är märkbar för användaren är det nödvändigt att göra ett minimum av ändringar av varje enskild bild;
En hel familj av algoritmer passar dessa villkor, som du kan bekanta dig med . Den mest avancerade av dem är algoritmen av Andreas Westfeld, som arbetar med DCT-koefficienterna för ljushetskomponenten (det mänskliga ögat är minst känsligt för dess förändringar). Dess allmänna layout när du arbetar med en befintlig JPEG-fil visas enligt följande:
F5-blocket använder en avancerad inbäddningsteknik baserad på matriskodning. Läsaren kan lära sig mer om den och själva algoritmen på länken ovan, men vi är i första hand intresserade av att man med dess hjälp kan göra ju färre ändringar när man bäddar in samma mängd information, desto större är behållaren som används. , och för att utföra Algoritmen behöver bara utföra enkla Huffman och RLE (av)kodningsoperationer.
Ändringarna i sig görs till heltalskoefficienter och går ner till att reducera deras absoluta värde med ett, vilket gör att man generellt sett kan använda F5 för datakomprimering. Poängen är att den reducerade koefficienten i absolut värde med största sannolikhet kommer att uppta färre bitar efter Huffman-kodning på grund av den statistiska fördelningen av värden i JPEG.
I fallet med bildandet av en nolla (den så kallade reduktionen), kommer antalet lagrad information att minskas med dess storlek, eftersom den tidigare oberoende koefficienten kommer att bli en del av den RLE-kodade sekvensen av nollor:
modifieringar
Dataskydd och komprimering är ortogonala problem, så den hemliga lösenordspermutationen från den ursprungliga algoritmen kan försummas. Dessutom måste vi veta exakt hur man extraherar data, så all information som är nödvändig för detta (vilka behållare användes, i vilken ordning, etc.) bör registreras i en separat fil och vara öppen för fri läsning av arkivet.
Den ursprungliga algoritmen är utformad för att sända hemliga meddelanden, så den fungerar med endast en behållare åt gången, förutsatt att användaren själv delar upp den i delar om det behövs, om någon. Dessutom, när du är inbäddad oberoende i varje behållare, måste du veta i förväg hur många bitar av data som ska läggas i varje. Därför bör koefficienterna för varje element i biblioteket kombineras till en abstrakt stor och arbetas med den enligt den ursprungliga algoritmen.
Eftersom den ursprungliga F5 tillåter upp till 12% av behållarstorleken, kommer denna modifiering också att öka den maximala kapaciteten: "upp till 12%" av storleken på hela biblioteket är större än eller lika med summan av "upp till 12% " från vart och ett av dess element.
Det kodifierade allmänna systemet är följande:
Själva algoritmen
Nu är det dags att beskriva själva algoritmen från början till slut, för att inte hålla läsaren i mörker:
- Användaren definierar den binära komprimerbara datan M och biblioteket L genom att använda ett reguljärt uttryck och en sökrotkatalog;
- I den ordning de visas på FS bildar bibliotekselementen MC:n:
- En serie koefficienter C avkodas från fildata;
- MC <- MC | C;
- Parametern k bestäms baserat på den fruktansvärda ojämlikheten:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Tagen nästa
n = (1 << k) - 1minst signifikanta bitar av icke-noll element från MC och skrivna tilla:- Den magiska hashfunktionen övervägs
f, som representerar ett n-bitars ordatill k-bits; - Om
s == 0, då finns det inget behov av att ändra något och algoritmen går vidare till nästa koefficient; - Minska det absoluta värdet av koefficienten som ansvarar för
s-hej bet i ordeta; - Om som ett resultat av minskningen en minskning inträffar (koefficienten blir 0), upprepa sedan steget från början;
- Den magiska hashfunktionen övervägs
- Alla koefficienter är kodade av RLE och Huffman, skrivna till källfilerna;
- Parametern k skrivs till arkivfilen;
- En MD5-hash beräknas från varje fil L i ordningsföljden för deras ursprungliga plats och skrivs till arkivfilen.
Högteknologisk
Den naiva formen av algoritmen och implementeringar på andra högnivåspråk (särskilt med sophämtningsspråk) skulle ge fruktansvärda prestanda, så jag implementerade alla dessa komplexiteter i ren C och genomförde ett antal optimeringar både när det gäller exekveringshastighet och minne (du har ingen aning om hur mycket dessa bilderna väger utan komprimering även före DCT). Men trots det lämnade exekveringshastigheten till en början mycket att önska, så jag kommer inte att beskriva hela processen och metoderna som används.
Cross-platform uppnås med en kombination av libjpeg, pcre och tinydir bibliotek, vilket vi tackar dem för. Som standard kompileras allt via normal make, så Windows-användare vill installera lite Cygwin för sig själva, eller hantera Visual Studio och bibliotek på egen hand.
Implementeringen är tillgänglig i form av ett konsolverktyg och bibliotek. Den som är intresserad kan ta reda på mer om att använda den senare i readme i arkivet på Github, länken som jag kommer att bifoga i slutet av inlägget. Och här går vi vidare till en beskrivning och demonstration av arbetet.
Hur man använder
Försiktigt. Använda bilder kan flyttas, byta namn och kopieras efter önskemål. Du bör dock vara extremt försiktig och inte ändra innehållet på något sätt. Att ändra en bit kommer att störa hashen och göra det omöjligt att återställa informationen.
Antag att vi efter kompileringen får den körbara filen f5ar. Du kan analysera storleken på biblioteket för att beräkna möjligheterna för dess användning med hjälp av flaggan -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Packning görs av teamet ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], och packa upp med hjälp av ./f5ar -u [файл архива] [имя восстановленного файла].
Demonstration av arbete
För att visa metodens effektivitet laddade jag upp en samling av 225 helt gratis foton av hundar från tjänsten . Var och en av dem har en något högre kvalitet än vanliga användarbilder, men ändå. Var och en av dem kodades om med libjpeg för att neutralisera effekten av bibliotekets kodningsfunktioner på den övergripande storleken. För att indikera det värsta exemplet på komprimerbar data, genererades en slumpmässigt 36-meters (något mer än 5% av den totala storleken) enhetligt distribuerad fil med hjälp av dd.
Testprocessen är ganska enkel:
$ 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/Eller en skärmdump för fans
Som du kan se, från de ursprungliga 633 + 36 == 669 megabyte data på hårddisken, slutade vi med en snyggare 563, vilket gav oss ett komprimeringsförhållande på ~1,188. Denna radikala skillnad förklaras av extremt små förluster, liknande de som erhålls vid optimering av JPEG-filer med klassiska metoder (som tinyjpg). Naturligtvis, när du använder steganografisk komprimering, "försvinner" information inte bara, utan används för att koda andra data. Dessutom är antalet "optimerade" koefficienter på grund av användningen av F5 mycket mindre än med traditionell optimering.
Vilka ändringar det än finns är de absolut osynliga för ögat. Under spoilern nedan kan läsaren utvärdera skillnaden både med ögat och genom att subtrahera värdena för den ändrade komponenten från originalet (ju mer dämpad färg, desto mindre skillnad):
Länkar till bilder som inte får plats på habrastorage
Original -
Ändrad -
Skillnad -
I stället för en slutsats
Jag hoppas att jag lyckades övertyga läsaren om att sådana metoder är möjliga och har rätt till liv. Att köpa en hårddisk eller en extra kanal (för nätverksöverföring) kan dock verka som ett mycket enklare alternativ än att försöka spara pengar på detta sätt. Å ena sidan är detta sant, omfattande utveckling är ofta enklare och mer tillförlitlig. Men å andra sidan ska vi inte glömma det intensiva. Det finns trots allt inga garantier för att du imorgon kommer att kunna komma till butiken och köpa dig ytterligare en tusen terabyte hårddisk, men du kan alltid använda de du redan har liggandes hemma.
->
Källa: www.habr.com