As wy prate oer steganography, minsken tinke oan terroristen, pedofilen, spionnen, of, op syn bêste, cryptoanarchists en oare wittenskippers. En echt, wa oars miskien nedich ferstopje wat fan eksterne eagen? Wat kin it foardiel fan dit wêze foar in gewoane persoan?
It docht bliken dat der ien is. Dêrom sille wy hjoed gegevens komprimearje mei steganografyske metoaden. En op it lêst sil de lêzer sels syn kostbere foto-argiven brûke kinne yn JPEG's om it oantal fergese gigabytes op it bestânsysteem te ferheegjen.
Wat?
As de lêzer it ûnthâldt, is steganografy sokke frjemde algoritmen dy't it mooglik meitsje om de oanwêzigens fan ien ynformaasje yn in oar te ferbergjen. Yn noch ienfâldiger taal: foto + triem == likernôch deselde foto, mar net hielendal (ynstee fan plaatsjes kin der fan alles wêze, mar meastentiids is alles dúdliker yn). D'r soe gjin maklike manier wêze moatte om te bepalen oft d'r wat yn sit of net.
Mar as it iene net fan it oare te ûnderskieden is, is d'r dan dan überhaupt ferskil? Ut it eachpunt fan de konsumint, de brûker net skele oer de wiskundige presyzje (reflektearre troch in bepaalde set fan bits), allinnich wat wurdt waarnommen troch him.
Litte wy bygelyks nei trije bylden fan in leuke hûn sjen:
Pas op, JPEG!
Nettsjinsteande it grutte ferskil yn grutte, in pear minsken sille kieze de tredde ferzje. Oan 'e oare kant is it ferskil tusken de earste twa foto's net sa merkber, en kin de hoemannichte ynformaasje dêryn (út myn eachpunt) gelyk wêze.
Dit prinsipe sels is al âld en is in protte jierren aktyf eksploitearre troch lossy ynformaasje kompresje metoaden. Mar brekken is net bouwen; wy binne ynteressearre yn 'e mear avansearre kant fan' e kwestje. Is it mooglik om ynfoegje ekstra grutte ynformaasje N nei it bestân sadat de grutte fergruttet mei M < N, mar de feroarings wiene net merkber foar de brûker?
Fansels kinne jo. Mar it is it wurdich om direkt in pear reservearrings te meitsjen:
- As earste moat de metoade universeel wêze en in posityf resultaat jaan op de measte ynfiergegevens. Dat is, yn trochsneed, foar in willekeurige ynput, moat der in feitlike fermindering wêze yn 'e hoemannichte ynformaasje opslein. "Gemiddeld" betsjut dat it tsjinoerstelde kin foarkomme, mar net oerhearskje moat.
- Twads moat de grutte fan 'e komprimearre kontener foardat ynformaasje ynbêde grutter wêze dan syn modifikaasje komprimearre op in ferlykbere manier. Gewoan ynbêde in boskje bits yn BMP-ôfbyldings mei de LSB-metoade is gjin steganografyske kompresje, om't, nei't se troch in soarte fan DEFLATE útfierd is, de orizjinele ôfbylding nei alle gedachten merkber lytser sil wêze.
- Tredde, it resultaat moat wurde útfierd en fergelike mei respekt foar gegevens al komprimearre troch klassike metoaden. Dit sil it probabilistyske effekt fan ferskillen yn har redundânsje ferwiderje en effisjinter kompresje leverje yn it algemiene gefal.
Wêr
It brûken fan steganography ymplisearret dat, neist de komprimearre ynformaasje, wy sille nedich containers dêr't it sil wurde ynbêde. De maksimale hoemannichte ynbêde ynformaasje hinget foar in grut part ôf fan yndividuele eigenskippen, mar it is folle makliker om te skaaljen mei har oantal. Dêrom moat it kontenerformaat gewoan wêze, sadat de brûker genôch fan har hat om foardiel te krijen fan it "kompresje" -proses.
Yn dit ferbân binne grafiken, audio- en fideobestannen goede kandidaten. Mar, fanwege it ferskaat oan ferskillende formaten, codecs, ensfh, yn 'e praktyk bliuwe wy mei in kar út net safolle opsjes.
Mei it each op dit alles foel myn kar op JPEG. Hast elkenien hat it, it wurdt in soad brûkt foar sawol persoanlike as saaklike doelen, en is hast it de facto-formaat foar de measte ôfbyldings.
It hinget ôf?
Dêrnei binne d'r tichtby- en technyske diagrammen en beskriuwingen sûnder folle útlis, sadat belangstellenden se kinne oerslaan troch te rôljen nei de seksje "High Technologies".
Mienskiplike funksjes
Om gegevens earne yn te foegjen, moatte jo earst bepale wêr. D'r kinne in oantal ferskillende foto's op it bestânsysteem wêze, wêrfan de brûker mar in pear wol brûke wol. Sa'n winske set fan konteners sille wy in bibleteek neame.
It wurdt foarme yn twa gefallen: foar kompresje en foar dekompresje. Yn it earste gefal kinne jo gewoan in set bestânsnammen brûke (of better noch, in reguliere útdrukking foar har) fan bestannen, mar yn it twadde is wat betrouberer nedich: de brûker kin se kopiearje en ferpleatse binnen it bestânsysteem , dêrmei foarkommen dat se korrekt identifisearre wurde. Dêrom is it nedich om har hashes op te slaan (md5 is genôch) nei't alle wizigingen binne makke.
Yn dit gefal is d'r gjin punt om de earste sykopdracht út te fieren mei in reguliere ekspresje yn it heule bestânsysteem; it is genôch om in bepaalde root-map op te jaan. In spesjale argyfbestân sil dêryn wurde bewarre, dy't dizze hashes sil befetsje, tegearre mei oare meta-ynformaasje dy't nedich is foar it folgjende herstel fan komprimearre ynformaasje.
Dit alles jildt likegoed foar elke ymplemintaasje fan elke steganografyske gegevenskompresjealgoritme. De prosessen fan gegevenskompresje en herstel sels kinne wurde neamd ynpakken en útpakke.
F5
No't dúdlik wurden is wat wy dogge en wêrom, bliuwt it om it algoritme te beskriuwen foar it berikken fan it doel. Litte wy it proses fan it kodearjen fan in JPEG-bestân ûnthâlde (mei tank oan de wiki fan 'e Bauman National Library):
As jo nei sjogge, is it better om fuortendaliks in pear opmerkingen te meitsjen:
- De grutte fan in JPEG-bestân kin as optimaal beskôge wurde sûnder sels te besykjen it te komprimearjen mei in soarte fan Winrar;
- Allinich de opsleine ynformaasje (dy't wurdt útfierd fan 'e diskrete cosinustransformaasje, DCT) kin wizige wurde om op syn minst akseptabele prestaasjes te leverjen.
- Om net te ferliezen gegevens op in yndustriële skaal merkber foar de brûker, is it nedich om te meitsje in minimum oanpassings oan elke yndividuele ôfbylding;
In hiele famylje fan algoritmen past by dizze betingsten, wêrmei jo josels fertroud meitsje kinne . De meast avansearre fan harren is it algoritme troch Andreas Westfeld, wurkjen mei de DCT-koëffisjinten fan 'e helderheidskomponint (it minsklik each is it minste gefoelich foar syn feroaringen). De algemiene yndieling by it wurkjen mei in besteande JPEG-bestân wurdt as folget werjûn:
It F5-blok brûkt in avansearre ynbêdetechnyk basearre op matrixkodearring. De lêzer kin der mear oer leare en it algoritme sels by de boppesteande link, mar wy binne benammen ynteressearre yn it feit dat jo mei har help hoe minder wizigingen meitsje kinne by it ynbêdzjen fan deselde hoemannichte ynformaasje, hoe grutter de grutte fan 'e brûkte kontener , en foar it útfieren fan it It algoritme hoecht allinich ienfâldige Huffman- en RLE (de)kodearjen operaasjes út te fieren.
De wizigingen sels wurde makke oan heulegetalkoëffisjinten en komme del op it ferminderjen fan har absolute wearde mei ien, wêrtroch, yn 't algemien, F5 kin wurde brûkt foar gegevenskompresje. It punt is dat de fermindere koëffisjint yn absolute wearde nei alle gedachten minder bits sil besette nei Huffman-kodearring fanwegen de statistyske ferdieling fan wearden yn JPEG.
Yn it gefal fan 'e foarming fan in nul (de saneamde reduksje) sil it oantal opsleine ynformaasje wurde fermindere troch syn grutte, om't de eardere ûnôfhinklike koeffizient diel wurde sil fan' e RLE-kodearre folchoarder fan nullen:
Feroarings
Gegevensbeskerming en kompresje binne ortogonale problemen, sadat de geheime wachtwurdpermutaasje fan it orizjinele algoritme kin wurde negeare. Boppedat moatte wy krekt witte hoe't jo de gegevens ekstrahearje, dus alle ynformaasje dy't hjirfoar nedich is (hokker konteners waarden brûkt, yn hokker folchoarder, ensfh.) moatte wurde opnommen yn in apart bestân en iepen wêze foar fergees lêzen troch de argivator.
It orizjinele algoritme is ûntworpen om geheime berjochten te ferstjoeren, sadat it wurket mei mar ien kontener tagelyk, oannommen dat de brûker sels it yn dielen sil brekke as it nedich is, as dat is. Boppedat, as jo ûnôfhinklik yn elke kontener binne ynbêde, moatte jo fan tefoaren witte hoefolle bits gegevens elk yn te setten. Dêrom moatte de koeffizienten fan elk elemint fan 'e bibleteek wurde kombineare yn ien abstrakte grutte en dêrmei wurkje neffens it orizjinele algoritme.
Om't de orizjinele F5 oant 12% fan 'e kontenergrutte tastiet, sil dizze modifikaasje ek de maksimale kapasiteit ferheegje: "oant 12%" fan 'e grutte fan' e hiele bibleteek is grutter as of lyk oan de som fan "oant 12% "fan elk fan syn eleminten.
It kodifisearre algemiene skema is as folget:
It algoritme sels
No is it tiid om it algoritme sels fan begjin oant ein te beskriuwen, om de lêzer net yn it tsjuster te hâlden:
- De brûker definiearret de binêre kompressibele gegevens M en de bibleteek L mei in reguliere ekspresje en in sykrootmap;
- Yn 'e folchoarder dy't se op' e FS ferskine, foarmje de biblioteekeleminten de MC:
- In rige fan koeffizienten C wurde dekodearre út de triem gegevens;
- MC <- MC | C;
- De parameter k wurdt bepaald op basis fan 'e skriklike ûngelikens:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Folgjende nommen
n = (1 << k) - 1minste wichtige bits fan net-nul eleminten út MC en skreaun oana:- De magyske hashfunksje wurdt beskôge
f, fertsjintwurdiget in n-bit wurdaoan k-bits; - as
s == 0, dan is it net nedich om neat te feroarjen en it algoritme giet troch nei de folgjende koeffizienten; - Ferminderje de absolute wearde fan 'e koeffizient ferantwurdlik foar
s-hey bit yn it wurda; - As as gefolch fan de reduksje in reduksje optreedt (de koeffizient wurdt 0), werhelje de stap fan it begjin ôf;
- De magyske hashfunksje wurdt beskôge
- Alle koeffizienten wurde kodearre troch RLE en Huffman, skreaun nei de boarne triemmen;
- De parameter k wurdt skreaun nei it argyfbestân;
- In MD5-hash wurdt berekkene út elke triem L yn 'e folchoarder fan har oarspronklike lokaasje en skreaun nei it argyfbestân.
High tech
De naïve foarm fan it algoritme en ymplemintaasjes yn oare talen op heech nivo (benammen mei garbage collection) soe ferskriklike prestaasjes jaan, dus ik ymplementearre al dizze kompleksiteiten yn pure C en útfierde in oantal optimalisaasjes sawol yn termen fan útfieringssnelheid as ûnthâld (jo hawwe gjin idee hoefolle dizze de foto's weagje sûnder kompresje sels foar DCT). Mar ek sa, yn 't earstoan liet de snelheid fan útfiering folle te winskjen oer, dus ik sil it heule proses en brûkte metoaden net beskriuwe.
Cross-platfoarm wurdt berikt mei in kombinaasje fan libjpeg, pcre en tinydir bibleteken, wêrfoar wy tankje se. Standert wurdt alles kompilearre fia normaal make, sadat Windows-brûkers wat Cygwin foar harsels ynstallearje wolle, of omgean mei Visual Studio en bibleteken op har eigen.
De ymplemintaasje is beskikber yn 'e foarm fan in konsole-hulpprogramma en biblioteek. Dyjingen dy't ynteressearre binne kinne mear útfine oer it brûken fan it lêste yn 'e readme yn' e repository op Github, de keppeling dêr't ik oan 'e ein fan' e post sil hechtsje. En hjir geane wy oer nei in beskriuwing en demonstraasje fan it wurk.
Hoe kinne jo brûke?
Foarsichtich. Brûkte ôfbyldings kinne wurde ferpleatst, omneamd en kopieare as jo wolle. Jo moatte lykwols ekstreem foarsichtich wêze en har ynhâld op gjin inkelde manier feroarje. It feroarjen fan ien bit sil de hash fersteure en it ûnmooglik meitsje om de ynformaasje te herstellen.
Stel dat wy nei kompilaasje de útfierbere triem f5ar krije. Jo kinne de grutte fan 'e bibleteek analysearje om de mooglikheden fan it gebrûk te berekkenjen mei de flagge -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Ferpakking wurdt dien troch it team ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], en útpakke mei help ./f5ar -u [файл архива] [имя восстановленного файла].
Demonstraasje fan wurk
Om de effektiviteit fan 'e metoade sjen te litten, haw ik in samling fan 225 absolút fergese foto's fan hûnen fan 'e tsjinst opladen . Elk fan har hat in wat hegere kwaliteit dan gewoane brûkersfoto's, mar dochs. Elk fan harren waard opnij kodearre mei libjpeg om de ynfloed fan 'e kodearringfunksjes fan' e biblioteek op 'e totale grutte te neutralisearjen. Om it slimste foarbyld fan komprimerbere gegevens oan te jaan, waard in willekeurige 36-meter (wat mear as 5% fan 'e totale grutte) unifoarm ferdielde triem generearre mei dd.
It testproses is frij simpel:
$ 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/Of in skermprint foar fans
Sa't jo sjen kinne, fan 'e orizjinele 633 + 36 == 669 megabytes oan gegevens op' e hurde skiif, einige wy mei in moaier 563, wat ús in kompresjeferhâlding fan ~1,188 joech. Dit radikale ferskil wurdt ferklearre troch ekstreem lytse ferliezen, fergelykber mei dy krigen by it optimalisearjen fan JPEG-bestannen mei klassike metoaden (lykas tinyjpg). Fansels, by it brûken fan steganografyske kompresje, wurdt ynformaasje net gewoan "ferlern", mar wurdt brûkt om oare gegevens te kodearjen. Boppedat is it oantal "optimisearre" koeffizienten troch it brûken fan F5 folle minder as by tradisjonele optimalisaasje.
Wat oanpassings der binne, se binne perfoarst ûnsichtber foar it each. Under de spoiler hjirûnder kin de lêzer it ferskil evaluearje sawol mei each as troch de wearden fan 'e feroare komponint fan it orizjineel ôf te lûken (hoe minder de kleur, hoe lytser it ferskil):
Keppelings nei ôfbyldings dy't net passe op habrastorage
Oarspronklik -
Feroare -
Ferskil -
Yn stee fan in konklúzje
Ik hoopje dat ik de lêzer oertsjûgje koe dat sokke metoaden mooglik binne en rjocht hawwe op it libben. It keapjen fan in hurde skiif of in ekstra kanaal (foar netwurktransmission) kin lykwols in folle ienfâldiger opsje lykje dan besykje op dizze manier jild te besparjen. Oan 'e iene kant is dit wier; wiidweidige ûntwikkeling is faak ienfâldiger en betrouber. Mar oan 'e oare kant moatte wy it yntinse net ferjitte. Der binne ommers gjin garânsjes dat jo moarn nei de winkel kinne komme en sels noch in tûzen terabyte hurde skiif keapje kinne, mar dy kinne jo altyd brûke dy't jo thús al lizzen hawwe.
->
Boarne: www.habr.com