Kasutame steganograafiat, et säästa ruumi kõvakettal

Kui me räägime steganograafiast, siis inimesed kujutavad endale ette terrorismi, pedofiile, spioone, ehkki parimal juhul ka krüptoanarchiste ja teisi teadlasi. Ja tõepoolest, kellele veel seda üldse võiks vaja minna? peita midagi väliste pilkude eest? Mis kasu sellest tavalisele inimesele võiks olla?

Selgub, et mingi kasu on olemas. Just seepärast hakkame täna andmeid steganograafia meetoditega kokkupanema. Ja lõpuks saab lugeja isegi kasutada oma väärtuslikke JPEG-fotoarhiive, et suurendada vabade gigabaitide arvu failisüsteemis.

Mida?

Kui lugeja mäletab, siis steganograafia — need on kummalised algoritmid, mis võimaldavad peita üht infot teise sisse. Veel lihtsamalt öeldes: pilt + fail == umbes sama pilt, aga mitte päris (pilti võib asendada millega iganes, aga tavaliselt on piltide puhul kõik arusaadavam). Samas ei tohiks olla lihtsat viisi määrata, kas sees on midagi või mitte.

Aga kui ühte teisest eristada ei saa, kas siis üldse on vahet? Tarbija, kasutaja ei muretse matemaatilise täpsuse pärast (mida peegeldab konkreetne bittide kogum), vaid ainult selle üle, kuidas nad seda tajuvad.

Vaatame näiteks kolme armsa koera pilti:

Olge ettevaatlik, JPEG!

Vaatamata tohutule suuruse erinevusele valib vähe inimesi kolmanda versiooni. Teiselt poolt ei ole kahe esimesse foto vahel vahe nii märgatav ja nende informatsiooni hulk (minu arvates) on sarnane.

See põhimõte on iseenesest juba vana ja on mitu aastat aktiivselt kasutusel kaotava infokasutatuse meetoditega. Kuid purustamine ei ole ehitamine; meie huvi on arenenumate küsimuste poole. Kas on võimalik lisada täiendavat teavet suuruses N faili nii, et selle suurus suureneks M < N, ja muudatused ei oleks kasutajale märgatavad?

Muidugi on see võimalik. Kuid tasub kohe teha paar tähelepanekut:

• Esiteks peab meetod olema universaalne ja andma positiivse tulemuse enamus sisendandmete korral. See tähendab, et keskmiselt, mistahes sisendi jaoks, peab toimuma tegelik salvestatud teabe vähenemine. "Keskmiselt" tähendab, et vastupidised juhtumid võivad esineda, kuid ei tohi olla enamuses.
• Teiseks peab komprimeeritud konteineri maht enne teabe sisestamist olema suurem kui sarnasel viisil komprimeeritud selle modifikatsioon. Lihtsalt BMP-pilte LSB meetodil mitmete bittide sisestamine ei ole steganograafiline kompressioon, kuna originaalpilt, kui see läbi näiteks DEFLATE'i viia, on tõenäoliselt märgatavalt väiksem.
• Kolmandaks tuleb tulemusi hinnata ja võrrelda juba klassikaliste meetoditega komprimeeritud andmete suhtes. See võimaldab kõrvaldada tõenäosusliku efekti nende liigsete andmete erinevustest ja viia ellu tõhusamat kompressiooni üldjuhul.

Kus?

Steganograafia kasutamine eeldab, et lisaks surutud teabele on meil vaja ka konteinerite faile, kuhu see integreeritakse. Integreeritava teabe maksimaalne hulk sõltub paljuski individuaalsetest omadustest, kuid nende arvu suurenedes muutub see palju lihtsamaks. Seetõttu peaks konteineriformaat olema levinud, et kasutajal oleks piisavalt nende varusid, et protsessist „surumine“ mingit kasu saada.

Selles kontekstis on head kandidaadid graafilised, audio- ja videofailid. Kuid, erinevate formaatide, koodekite jms mitmekesisuse tõttu jääb meile praktikas valik mitte kuigi paljusid variante.

Kuna arvesse tuleb võtta kõiki neid aspekte, langetasin otsuse JPEG-i kasuks. See on praktiliselt kõigil kasutuses, laialdaselt nii isiklikel kui äritegevuse eesmärkidel, olles de facto formaat enamikule piltidest.

K̶o̶g̶d̶a̶ Kuidas?

Edasi liikudes on umbes tehnilised skeemid ja kirjeldused, ilma eriliste selgitusteta, seega soovijad võivad need vahele jätta, kerides jaotisse „Tipptehnoloogia“.

Üldised jooned

Andmete lisamiseks on kõigepealt vaja määrata, kuhu need paigutada. Failisüsteemis võib olla palju erinevaid fotosid, millest kasutaja soovib valida ainult mõned. Sellist soovitud konteinerite kogumit nimetame raamatukoguks.

