Sparar utrymme på hårddisken med hjälp av steganografi

När vi talar om steganografi, föreställer sig folk terrorister, pedofiler, spioner, eller i bästa fall kryptoanarkister och andra forskare. Och det är sant, vem skulle annars behöva gömma någonting från yttre ögon? Vad kan egentligen en vanlig människa ha för nytta av detta?

Det visar sig att det finns en viss nytta. Just därför kommer vi idag att komprimera data med hjälp av steganografiska metoder. I slutet kommer läsaren till och med att kunna använda sina värdefulla JPEG-fotografier för att öka antalet lediga gigabyte på filsystemet.

Vad?

Om läsaren minns, så är steganografi en slags märkliga algoritmer som möjliggör att gömma en informations närvaro inom en annan. Med enklare ord: bild + fil == ungefär samma bild, men inte riktigt (det kan vara vad som helst istället för bilder, men de är oftast lättare att förstå). Samtidigt ska det inte finnas något enkelt sätt att avgöra om det finns något inuti eller inte.

Men om det inte går att särskilja det ena från det andra, finns det då någon skillnad? Ur ett konsumentperspektiv bryr sig inte användaren om matematisk noggrannhet (reflekterad av en specifik uppsättning bitar), utan enbart om vad de uppfattar.

Till exempel, låt oss titta på tre bilder av en söt hund:

Varning, JPEG!

Trots den kolossala skillnaden i storlek är det få som skulle 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 (enligt min åsikt) kan likställas.

Själva denna princip är länge gammal och har i många år aktivt utnyttjats i metoder för informationstryck med förlust. Men att bryta ner är inte att bygga, vi är intresserade av en mer avancerad sida av frågan. Är det möjligt att integrera extra information av storlek N i en fil så att dess storlek ökar med M < N, och att ändringar inte märks av användaren?

Självklart är det möjligt. Men det är värt att göra några förbehåll direkt:

• För det första måste metoden vara universell och ge ett positivt resultat på de flesta ingångar. Det vill säga, i genomsnitt bör det ske en faktisk minskning av den lagrade mängden information för godtycklig ingång. "I genomsnitt" innebär att motsatta fall kan förekomma, men de bör inte dominera.
• För det andra ska storleken på den komprimerade containern innan informationen integreras vara större än den komprimerade motsvarigheten av den modifieringen. Att bara integrera en massa bitar i BMP-bilder med LSB-metoden är inte steganografisk komprimering, eftersom den ursprungliga bilden troligen kommer att vara betydligt mindre efter att ha körts genom någon DEFLATE.
• För det tredje måste resultaten jämföras med redan komprimerade data som använts med klassiska metoder. Detta gör det möjligt att eliminera den probabilistiska effekten av deras överflöd och genomföra en mer effektiv komprimering i allmänhet.

Var?

Användningen av steganografi innebär att vi, utöver den information som ska komprimeras, behöver containrar där den kommer att integreras. Den maximala mängden information som kan integreras beror till stor del på specifika egenskaper, men ju fler det finns, desto enklare går det att skala. Därför bör formatet på containrarna vara allmänt, så att användaren har tillräckligt många för att få någon nytta av "komprimeringsprocessen".

I det här sammanhanget är grafiska, ljud- och videofiler goda kandidater. Men på grund av mångfalden av olika format och codecs kvarstår praktiskt taget ett ganska begränsat antal alternativ att välja mellan.

Med detta i åtanke har jag valt JPEG. Det används av nästan alla, och är mycket vanligt både för privata och affärsmässiga ändamål, och har blivit nästan de facto-formatet för de flesta bilder.

H̶u̶r̶?

Sedan följer omkringliggande och tekniska diagram och beskrivningar utan några större förklaringar, så de som vill kan hoppa över dem och gå vidare till avsnittet "Högteknologi".

Gemensamma drag

För att integrera data någonstans måste man först bestämma var. Det kan finnas hur många olika fotografier som helst på filsystemet, bland vilka användaren kanske bara vill använda några. Den uppsättning av containrar som önskas kommer vi att kalla bibliotek.

Det bildas i två fall: före komprimering och före dekomprimering. I det första fallet kan man enkelt använda en uppsättning filnamn (eller bättre, ett reguljärt uttryck för dem), men i det andra fallet krävs något mer pålitligt: användaren kan kopiera och flytta dem inom filsystemet, vilket gör det svårt att korrekt identifiera dem. Därför behöver man lagra deras hash (md5 räcker) efter att alla modifikationer har genomförts.

Inledande sökningar med reguljära uttryck är meningslösa att utföra på hela filsystemet, det räcker att ange en viss rotmapp. Dit kommer en speciell arkivfil att sparas, som kommer att innehålla dessa hashvärden, tillsammans med annan metainformation som är nödvändig för framtida återställning av den komprimerade informationen.

