As ons van steganografie praat, dink mense aan terroriste, pedofiele, spioene, of, op sy beste, kriptoanargiste en ander wetenskaplikes. En regtig, wie anders kan dit nodig hê wegkruip iets van eksterne oë? Wat kan die voordeel hiervan vir 'n gewone mens wees?
Dit blyk dat daar een is. Daarom sal ons vandag data saampers met behulp van steganografie-metodes. En op die ou end sal die leser selfs sy kosbare foto-argiewe in JPEG's kan gebruik om die aantal gratis gigagrepe op die lêerstelsel te vermeerder.
Wat?
As die leser onthou, is steganografie sulke vreemde algoritmes wat dit moontlik maak om die teenwoordigheid van een inligting in 'n ander weg te steek. In nog eenvoudiger taal: prentjie + lêer == ongeveer dieselfde prentjie, maar nie heeltemal nie (in plaas van prentjies kan daar enigiets wees, maar gewoonlik is alles duideliker daarin). Daar behoort nie 'n maklike manier te wees om te bepaal of daar iets binne is of nie.
Maar as die een nie van die ander onderskei kan word nie, is daar hoegenaamd enige verskil? Vanuit die verbruiker se oogpunt gee die gebruiker nie om oor die wiskundige presisie (weerspieël deur 'n bepaalde stel stukkies nie), net wat deur hom waargeneem word.
Kom ons kyk byvoorbeeld na drie beelde van 'n oulike hond:
Pasop, JPEG!
Ten spyte van die groot verskil in grootte, sal min mense die derde weergawe kies. Aan die ander kant is die verskil tussen die eerste twee foto's nie so opvallend nie, en die hoeveelheid inligting daarin (uit my oogpunt) kan ewe groot wees.
Hierdie beginsel self is reeds oud en word vir baie jare aktief uitgebuit deur verliesvolle inligtingsamedrukkingsmetodes. Maar breek is nie bou nie; ons stel belang in die meer gevorderde kant van die saak. Is dit moontlik om addisionele grootte inligting in te sluit N na die lêer sodat die grootte daarvan met M < N, maar die veranderinge was nie opmerklik vir die gebruiker nie?
Natuurlik kan jy. Maar dit is die moeite werd om dadelik 'n paar besprekings te maak:
- Eerstens moet die metode universeel wees en 'n positiewe resultaat op die meeste insetdata gee. Dit wil sê, gemiddeld vir 'n ewekansige inset, moet daar 'n werklike afname wees in die hoeveelheid inligting wat gestoor word. "Gemiddeld" beteken dat die teenoorgestelde mag voorkom, maar nie die oorhand moet kry nie.
- Tweedens moet die grootte van die saamgeperste houer voor die inbedding van inligting groter wees as die wysiging daarvan wat op 'n soortgelyke manier saamgepers is. Om bloot 'n klomp stukkies in BMP-beelde in te sluit met behulp van die LSB-metode is nie steganografiese kompressie nie, aangesien die oorspronklike beeld heel waarskynlik merkbaar kleiner sal wees, nadat dit deur 'n soort DEFLATE uitgevoer is.
- Derdens moet die resultaat uitgevoer en vergelyk word met betrekking tot data wat reeds deur klassieke metodes saamgepers is. Dit sal die probabilistiese effek van verskille in hul oortolligheid verwyder en meer doeltreffende kompressie in die algemene geval verskaf.
Waar?
Die gebruik van steganografie impliseer dat ons, benewens die saamgeperste inligting, houers sal benodig waarin dit ingebed sal word. Die maksimum hoeveelheid ingebedde inligting hang grootliks af van individuele eienskappe, maar dit is baie makliker om met hul getal te skaal. Daarom moet die houerformaat algemeen wees sodat die gebruiker genoeg daarvan het om enige voordeel uit die "kompressie"-proses te trek.
In hierdie konteks is grafika-, oudio- en videolêers goeie kandidate. Maar as gevolg van die verskeidenheid verskillende formate, codecs, ens., het ons in die praktyk 'n keuse uit nie soveel opsies nie.
As ek dit alles in ag neem, het my keuse op JPEG geval. Byna almal het dit, dit word wyd gebruik vir beide persoonlike en besigheidsdoeleindes, en is amper die de facto-formaat vir die meeste beelde.
Dit hang af?
Vervolgens is daar naby- en tegniese diagramme en beskrywings sonder veel verduideliking, so belangstellendes kan dit oorslaan deur na die "Hoë Tegnologie"-afdeling te blaai.
Algemene kenmerke
Om data iewers in te bed, moet jy eers bepaal waar. Daar kan enige aantal verskillende foto's op die lêerstelsel wees, waarvan die gebruiker dalk net 'n paar wil gebruik. Ons sal so 'n gewenste stel houers 'n biblioteek noem.
Dit word in twee gevalle gevorm: voor kompressie en voor dekompressie. In die eerste geval kan jy eenvoudig 'n stel lêername (of beter nog, 'n gereelde uitdrukking daarvoor) van lêers gebruik, maar in die tweede geval word iets meer betroubaar vereis: die gebruiker kan dit kopieer en skuif binne die lêerstelsel , en sodoende verhoed dat hulle korrek geïdentifiseer word. Daarom is dit nodig om hul hashes te stoor (md5 is genoeg) nadat alle wysigings aangebring is.
In hierdie geval is dit geen sin om die aanvanklike soektog uit te voer deur 'n gewone uitdrukking deur die hele lêerstelsel te gebruik nie; dit is genoeg om 'n sekere wortelgids te spesifiseer. 'n Spesiale argieflêer sal daarin gestoor word, wat daardie hashes sal bevat, saam met ander meta-inligting wat nodig is vir die daaropvolgende herwinning van saamgeperste inligting.
Dit alles is ewe van toepassing op enige implementering van enige steganografiese data-kompressie-algoritme. Die prosesse van datakompressie en -herwinning self kan inpak en uitpak genoem word.
F5
Noudat dit duidelik geword het wat ons doen en hoekom, bly dit om die algoritme vir die bereiking van die doel te beskryf. Kom ons onthou die proses van enkodering van 'n JPEG-lêer (danksy die wiki van die Bauman Nasionale Biblioteek):
As u daarna kyk, is dit beter om onmiddellik 'n paar opmerkings te maak:
- Die grootte van 'n JPEG-lêer kan as optimaal beskou word sonder om dit eers met 'n soort Winrar te probeer saamdruk;
- Slegs die gestoorde inligting (dit wat uit die diskrete cosinus-transform, DCT) uitgevoer word, kan gewysig word om ten minste aanvaarbare werkverrigting te verskaf.
- Om nie data op 'n industriële skaal te verloor wat vir die gebruiker opvallend is nie, is dit nodig om 'n minimum van wysigings aan elke individuele beeld aan te bring;
’n Hele familie algoritmes pas by hierdie toestande, waarmee jy jouself kan vergewis . Die mees gevorderde van hulle is die algoritme deur Andreas Westfeld, wat met die DCT-koëffisiënte van die helderheidskomponent werk (die menslike oog is die minste sensitief vir sy veranderinge). Die algemene uitleg daarvan wanneer u met 'n bestaande JPEG-lêer werk, word soos volg vertoon:
Die F5-blok gebruik 'n gevorderde inbeddingstegniek gebaseer op matrikskodering. Die leser kan meer daaroor en die algoritme self by die skakel hierbo leer, maar ons stel hoofsaaklik belang in die feit dat jy met die hulp daarvan hoe minder veranderinge kan maak wanneer dieselfde hoeveelheid inligting ingebed word, hoe groter is die grootte van die houer wat gebruik word. , en vir die uitvoering van die Die algoritme hoef slegs eenvoudige Huffman- en RLE- (de)koderingsbewerkings uit te voer.
Die veranderinge self word aan heelgetalkoëffisiënte aangebring en kom daarop neer dat hul absolute waarde met een verminder word, wat dit in die algemeen moontlik maak om F5 vir datakompressie te gebruik. Die punt is dat die verminderde koëffisiënt in absolute waarde heel waarskynlik minder bisse sal beslaan na Huffman-kodering as gevolg van die statistiese verspreiding van waardes in JPEG.
In die geval van die vorming van 'n nul (die sogenaamde reduksie), sal die aantal gestoorde inligting verminder word met sy grootte, aangesien die voormalige onafhanklike koëffisiënt deel sal word van die RLE-gekodeerde volgorde van nulle:
modifikasies
Databeskerming en kompressie is ortogonale probleme, so die geheime wagwoordpermutasie van die oorspronklike algoritme kan verwaarloos word. Boonop moet ons presies weet hoe om die data te onttrek, dus moet al die inligting wat hiervoor nodig is (watter houers gebruik is, in watter volgorde, ens.) in 'n aparte lêer aangeteken word en oop wees vir gratis lees deur die argiveerder.
Die oorspronklike algoritme is ontwerp om geheime boodskappe oor te dra, dus werk dit met slegs een houer op 'n slag, met die veronderstelling dat die gebruiker dit self in dele sal opbreek indien nodig, indien enige. Boonop, wanneer u onafhanklik in elke houer ingebed is, sal u vooraf moet weet hoeveel stukkies data in elkeen moet sit. Daarom moet die koëffisiënte van elke element van die biblioteek gekombineer word in een abstrakte groot een en daarmee gewerk word volgens die oorspronklike algoritme.
Aangesien die oorspronklike F5 tot 12% van die houergrootte toelaat, sal hierdie wysiging ook die maksimum kapasiteit verhoog: "tot 12%" van die grootte van die hele biblioteek is groter as of gelyk aan die som van "tot 12% " van elk van sy elemente.
Die gekodifiseerde algemene skema is soos volg:
Die algoritme self
Nou is dit tyd om die algoritme self van begin tot einde te beskryf, om nie die leser in die duister te hou nie:
- Die gebruiker definieer die binêre saamdrukbare data M en die biblioteek L deur 'n gewone uitdrukking en 'n soekhoofgids te gebruik;
- In die volgorde wat hulle op die FS verskyn, vorm die biblioteekelemente die MC:
- 'n Reeks koëffisiënte C word uit die lêerdata gedekodeer;
- MC <- MC | C;
- Die parameter k word bepaal op grond van die verskriklike ongelykheid:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Volgende geneem
n = (1 << k) - 1minste betekenisvolle stukkies van nie-nul elemente van MC en geskryf naa:- Die magiese hash-funksie word oorweeg
f, wat 'n n-bis woord verteenwoordigana k-biss; - As
s == 0, dan is dit nie nodig om iets te verander nie en die algoritme beweeg aan na die volgende koëffisiënte; - Verminder die absolute waarde van die koëffisiënt wat verantwoordelik is vir
s-Hey het in die woord gebyta; - As as gevolg van die vermindering 'n vermindering plaasvind (die koëffisiënt word 0), herhaal dan die stap van die begin af;
- Die magiese hash-funksie word oorweeg
- Alle koëffisiënte word geënkodeer deur RLE en Huffman, geskryf na die bronlêers;
- Die parameter k word na die argieflêer geskryf;
- 'n MD5-hash word uit elke lêer L in die volgorde van hul oorspronklike ligging bereken en na die argieflêer geskryf.
Hoë tegnologie
Die naïewe vorm van die algoritme en implementerings in ander hoëvlak (veral met vullisversameling) tale sou verskriklike werkverrigting lewer, so ek het al hierdie kompleksiteite in suiwer C geïmplementeer en 'n aantal optimaliserings uitgevoer, beide in terme van uitvoeringspoed en geheue (jy het geen idee hoeveel hierdie prente weeg sonder kompressie selfs voor DCT nie). Maar tog het die spoed van uitvoering aanvanklik veel te wense oorgelaat, so ek sal nie die hele proses en metodes wat gebruik word beskryf nie.
Kruisplatform word bereik deur 'n kombinasie van libjpeg-, pcre- en tinydir-biblioteke te gebruik, waarvoor ons hulle bedank. By verstek word alles via normaal saamgestel make, dus wil Windows-gebruikers 'n paar Cygwin vir hulself installeer, of op hul eie met Visual Studio en biblioteke handel.
Die implementering is beskikbaar in die vorm van 'n konsolehulpmiddel en biblioteek. Belangstellendes kan meer uitvind oor die gebruik van laasgenoemde in die readme in die repository op Github, die skakel waaraan ek aan die einde van die pos sal heg. En hier gaan ons oor na 'n beskrywing en demonstrasie van die werk.
Hoe om te gebruik?
Versigtig. Gebruikte beelde kan na wense geskuif, hernoem en gekopieer word. U moet egter uiters versigtig wees en nie die inhoud daarvan op enige manier verander nie. Die verandering van een bietjie sal die hash ontwrig en dit onmoontlik maak om die inligting te herwin.
Gestel dat ons na samestelling die uitvoerbare lêer f5ar kry. Jy kan die grootte van die biblioteek ontleed om die gebruiksmoontlikhede daarvan te bereken deur die vlag te gebruik -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Verpakking word deur die span gedoen ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], en uitpak met behulp van ./f5ar -u [файл архива] [имя восстановленного файла].
Demonstrasie van werk
Om die doeltreffendheid van die metode te wys, het ek 'n versameling van 225 absoluut gratis foto's van honde van die diens opgelaai . Elkeen van hulle het 'n effens hoër gehalte as gewone gebruikersfoto's, maar tog. Elkeen van hulle is her-enkodeer met libjpeg om die impak van die biblioteek se enkoderingskenmerke op die algehele grootte te neutraliseer. Om die slegste voorbeeld van saamdrukbare data aan te dui, is 'n ewekansige 36-meter (effens meer as 5% van die totale grootte) eenvormig verspreide lêer gegenereer met behulp van dd.
Die toetsproses is redelik eenvoudig:
$ 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 'n kiekie vir aanhangers
Soos jy kan sien, van die oorspronklike 633 + 36 == 669 megagrepe se data op die hardeskyf, het ons met 'n mooier 563 geëindig, wat ons 'n kompressieverhouding van ~1,188 gee. Hierdie radikale verskil word verklaar deur uiters klein verliese, soortgelyk aan dié wat verkry word wanneer JPEG-lêers met klassieke metodes (soos tinyjpg) geoptimaliseer word. Natuurlik, wanneer steganografiese kompressie gebruik word, gaan inligting nie bloot "verlore" nie, maar word dit gebruik om ander data te enkodeer. Verder is die aantal "geoptimaliseerde" koëffisiënte as gevolg van die gebruik van F5 baie minder as met tradisionele optimalisering.
Watter veranderinge daar ook al is, hulle is absoluut onsigbaar vir die oog. Onder die bederf hieronder kan die leser die verskil met die oog evalueer en deur die waardes van die veranderde komponent van die oorspronklike af te trek (hoe meer gedempte die kleur, hoe kleiner is die verskil):
Skakels na beelde wat nie op habrastorage pas nie
Oorspronklik -
Gewysig -
Verskil -
In plaas daarvan om 'n gevolgtrekking
Ek hoop ek kon die leser oortuig dat sulke metodes moontlik is en 'n reg op lewe het. Die koop van 'n hardeskyf of 'n bykomende kanaal (vir netwerkversending) kan egter na 'n baie eenvoudiger opsie lyk as om op hierdie manier geld te probeer spaar. Aan die een kant is dit waar; uitgebreide ontwikkeling is dikwels eenvoudiger en meer betroubaar. Maar aan die ander kant moet ons nie van die intense vergeet nie. Daar is immers geen waarborge dat jy môre winkel toe sal kan kom en vir jou nog duisend teragrepe hardeskywe sal kan koop nie, maar jy kan altyd dié gebruik wat jy reeds by die huis rondlê.
->
Bron: www.habr.com