Kasutame kõvakettaruumi kokkuhoidu steganograafia abil

Kui me räägime steganograafiast, siis inimesed näevad silme ees terroriste, pedofiile, spioone ja parimal juhul krüptoanarkiste ning muid teadlasi. Ja tõepoolest, kellele muule võiks olla vaja vaikimisi midagi välistest pilkudest? Milline võiks sellest olla kasu tavalisele inimesele?

Selgub, et mingi kasu on. Just seetõttu hakkame täna andmeid tihendama steganograafia meetodite abil. Ja lõpuks saab lugeja isegi kasutada oma väärtuslikke JPEG-fotokollektsioone, et suurendada vabade gigabaitide arvu failisüsteemis.

Mis?

Kui lugeja mäletab, siis steganograafia on sellised kummalised algoritmid, mis võimaldavad peita ühe teabe olemasolu teise sisse. Veel lihtsamalt öeldes: pilt + fail == umbes sama pilt, aga mitte päris (koos piltidega võib olla midagi, aga tavaliselt on see nende peal selgem). Samuti ei tohiks olla lihtsat viisi kindlaks tegemiseks, kas sees on midagi või mitte.

Kuid kui ühte teisest eristada ei saa, siis kas mingi vahe on? Tarbija ja kasutaja seisukohalt ei huvita matemaatiline täpsus (mida peegeldab konkreetne bitide kogum), vaid vaid see, kuidas ta seda tajub.

Näiteks vaatame kolme armsa koera pilti:

Olge ettevaatlikud, JPEG!

Vaatamata tohutule suuruse erinevusele, valib vähesed kolmanda variandi. Teisest küljest ei ole esimeste kahe foto vahel vahe nii märgatav ja teabe hulk neis (minu arvates) on ligikaudu võrdne.

See põhimõte iseenesest on juba vana ning on aastaid aktiivselt kasutatud kaotusega andmete tihendamise meetodites. Kuid purustada – ei tähenda ehitada, meid huvitab küsimuse arenenum külg. Kas on võimalik sisestada täiendavat teavet suuruses N faili nii, et selle suurus suureneks M < N, ja muudatused ei oleks kasutajale nähtavad?

Muidugi on see võimalik. Kuid tuleb kohe teha paar märkust:

• Esiteks peab meetod olema universaalne ja andma positiivse tulemuse enamiku sisendandmete puhul. See tähendab, et keskmiselt, juhusliku sisendi puhul, peaks toimuma tegelik salvestatava teabe hulga vähenemine. "Keskmiselt" tähendab, et vastupidised juhused võivad esineda, kuid ei tohi domineerida.
• Teiseks, enne teabe sisestamist peab kokkusurutud konteineri suurus olema suurem kui selle kokkusurutud sarnane modifikatsioon. BMP-pilte LSB meetodil bittide kuhjamisega ei saa pidada steganograafiliseks kokkusurutiseks, kuna pärast DEFLATE'i kasutamist on originaalpilt tõenäoliselt oluliselt väiksem.
• Kolmandaks, tulemusi tuleb võrrelda klassikaliste meetoditega juba kokku surutud andmete suhtes. See aitab kõrvaldada tõenäosusliku eriülesande mõju ja tagab tõhusama kokkusurumise üldiselt.

Kus?

Steganograafia kasutamine eeldab, et lisaks kokkusurutavale teabele on meil vaja ka konteinereid, kuhu see sisse kirjutatakse. Maksimaalne sisestatav teabe hulk sõltub paljuski eraldiseisvatest omadustest, kuid see skaleerub nende arvu tõttu palju lihtsamalt. Seetõttu peaks konteinerite formaat olema levinud, et kasutajal oleks piisavalt neist valikuid, et saavutada mingit kasu kokkusurumise protsessist.

Sellises kontekstis on head kandidaadid graafika-, audio- ja videofailid. Kuid erinevate formaatide, koodekite jm mitmekesisuse tõttu on valik tegelikult mitte nii suur.