Allt detta är lika tillämpligt på vilken implementering som helst av något steganografiskt datakomprimeringsalgoritm. Själva processerna för komprimering och återställande av data kan kallas paketering och unpacking.

F5

Nu när det är klart vad vi gör och varför, är det dags att beskriva själva algoritmen för att uppnå målet. Låt oss påminna oss om processen för kodning av en JPEG-fil (tack Wikipedia för Bauman National Library):

När man ser på den, är det bra att omedelbart göra några anmärkningar:

• Storleken på en JPEG-fil kan anses vara optimal, även utan att försöka komprimera den med något WinRAR;
• Det som kan ändras är endast den lagrade informationen (den som är output från den diskreta cosinustransformationen, DCT), för att säkerställa en acceptabel prestanda.
• För att inte förlora data i märkbara användarindustrier krävs det att göra minimiändringar i varje enskild bild;

Under sådana förhållanden finns det en hel familj algoritmer som man kan bekanta sig med i denna bra presentation. Den mest avancerade av dem är algoritmen F5 av Andreas Westfeld, som arbetar med DCT-koefficienterna för ljusstyrkekomponenten (den mänskliga ögat är minst känsligt för just dessa förändringar). Dess allmänna schema när det gäller att arbeta med en existerande JPEG-fil visas med följande diagram:

Block F5 använder en avancerad inbäddningsteknik baserad på matrisprogrammering. Mer om det och själva algoritmen kan läsaren ta del av via länken ovan, men vi är främst intresserade av det faktum att färre ändringar kan göras med hjälp av den ju större storlek på den använda containern, och för att genomföra själva algoritmen krävs endast enkla (de)kodningsoperationer av Huffman och RLE.

Själva ändringarna görs på heltalskoefficienterna och handlar om att minska deras absolutvärde med ett, vilket gör det möjligt att använda F5 för datakomprimering. Anledningen är att en minskad koefficient i absolutvärde troligtvis kommer att ta upp färre bitar efter Huffman-kodning på grund av den statistiska fördelningen av värden i JPEG.

Vid bildandet av nollor (så kallade förkortningar) kommer den lagrade informationen att minska med dess storlek, eftersom den tidigare oberoende koefficienten blir en del av den kodade RLE-sekvensen av nollor:

Modifieringar

Dataskydd och komprimering är ortogonala uppgifter, så den hemliga lösenordspermutationen från den ursprungliga algoritmen kan ignoreras. Dessutom behöver vi exakt veta hur man extraherar data, så all nödvändig information (vilka containrar som användes, i vilken ordning osv.) bör skrivas ner i en separat fil och vara tillgänglig för fri läsning av arkivprogrammet.

Den ursprungliga algoritmen är avsedd för överföring av hemliga meddelanden, så den arbetar endast med en container åt gången, och förutsätter att användaren själv kommer att dela upp den i delar om behovet uppstår. Dessutom, vid oberoende inbäddning i varje container kommer det krävas att man i förväg vet hur många bitar data som ska placeras i varje. Därför är det klokt att sammanfoga koefficienterna för varje element i biblioteket till en stor abstrakt och arbeta med den enligt den ursprungliga algoritmen.

Eftersom den ursprungliga F5 tillåter användning av upp till 12% av containerns storlek kommer en sådan modifiering också att öka den maximala kapaciteten: "upp till 12%" av hela bibliotekets storlek är större än eller lika med summan av "upp till 12%" av vart och ett av dess element.

Den kodade övergripande schemat ser ut som följer:

Algoritmen

Nu är det dags att beskriva själva algoritmen från början till slut, så att läsaren inte hålls i okunnighet:

• Användaren definierar de binära komprimerbara data M och biblioteket L med hjälp av reguljära uttryck och den sökande rotkatalogen;
• I ordning på FS bildar bibliotekelementen MC:
  • Från filens data dekodas en serie koefficienter C;
  • MC <- MC | C;
• Parametern k definieras utifrån det fruktansvärda olikhetsvillkoret: |M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1);
• Det tas successivt n = (1 << k) - 1 av de lägsta bitarna av de icke-noll element från MC och skrivs ner i a:
  • Den magiska hashfunktionen f, som avbildar ett n-bitar ord a till ett k-bitar s;
  • Om s == 0, betyder att ingen ändring behövs och algoritmen går vidare till nästa koefficienter;
  • Minska det absoluta värdet av koefficienten som ansvarar för s-e biten i ordet a;
  • Om minskningen resulterade i en förkortning (koefficienten blev 0), upprepa steget från början;
• Alla koefficienter kodas med RLE och Huffman, skrivs till de ursprungliga filerna;
• Parametern k skrivs till arkivfilen;
• För varje fil L, i ordning av deras ursprungliga placering, beräknas en MD5-hash och skrivs till arkivfilen.

Högteknologier

