Quan parlem d'esteganografia, la gent pensa en terroristes, pedòfils, espies o, en el millor dels casos, en criptoanarquistes i altres científics. I realment, qui més podria necessitar amagar-se alguna cosa dels ulls externs? Quin pot ser el benefici d'això per a una persona normal?
Resulta que n'hi ha un. És per això que avui comprimirem dades mitjançant mètodes d'esteganografia. I al final, el lector fins i tot podrà utilitzar els seus preciosos arxius de fotos en JPEG per augmentar el nombre de gigabytes gratuïts al sistema de fitxers.
Què?
Si el lector ho recorda, l'esteganografia són algorismes tan estranys que permeten amagar la presència d'una informació dins d'una altra. En un llenguatge encara més senzill: imatge + fitxer == aproximadament la mateixa imatge, però no del tot (en lloc d'imatges hi pot haver qualsevol cosa, però normalment tot és més clar). No hi hauria d'haver una manera fàcil de determinar si hi ha alguna cosa a dins o no.
Però si no es pot distingir un de l'altre, hi ha alguna diferència? Des del punt de vista del consumidor, a l'usuari no li importa la precisió matemàtica (reflectada per un conjunt de bits determinat), només allò que ell percep.
Per exemple, mirem tres imatges d'un gos bonic:
Compte, JPEG!
Malgrat l'enorme diferència de mida, poca gent triarà la tercera versió. D'altra banda, la diferència entre les dues primeres fotografies no es nota tant, i la quantitat d'informació que hi ha (des del meu punt de vista) pot ser igual.
Aquest principi ja és antic i ha estat explotat activament mitjançant mètodes de compressió d'informació amb pèrdues durant molts anys. Però trencar no és construir; ens interessa la part més avançada de la qüestió. És possible incrustar informació addicional sobre la mida? N al fitxer perquè la seva mida augmenti M < N, però els canvis no es van notar per l'usuari?
Per descomptat que pot. Però val la pena fer un parell de reserves immediatament:
- En primer lloc, el mètode ha de ser universal i donar un resultat positiu a la majoria de dades d'entrada. És a dir, de mitjana, per a una entrada aleatòria, hi hauria d'haver una disminució real de la quantitat d'informació emmagatzemada. "De mitjana" vol dir que pot passar el contrari, però no hauria de predominar.
- En segon lloc, la mida del contenidor comprimit abans d'incrustar la informació ha de ser més gran que la seva modificació comprimida de manera similar. Simplement incrustar un munt de bits a imatges BMP mitjançant el mètode LSB no és compressió esteganogràfica, ja que, després d'haver passat amb algun tipus de DEFLATE, la imatge original probablement serà notablement més petita.
- En tercer lloc, el resultat s'ha de dur a terme i comparar respecte a dades ja comprimides per mètodes clàssics. Això eliminarà l'efecte probabilístic de les diferències en la seva redundància i proporcionarà una compressió més eficient en el cas general.
On?
L'ús de l'esteganografia implica que, a més de la informació comprimida, necessitarem contenidors on s'incorporarà. La quantitat màxima d'informació incrustada depèn en gran mesura de les propietats individuals, però és molt més fàcil escalar amb el seu nombre. Per tant, el format del contenidor ha de ser comú perquè l'usuari en tingui prou per treure'n algun benefici del procés de "compressió".
En aquest context, els fitxers de gràfics, àudio i vídeo són bons candidats. Però, a causa de la varietat de diferents formats, còdecs, etc., a la pràctica ens queda una opció entre no tantes opcions.
Tenint en compte tot això, la meva elecció va recaure en el JPEG, gairebé tothom el té, és molt utilitzat tant per a finalitats personals com empresarials, sent gairebé el format de facto de la majoria d'imatges.
Depèn?
A continuació, hi ha diagrames i descripcions properes i tècniques sense gaire explicació, de manera que els interessats poden saltar-los desplaçant-se a la secció "Altes tecnologies".
Característiques comunes
Per incrustar dades en algun lloc, primer heu de determinar on. Hi pot haver qualsevol nombre de fotografies diferents al sistema de fitxers, de les quals l'usuari potser voldria utilitzar només unes quantes. A aquest conjunt desitjat de contenidors l'anomenarem biblioteca.
Es forma en dos casos: abans de la compressió i abans de la descompressió. En el primer cas, podeu utilitzar simplement un conjunt de noms de fitxers (o millor encara, una expressió regular per a ells) de fitxers, però en el segon, cal una cosa més fiable: l'usuari pot copiar-los i moure'ls dins del sistema de fitxers. , evitant així que s'identifiquin correctament. Per tant, cal emmagatzemar els seus hash (md5 és suficient) després de fer totes les modificacions.
En aquest cas, no té sentit dur a terme la cerca inicial utilitzant una expressió regular a tot el sistema de fitxers; n'hi ha prou amb especificar un directori arrel determinat. S'hi desarà un fitxer d'arxiu especial, que contindrà aquests hash, juntament amb altra metainformació necessària per a la posterior recuperació de la informació comprimida.
Tot això s'aplica igualment a qualsevol implementació de qualsevol algorisme de compressió de dades esteganogràfics. Els propis processos de compressió i recuperació de dades es poden anomenar embalatge i desempaquetat.
F5
Ara que ha quedat clar què estem fent i per què, queda per descriure l'algorisme per assolir l'objectiu. Recordem el procés de codificació d'un fitxer JPEG (gràcies a la wiki de la Biblioteca Nacional Bauman):
Mirant-ho, és millor fer uns quants comentaris immediatament:
- La mida d'un fitxer JPEG es pot considerar òptima sense ni tan sols intentar comprimir-lo amb algun tipus de Winrar;
- Només la informació emmagatzemada (la que surt de la transformada discreta del cosinus, DCT) es pot modificar per oferir almenys un rendiment acceptable.
- Per no perdre dades a escala industrial perceptibles per l'usuari, cal fer un mínim de modificacions a cada imatge individual;
Tota una família d'algorismes s'adapta a aquestes condicions, amb les quals us podeu familiaritzar . El més avançat d'ells és l'algorisme d'Andreas Westfeld, treballant amb els coeficients DCT del component de brillantor (l'ull humà és el menys sensible als seus canvis). El seu disseny general quan es treballa amb un fitxer JPEG existent es mostra de la següent manera:
El bloc F5 utilitza una tècnica d'incrustació avançada basada en la codificació matricial. El lector pot obtenir més informació sobre això i sobre el propi algorisme a l'enllaç anterior, però ens interessa principalment que amb la seva ajuda podeu fer com menys canvis en incrustar la mateixa quantitat d'informació, més gran serà la mida del contenidor utilitzat. , i per dur a terme l'algorisme només necessita realitzar operacions simples de (des)codificació de Huffman i RLE.
Els propis canvis es fan als coeficients enters i es redueixen a reduir el seu valor absolut en un, cosa que permet, en general, utilitzar F5 per a la compressió de dades. La qüestió és que el coeficient reduït en valor absolut probablement ocuparà menys bits després de la codificació de Huffman a causa de la distribució estadística dels valors en JPEG.
En el cas de la formació d'un zero (l'anomenada reducció), el nombre d'informació emmagatzemada es reduirà per la seva mida, ja que l'antic coeficient independent passarà a formar part de la seqüència de zeros codificada RLE:
Modificacions
La protecció i la compressió de dades són problemes ortogonals, de manera que es pot descuidar la permutació de la contrasenya secreta de l'algorisme original. A més, hem de saber exactament com extreure les dades, de manera que tota la informació necessària per a això (quins contenidors s'han utilitzat, en quin ordre, etc.) s'hauria d'enregistrar en un fitxer a part i estar oberta a la lectura gratuïta per part de l'arxivador.
L'algorisme original està dissenyat per transmetre missatges secrets, de manera que només funciona amb un contenidor alhora, suposant que el mateix usuari el trencarà en parts si cal, si n'hi ha. A més, quan s'incrusteu de manera independent a cada contenidor, haureu de saber per endavant quants bits de dades heu de posar en cadascun. Per tant, els coeficients de cada element de la biblioteca s'han de combinar en un de gran abstracte i treballar-hi segons l'algorisme original.
Com que l'F5 original permet fins a un 12% de la mida del contenidor, aquesta modificació també augmentarà la capacitat màxima: "fins a un 12%" de la mida de tota la biblioteca és superior o igual a la suma de "fins a un 12%". " de cadascun dels seus elements.
L'esquema general codificat és el següent:
El propi algorisme
Ara és el moment de descriure el propi algorisme de principi a fi, per no mantenir el lector a les fosques:
- L'usuari defineix les dades binàries compressibles M i la biblioteca L utilitzant una expressió regular i un directori arrel de cerca;
- En l'ordre en què apareixen al FS, els elements de la biblioteca formen el MC:
- Una sèrie de coeficients C es descodifiquen a partir de les dades del fitxer;
- MC <- MC | C;
- El paràmetre k es determina a partir de la terrible desigualtat:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Presa a continuació
n = (1 << k) - 1bits menys significatius d'elements diferents de zero de MC i escrits aa:- Es considera la funció hash màgica
f, que representa una paraula de n bitsaa k-bits; - Si
s == 0, aleshores no cal canviar res i l'algorisme passa als coeficients següents; - Reduir el valor absolut del coeficient responsable de
s-Hey mossegar la paraulaa; - Si com a resultat de la reducció es produeix una reducció (el coeficient passa a ser 0), llavors repeteix el pas des del principi;
- Es considera la funció hash màgica
- Tots els coeficients estan codificats per RLE i Huffman, escrits als fitxers font;
- El paràmetre k s'escriu al fitxer d'arxiu;
- Es calcula un hash MD5 a partir de cada fitxer L en l'ordre de la seva ubicació original i s'escriu al fitxer d'arxiu.
Alta tecnologia
La forma ingènua de l'algoritme i les implementacions en altres llenguatges d'alt nivell (especialment amb la recollida d'escombraries) donarien un rendiment terrible, així que vaig implementar totes aquestes complexitats en C pur i vaig realitzar una sèrie d'optimitzacions tant pel que fa a la velocitat d'execució com a la memòria (no teniu ni idea de quant pesen aquestes imatges sense compressió fins i tot abans de DCT). Però tot i així, al principi la velocitat d'execució deixava molt a desitjar, per la qual cosa no descriuré tot el procés i els mètodes utilitzats.
La multiplataforma s'aconsegueix mitjançant una combinació de biblioteques libjpeg, pcre i tinydir, per la qual cosa els agraïm. Per defecte, tot es compila de manera normal make, de manera que els usuaris de Windows volen instal·lar algun Cygwin per ells mateixos o tractar amb Visual Studio i biblioteques per si mateixos.
La implementació està disponible en forma d'utilitat de consola i biblioteca. Els interessats poden obtenir més informació sobre l'ús d'aquest últim al readme del repositori de Github, l'enllaç al qual adjuntaré al final de la publicació. I aquí passem a una descripció i demostració de l'obra.
Com s'utilitza?
Amb cura. Les imatges utilitzades es poden moure, canviar el nom i copiar-se com es desitgi. Tanmateix, heu de tenir molta cura i no canviar-ne el contingut de cap manera. Canviar un bit alterarà el hash i farà impossible recuperar la informació.
Suposem que després de la compilació obtenim el fitxer executable f5ar. Podeu analitzar la mida de la biblioteca per calcular les possibilitats del seu ús mitjançant la bandera -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. L'embalatge el fa l'equip ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], i desembalar utilitzant ./f5ar -u [файл архива] [имя восстановленного файла].
Demostració de treball
Per mostrar l'eficàcia del mètode, he penjat una col·lecció de 225 fotos absolutament gratuïtes de gossos del servei. . Cadascun d'ells té una qualitat lleugerament superior a les fotos d'usuari normals, però tot i així. Cadascun d'ells es va tornar a codificar mitjançant libjpeg per neutralitzar l'impacte de les característiques de codificació de la biblioteca en la mida general. Per indicar el pitjor exemple de dades compressibles, es va generar un fitxer aleatori de 36 metres (una mica més del 5% de la mida total) distribuït uniformement mitjançant dd.
El procés de prova és bastant senzill:
$ 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/O una captura de pantalla per als fans
Com podeu veure, a partir dels 633 + 36 == 669 megabytes de dades originals al disc dur, vam acabar amb un 563 més agradable, donant-nos una relació de compressió de ~ 1,188. Aquesta diferència radical s'explica per pèrdues extremadament petites, similars a les que s'obtenen en optimitzar fitxers JPEG mitjançant mètodes clàssics (com ara tinyjpg). Naturalment, quan s'utilitza la compressió esteganogràfica, la informació no només es "perd", sinó que s'utilitza per codificar altres dades. A més, el nombre de coeficients "optimitzats" a causa de l'ús de F5 és molt menor que amb l'optimització tradicional.
Independentment de les modificacions que hi hagi, són absolutament invisibles als ulls. Sota l'aleró següent, el lector pot avaluar la diferència tant a simple vista com restant els valors del component canviat de l'original (com més silenciat sigui el color, menor serà la diferència):
Enllaços a imatges que no encaixen a habrastorage
Original -
Modificat -
Diferència -
En lloc d'una conclusió
Espero haver pogut convèncer el lector que aquests mètodes són possibles i tenen dret a la vida. Tanmateix, comprar un disc dur o un canal addicional (per a la transmissió de la xarxa) pot semblar una opció molt més senzilla que intentar estalviar diners d'aquesta manera. D'una banda, això és cert; el desenvolupament extensiu sovint és més senzill i més fiable. Però, d'altra banda, no ens hem d'oblidar de l'intens. Al cap i a la fi, no hi ha garanties que demà podràs venir a la botiga i comprar-te un altre disc dur de mil terabytes, però sempre pots utilitzar els que ja tens a casa.
->
Font: www.habr.com