See kujuneb kahes olukorras: enne kokkusurumist ja enne lahti pakkimist. Esimeses olukorras võib kasutada lihtsalt failide nimede komplekti (veel parem, regulaarset väljendit nende jaoks), kuid teises olukorras on vajalik midagi usaldusväärsemat: kasutaja võib neid failide süsteemide vahel kopeerida ja liigutada, mistõttu on keeruline neid korrektselt määrata. Seetõttu on vajalik nende hash-koodide (md5 piisab) salvestamine pärast kõiki muudatusi.

Algne otsing regulaarse väljendi abil ei ole mõtet teha kogu FS-i ulatuses, piisab, kui määrata mõni juurkataloog. Just sellesse salvestatakse eriline arhivifail, kus hoitakse neid hash-koodide koos muu meta-informatsiooniga, mis on vajalik edasiseks kokkusurutud teabe taastamiseks.

Kõik see kehtib igasuguste steganograafilise andmekompressiooni algoritmide rakenduste kohta. Andmete kokkusurumise ja taastamise protsesse võib nimetada pakkimiseks ja lahtipakkimiseks.

F5

Nüüd, kui on selge, mida ja miks teeme, jääb veel 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 kui ei proovita seda näiteks WinRARiga tihendada;
• Muutma tohib ainult salvestatud teavet (seda, mis on diskreetse kosinuse transformatsiooni, DCT, väljundis), et tagada mingisugune vastuvõetav jõudlus.
• Et vältida andmete kadumist märgatavates tööstuslikes mõõtmetes, on vajalik teha iga eraldi pildi korral minimaalne muudatus;

Nende tingimuste jaoks sobib terve algoritmide perekond, millega on võimalik tutvuda selles heas esituses. Kõige arenenum neist on algoritm F5 Andreas Westfeldi autorlusega, kes töötas DCT komponentide heleduse koefitsientide peal (inimese silm on kõige vähem tundlik nende muutuste suhtes). Tema üldine skeem olemasoleva JPEG-faili töötlemiseks on järgmine:

F5 plokk kasutab edasijõudnud sisestamismeetodit, mis põhineb maatriksi kodeerimisel. Lugeja võib selle ja algoritmiga tutvuda ülaltoodud lingil, kuid meid huvitab eelkõige tõsiasi, et selle abil võib sama teabe sisestamiseks teha seda vähem muudatusi, mida suurem on kasutatav konteiner, samas kui algoritmi läbiviimiseks on vajalikud vaid lihtsad (de)koodimise Haffmanni ja RLE toimingud.

Muutused toimuvad täisarvuliste koefitsientide üle ning need vähendavad nende absoluutväärtust ühe võrra, mis võimaldab üldiselt kasutada F5 andmete tihendamiseks. Asi on selles, et absoluutväärtuse vähenenud koefitsient võtab tõenäoliselt pärast Huffmani kodeerimist vähem bitti tänu JPEG-väärtuste statistilisele jaotusele.

Kui moodustub null (nn lühendamine), väheneb salvestatud teabe hulk selle suuruse võrra, kuna endine iseseisev koefitsient muutub osa kodeeritud RLE järjestusest nullidest:

Muutmised

Andmete kaitsmine ja nende tihendamine on ortogonaalsed ülesanded, seega võib originaalalgoritmi salajast parooliga segamist puudutada. Veelgi enam, peame täpselt teadma, kuidas andmeid välja võtta, seega kogu vajalik info (milliseid konteinerit kasutati, missuguses järjekorras jne) peab olema salvestatud eraldi faili ja olema avatud arhivaatori vabaks lugemiseks.

Algoritm on loodud salajaste sõnumite edastamiseks, seega töötab see korraga vaid ühe konteineriga, eeldades, et kasutaja jagab selle vajadusel osadeks, kui seda peaks üldse vajalikuks pidama. Veelgi enam, iga konteineri iseseisva sisestamise korral tuleb eelnevalt teada, kui palju bitsid andmeid igasse paigutada. Seetõttu on mõistlik kõik elemendid raamatukogust koondada üheks abstraktseks suuremaks, millega töötada algset algoritmi järgides.

Kuna originaalne F5 lubab kasutada kuni 12% konteineri suurusest, suurendab selline muudatus ka maksimaalset mahtu: 'kuni 12%' kogu raamatukogu suurusest on suurem või võrdne summaga 'kuni 12%' iga selle elementi puhul.

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

Algoritm ise

Nüüd on aeg kirjeldada algoritmi algusest lõpuni, et mitte jätta lugejat teadmatusse:

• Kasutaja määratleb binaarsed kompressitavad andmed M ja raamatukogu L koos regulaaravalduse ning otsingu juurdirektori abil;
• Järjekorras FS-is kujundavad raamatukogu elemendid MC:
  • Failist dekoeeritakse C koefitsientide seeria;
  • MC <- MC | C;
• Parameeter k määratakse kohutavast ebavõrdsusest: |M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1);
• Järjekorras võetakse n = (1 << k) - 1 nulli elementide madalamaid bitte MC-st ja kirjutatakse a:
  • Arvutatakse maagiline hash-funktsioon f, mis kaardistab n-bitise sõna a k-bitiseks s;
  • Kui s == 0, siis ei ole vaja midagi muuta ja algoritm läheb järgmistele koefitsientidele;
  • Vähendada koefitsiendi absoluutväärtust, mis vastutab s-ná biti sõnas a;
  • Kui vähendamise tulemusel toimus kokkuvõte (koefitsient sai 0), siis alusta samast sammust;