Arvestades kõike seda, langetasin oma valiku JPEG'i kasuks. See on peaaegu kõigil olemas, seda kasutatakse laialdaselt nii isiklikel kui ka äriotstarbel, olles peaaegu de facto formaat enamikule piltidele.

Kuidas?

Edasi tulevad umbes tehnilised skeemid ja kirjeldused ilma erilise selgituseta, nii et soovijad võivad need vahele jätta ja liikuda jaotisse 'Tipptehnoloogia'.

Üldised jooned

Andmete sisestamiseks tuleb esmalt kindlaks teha, kuhu. Failisüsteemis võib olla mitmeid erinevaid fotosid, millest kasutaja soovib kasutada vaid mõnda. Seda soovitud konteinerite kogumit nimetame raamatukoguks.

See tekib kahes olukorras: enne kokkusurumist ja enne lahtipakkimist. Esimesel juhul saab lihtsalt kasutada failide nimede komplekti (ja veelgi parem, regulaaravaldust nende jaoks), kuid teisel juhul on vajalik midagi usaldusväärsemat: kasutaja võib neid kopeerida ja liikuda failisüsteemi piiresse, mistõttu on keeruline neid õigesti tuvastada. Seetõttu on vajalik nende hashide (md5 piisab) salvestamine pärast kõiki modifikatsioone.

Algne otsing regulaaravaldusega ei oma mõtet läbi kogu failisüsteemi teostada, piisab, kui näidata mõnda juurdirectory. Sellesse salvestatakse spetsiaalne arhiivifail, milles asuvad need hashid koos muu meta-informatsiooniga, mis on vajalik edasise tihendamise teabe taastamiseks.

Kõik see kehtib võrdselt iga steganograafilise andmekokkusurumise algoritmi rakenduste kohta. Andmete kokkusurumise ja taastamise protsesse võib nimetada pakkimiseks ja lahtipakkimiseks.

F5

Nüüd, kui on selge, mida ja miks teeme, on jäänud kirjeldada eesmärgi saavutamise algoritmi. Tuletame meelde JPEG-faili kodeerimise protsessi (tänu Bauman National Library wiki-le):

Seda vaadates on parem kohe teha mõned märkused:

• JPEG faili suurust võib pidada optimaalseks, isegi mitte proovimata seda näiteks WinRARiga tihendada;
• Muudatada tohib ainult salvestatud teavet (seda, mis on diskreetse kosinusse muundamise, DCT, väljundis), et tagada vähemalt mingisugune vastuvõetav jõudlus.
• Et mitte kaotada andmeid kasutaja jaoks märgatavas tööstuslikus skaalas, tuleb iga üksiku pildi puhul teha minimaalne muudatus;

Sellistele tingimustele sobib terve algoritmide perekond, millega saab tutvuda. selles heas esituses. Kõige arenenum neist on algoritm F5 autoriõigusega Andreas Westfeld, kes töötab DCT heleduskomplekti koefitsientidega (inimese silm on nende muutumise suhtes kõige vähem tundlik). Tema töö üldine skeem olemasoleva JPEG-failiga töötamisel on järgmine skeem:

F5 plokk kasutab edasijõudnud sisestusmeetodit, mis põhineb maatrixkoodil. Lisainfot selle ja algoritmi kohta saab lugeda ülaltoodud lingilt, kuid meid huvitab eelkõige see, et selle abil saab teha seda vähem muudatusi, kui sisestatakse sama palju teavet, kui containeri suurus kasvab, ja algoritmi teostamiseks on vajalikud vaid lihtsad (de)koodi operatsioonid, nagu Haffmani ja RLE dekodeerimine.

Muutused ise toimuvad täisarvuliste koefitsientide üle ning need vähenevad nende absoluutväärtuse võrra ühe võrra, mis võimaldab, et F5-d saab kasutada andmete surumisel. See tuleneb asjaolust, et absoluutväärtuse poolest vähendatud koefitsient kasutamise ajal tõenäoliselt vajab Haffmani kodeerimise tõttu vähem bitti, arvestades JPEG'i väärtuste statistilist jaotust.