En naiv form av algoritmen och implementeringen på andra högre nivåer (särskilt de med skräpsamling) skulle ge förfärlig prestanda, så jag implementerade alla dessa komplexiteter i rent C och genomförde en rad optimeringar både för exekveringshastighet och minnesanvändning (ni kan inte föreställa er hur mycket dessa bilder väger utan komprimering, även till DCT). Men även då lämnade exekveringshastigheten mycket att önska i början, så jag kommer inte att beskriva hela processen och de använda metoderna.

Korsplattformsenhet har uppnåtts genom att använda en kombination av biblioteken libjpeg, pcre och tinydir, varav jag tackar dem. Som standard kompileras allt genom en vanlig make, så Windows-användare vill installera Cygwin eller hantera Visual Studio och biblioteken själva.

Implementeringen är tillgänglig som ett kommandoradsverktyg och ett bibliotek. De som vill veta mer om hur man använder det senaste kan läsa README-filen i repositoryt på GitHub, länken till vilken jag kommer att bifoga i slutet av inlägget. Låt oss här gå vidare till beskrivningen och demonstration av funktionaliteten.

Hur man använder?

Var försiktig. Använda bilder kan flyttas, döpas om och kopieras efter önskemål. Dock bör man vara oerhört försiktig och inte på något sätt förändra innehållet. Att ändra en enda bit kommer att leda till att hashen bryts och informationen inte kan återställas.

Låt oss säga att vi efter kompileringen har fått den körbara filen f5ar. Vi kan analysera storleken på biblioteket för att beräkna dess användningsmöjligheter med hjälp av flaggan -a: . /f5ar -a [sökmapp] [Perl-kompatibelt reguljärt uttryck]. Packningen utförs med kommandot . /f5ar -p [sökmapp] [Perl-kompatibelt reguljärt uttryck] [packad fil] [arkivnamn], och uppackning sker med hjälp av . /f5ar -u [arkivfil] [återställt filnamn].

Demonstration av funktionen.

För att visa metodens effektivitet har jag laddat upp en samling av 225 helt gratis hundbilder från tjänsten Unsplash. Varje bild har något högre kvalitet än vanliga användarfotografier, men ändå. Varje bild har omkodats med hjälp av libjpeg för att minska påverkan av bibliotekets kodningsspecifikationer på den totala storleken. För att exemplifiera det sämsta exemplet på komprimerade data har en slumpmässig fil på 36 meter (lite mer än 5 % av den totala storleken) skapats med jämn fördelning 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
Läser komprimeringsfil... okej
Initierar arkivet... okej
Analyserar bibliotekets kapacitet... klart på 16.8s
Upptäckte något guaranteed kapacitet på 48439359 byte
Upptäckte möjlig kapacitet på upp till 102618787 byte
Komprimerar... klart på 32.6s
Sparar arkivet... okej

$ ./f5ar -u dogs/dogs.f5ar unpacked
Initierar arkivet... okej
Läser arkivfilen... okej
Fyller arkivet med filer... klart på 1.2s
Avkomprimerar... klart på 17.5s
Skriver ut data... okej

$ sha1sum binary_data unpacked
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 binary_data
ba7ade4bc77881ab463121e77bbd4d41ee181ae9 unpacked
$ du -sh dogs/
563M dogs/

Eller med en skärmdump för entusiasterna.

Som det framgår, har vi från de ursprungliga 633 + 36 == 669 megabyte data på hårddisken kommit ner till mer tilltalande 563, vilket ger oss en komprimeringskoefficient på ~1,188. Denna radikala skillnad förklaras av extremt små förluster, liknande dem som uppnås vid optimering av JPEG-filer med klassiska metoder (som tinyjpg). Naturligtvis, med hjälp av steganografisk komprimering förloras informationen inte bara utan används för att koda andra data. Dessutom är antalet "optimerade" koefficienter genom användning av F5 mycket mindre än vid traditionell optimering.

Oavsett vilka modifieringar som görs, är de helt osynliga för ögat. Under spoileravsnittet nedan kan läsaren bedöma skillnaden både visuellt och genom att subtrahera värdena för den ändrade komponenten från originalet (ju mer dämpad färgen är, desto mindre skillnad):

Länkar till bilder som inte fick plats på habrastorage

Original — https://i.ibb.co/wNDLNcZ/1.jpg
Modifierad — https://i.ibb.co/qWvpfFM/1.jpg
Skillnad — https://i.ibb.co/2ZzhHfD/diff.jpg

Avslutande

Jag hoppas att jag har kunnat övertyga läsaren om att sådana metoder är möjliga och har rätt att existera. Samtidigt kan det verka mycket enklare att köpa en hårddisk eller en extra kanal (för nätverksöverföring) än att försöka spara på det här sättet. Å ena sidan är det verkligen så, att extensiv utveckling ofta är enklare och mer pålitlig. Men å andra sidan bör man inte glömma den intensiva aspekten. Det finns ju inga garantier för att man i morgon kan gå till affären och köpa en ny hårddisk på tusen terabyte, men de som redan finns hemma kan alltid användas.

-> GitHub

Källa: habr.com