• Kõik koefitsiendid kodeeritakse RLE ja Huffmaniga, kirjutatakse algfailidesse;
• Arhiivifaili kirjutatakse parameeter k;
• Iga faili L puhul, nende algse leidmise järjekorras, arvutatakse MD5-hash ja kirjutatakse arhiivifaili.

Tipptasemel tehnoloogia

Algoritmi ja rakenduste naiivne vorm teistes kõrgema taseme (eriti prügikorjatega) keeltes annaks horrikultöötava jõudluse, seetõttu oleme need keerukused rakendanud puhtas C-s ja teinud rida optimeerimisi nii täitmise kiirusel kui ka mälus (te ei kujuta ette, kui palju need pildid ilma tihendamiseta kaaluvad isegi DCT tasemeni). Kuid sellele vaatamata jättis täitmise kiirus alguses palju soovida, seega ei hakka ma kogu protsessi ja kasutatud meetodeid kirjeldama.

Platvormidevahelisuse oleme saavutanud libjpeg, pcre ja tinydir teekide kombinatsiooni kasutamisega, mille eest rõõmustame. Vaikimisi kompileeritakse kõik tavalise kaudu make, seega soovivad Windowsi kasutajad endale Cygwini installida või ise Visual Studio ja teekide kallal vaeva näha.

Teostus on saadaval konsoolirakenduse ja teekide kujul. Soovijad saavad viimase kasutamise kohta rohkem teavet lugeda readmi-st GitHubi repole, mille linki ma postituse lõpus jagan. Nüüd liigume edasi töötamise kirjelduse ja demonstreerimise juurde.

Kuidas kasutada?

Ole ettevaatlik. Kasutatud pilte võib soovitud viisil liikuda, ümber nimetada ja kopeerida. Siiski tuleb olla äärmiselt ettevaatlik ja mitte muuta nende sisu. Ühe bitti muutmine rikub hash'i ja häirib teabe taastamist.

Olgu, pärast kompileerimist saime täitmise faili f5ar. Raamatukogu suurust saab analüüsida selle kasutusvõimaluste arvutamiseks lipu abil -a: ./f5ar -a [otsingukaust] [Perl-ühilduv regulaaravaldis]. Pakkimine toimub käsuga ./f5ar -p [otsingukaust] [Perl-ühilduv regulaaravaldis] [pakkitav fail] [arhiivi nimi], ja lahtipakkimine toimub ./f5ar -u [arhiivi fail] [taasloodud faili nimi].

Demonstratsioon

Meetodi efektiivsuse näitamiseks laadisin üles 225 täiesti tasuta koerapilti teenusest Unsplash. Iga neist omab veidi kõrgemat kvaliteeti kui tavalised kasutajafotod, kuid sellegipoolest. Iga üks neist on ümberkodeeritud libjpeg'i abil, et vähendada kodeerimise teegi mõju üldisele suurusele. Halvima tihendatud andmete näitamiseks genereeriti juhuslik 36-megabaidine (veidi rohkem kui 5% kogusuurusest) ühtlaselt jaotatud fail.

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

Või ekraanipildina huvilistele

Nagu näha, oleme alates algsetest 633 + 36 == 669 megabytist kettal jõudnud meeldivamate 563-ni, mis annab meile kokkusurumise teguri ~1,188. Selline radikaalne erinevus on seletatav äärmiselt väikeste kadudega, mis on sarnased klassikaliste JPEG-failide optimeerimiseks kasutatavate meetodite (nt tinyjpg) kaudu saadud tulemustele. Loomulikult ei kaota steganograafilise kokkusurumise puhul teave lihtsalt "kaotatakse", vaid seda kasutatakse teiste andmete kodeerimiseks. Veelgi enam, "optimeeritud" koefitsientide arv, kasutades F5-d, on tunduvalt väiksem kui traditsioonilise optimeerimise puhul.

Olenemata modifikatsioonidest ei ole need silmale absoluutselt nähtavad. Allolevas spoileris võib lugeja hinnata erinevust nii pilguga kui ka muudetud komponendi väärtuste originaalsetest lahutades (mida vähem on värv tõlgendatud, seda väiksem on erinevus):

Lingid piltidele, 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

Kokkuvõtte asemel

Loodan, et suutsin veenda lugejat, et sellised meetodid on võimalikud ja nendele on koht olemas. Kuid kõvaketta ostmine või lisakanali hankimine (võrguedastuseks) võib tunduda palju lihtsam lahendus kui sellise meetodi kasutamine. Ühelt poolt on see tõsi, et ulatuslik areng on tihti lihtsam ja usaldusväärsem. Teiselt poolt ei tohiks unustada ka intensiivseid meetodeid. Lõppude lõpuks ei ole mingit garantiid, et homme on võimalik minna poodi ja osta endale järgmine tuhande terabaiti kõvaketas, kuid kodus juba olemasolevate kasutamine on alati võimalik.

-> GitHub

Allikas: habr.com