Kui tekib null (nn lühendamine), väheneb salvestatud teabe maht selle suuruse võrra, kuna endine iseseisev koefitsient muutub osa kodeeritud RLE nullide jadast:

Muudatused

Andmete kaitse ja nende kokkusurumine on ortogonaalsed ülesanded, seetõttu saab disainida salajase parooli ümberpaigutamise algorütmist. Veelgi enam, meil on vaja täpselt teada, kuidas andmeid taastada, seetõttu peab kogu vajalik teave (millised konteinerid on kasutatud, millises järjekorras jne) olema salvestatud eraldi faili ja olema avatud ilma piiranguteta arhiveerijale.

Algne algoritm on mõeldud salajaste sõnumite edastamiseks, seetõttu töötab see korraga vaid ühe konteineriga, eeldades, et kasutaja jagab selle vajadusel osadeks, kui see peaks tekkima. Veelgi enam, iseseisva sisestamise korral igasse konteinerisse tuleb eelnevalt teada, kui palju biti andmeid igasse mahutada. Seetõttu tasub iga elemendi koefitsiendid ühendada üheks abstraktseks suureks ja töötada selle põhjal algse algoritmiga.

Kuna originaalne F5 võimaldab kasutada kuni 12% konteineri suurusest, suurendab see modifikatsioon ka maksimaalset mahtu: „kuni 12%“ kogu raamatukogu suurusest on suurem või võrdne iga selle elementi „kuni 12%“ summa.

Kodeeritud üldskeem näeb välja järgmine:

Algoritm ise

Nüüd on aeg kirjeldada algoritmi algusest lõpuni, et lugejat teadmatuses hoida:

• Kasutaja määrab binaarsed tihendatavad andmed M ja raamatukogu L regulaaravalduse ja otsingudirektori abil;
• Failisüsteemis raamatukogu elemendid moodustavad MC:
  • Failist dekodeeritakse koefitsientide seeria C;
  • MC <- MC | C;
• Määratakse parameeter k, lähtudes kohutavast ebavõrdsusest: |M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1);
• Järgemööda võetakse n = (1 << k) - 1 nulliga mittetäielike elementide madalamad bitid MC-st ja salvestatakse a:
  • Arvutatakse maagiline hash-funktsioon f, mis tõlgendab n-bitist sõna a k-bitiseks s;
  • Kui s == 0, siis ei ole midagi muuta ja algoritm läheb järgmistele koefitsientidele;
  • Vähendada koefitsiendi absoluutset väärtust, mis vastutab s-ndate bitide eest sõnas a;
  • Kui vähendamise tulemusena toimus lühenemine (koefitsient sai 0), siis korrata sammu algusest;
• Kõik koefitsiendid kodeeritakse RLE ja Huffmani järgi, salvestatakse algsetesse failidesse;
• Arhiivifaili salvestatakse parameeter k;
• Iga faili L originaalses järjekorras arvutatakse MD5-hash ja salvestatakse arhiivifaili.

Tipptehnoloogia

Algoritmi naiivne vorm ja rakendused teistes kõrgematähtsusega (eriti, prügikoristusega) keeltes annaksid kohutava jõudluse, seega realiseerisin kõik need keerukused puhtas C-s ja tegin rida optimeerimisi nii täitmise kiirusel kui ka mälus (te ei oska ette kujutada, kui palju need pildid kaaluvad ilma tihendamiseta isegi DCT-le). Kuid ka nii, alguses jättis täitmise kiirus pigem soovida, seega ei kavatse ma kogu protsessi ja kasutatud meetodeid kirjeldada.

Platvormideülene toimimine on saavutatud libjpeg, pcre ja tinydir raamatukogude kombinatsiooni kasutamise kaudu, mille eest olen neile tänulik. Vaikimisi kompileeritakse kõik tavalisest tee, seega tahavad Windowsi kasutajad endale mingi Cygwini installida või ise Visual Studio ja raamatukogudega tegeleda.

