Kun puhumme steganografiasta, ihmiset ajattelevat terroristeja, pedofiilejä, vakoojia tai parhaimmillaan kryptoanarkisteja ja muita tiedemiehiä. Ja oikeasti, kuka muu voisi tarvita piilottaa jotain ulkoisista silmistä? Mitä hyötyä tästä voisi olla tavalliselle ihmiselle?
Osoittautuu, että yksi on olemassa. Siksi tänään pakkaamme tiedot steganografiamenetelmillä. Ja loppujen lopuksi lukija voi jopa käyttää arvokkaita valokuva-arkistojaan JPEG-muodossa lisätäkseen ilmaisten gigatavujen määrää tiedostojärjestelmässä.
Mitä?
Jos lukija muistaa, steganografia on sellaisia outoja algoritmeja, jotka mahdollistavat tiedon piilottamisen toisen sisään. Vielä yksinkertaisemmalla kielellä: kuva + tiedosto == suunnilleen sama kuva, mutta ei aivan (kuvien sijasta voi olla mitä tahansa, mutta niissä yleensä kaikki on selkeämpää). Ei pitäisi olla helppoa tapaa määrittää, onko sisällä jotain vai ei.
Mutta jos toista ei voida erottaa toisistaan, onko mitään eroa? Kuluttajan näkökulmasta katsottuna käyttäjä ei välitä matemaattisesta tarkkuudesta (joka heijastuu tietyllä bittijoukolla), vaan vain siitä, mitä hän havaitsee.
Katsotaanpa esimerkiksi kolmea kuvaa söpöstä koirasta:
Varo, JPEG!
Valtavasta kokoerosta huolimatta harvat valitsevat kolmannen version. Toisaalta kahden ensimmäisen valokuvan ero ei ole niin havaittavissa, ja niissä olevan tiedon määrä (minun näkökulmastani) voi olla yhtä suuri.
Tämä periaate itsessään on jo vanha ja sitä on hyödynnetty aktiivisesti häviöllisillä tiedonpakkausmenetelmillä useiden vuosien ajan. Mutta murtaminen ei ole rakentamista, vaan olemme kiinnostuneita asian edistyneemmästä puolesta. Onko mahdollista upottaa lisää kokotietoja N tiedostoon niin, että sen koko kasvaa M < N, mutta muutokset eivät olleet käyttäjän havaittavissa?
Voit tietysti. Mutta kannattaa tehdä pari varausta heti:
- Ensinnäkin menetelmän on oltava universaali ja annettava positiivinen tulos useimmille syöttötiedoille. Toisin sanoen keskimäärin satunnaiselle syötteelle tallennetun tiedon määrän pitäisi olla todellinen lasku. "Keskimäärin" tarkoittaa, että päinvastoin voi tapahtua, mutta sen ei pitäisi olla vallitsevaa.
- Toiseksi pakatun säiliön koon ennen informaation upottamista on oltava suurempi kuin sen vastaavalla tavalla pakatun muunnelman. Pelkästään joukon bittien upottaminen BMP-kuviin LSB-menetelmällä ei ole steganografista pakkausta, koska jonkinlaisen DEFLATE:n läpi ajettuaan alkuperäinen kuva on todennäköisesti huomattavasti pienempi.
- Kolmanneksi tulos on suoritettava ja verrattava klassisilla menetelmillä jo pakattuun tietoon. Tämä poistaa niiden redundanssierojen todennäköisyysvaikutuksen ja tarjoaa tehokkaamman pakkaamisen yleisessä tapauksessa.
Missä?
Steganografian käyttö tarkoittaa, että pakattujen tietojen lisäksi tarvitsemme säiliöitä, joihin se upotetaan. Upotetun tiedon enimmäismäärä riippuu pitkälti yksittäisistä ominaisuuksista, mutta niiden lukumäärällä on paljon helpompi skaalata. Siksi säiliömuodon on oltava yhteinen, jotta käyttäjällä on tarpeeksi niitä saadakseen hyötyä "pakkausprosessista".
Tässä yhteydessä grafiikka-, ääni- ja videotiedostot ovat hyviä ehdokkaita. Mutta eri muotojen, koodekkien jne. moninaisuuden vuoksi meillä on käytännössä valinnanvaraa ei niin monista vaihtoehdoista.
Kaiken tämän huomioon ottaen valintani putosi JPEG:iin, se on melkein kaikilla, se on laajalti käytössä sekä henkilökohtaisiin että liiketarkoituksiin, koska se on lähes de facto -muoto useimmille kuville.
Se riippuu?
Seuraavaksi on lähetys- ja tekniset kaaviot ja kuvaukset ilman suurempia selityksiä, joten kiinnostuneet voivat ohittaa ne rullaamalla "High teknologiat" -osioon.
Yhteiset ominaisuudet
Jos haluat upottaa tietoja jonnekin, sinun on ensin määritettävä minne. Tiedostojärjestelmässä voi olla useita erilaisia valokuvia, joista käyttäjä saattaa haluta käyttää vain muutamia. Kutsumme tällaista haluttua konttisarjaa kirjastoksi.
Se muodostuu kahdessa tapauksessa: ennen pakkausta ja ennen purkamista. Ensimmäisessä tapauksessa voit yksinkertaisesti käyttää tiedostojen tiedostonimiä (tai vielä parempi, säännöllistä lauseketta niille), mutta toisessa tarvitaan jotain luotettavampaa: käyttäjä voi kopioida ja siirtää ne tiedostojärjestelmässä. , mikä estää niitä tunnistamasta oikein. Siksi on tarpeen tallentaa niiden tiivisteet (md5 riittää) sen jälkeen, kun kaikki muutokset on tehty.
Tässä tapauksessa ei ole mitään järkeä suorittaa alustavaa hakua säännöllisellä lausekkeella koko tiedostojärjestelmässä, riittää, kun määritetään tietty juurihakemisto. Siihen tallennetaan erityinen arkistotiedosto, joka sisältää nämä tiivisteet sekä muut metatiedot, joita tarvitaan pakattujen tietojen myöhempään palauttamiseen.
Kaikki tämä koskee yhtä hyvin minkä tahansa steganografisen tiedon pakkausalgoritmin toteutusta. Itse tietojen pakkaus- ja palautusprosesseja voidaan kutsua pakkaamiseksi ja purkamiseksi.
F5
Nyt kun on käynyt selväksi, mitä teemme ja miksi, on vielä kuvattava tavoitteen saavuttamisen algoritmi. Muistetaanpa JPEG-tiedoston koodausprosessi (kiitos Baumanin kansalliskirjaston wikin kautta):
Sitä katsoessa on parempi tehdä välittömästi muutama kommentti:
- JPEG-tiedoston kokoa voidaan pitää optimaalisena ilman, että sitä edes yritetään pakata jollain Winrarilla;
- Vain tallennettua tietoa (se, joka tulee ulos diskreetistä kosinimuunnoksesta, DCT) voidaan muokata antamaan vähintään hyväksyttävä suorituskyky.
- Jotta käyttäjä ei menetä tietoja teollisessa mittakaavassa, on tarpeen tehdä mahdollisimman vähän muutoksia jokaiseen yksittäiseen kuvaan;
Näihin ehtoihin sopii koko joukko algoritmeja, joihin voit tutustua . Edistyksellisin niistä on algoritmi Andreas Westfeld, joka työskentelee kirkkauskomponentin DCT-kertoimien kanssa (ihmissilmä on vähiten herkkä sen muutoksille). Sen yleinen asettelu olemassa olevan JPEG-tiedoston kanssa työskenneltäessä näytetään seuraavasti:
F5-lohko käyttää edistynyttä sulautustekniikkaa, joka perustuu matriisikoodaukseen. Lukija saa lisätietoa siitä ja itse algoritmista yllä olevasta linkistä, mutta meitä kiinnostaa ensisijaisesti se, että sen avulla voi tehdä mitä vähemmän muutoksia upottamalla saman määrän tietoa, sitä suurempi on käytetyn säiliön koko , ja suorittamiseen Algoritmin tarvitsee suorittaa vain yksinkertaisia Huffman- ja RLE- (de)koodausoperaatioita.
Muutokset itsessään tehdään kokonaislukukertoimiin ja niiden absoluuttisen arvon pienentämiseen yhdellä, mikä mahdollistaa yleisesti ottaen F5:n käytön tietojen pakkaamiseen. Asia on siinä, että absoluuttisen arvon pienentynyt kerroin vie todennäköisesti vähemmän bittejä Huffman-koodauksen jälkeen johtuen arvojen tilastollisesta jakautumisesta JPEG:ssä.
Jos muodostuu nolla (ns. vähennys), tallennetun tiedon määrä pienenee sen koon verran, koska entisestä riippumattomasta kertoimesta tulee osa RLE-koodattua nollien sekvenssiä:
muutoksia
Tietosuoja ja pakkaus ovat ortogonaalisia ongelmia, joten salasanojen permutaatio alkuperäisestä algoritmista voidaan jättää huomiotta. Lisäksi meidän on tiedettävä tarkalleen kuinka tiedot puretaan, joten kaikki tähän tarvittavat tiedot (mitä säiliöitä käytettiin, missä järjestyksessä jne.) tulee tallentaa erilliseen tiedostoon ja olla arkistaattorin vapaasti luettavissa.
Alkuperäinen algoritmi on suunniteltu välittämään salaisia viestejä, joten se toimii vain yhden kontin kanssa kerrallaan olettaen, että käyttäjä itse jakaa sen tarvittaessa osiin. Lisäksi, kun upotetaan erikseen kuhunkin säilöön, sinun on tiedettävä etukäteen, kuinka monta bittiä dataa kuhunkin sisällytetään. Siksi jokaisen kirjaston elementin kertoimet tulisi yhdistää yhdeksi abstraktiksi suureksi ja työstää sen kanssa alkuperäisen algoritmin mukaisesti.
Koska alkuperäinen F5 sallii jopa 12 % säilön koosta, tämä muutos lisää myös maksimikapasiteettia: "jopa 12%" koko kirjaston koosta on suurempi tai yhtä suuri kuin summa "jopa 12% " jokaisesta sen elementistä.
Kodifioitu yleinen järjestelmä on seuraava:
Itse algoritmi
Nyt on aika kuvata itse algoritmi alusta loppuun, jotta lukija ei jää pimeyteen:
- Käyttäjä määrittelee binäärisen pakattavan datan M ja kirjaston L käyttämällä säännöllistä lauseketta ja haun juurihakemistoa;
- Kirjastoelementit muodostavat MC:n siinä järjestyksessä kuin ne näkyvät FS:ssä:
- Sarja kertoimia C dekoodataan tiedostodatasta;
- MC <- MC | C;
- Parametri k määritetään kauhean epäyhtälön perusteella:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Seuraavaksi otettu
n = (1 << k) - 1vähiten merkitsevät bitit nollasta poikkeavia elementtejä MC:stä ja kirjoitetaan niihina:- Maaginen hash-funktio otetaan huomioon
f, edustaa n-bittistä sanaaak-bittiseksis; - Jos
s == 0, silloin ei tarvitse muuttaa mitään ja algoritmi siirtyy seuraaviin kertoimiin; - Pienennä vastaavan kertoimen absoluuttista arvoa
s- hei, pisti sanaana; - Jos vähennyksen seurauksena tapahtuu vähennys (kerroin tulee 0), toista vaihe alusta;
- Maaginen hash-funktio otetaan huomioon
- Kaikki kertoimet ovat RLE:n ja Huffmanin koodaamia, ja ne kirjoitetaan lähdetiedostoihin;
- Parametri k kirjoitetaan arkistotiedostoon;
- Jokaisesta tiedostosta L lasketaan MD5-tiiviste niiden alkuperäisen sijainnin järjestyksessä ja kirjoitetaan arkistotiedostoon.
Huipputekniikka
Algoritmin naiivi muoto ja toteutukset muilla korkean tason (erityisesti roskienkeräys) kielillä antaisivat kauhean suorituskyvyn, joten toteutin kaikki nämä monimutkaisuudet puhtaalla C:llä ja tein useita optimointeja sekä suoritusnopeuden että muisti (sinulla ei ole aavistustakaan kuinka paljon nämä kuvat painavat ilman pakkausta jo ennen DCT:tä). Mutta siitä huolimatta, aluksi suoritusnopeus jätti paljon toivomisen varaa, joten en kuvaile koko prosessia ja käytettyjä menetelmiä.
Cross-platform saavutetaan käyttämällä libjpeg-, pcre- ja tinydir-kirjastojen yhdistelmää, mistä kiitämme heitä. Oletuksena kaikki käännetään normaalilla make, joten Windows-käyttäjät haluavat asentaa Cygwiniä itselleen tai käsitellä Visual Studiota ja kirjastoja yksin.
Toteutus on saatavilla konsoliapuohjelman ja kirjaston muodossa. Kiinnostuneet voivat tutustua jälkimmäisen käyttöön Githubin arkiston readme-osiossa, jonka linkin liitän postauksen loppuun. Ja tässä siirrymme työn kuvaukseen ja esittelyyn.
Kuinka käyttää?
Huolellisesti. Käytettyjä kuvia voidaan siirtää, nimetä uudelleen ja kopioida halutessaan. Sinun tulee kuitenkin olla erittäin varovainen, äläkä muuta niiden sisältöä millään tavalla. Yhden bitin muuttaminen häiritsee tiivistettä ja tekee mahdottomaksi palauttaa tietoja.
Oletetaan, että kääntämisen jälkeen saamme suoritettavan tiedoston f5ar. Voit analysoida kirjaston kokoa ja laskea sen käyttömahdollisuudet lipun avulla -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Pakkauksen tekee tiimi ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], ja purkaminen käyttämällä ./f5ar -u [файл архива] [имя восстановленного файла].
Työn esittely
Osoittaakseni menetelmän tehokkuutta latasin palvelusta 225 täysin ilmaista valokuvaa koirista. . Jokainen niistä on hieman korkeampi laatu kuin tavalliset käyttäjäkuvat, mutta silti. Jokainen niistä koodattiin uudelleen libjpegillä neutraloimaan kirjaston koodausominaisuuksien vaikutusta kokonaiskokoon. Pakkautuvan datan huonoimman esimerkin osoittamiseksi luotiin satunnainen 36 metrin (hieman yli 5 % kokonaiskoosta) tasaisesti jakautunut tiedosto käyttämällä dd:tä.
Testausprosessi on melko yksinkertainen:
$ 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/Tai kuvakaappaus faneille
Kuten näette, kiintolevyn alkuperäisestä 633 + 36 == 669 megatavua datasta päädyimme hienompaan 563:een, joka antoi meille pakkaussuhteeksi ~1,188. Tämä radikaali ero selittyy erittäin pienillä häviöillä, jotka ovat samankaltaisia kuin optimoitaessa JPEG-tiedostoja klassisilla menetelmillä (kuten tinyjpg). Luonnollisestikin steganografista pakkausta käytettäessä informaatiota ei vain "kadota", vaan sitä käytetään muun datan koodaamiseen, ja F5:n käytön ansiosta "optimoitujen" kertoimien määrä on huomattavasti pienempi kuin perinteisessä optimoinnissa.
Olivatpa muutokset mitä tahansa, ne ovat täysin näkymättömiä silmälle. Alla olevan spoilerin alla lukija voi arvioida eron sekä silmällä että vähentämällä muutetun komponentin arvot alkuperäisestä (mitä mykisempi väri, sitä pienempi ero):
Linkkejä kuviin, jotka eivät mahdu habrastorageen
Alkuperäinen -
Muokattu -
Ero -
Sen sijaan johtopäätös
Toivon, että pystyin vakuuttamaan lukijan siitä, että tällaiset menetelmät ovat mahdollisia ja että heillä on oikeus elämään. Kiintolevyn tai lisäkanavan ostaminen (verkkosiirtoa varten) voi kuitenkin tuntua paljon yksinkertaisemmalta vaihtoehdolta kuin yrittää säästää rahaa tällä tavalla. Toisaalta tämä on totta, laaja kehitys on usein yksinkertaisempaa ja luotettavampaa. Mutta toisaalta, meidän ei pidä unohtaa intensiivistä. Loppujen lopuksi ei ole mitään takeita siitä, että pääset huomenna kauppaan ostamaan itsellesi vielä tuhannen teratavun kovalevyn, mutta voit aina käyttää niitä, joita sinulla on jo kotona.
->
Lähde: www.habr.com