Cando falamos de esteganografía, a xente pensa en terroristas, pederastas, espías ou, no mellor dos casos, criptoanarquistas e outros científicos. E realmente, quen máis podería necesitar agochar algo de ollos externos? Cal podería ser o beneficio deste para unha persoa común?
Resulta que hai un. É por iso que hoxe comprimiremos os datos mediante métodos de esteganografía. E ao final, o lector mesmo poderá usar os seus preciosos arquivos de fotos en JPEG para aumentar o número de gigabytes libres no sistema de ficheiros.
Que?
Se o lector lembra, a esteganografía é uns algoritmos tan estraños que permiten ocultar a presenza dunha información dentro doutra. Nunha linguaxe aínda máis sinxela: imaxe + ficheiro == aproximadamente a mesma imaxe, pero non do todo (en lugar de imaxes pode haber calquera cousa, pero normalmente todo está máis claro nelas). Non debería haber un xeito sinxelo de determinar se hai algo dentro ou non.
Pero se non se pode distinguir un do outro, hai algunha diferenza? Desde o punto de vista do consumidor, ao usuario non lle importa a precisión matemática (reflectada por un determinado conxunto de bits), só o que é percibido por el.
Por exemplo, vexamos tres imaxes dun can bonito:
Coidado, JPEG!
A pesar da enorme diferenza de tamaño, poucas persoas escollerán a terceira versión. Por outra banda, a diferenza entre as dúas primeiras fotografías non se nota tanto, e a cantidade de información nelas (desde o meu punto de vista) pode ser igual.
Este principio en si xa é antigo e foi explotado activamente por métodos de compresión de información con perdas durante moitos anos. Pero romper non é construír; estamos interesados no lado máis avanzado do tema. É posible inserir información adicional sobre o tamaño N ao ficheiro para que o seu tamaño aumente M < N, pero os cambios non foron perceptibles para o usuario?
Por suposto que podes. Pero paga a pena facer un par de reservas de inmediato:
- En primeiro lugar, o método debe ser universal e dar un resultado positivo na maioría dos datos de entrada. É dicir, de media, para unha entrada aleatoria, debería haber unha diminución real da cantidade de información almacenada. "De media" significa que pode ocorrer o contrario, pero non debe predominar.
- En segundo lugar, o tamaño do recipiente comprimido antes de incorporar información debe ser maior que a súa modificación comprimida de xeito similar. Simplemente incorporar unha morea de bits en imaxes BMP usando o método LSB non é compresión esteganográfica, xa que, tras ser executado a través dalgún tipo de DEFLATE, a imaxe orixinal probablemente será notablemente máis pequena.
- En terceiro lugar, o resultado debe ser realizado e comparado con respecto a datos xa comprimidos por métodos clásicos. Isto eliminará o efecto probabilístico das diferenzas na súa redundancia e proporcionará unha compresión máis eficiente no caso xeral.
Onde?
O uso da esteganografía implica que, ademais da información comprimida, necesitaremos contenedores nos que se incrustará. A cantidade máxima de información incorporada depende en gran medida das propiedades individuais, pero é moito máis fácil escalar co seu número. Polo tanto, o formato do contedor debe ser común para que o usuario teña suficientes para sacar proveito do proceso de "compresión".
Neste contexto, os ficheiros de gráficos, audio e vídeo son bos candidatos. Pero, debido á variedade de diferentes formatos, códecs, etc., na práctica quédanos a escoller entre non tantas opcións.
Tendo en conta todo isto, a miña elección recaeu en JPEG, case todo o mundo o ten, é moi utilizado tanto para fins persoais como comerciais, sendo case o formato de facto da maioría das imaxes.
Depende?
A continuación hai diagramas e descricións próximas e técnicas sen moita explicación, polo que os interesados poden saltalos desprazándose ata a sección "Altas tecnoloxías".
Características comúns
Para inserir datos nalgún lugar, primeiro debes determinar onde. Pode haber calquera número de fotografías diferentes no sistema de ficheiros, das que o usuario pode querer usar só algunhas. Chamaremos biblioteca a ese conxunto desexado de contedores.
Fórmase en dous casos: antes da compresión e antes da descompresión. No primeiro caso, pode simplemente usar un conxunto de nomes de ficheiros (ou mellor aínda, unha expresión regular para eles) de ficheiros, pero no segundo, requírese algo máis fiable: o usuario pode copialos e movelos dentro do sistema de ficheiros. , evitando así que sexan identificados correctamente. Polo tanto, é necesario almacenar os seus hash (md5 é suficiente) despois de que se fixeran todas as modificacións.
Neste caso, non ten sentido realizar a busca inicial usando unha expresión regular en todo o sistema de ficheiros; basta con especificar un determinado directorio raíz. Nel gardarase un ficheiro de arquivo especial, que conterá eses hash, xunto con outra metainformación necesaria para a posterior recuperación da información comprimida.
Todo isto aplícase igualmente a calquera implementación de calquera algoritmo de compresión de datos esteganográficos. Os propios procesos de compresión e recuperación de datos pódense denominar empaquetado e desempaquetado.
F5
Agora que quedou claro o que estamos facendo e por que, queda por describir o algoritmo para acadar o obxectivo. Lembremos o proceso de codificación dun ficheiro JPEG (grazas á wiki da Biblioteca Nacional Bauman):
Mirando isto, é mellor facer inmediatamente algúns comentarios:
- O tamaño dun ficheiro JPEG pódese considerar óptimo sen sequera tentar comprimilo con algún tipo de Winrar;
- Só a información almacenada (a que sae da transformada coseno discreta, DCT) pode modificarse para proporcionar polo menos un rendemento aceptable.
- Para non perder datos a escala industrial perceptibles para o usuario, é necesario realizar un mínimo de modificacións en cada imaxe individual;
Toda unha familia de algoritmos encaixa nestas condicións, coas que podes familiarizarte . O máis avanzado deles é o algoritmo de Andreas Westfeld, traballando cos coeficientes DCT do compoñente de brillo (o ollo humano é o menos sensible aos seus cambios). O seu deseño xeral cando se traballa cun ficheiro JPEG existente móstrase do seguinte xeito:
O bloque F5 usa unha técnica de incrustación avanzada baseada na codificación matricial. O lector pode aprender máis sobre el e sobre o propio algoritmo na ligazón anterior, pero interésanos principalmente que coa súa axuda poida facer cantos menos cambios se incruste ao incorporar a mesma cantidade de información, maior será o tamaño do contedor utilizado. , e para levar a cabo o O algoritmo só precisa realizar operacións sinxelas de (des)codificación de Huffman e RLE.
Os propios cambios realízanse nos coeficientes enteiros e redúcense a reducir nun un o seu valor absoluto, o que permite, en xeral, empregar F5 para a compresión de datos. A cuestión é que o coeficiente reducido en valor absoluto probablemente ocupe menos bits despois da codificación de Huffman debido á distribución estatística dos valores en JPEG.
No caso da formación dun cero (a chamada redución), o número de información almacenada reducirase polo seu tamaño, xa que o anterior coeficiente independente pasará a formar parte da secuencia de ceros codificada RLE:
Modificacións
A protección e a compresión de datos son problemas ortogonais, polo que se pode descoidar a permutación secreta do contrasinal do algoritmo orixinal. Ademais, cómpre saber exactamente como extraer os datos, polo que toda a información necesaria para iso (que contedores se utilizaron, en que orde, etc.) debería rexistrarse nun ficheiro separado e estar aberta para a lectura libre polo arquivador.
O algoritmo orixinal está deseñado para transmitir mensaxes secretas, polo que só funciona cun contedor á vez, asumindo que o propio usuario o dividirá en partes se é necesario, se é o caso. Ademais, cando se incrusta de forma independente en cada contedor, terá que saber de antemán cantos bits de datos poñer en cada un. Polo tanto, os coeficientes de cada elemento da biblioteca deben combinarse nun abstracto grande e traballar con el segundo o algoritmo orixinal.
Dado que o F5 orixinal permite ata o 12% do tamaño do contedor, esta modificación tamén aumentará a capacidade máxima: "ata o 12%" do tamaño de toda a biblioteca é maior ou igual á suma de "ata o 12%". " de cada un dos seus elementos.
O réxime xeral codificado é o seguinte:
O propio algoritmo
Agora é o momento de describir o propio algoritmo de principio a fin, para non manter o lector na escuridade:
- O usuario define os datos binarios comprimibles M e a biblioteca L usando unha expresión regular e un directorio raíz de busca;
- Na orde en que aparecen no FS, os elementos da biblioteca forman o MC:
- A partir dos datos do ficheiro decodícanse unha serie de coeficientes C;
- MC <- MC | C;
- O parámetro k determínase en función da terrible desigualdade:
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Tomado a continuación
n = (1 << k) - 1bits menos significativos de elementos distintos de cero de MC e escritos ena:- Considérase a función hash máxica
f, que representa unha palabra de n bitsaa k-bits; - Se
s == 0, entón non hai que cambiar nada e o algoritmo pasa aos seguintes coeficientes; - Reducir o valor absoluto do coeficiente responsable de
s-hey mordeu a palabraa; - Se como resultado da redución se produce unha redución (o coeficiente pasa a ser 0), repita o paso desde o principio;
- Considérase a función hash máxica
- Todos os coeficientes están codificados por RLE e Huffman, escritos nos ficheiros fonte;
- O parámetro k escríbese no ficheiro de arquivo;
- Calcúlase un hash MD5 a partir de cada ficheiro L na orde da súa localización orixinal e escríbese no ficheiro de arquivo.
Alta tecnoloxía
A forma inxenua do algoritmo e as implementacións noutras linguaxes de alto nivel (especialmente coa recollida de lixo) darían un rendemento terrible, polo que implementei todas estas complexidades en C puro e realicei unha serie de optimizacións tanto en termos de velocidade de execución como de memoria (non tes idea de canto pesan estas imaxes sen comprimir mesmo antes da DCT). Pero aínda así, ao principio a velocidade de execución deixou moito que desexar, polo que non vou describir todo o proceso e os métodos utilizados.
A multiplataforma conséguese mediante unha combinación de bibliotecas libjpeg, pcre e tinydir, polo que lles agradecemos. Por defecto, todo compílase de xeito normal make, polo que os usuarios de Windows queren instalar algún Cygwin por si mesmos ou xestionar Visual Studio e as bibliotecas por si mesmos.
A implementación está dispoñible en forma de utilidade de consola e biblioteca. Os interesados poden saber máis sobre o uso deste último no readme do repositorio de Github, a ligazón á que adxuntarei ao final da publicación. E aquí pasamos á descrición e demostración do traballo.
Como usar?
Con coidado. As imaxes usadas pódense mover, renomear e copiar segundo o desexa. Non obstante, debes ter moito coidado e non cambiar o seu contido de ningún xeito. Cambiar un bit perturbará o hash e imposibilitará a recuperación da información.
Supoñamos que despois da compilación obtemos o ficheiro executable f5ar. Podes analizar o tamaño da biblioteca para calcular as posibilidades do seu uso mediante a bandeira -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. O embalaxe faise polo equipo ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], e desembalar usando ./f5ar -u [файл архива] [имя восстановленного файла].
Demostración de traballo
Para mostrar a eficacia do método, carguei unha colección de 225 fotos absolutamente gratuítas de cans do servizo . Cada un deles ten unha calidade lixeiramente superior á das fotos de usuarios comúns, pero aínda así. Cada un deles foi recodificado usando libjpeg para neutralizar o impacto das funcións de codificación da biblioteca no tamaño total. Para indicar o peor exemplo de datos comprimibles, xerou un ficheiro aleatorio de 36 metros (algo máis do 5% do tamaño total) distribuído uniformemente mediante dd.
O proceso de proba é bastante sinxelo:
$ 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/Ou unha captura de pantalla para os fans
Como podes ver, a partir dos orixinais 633 + 36 == 669 megabytes de datos no disco duro, acabamos cun 563 máis agradable, dándonos unha relación de compresión de ~ 1,188. Esta diferenza radical explícase por perdas extremadamente pequenas, similares ás obtidas ao optimizar ficheiros JPEG mediante métodos clásicos (como tinyjpg). Por suposto, cando se usa a compresión esteganográfica, a información non se "perde", senón que se usa para codificar outros datos. Ademais, o número de coeficientes "optimizados" debido ao uso de F5 é moito menor que coa optimización tradicional.
Sexa cal sexan as modificacións que haxa, son absolutamente invisibles aos ollos. Baixo o spoiler a continuación, o lector pode avaliar a diferenza tanto a vista como restando os valores do compoñente modificado do orixinal (canto máis silenciada sexa a cor, menor será a diferenza):
Ligazóns a imaxes que non caben en habrastorage
Orixinal -
Modificado -
Diferenza -
En vez de unha conclusión
Espero poder convencer ao lector de que tales métodos son posibles e teñen dereito á vida. Non obstante, comprar un disco duro ou unha canle adicional (para transmisión en rede) pode parecer unha opción moito máis sinxela que tentar aforrar diñeiro deste xeito. Por unha banda, isto é certo; o desenvolvemento extensivo adoita ser máis sinxelo e fiable. Pero, por outra banda, non debemos esquecernos do intenso. Despois de todo, non hai garantía de que mañá poderás vir á tenda e mercarche outro disco duro de mil terabytes, pero sempre podes usar os que xa tes na casa.
->
Fonte: www.habr.com