Kui me räägime steganograafiast, siis mõtlevad inimesed terroristidele, pedofiilidele, spioonidele või parimal juhul krüptoanarhistidele ja teistele teadlastele. Ja tõesti, kellel veel vaja võiks minna peita midagi välistest silmadest? Mis kasu võib sellest olla tavainimesele?
Selgub, et üks on olemas. Seetõttu tihendame täna andmeid steganograafia meetoditega. Ja lõpuks saab lugeja isegi kasutada oma väärtuslikke fotoarhiive JPEG-vormingus, et suurendada failisüsteemis vabade gigabaitide arvu.
Mis?
Kui lugeja mäletab, on steganograafia sellised kummalised algoritmid, mis võimaldavad peita ühe teabe olemasolu teise sees. Veel lihtsamas keeles: pilt + fail == umbes sama pilt, kuid mitte päris (piltide asemel võib olla mida iganes, aga tavaliselt on neil kõik selgem). Ei tohiks olla lihtne viis kindlaks teha, kas sees on midagi või mitte.
Aga kui ühte ei saa teisest eristada, kas siis on üldse vahet? Tarbija seisukohast ei huvita kasutajat matemaatiline täpsus (mida peegeldab konkreetne bittide kogum), vaid see, mida ta tajub.
Näiteks vaatame kolme pilti armsast koerast:
Ettevaatust, JPEG!
Vaatamata tohutule suuruse erinevusele valivad vähesed inimesed kolmanda versiooni. Teisest küljest ei ole kahe esimese foto erinevus nii märgatav ja info hulk neil (minu vaatenurgast) võib olla võrdne.
See põhimõte ise on juba vana ja seda on palju aastaid aktiivselt kasutatud kadudega teabe tihendamise meetodite abil. Kuid lõhkumine ei ole ehitamine, meid huvitab probleemi arenenum pool. Kas on võimalik manustada lisateavet suuruse kohta N faili, nii et selle suurus suureneb M < N, kuid muudatused ei olnud kasutajale märgatavad?
Muidugi sa suudad. Kuid tasub kohe teha paar reservatsiooni:
- Esiteks peab meetod olema universaalne ja andma positiivse tulemuse enamiku sisendandmete puhul. See tähendab, et keskmiselt peaks juhusliku sisendi korral salvestatava teabe hulk tegelikult vähenema. "Keskmiselt" tähendab, et võib juhtuda vastupidine, kuid see ei tohiks domineerida.
- Teiseks peab tihendatud konteineri suurus enne teabe manustamist olema suurem kui selle sarnasel viisil tihendatud modifikatsioon. Lihtsalt hunniku bittide manustamine BMP-piltidesse LSB-meetodi abil ei ole steganograafiline pakkimine, kuna pärast mingit tüüpi DEFLATE'i läbimist on algne pilt tõenäoliselt märgatavalt väiksem.
- Kolmandaks tuleb tulemus läbi viia ja võrrelda klassikaliste meetoditega juba tihendatud andmetega. See eemaldab nende liiasuse erinevuste tõenäosusliku mõju ja tagab üldiselt tõhusama tihendamise.
Kus?
Steganograafia kasutamine tähendab, et lisaks tihendatud teabele vajame konteinereid, kuhu see manustatakse. Manustatud teabe maksimaalne hulk sõltub suuresti üksikutest omadustest, kuid nende arvuga on palju lihtsam skaleerida. Seetõttu peab konteinerivorming olema ühine, et kasutajal oleks neid piisavalt, et pakkimisprotsessist kasu saada.
Selles kontekstis on graafika-, heli- ja videofailid head kandidaadid. Kuid erinevate vormingute, koodekite jne mitmekesisuse tõttu on meil praktikas jäetud valik mitte nii paljude võimaluste hulgast.
Seda kõike arvestades langes minu valik JPEG-ile, see on peaaegu kõigil olemas, see on laialdaselt kasutusel nii isiklikul kui ka ärilistel eesmärkidel, olles enamiku piltide jaoks peaaegu de facto formaat.
See sõltub?
Järgmiseks on ilma suurema selgituseta lähi- ja tehnilised skeemid ning kirjeldused, nii et huvilised võivad need vahele jätta, kerides rubriiki “Kõrgtehnoloogiad”.
Ühised omadused
Andmete kuhugi manustamiseks peate esmalt määrama, kuhu. Failisüsteemis võib olla suvaline arv erinevaid fotosid, millest kasutaja võib soovida kasutada vaid mõnda. Nimetame sellist soovitud konteinerite komplekti raamatukoguks.
See moodustub kahel juhul: enne kompressiooni ja enne dekompressiooni. Esimesel juhul saate lihtsalt kasutada failide failinimede komplekti (või veel parem, nende jaoks regulaaravaldist), kuid teisel juhul on vaja midagi usaldusväärsemat: kasutaja saab neid failisüsteemis kopeerida ja teisaldada. , mis takistab nende õiget tuvastamist. Seetõttu tuleb pärast kõigi muudatuste tegemist salvestada nende räsid (piisab md5-st).
Sel juhul pole mõtet esialgset otsingut läbi viia regulaaravaldise abil kogu failisüsteemi ulatuses, piisab teatud juurkataloogi määramisest. Sellesse salvestatakse spetsiaalne arhiivifail, mis sisaldab neid räsi koos muu metateabega, mis on vajalik tihendatud teabe hilisemaks taastamiseks.
Kõik see kehtib võrdselt mis tahes steganograafilise andmete tihendamise algoritmi rakendamise kohta. Andmete tihendamise ja taastamise protsesse võib nimetada pakkimiseks ja lahtipakkimiseks.
F5
Nüüd, kus on selgeks saanud, mida ja miks me teeme, jääb üle kirjeldada eesmärgi saavutamise algoritmi. Tuletagem meelde JPEG-faili kodeerimise protsessi (tänu Baumani rahvusraamatukogu wikile):
Seda vaadates on parem teha kohe mõned kommentaarid:
- JPEG-faili suurust võib pidada optimaalseks, isegi proovimata seda mingisuguse Winrariga tihendada;
- Ainult salvestatud teavet (mis on väljastatud diskreetsest koosinuse teisendusest, DCT) saab muuta, et tagada vähemalt vastuvõetav jõudlus.
- Selleks, et mitte kaotada kasutajale märgatavaid andmeid tööstuslikus mastaabis, tuleb iga üksiku pildi puhul teha minimaalselt muudatusi;
Nende tingimustega sobib terve algoritmide perekond, millega saate end kurssi viia . Neist kõige arenenum on algoritm Andreas Westfeld, kes töötab heleduse komponendi DCT koefitsientidega (inimsilm on selle muutuste suhtes kõige vähem tundlik). Selle üldine paigutus olemasoleva JPEG-failiga töötamisel kuvatakse järgmiselt:
F5 plokk kasutab maatrikskodeeringul põhinevat täiustatud manustamistehnikat. Lugeja saab selle ja algoritmi enda kohta lähemalt tutvuda ülaltoodud lingilt, kuid meid huvitab eelkõige see, et tema abiga saab sama infohulga manustamisel teha seda vähem muudatusi, seda suurem on kasutatava konteineri suurus. , ja teostamiseks. Algoritm peab tegema ainult lihtsaid Huffmani ja RLE (de)kodeerimisoperatsioone.
Muudatused ise tehakse täisarvu koefitsientides ja taanduvad nende absoluutväärtuse ühe võrra vähendamisele, mis võimaldab üldiselt andmete tihendamiseks kasutada F5. Asi on selles, et vähendatud koefitsient absoluutväärtuses võtab pärast Huffmani kodeerimist JPEG-i väärtuste statistilise jaotuse tõttu tõenäoliselt vähem bitte.
Nulli moodustamise korral (nn redutseerimine) vähendatakse salvestatud teabe arvu selle suuruse võrra, kuna endine sõltumatu koefitsient muutub osaks RLE kodeeritud nullide jadast:
Muudatused
Andmekaitse ja tihendamine on ortogonaalsed probleemid, seega võib algse algoritmi salajase parooli permutatsiooni tähelepanuta jätta. Veelgi enam, me peame teadma täpselt, kuidas andmeid välja tõmmata, nii et kogu selleks vajalik teave (mis konteinereid kasutati, millises järjekorras jne) tuleks salvestada eraldi faili ja olla arhiveerijale tasuta lugemiseks avatud.
Algoritm on loodud salasõnumite edastamiseks, seega töötab see korraga ainult ühe konteineriga, eeldades, et kasutaja ise jagab selle vajadusel osadeks, kui neid on. Veelgi enam, igasse konteinerisse eraldi manustatuna peate eelnevalt teadma, mitu bitti andmeid igasse konteinerisse sisestada. Seetõttu tuleks teegi iga elemendi koefitsiendid ühendada üheks abstraktseks suureks ja töötada sellega algse algoritmi järgi.
Kuna algne F5 lubab kuni 12% konteineri suurusest, suurendab see muudatus ka maksimaalset mahtu: "kuni 12%" kogu teegi suurusest on suurem kui "kuni 12%" või sellega võrdne. " igast selle elemendist.
Kodifitseeritud üldskeem on järgmine:
Algoritm ise
Nüüd on aeg kirjeldada algoritmi ennast algusest lõpuni, et lugejat mitte pimedas hoida:
- Kasutaja määrab binaarsed tihendatavad andmed M ja teegi L kasutades regulaaravaldist ja otsingu juurkataloogi;
- FS-is kuvamise järjekorras moodustavad teegi elemendid MC:
- Faili andmetest dekodeeritakse rida koefitsiente C;
- MC <- MC | C;
- Parameeter k määratakse kohutava ebavõrdsuse põhjal:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Järgmisena võetud
n = (1 << k) - 1nullist erineva elemendi vähima tähtsusega bitid MC-st ja kirjutatud sinnaa:- Arvestatakse maagilist räsifunktsiooni
f, mis esindab n-bitist sõnaak-bitisekss; - kui
s == 0, siis pole vaja midagi muuta ja algoritm liigub edasi järgmiste koefitsientide juurde; - Vähendage eest vastutava koefitsiendi absoluutväärtust
s- hei, jäi sõna sekkaa; - Kui vähendamise tulemusena toimub vähenemine (koefitsient muutub 0-ks), siis korrake sammu algusest peale;
- Arvestatakse maagilist räsifunktsiooni
- Kõik koefitsiendid on kodeeritud RLE ja Huffmani poolt, kirjutatud lähtefailidesse;
- Parameeter k kirjutatakse arhiivifaili;
- Igast failist L arvutatakse MD5 räsi nende algse asukoha järjekorras ja kirjutatakse arhiivifaili.
Kõrgtehnoloogiline
Algoritmi naiivne vorm ja rakendused teistes kõrgetasemelistes (eriti prügikoristus) keeltes annaksid kohutava jõudluse, nii et rakendasin kõik need keerukused puhtas C-s ja tegin mitmeid optimeerimisi nii täitmiskiiruse kui ka mälu (teil pole õrna aimugi, kui palju need pildid ilma pakkimiseta kaaluvad isegi enne DCT-d). Kuid isegi nii jättis täitmise kiirus esialgu palju soovida, nii et ma ei kirjelda kogu protsessi ja kasutatud meetodeid.
Platvormideülene saavutatakse libjpeg, pcre ja tinydiri teekide kombinatsiooni abil, mille eest täname neid. Vaikimisi kompileeritakse kõik tavalise kaudu make, nii et Windowsi kasutajad soovivad installida mõne Cygwini või tegeleda Visual Studio ja teekidega iseseisvalt.
Rakendus on saadaval konsooliutiliidi ja teegi kujul. Viimase kasutamise kohta saavad huvilised lähemalt tutvuda Githubis asuvas repositooriumis readme'is, mille lingi lisan postituse lõppu. Ja siin liigume edasi töö kirjelduse ja demonstratsiooni juurde.
Kuidas kasutada?
Hoolikalt. Kasutatud pilte saab vastavalt soovile teisaldada, ümber nimetada ja kopeerida. Siiski peaksite olema äärmiselt ettevaatlik ja ärge muutke nende sisu mingil viisil. Ühe biti muutmine häirib räsi ja muudab teabe taastamise võimatuks.
Oletame, et pärast kompileerimist saame käivitatava faili f5ar. Saate lipu abil analüüsida raamatukogu suurust, et arvutada selle kasutusvõimalused -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Pakkimise teeb meeskond ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива]ja lahti pakkimine kasutades ./f5ar -u [файл архива] [имя восстановленного файла].
Töö demonstreerimine
Meetodi tõhususe näitamiseks laadisin teenusest üles 225 täiesti tasuta fotost koosneva kollektsiooni koertest. . Igaüks neist on tavakasutajate fotodest veidi kõrgema kvaliteediga, kuid siiski. Igaüks neist kodeeriti uuesti libjpegi abil, et neutraliseerida teegi kodeerimisfunktsioonide mõju üldisele suurusele. Et näidata kokkusurutavate andmete halvimat näidet, genereeriti dd abil juhuslikult 36-meetrine (veidi üle 5% kogumahust) ü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 ekraanipilt fännidele
Nagu näete, saime kõvakettal olevast algsest 633 + 36 == 669 megabaidist andmemahust ilusama 563, mis andis meile tihendussuhteks ~1,188. Seda radikaalset erinevust seletatakse äärmiselt väikeste kadudega, mis on sarnased JPEG-failide optimeerimisel klassikaliste meetodite (nt tinyjpg) abil. Loomulikult ei lähe steganograafilise pakkimise kasutamisel informatsioon lihtsalt "kaotsi", vaid seda kasutatakse muude andmete kodeerimiseks, lisaks on F5 kasutamise tõttu "optimeeritud" koefitsiente palju väiksem kui traditsioonilise optimeerimise korral.
Ükskõik, millised modifikatsioonid on, on need silmale täiesti nähtamatud. Alloleva spoileri all saab lugeja erinevust hinnata nii silma järgi kui ka muudetud komponendi väärtused originaalist lahutades (mida vaigisem värv, seda väiksem on erinevus):
Lingid piltidele, mis ei mahu habrastorage'i
Originaal -
Muudetud –
Erinevus –
Selle asemel, et järeldus
Loodan, et suutsin lugejat veenda, et sellised meetodid on võimalikud ja neil on õigus elule. Kõvaketta või lisakanali ostmine (võrguedastuseks) võib aga tunduda palju lihtsama võimalusena, kui sellisel viisil raha säästa. Ühest küljest on see tõsi, ulatuslik arendus on sageli lihtsam ja usaldusväärsem. Kuid teisest küljest ei tohiks me unustada intensiivset. Pole ju mingit garantiid, et homme jõuad poodi ja ostad endale veel tuhande terabaidise kõvaketta, vaid saad alati kasutada neid, mis sul juba kodus lebavad.
->
Allikas: www.habr.com