Keď hovoríme o steganografii, ľudia si predstavia teroristov, pedofilov, špiónov alebo v lepšom prípade kryptoanarchistov a iných vedcov. A naozaj, kto iný by mohol potrebovať skryť sa niečo z vonkajších očí? Aký úžitok z toho môže mať obyčajného človeka?
Ukazuje sa, že jeden existuje. Preto dnes budeme komprimovať dáta pomocou metód steganografie. A v konečnom dôsledku bude môcť čitateľ použiť svoje vzácne fotoarchívy vo formáte JPEG na zvýšenie počtu voľných gigabajtov v súborovom systéme.
Čo je?
Ak si čitateľ pamätá, steganografia sú také zvláštne algoritmy, ktoré umožňujú skryť prítomnosť jednej informácie v druhej. V ešte jednoduchšom jazyku: obrázok + súbor == približne rovnaký obrázok, ale nie celkom (namiesto obrázkov môže byť čokoľvek, ale zvyčajne je v nich všetko jasnejšie). Nemal by byť jednoduchý spôsob, ako určiť, či je vo vnútri niečo alebo nie.
Ale ak sa nedá odlíšiť jedno od druhého, existuje vôbec nejaký rozdiel? Z pohľadu spotrebiteľa sa užívateľ nestará o matematickú presnosť (odrážanú konkrétnou sadou bitov), iba o to, čo vníma.
Pozrime sa napríklad na tri obrázky roztomilého psa:
Pozor, JPEG!
Napriek obrovskému rozdielu vo veľkosti si tretiu verziu vyberie málokto. Na druhej strane rozdiel medzi prvými dvoma fotografiami nie je až taký badateľný a množstvo informácií na nich (z môjho pohľadu) sa môže rovnať.
Tento princíp sám o sebe je už starý a už mnoho rokov ho aktívne využívajú metódy stratovej kompresie informácií. Ale lámanie nie je budovanie, nás zaujíma pokročilejšia stránka problému. Je možné vložiť ďalšie informácie o veľkosti N do súboru tak, aby sa jeho veľkosť zväčšila o M < N, ale zmeny neboli pre používateľa viditeľné?
Samozrejme môžete. Ale stojí za to urobiť hneď niekoľko rezervácií:
- Po prvé, metóda musí byť univerzálna a poskytovať pozitívny výsledok na väčšine vstupných údajov. To znamená, že v priemere pre náhodný vstup by malo dôjsť k skutočnému zníženiu množstva uložených informácií. „V priemere“ znamená, že opak môže nastať, ale nemal by prevládať.
- Po druhé, veľkosť komprimovaného kontajnera pred vložením informácií musí byť väčšia ako jeho modifikácia komprimovaná podobným spôsobom. Jednoduché vloženie hromady bitov do obrázkov BMP pomocou metódy LSB nie je steganografická kompresia, pretože po vykonaní nejakého typu DEFLATE bude pôvodný obrázok s najväčšou pravdepodobnosťou výrazne menší.
- Po tretie, výsledok sa musí vykonať a porovnať s údajmi, ktoré už boli komprimované klasickými metódami. Tým sa odstráni pravdepodobnostný efekt rozdielov v ich redundancii a vo všeobecnom prípade sa zabezpečí efektívnejšia kompresia.
Kde?
Použitie steganografie znamená, že okrem komprimovanej informácie budeme potrebovať kontajnery, do ktorých budú vložené. Maximálne množstvo vložených informácií do značnej miery závisí od jednotlivých vlastností, ale je oveľa jednoduchšie škálovať s ich počtom. Preto musí byť formát kontajnera bežný, aby ich mal používateľ dostatok na to, aby mal z procesu „kompresie“ akýkoľvek úžitok.
V tomto kontexte sú grafické, zvukové a video súbory dobrými kandidátmi. Ale vzhľadom na rozmanitosť rôznych formátov, kodekov atď., v praxi nám zostáva na výber z nie tak veľkého množstva možností.
Vzhľadom na toto všetko padla moja voľba na JPEG, ktorý má takmer každý, je široko používaný na osobné aj firemné účely, je to takmer de facto formát väčšiny obrázkov.
Záleží?
Ďalej sú tu takmer technické nákresy a popisy bez veľkého vysvetlenia, takže záujemcovia ich môžu preskočiť rolovaním do sekcie „Vysoké technológie“.
Spoločné znaky
Ak chcete niekde vložiť údaje, musíte najprv určiť, kde. V súborovom systéme môže byť ľubovoľný počet rôznych fotografií, z ktorých používateľ môže chcieť použiť len niekoľko. Takúto požadovanú sadu kontajnerov nazveme knižnica.
Vzniká v dvoch prípadoch: pred kompresiou a pred dekompresiou. V prvom prípade môžete jednoducho použiť množinu názvov súborov (alebo ešte lepšie, regulárny výraz) súborov, ale v druhom prípade sa vyžaduje niečo spoľahlivejšie: používateľ ich môže kopírovať a presúvať v rámci systému súborov. , čím sa zabráni ich správnej identifikácii. Preto je potrebné po vykonaní všetkých úprav uložiť ich hashe (stačí md5).
V tomto prípade nemá zmysel vykonávať počiatočné vyhľadávanie pomocou regulárneho výrazu v celom súborovom systéme, stačí zadať určitý koreňový adresár. Bude v ňom uložený špeciálny archívny súbor, ktorý bude obsahovať tieto hashe spolu s ďalšími metainformáciami potrebnými na následnú obnovu komprimovaných informácií.
Toto všetko platí rovnako pre akúkoľvek implementáciu akéhokoľvek algoritmu kompresie steganografických údajov. Samotné procesy kompresie a obnovy dát možno nazvať balenie a rozbaľovanie.
F5
Teraz, keď je jasné, čo robíme a prečo, zostáva popísať algoritmus na dosiahnutie cieľa. Pripomeňme si proces kódovania súboru JPEG (vďaka wiki Národnej knižnice Bauman):
Pri pohľade na to je lepšie okamžite urobiť niekoľko komentárov:
- Veľkosť súboru JPEG možno považovať za optimálnu bez toho, aby ste sa ho pokúsili komprimovať nejakým druhom Winraru;
- Len uložené informácie (tie, ktoré sú výstupom z diskrétnej kosínusovej transformácie, DCT) možno upraviť tak, aby poskytovali aspoň prijateľný výkon.
- Aby nedošlo k strate údajov v priemyselnom meradle, ktoré si používateľ všimne, je potrebné vykonať minimálne úpravy každého jednotlivého obrázka;
Týmto podmienkam vyhovuje celá rodina algoritmov, s ktorými sa môžete zoznámiť . Najpokročilejší z nich je algoritmus od Andreasa Westfelda, pracujúceho s DCT koeficientmi jasovej zložky (ľudské oko je najmenej citlivé na jej zmeny). Jeho všeobecné rozloženie pri práci s existujúcim súborom JPEG sa zobrazí takto:
Blok F5 využíva pokročilú techniku vkladania založenú na maticovom kódovaní. Čitateľ sa o ňom a samotnom algoritme môže dozvedieť viac na vyššie uvedenom odkaze, ale nás zaujíma predovšetkým to, že s jeho pomocou môžete urobiť čím menej zmien pri vkladaní rovnakého množstva informácií, tým väčšia bude veľkosť použitého kontajnera a na vykonanie algoritmu potrebuje vykonať iba jednoduché Huffmanove a RLE (de)kódovacie operácie.
Samotné zmeny sa vykonávajú v celočíselných koeficientoch a znižujú ich absolútnu hodnotu o jednu, čo vo všeobecnosti umožňuje použiť F5 na kompresiu údajov. Ide o to, že znížený koeficient v absolútnej hodnote bude s najväčšou pravdepodobnosťou zaberať menej bitov po Huffmanovom kódovaní kvôli štatistickému rozdeleniu hodnôt v JPEG.
V prípade vytvorenia nuly (tzv. redukcia) sa počet uložených informácií zníži o ich veľkosť, pretože bývalý nezávislý koeficient sa stane súčasťou RLE kódovanej sekvencie núl:
modifikácie
Ochrana a kompresia údajov sú ortogonálne problémy, takže permutáciu tajného hesla z pôvodného algoritmu možno zanedbať. Okrem toho musíme presne vedieť, ako extrahovať údaje, takže všetky informácie potrebné na to (ktoré kontajnery boli použité, v akom poradí atď.) by mali byť zaznamenané v samostatnom súbore a mali by byť otvorené na bezplatné prečítanie archivátorom.
Pôvodný algoritmus je navrhnutý na prenos tajných správ, takže pracuje naraz iba s jedným kontajnerom za predpokladu, že používateľ ho v prípade potreby rozdelí na časti, ak nejaké existujú. Okrem toho, keď sú vložené nezávisle do každého kontajnera, budete musieť vopred vedieť, koľko bitov dát do každého vložiť. Preto by sa koeficienty každého prvku knižnice mali spojiť do jedného abstraktného veľkého a pracovať s ním podľa pôvodného algoritmu.
Keďže pôvodný F5 umožňuje až 12 % veľkosti kontajnera, táto úprava zvýši aj maximálnu kapacitu: „až 12 %“ veľkosti celej knižnice je väčšie alebo rovné súčtu „až 12 % “ z každého jeho prvku.
Kodifikovaná všeobecná schéma je takáto:
Samotný algoritmus
Teraz je čas opísať samotný algoritmus od začiatku do konca, aby ste čitateľa neudržali v tme:
- Užívateľ definuje binárne komprimovateľné dáta M a knižnicu L pomocou regulárneho výrazu a vyhľadávacieho koreňového adresára;
- V poradí, v akom sa objavujú na FS, tvoria prvky knižnice MC:
- Séria koeficientov C sa dekóduje z dát súboru;
- MC <- MC | C;
- Parameter k je určený na základe strašnej nerovnosti:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Prevzaté ako ďalšie
n = (1 << k) - 1najmenej významných bitov nenulových prvkov z MC a zapísaných doa:- Zvažuje sa magická hašovacia funkcia
f, predstavujúce n-bitové slovoana k-bits; - Ak
s == 0, potom nie je potrebné nič meniť a algoritmus prejde na ďalšie koeficienty; - Znížiť absolútnu hodnotu zodpovedného koeficientu
s-hej zahryzol sa do slovaa; - Ak v dôsledku zníženia dôjde k zníženiu (koeficient sa stane 0), potom zopakujte krok od začiatku;
- Zvažuje sa magická hašovacia funkcia
- Všetky koeficienty sú zakódované pomocou RLE a Huffman, zapísané do zdrojových súborov;
- Parameter k sa zapíše do archívneho súboru;
- Z každého súboru L sa vypočíta hash MD5 v poradí ich pôvodného umiestnenia a zapíše sa do archívneho súboru.
High-tech
Naivná forma algoritmu a implementácie v iných jazykoch na vysokej úrovni (najmä s garbage collection) by poskytli hrozný výkon, takže som implementoval všetky tieto zložitosti v čistom C a vykonal som niekoľko optimalizácií z hľadiska rýchlosti vykonávania a pamäť (nemáte ani potuchy, koľko tieto obrázky vážia bez kompresie ešte pred DCT). Ale aj napriek tomu bola rýchlosť vykonania spočiatku veľmi nedostačujúca, takže nebudem popisovať celý proces a použité metódy.
Multiplatformnosť je dosiahnutá pomocou kombinácie knižníc libjpeg, pcre a tinydir, za čo im ďakujeme. V predvolenom nastavení je všetko kompilované cez normálne make, takže používatelia Windows Chcú si nainštalovať nejaký Cygwin alebo si sami zistiť, ako funguje Visual Studio a knižnice.
Implementácia je dostupná vo forme konzolovej utility a knižnice. Záujemcovia sa o používaní posledného môžu dozvedieť viac v readme v úložisku na Github, odkaz na ktorý pripojím na konci príspevku. A tu prejdeme k popisu a ukážke práce.
Ako používať?
Opatrne. Použité obrázky je možné podľa potreby presúvať, premenovať a kopírovať. Mali by ste byť však maximálne opatrní a nijako nemeniť ich obsah. Zmena jedného bitu naruší hash a znemožní obnovenie informácií.
Predpokladajme, že po kompilácii dostaneme spustiteľný súbor f5ar. Pomocou príznaku môžete analyzovať veľkosť knižnice a vypočítať možnosti jej použitia -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Balenie vykonáva tím ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], a rozbalenie pomocou ./f5ar -u [файл архива] [имя восстановленного файла].
Ukážka práce
Aby som ukázal účinnosť metódy, odovzdal som zbierku 225 úplne bezplatných fotografií psov zo služby . Každá z nich má o niečo vyššiu kvalitu ako bežné používateľské fotografie, ale predsa. Každý z nich bol prekódovaný pomocou libjpeg, aby sa neutralizoval vplyv kódovacích funkcií knižnice na celkovú veľkosť. Na označenie najhoršieho príkladu komprimovateľných údajov sa pomocou dd vygeneroval náhodný 36-metrový (o niečo viac ako 5 % celkovej veľkosti) rovnomerne distribuovaný súbor.
Proces testovania je pomerne jednoduchý:
$ 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/Alebo screenshot pre fanúšikov
Ako vidíte, z pôvodných 633 + 36 == 669 megabajtov dát na pevnom disku sme skončili s krajšími 563, čo nám dáva kompresný pomer ~1,188. Tento radikálny rozdiel sa vysvetľuje extrémne malými stratami, podobnými tým, ktoré sa získajú pri optimalizácii súborov JPEG pomocou klasických metód (napríklad tinyjpg). Prirodzene, pri použití steganografickej kompresie sa informácie jednoducho „nestratí“, ale sú použité na zakódovanie iných údajov.Navyše počet „optimalizovaných“ koeficientov vďaka použitiu F5 je oveľa menší ako pri tradičnej optimalizácii.
Nech už existujú akékoľvek úpravy, sú pre oko absolútne neviditeľné. Pod spojlerom nižšie môže čitateľ vyhodnotiť rozdiel okom aj odčítaním hodnôt zmeneného komponentu od originálu (čím je farba tlmenejšia, tým je rozdiel menší):
Odkazy na obrázky, ktoré sa nezmestia na habrastorage
Originál -
Upravené -
Rozdiel -
namiesto záveru
Dúfam, že sa mi podarilo presvedčiť čitateľa, že takéto metódy sú možné a majú právo na život. Nákup pevného disku alebo dodatočného kanála (na sieťový prenos) sa však môže zdať oveľa jednoduchšou možnosťou, ako sa snažiť ušetriť peniaze týmto spôsobom. Na jednej strane je to pravda, rozsiahly vývoj je často jednoduchší a spoľahlivejší. No na druhej strane netreba zabúdať na intenzívne. Koniec koncov, neexistujú žiadne záruky, že zajtra budete môcť prísť do obchodu a kúpiť si ďalší tisíc terabajtový pevný disk, ale vždy môžete použiť tie, ktoré už máte doma.
->
Zdroj: www.habr.com