Rakendamine on saadaval käsurea utiliidi ja teegi vormis. Üksikasjade tutvumiseks viimasest saavad huvilised lugeda rida README failis GitHubis, mille lingi ma postituse lõpus jagan. Siin liigume edasi kirjelduse ja töö demonstreerimise juurde.

Kuidas kasutada?

Olgem ettevaatlikud. Kasutatud pilte võib liigutada, ümber nimetada ja kopeerida, kuid tuleb olla äärmiselt ettevaatlik ja mitte muuta nende sisu. Ühe bitti muutmine toob kaasa rikka häire ja teabe taastamise võimatuse.

Oletame, et kompileerimise käigus saime täitmisfaili f5ar. Saame analüüsida teegi suurust, et arvutada selle kasutamise võimalusi lipuga -a: .\/f5ar -a [otsingu kaust] [Perl-i ühilduv regulaaravaldis]. Pakendamine toimub käsuga .\/f5ar -p [otsingu kaust] [Perl-i ühilduv regulaaravaldis] [pakendatav fail] [arhivi nimi], ja dekompresseerimine toimub käsu abil .\/f5ar -u [arhvi fail] [taas taastatud faili nimi].

Töö demonstreerimine

Kuna meetodi efektiivsust näidata, laadisin üles kogu 225 täiesti tasuta koera fotograafia kogu teenusest. Unsplash. Igaühel neist on veidi parem kvaliteet kui tavalised kasutaja fotod, kuid siiski. Igaüks neist on kodeeritud libjpeg abil, et vähendada koodimisraamatukogu eripärade mõju üldisele suurusele. Halvimate tihendatavate andmete näitamiseks genereeriti dd abil juhuslik 36-meetrine (natuke üle 5% kogusuurusest) ühtlaselt jaotatud fail.

Testimise protsess on üsna lihtne:

$ 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
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/

Või ekraanipildina selle huvitatud jaoks

Kuidas näha, algsetest 633 + 36 == 669 megabaidist andmeid kõvakettal jõudsime meeldivamatele 563-le, mis annab meile tihendustegevuse koefitsiendiks umbes 1,188. Selline radikaalne erinevus tuleneb äärmiselt väikestest kaotustest, mis on sarnased klassikaliste meetodite (nt tinyjpg) JPEG-failide optimeerimisega saadud tulemustele. Loomulikult, kasutades steganograafilist tihendamist, ei kaotata teave lihtsalt, vaid seda kasutatakse teiste andmete kodeerimiseks. Veelgi enam, F5 kasutamise tõttu on

Ükskõik millised modifikatsioonid ei ole silmale absoluutselt märgatavad. Allpool oleva spoileriga saab lugeja hinnata erinevust nii visuaalselt kui ka muudatuste komponentide väärtuste originaalist lahutamise teel (mida vähem küllastunud on värv, seda väiksem on erinevus):

Pildilinkide kohta, mis ei mahtunud habrastorage'i

Originaal — https://i.ibb.co/wNDLNcZ/1.jpg
Muudetud — https://i.ibb.co/qWvpfFM/1.jpg
Erinevus — https://i.ibb.co/2ZzhHfD/diff.jpg

Lõpetuseks

Loodan, et suutsin veenda lugejat, et sellised meetodid on võimalikud ja väärivad ellujäämist. Samas võib olla palju lihtsam osta kõvaketas või täiendav kanal (võrgus edastamiseks), kui proovida sel viisil kokku hoida. Ühelt poolt on see tõsi, ekstensiivne areng on sageli lihtsam ja usaldusväärsem. Kuid teisest küljest ei tohiks unustada ka intensiivset lähenemist. Lõppude lõpuks ei ole mingit garantiid, et homme saab poodi minna ja osta endale uus kõvaketas tuhande terabaidi mahuga, aga juba kodus olemasolevaid saab alati kasutada.

-> GitHub

Allikas: habr.com