Ko govorimo o steganografiji, ljudje pomislimo na teroriste, pedofile, vohune ali v najboljšem primeru na kriptoanarhiste in druge znanstvenike. In res, kdo bi še potreboval skriti nekaj od zunanjih oči? Kakšna bi lahko bila korist od tega navadnemu človeku?
Izkazalo se je, da obstaja ena. Zato bomo danes stiskali podatke s steganografskimi metodami. In na koncu bo bralec lahko celo uporabil svoje dragocene arhive fotografij v JPEG za povečanje števila brezplačnih gigabajtov v datotečnem sistemu.
Kaj?
Če se bralec spomni, so steganografija tako čudni algoritmi, ki omogočajo skrivanje prisotnosti ene informacije v drugi. V še enostavnejšem jeziku: slika + datoteka == približno enaka slika, vendar ne povsem (namesto slik je lahko karkoli, vendar je na njih običajno vse bolj jasno). Ne bi smelo biti preprostega načina za ugotavljanje, ali je kaj notri ali ne.
Če pa enega ni mogoče ločiti od drugega, ali sploh obstaja razlika? Z vidika potrošnika uporabniku ni pomembna matematična natančnost (ki se odraža v določenem nizu bitov), temveč le tisto, kar sam zazna.
Na primer, poglejmo tri slike ljubkega psa:
Pozor, JPEG!
Kljub veliki razliki v velikosti se bo malokdo odločil za tretjo različico. Po drugi strani pa razlika med prvima dvema fotografijama ni tako opazna, količina informacij pa je (z mojega vidika) lahko enaka.
To načelo je že staro in se že vrsto let aktivno izkorišča pri metodah stiskanja informacij z izgubo. Toda razbijanje ni gradnja; zanima nas naprednejša plat vprašanja. Ali je mogoče vdelati dodatne podatke o velikosti N v datoteko, tako da se njena velikost poveča za M < N, vendar spremembe niso bile opazne za uporabnika?
Seveda lahko. Vendar je vredno takoj narediti nekaj rezervacij:
- Prvič, metoda mora biti univerzalna in dati pozitiven rezultat na večini vhodnih podatkov. To pomeni, da bi moralo pri naključnem vnosu dejansko priti do zmanjšanja količine shranjenih informacij. »V povprečju« pomeni, da se lahko zgodi nasprotno, vendar ne sme prevladovati.
- Drugič, velikost stisnjenega vsebnika pred vdelavo informacij mora biti večja od njegove modifikacije, stisnjene na podoben način. Enostavna vdelava množice bitov v slike BMP z metodo LSB ni steganografska kompresija, saj bo izvirna slika najverjetneje opazno manjša, če jo preženete skozi nekakšen DEFLATE.
- Tretjič, rezultat je treba izvesti in primerjati glede na podatke, ki so že stisnjeni s klasičnimi metodami. To bo odpravilo verjetnostni učinek razlik v njihovi redundanci in zagotovilo učinkovitejše stiskanje v splošnem primeru.
Kje?
Uporaba steganografije pomeni, da bomo poleg stisnjenih informacij potrebovali vsebnike, v katere bodo le-te vgrajene. Največja količina vgrajenih informacij je v veliki meri odvisna od posameznih lastnosti, vendar je veliko lažje skalirati z njihovim številom. Zato mora biti oblika vsebnika običajna, tako da jih ima uporabnik dovolj, da lahko izkoristi kakršno koli korist od postopka »stiskanja«.
V tem kontekstu so grafične, zvočne in video datoteke dobri kandidati. Toda zaradi pestrosti različnih formatov, kodekov ipd. nam v praksi preostane izbira med malo možnostmi.
Glede na vse to je moja izbira padla na JPEG, saj ga imajo skoraj vsi, uporablja se tako v osebne kot poslovne namene in je skoraj de facto format za večino slik.
Odvisno?
Sledijo bližnji in tehnični diagrami ter opisi brez večjih pojasnil, tako da jih lahko zainteresirani preskočijo tako, da se pomaknejo na razdelek »Visoke tehnologije«.
Skupne lastnosti
Če želite nekam vdelati podatke, morate najprej določiti, kam. V datotečnem sistemu je lahko poljubno število različnih fotografij, od katerih bo uporabnik morda želel uporabiti le nekaj. Tak želeni nabor vsebnikov bomo imenovali knjižnica.
Nastane v dveh primerih: pred kompresijo in pred dekompresijo. V prvem primeru lahko preprosto uporabite nabor imen datotek (ali še bolje, regularni izraz zanje) datotek, v drugem pa je potrebno nekaj bolj zanesljivega: uporabnik jih lahko kopira in premika znotraj datotečnega sistema. , s čimer prepreči njihovo pravilno identifikacijo. Zato je treba po vseh spremembah shraniti njihove zgoščene vrednosti (zadostuje md5).
V tem primeru nima smisla izvajati začetnega iskanja z regularnim izrazom po celotnem datotečnem sistemu, dovolj je določiti določen korenski imenik. Vanj bo shranjena posebna arhivska datoteka, ki bo vsebovala te zgoščene vrednosti, skupaj z drugimi metapodatki, potrebnimi za kasnejšo obnovitev stisnjenih informacij.
Vse to velja enako za vsako izvedbo katerega koli algoritma za stiskanje steganografskih podatkov. Same procese stiskanja in obnavljanja podatkov lahko imenujemo pakiranje in razpakiranje.
F5
Zdaj, ko je postalo jasno, kaj počnemo in zakaj, je ostalo še opisati algoritem za dosego cilja. Spomnimo se postopka kodiranja datoteke JPEG (zahvaljujoč wikiju Baumanove nacionalne knjižnice):
Če pogledamo na to, je bolje takoj dati nekaj komentarjev:
- Velikost datoteke JPEG se lahko šteje za optimalno, ne da bi jo poskušali stisniti z nekakšnim Winrarjem;
- Samo shranjene informacije (tiste, ki so izhodne iz diskretne kosinusne transformacije, DCT) je mogoče spremeniti, da zagotovijo vsaj sprejemljivo zmogljivost.
- Da ne bi izgubili podatkov v industrijskem obsegu, opaznem za uporabnika, je treba narediti najmanj sprememb na vsaki posamezni sliki;
Tem pogojem ustreza cela družina algoritmov, s katerimi se lahko seznanite . Najnaprednejši med njimi je algoritem Andreasa Westfelda, ki dela s koeficienti DCT komponente svetlosti (človeško oko je najmanj občutljivo na njene spremembe). Njegova splošna postavitev pri delu z obstoječo datoteko JPEG je prikazana takole:
Blok F5 uporablja napredno tehniko vdelave, ki temelji na matričnem kodiranju. Več o njem in samem algoritmu lahko bralec izve na zgornji povezavi, nas pa zanima predvsem dejstvo, da lahko z njegovo pomočjo naredite manj sprememb pri vdelavi enake količine informacij, večja je velikost uporabljenega vsebnika. , in za izvedbo algoritma je treba izvesti le enostavne operacije (de)kodiranja Huffman in RLE.
Same spremembe so narejene na celih koeficientih in se zmanjšajo na zmanjšanje njihove absolutne vrednosti za eno, kar na splošno omogoča uporabo F5 za stiskanje podatkov. Bistvo je, da bo zmanjšani koeficient v absolutni vrednosti najverjetneje zasedel manj bitov po Huffmanovem kodiranju zaradi statistične porazdelitve vrednosti v JPEG.
V primeru oblikovanja ničle (tako imenovana redukcija) se bo število shranjenih informacij zmanjšalo za njeno velikost, saj bo prejšnji neodvisni koeficient postal del RLE kodiranega zaporedja ničel:
Spremembe
Zaščita podatkov in stiskanje sta pravokotna problema, zato je mogoče zanemariti permutacijo tajnega gesla iz izvirnega algoritma. Poleg tega moramo natančno vedeti, kako ekstrahirati podatke, zato je treba vse informacije, ki so za to potrebne (kateri vsebniki so bili uporabljeni, v kakšnem vrstnem redu itd.), zabeležiti v ločeni datoteki in jih arhivarju omogočiti prosto branje.
Izvirni algoritem je zasnovan za prenos skrivnih sporočil, zato deluje le z enim vsebnikom naenkrat, ob predpostavki, da ga bo uporabnik sam razdelil na dele, če bo to potrebno, če sploh. Poleg tega boste morali pri vdelavi neodvisno v vsak vsebnik vnaprej vedeti, koliko bitov podatkov vstaviti v vsakega. Zato je treba koeficiente vsakega elementa knjižnice združiti v eno abstraktno veliko in z njo delati v skladu z izvirnim algoritmom.
Ker prvotni F5 dovoljuje do 12 % velikosti vsebnika, bo ta sprememba povečala tudi največjo zmogljivost: "do 12 %" velikosti celotne knjižnice je večje ali enako vsoti "do 12% " iz vsakega od njegovih elementov.
Kodificirana splošna shema je naslednja:
Sam algoritem
Zdaj je čas, da opišemo sam algoritem od začetka do konca, da ne obdržimo bralca v temi:
- Uporabnik definira binarne stisljive podatke M in knjižnico L z uporabo regularnega izraza in iskalnega korenskega imenika;
- V vrstnem redu, kot so prikazani na FS, elementi knjižnice tvorijo MC:
- Niz koeficientov C se dekodira iz podatkov datoteke;
- MC <- MC | C;
- Parameter k je določen na podlagi strašne neenakosti:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Posneto naslednje
n = (1 << k) - 1najmanj pomembni biti neničelnih elementov iz MC in zapisania:- Upoštevana je čarobna zgoščevalna funkcija
f, ki predstavlja n-bitno besedoana k-bits; - če
s == 0, potem ni treba ničesar spreminjati in algoritem preide na naslednje koeficiente; - Zmanjšajte absolutno vrednost koeficienta, odgovornega za
s-hej malo v besedia; - Če zaradi zmanjšanja pride do zmanjšanja (koeficient postane 0), ponovite korak od začetka;
- Upoštevana je čarobna zgoščevalna funkcija
- Vsi koeficienti so kodirani z RLE in Huffmanom, zapisani v izvorne datoteke;
- Parameter k se zapiše v arhivsko datoteko;
- Zgoščena vrednost MD5 se izračuna iz vsake datoteke L v vrstnem redu njihove prvotne lokacije in zapiše v arhivsko datoteko.
Visoka tehnologija
Naivna oblika algoritma in implementacije v drugih jezikih na visoki ravni (zlasti z zbiranjem smeti) bi dale grozno zmogljivost, zato sem vse te zapletenosti implementiral v čisti C in izvedel številne optimizacije tako glede hitrosti izvajanja kot spomin (nimaš pojma koliko tehtajo te slike brez kompresije tudi pred DCT). Toda kljub temu je sprva hitrost izvedbe pustila veliko želenega, zato ne bom opisoval celotnega postopka in uporabljenih metod.
Večplatformnost je dosežena s kombinacijo knjižnic libjpeg, pcre in tinydir, za kar se jim zahvaljujemo. Privzeto je vse prevedeno prek običajnega načina make, zato želijo uporabniki sistema Windows sami namestiti nekaj Cygwina ali pa se sami ukvarjati z Visual Studio in knjižnicami.
Izvedba je na voljo v obliki konzolnega pripomočka in knjižnice. Zainteresirani lahko izveste več o uporabi slednjega v readme-u v repozitoriju na Githubu, povezavo do katerega bom priložil na koncu objave. In tukaj preidemo na opis in predstavitev dela.
Kako uporabljati?
Previdno. Uporabljene slike lahko poljubno premikate, preimenujete in kopirate. Vendar bodite zelo previdni in nikakor ne spreminjajte njihove vsebine. Sprememba enega bita bo motila zgoščevanje in onemogočila obnovitev informacij.
Recimo, da po prevajanju dobimo izvršljivo datoteko f5ar. Z zastavico lahko analizirate velikost knjižnice, da izračunate možnosti njene uporabe -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Pakiranje izvaja ekipa ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], in razpakiranje z uporabo ./f5ar -u [файл архива] [имя восстановленного файла].
Demonstracija dela
Da bi pokazal učinkovitost metode, sem naložil zbirko 225 popolnoma brezplačnih fotografij psov iz storitve . Vsaka od njih ima nekoliko višjo kakovost kot običajne uporabniške fotografije, a vseeno. Vsak od njih je bil ponovno kodiran z uporabo libjpeg, da se nevtralizira vpliv funkcij kodiranja knjižnice na celotno velikost. Za prikaz najslabšega primera stisljivih podatkov je bila z uporabo dd ustvarjena naključna 36-metrska (malo več kot 5 % celotne velikosti) enakomerno porazdeljena datoteka.
Postopek testiranja je precej preprost:
$ 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/Ali posnetek zaslona za oboževalce
Kot lahko vidite, smo od prvotnih 633 + 36 == 669 megabajtov podatkov na trdem disku dobili lepših 563, kar nam daje kompresijsko razmerje ~1,188. To radikalno razliko pojasnjujejo izjemno majhne izgube, podobne tistim, ki jih dobimo pri optimizaciji datotek JPEG s klasičnimi metodami (kot je tinyjpg). Seveda se pri uporabi steganografske kompresije informacije ne preprosto "izgubijo", ampak se uporabljajo za kodiranje drugih podatkov.Še več, število "optimiziranih" koeficientov zaradi uporabe F5 je veliko manj kot pri tradicionalni optimizaciji.
Kakršne koli spremembe že obstajajo, so očem popolnoma nevidne. Pod spodnjim spojlerjem lahko bralec oceni razliko tako na oko kot z odštevanjem vrednosti spremenjene komponente od izvirnika (bolj utišana je barva, manjša je razlika):
Povezave do slik, ki ne sodijo na habrastorage
izvirno -
spremenjeno -
Razlika -
Namesto zaključka
Upam, da sem bralca uspel prepričati, da so takšne metode možne in imajo pravico do življenja. Nakup trdega diska ali dodatnega kanala (za omrežni prenos) pa se morda zdi precej enostavnejša možnost kot poskušanje varčevanja na ta način. Po eni strani je to res, ekstenziven razvoj je pogosto enostavnejši in zanesljivejši. A po drugi strani ne smemo pozabiti na intenzivno. Konec koncev ni zagotovil, da boste jutri lahko prišli v trgovino in si kupili še tisoč terabajtnih trdih diskov, vedno pa lahko uporabite tiste, ki jih že imate doma.
->
Vir: www.habr.com