Quand on parle de stéganographie, les gens pensent aux terroristes, aux pédophiles, aux espions ou, au mieux, aux cryptoanarchistes et autres scientifiques. Et vraiment, qui d'autre pourrait avoir besoin se cacher quelque chose des yeux extérieurs ? Quel pourrait être l’avantage de cela pour une personne ordinaire ?
Il s'avère qu'il y en a un. C'est pourquoi aujourd'hui nous compresserons les données à l'aide de méthodes de stéganographie. Et au final, le lecteur pourra même utiliser ses précieuses archives photos au format JPEG pour augmenter le nombre de gigaoctets libres sur le système de fichiers.
Quoi?
Si le lecteur s'en souvient, la stéganographie est un algorithme si étrange qui permet de cacher la présence d'une information dans une autre. Dans un langage encore plus simple : image + fichier == à peu près la même image, mais pas tout à fait (au lieu d'images, il peut y avoir n'importe quoi, mais généralement tout y est plus clair). Il ne devrait pas y avoir de moyen simple de déterminer s’il y a quelque chose à l’intérieur ou non.
Mais si l’un ne peut pas être distingué de l’autre, y a-t-il une différence ? Du point de vue du consommateur, l'utilisateur ne se soucie pas de la précision mathématique (reflétée par un ensemble particulier de bits), mais seulement de ce qu'il perçoit.
Par exemple, regardons trois images d'un chien mignon :
Attention, JPEG !
Malgré l’énorme différence de taille, peu de gens choisiront la troisième version. D'un autre côté, la différence entre les deux premières photographies n'est pas si perceptible et la quantité d'informations qu'elles contiennent (de mon point de vue) peut être égale.
Ce principe lui-même est déjà ancien et est activement exploité par les méthodes de compression d’informations avec perte depuis de nombreuses années. Mais briser n’est pas construire ; nous nous intéressons à l’aspect le plus avancé de la question. Est-il possible d'intégrer des informations de taille supplémentaires N au fichier afin que sa taille augmente de M < N, mais les changements n'ont pas été perceptibles par l'utilisateur ?
Bien sûr vous pouvez. Mais cela vaut la peine de faire quelques réserves tout de suite :
- Premièrement, la méthode doit être universelle et donner un résultat positif sur la plupart des données d’entrée. Autrement dit, en moyenne, pour une entrée aléatoire, il devrait y avoir une diminution réelle de la quantité d'informations stockées. « En moyenne » signifie que l’inverse peut se produire, mais ne doit pas prédominer.
- Deuxièmement, la taille du conteneur compressé avant l'intégration des informations doit être supérieure à sa modification compressée de la même manière. Le simple fait d'incorporer un tas de bits dans des images BMP à l'aide de la méthode LSB n'est pas une compression stéganographique, car, après avoir subi une sorte de DEFLATE, l'image originale sera très probablement sensiblement plus petite.
- Troisièmement, le résultat doit être réalisé et comparé par rapport à des données déjà compressées par les méthodes classiques. Cela supprimera l'effet probabiliste des différences dans leur redondance et fournira une compression plus efficace dans le cas général.
Où?
L’utilisation de la stéganographie implique qu’en plus des informations compressées, nous aurons besoin de conteneurs dans lesquels elles seront intégrées. La quantité maximale d'informations intégrées dépend en grande partie des propriétés individuelles, mais il est beaucoup plus facile de l'adapter en fonction de leur nombre. Par conséquent, le format des conteneurs doit être commun afin que l'utilisateur en ait suffisamment pour tirer profit du processus de « compression ».
Dans ce contexte, les fichiers graphiques, audio et vidéo sont de bons candidats. Mais, en raison de la variété des formats, codecs, etc., dans la pratique, nous n'avons pas le choix parmi beaucoup d'options.
Compte tenu de tout cela, mon choix s'est porté sur JPEG. Presque tout le monde l'a, il est largement utilisé à des fins personnelles et professionnelles, étant presque le format de facto pour la plupart des images.
Ça dépend?
Ensuite, il y a des diagrammes et des descriptions proches et techniques sans beaucoup d'explications, afin que les personnes intéressées puissent les ignorer en faisant défiler jusqu'à la section « Hautes technologies ».
Caractéristiques communes
Pour intégrer des données quelque part, vous devez d’abord déterminer où. Il peut y avoir un nombre illimité de photographies différentes sur le système de fichiers, dont l'utilisateur peut souhaiter n'en utiliser que quelques-unes. Nous appellerons un tel ensemble de conteneurs souhaité une bibliothèque.
Il se forme dans deux cas : avant compression et avant décompression. Dans le premier cas, vous pouvez simplement utiliser un ensemble de noms de fichiers (ou mieux encore, une expression régulière pour eux) de fichiers, mais dans le second, quelque chose de plus fiable est requis : l'utilisateur peut les copier et les déplacer dans le système de fichiers. , empêchant ainsi leur identification correcte. Il est donc nécessaire de stocker leurs hachages (md5 suffit) une fois toutes les modifications effectuées.
Dans ce cas, cela n'a aucun sens d'effectuer la recherche initiale à l'aide d'une expression régulière dans l'ensemble du système de fichiers, il suffit de spécifier un certain répertoire racine. Un fichier d'archive spécial y sera enregistré, qui contiendra ces hachages, ainsi que d'autres méta-informations nécessaires à la récupération ultérieure des informations compressées.
Tout cela s'applique également à toute implémentation de tout algorithme de compression de données stéganographique. Les processus de compression et de récupération des données eux-mêmes peuvent être appelés emballage et déballage.
F5
Maintenant qu'il est devenu clair ce que nous faisons et pourquoi, il reste à décrire l'algorithme permettant d'atteindre l'objectif. Rappelons le processus d'encodage d'un fichier JPEG (grâce au wiki de la Bibliothèque Nationale Bauman) :
En y regardant, il vaut mieux faire immédiatement quelques commentaires :
- La taille d'un fichier JPEG peut être considérée comme optimale sans même essayer de le compresser avec une sorte de Winrar ;
- Seules les informations stockées (celles qui sont sorties de la transformée en cosinus discrète, DCT) peuvent être modifiées pour fournir des performances au moins acceptables.
- Afin de ne pas perdre de données à l'échelle industrielle perceptible par l'utilisateur, il est nécessaire d'apporter un minimum de modifications à chaque image individuelle ;
Toute une famille d'algorithmes répond à ces conditions, avec lesquelles vous pouvez vous familiariser . Le plus avancé d'entre eux est l'algorithme par Andreas Westfeld, travaillant avec les coefficients DCT de la composante de luminosité (l'œil humain est le moins sensible à ses changements). Sa disposition générale lorsque vous travaillez avec un fichier JPEG existant s'affiche comme suit :
Le bloc F5 utilise une technique d'intégration avancée basée sur le codage matriciel. Le lecteur peut en apprendre davantage sur celui-ci et sur l'algorithme lui-même sur le lien ci-dessus, mais nous sommes principalement intéressés par le fait qu'avec son aide, vous pouvez apporter moins de modifications en intégrant la même quantité d'informations, plus la taille du conteneur utilisé est grande. , et pour réaliser l'algorithme. Il suffit d'effectuer des opérations simples de (dé)codage de Huffman et RLE.
Les modifications elles-mêmes portent sur des coefficients entiers et se résument à réduire leur valeur absolue de un, ce qui permet, de manière générale, d'utiliser F5 pour la compression des données. Le fait est que le coefficient réduit en valeur absolue occupera très probablement moins de bits après le codage de Huffman en raison de la distribution statistique des valeurs en JPEG.
Dans le cas de la formation d'un zéro (ce qu'on appelle la réduction), le nombre d'informations stockées sera réduit de sa taille, puisque l'ancien coefficient indépendant fera partie de la séquence de zéros codée RLE :
Modifications
La protection et la compression des données sont des problèmes orthogonaux, de sorte que la permutation du mot de passe secret de l'algorithme d'origine peut être négligée. De plus, nous devons savoir exactement comment extraire les données, donc toutes les informations nécessaires à cela (quels conteneurs ont été utilisés, dans quel ordre, etc.) doivent être enregistrées dans un fichier séparé et être ouvertes en lecture libre par l'archiveur.
L'algorithme original est conçu pour transmettre des messages secrets, il fonctionne donc avec un seul conteneur à la fois, en supposant que l'utilisateur lui-même le divisera en plusieurs parties si nécessaire, le cas échéant. De plus, lorsqu’ils sont intégrés indépendamment dans chaque conteneur, vous devrez savoir à l’avance combien de bits de données mettre dans chacun. Par conséquent, les coefficients de chaque élément de la bibliothèque doivent être combinés en un seul grand abstrait et travaillés avec lui selon l'algorithme original.
Puisque le F5 d'origine autorise jusqu'à 12 % de la taille du conteneur, cette modification augmentera également la capacité maximale : « jusqu'à 12 % » de la taille de l'ensemble de la bibliothèque est supérieur ou égal à la somme de « jusqu'à 12 % » " de chacun de ses éléments.
Le régime général codifié est le suivant :
L'algorithme lui-même
Il est maintenant temps de décrire l’algorithme lui-même du début à la fin, afin de ne pas laisser le lecteur dans le flou :
- L'utilisateur définit les données binaires compressibles M et la bibliothèque L à l'aide d'une expression régulière et d'un répertoire racine de recherche ;
- Dans l'ordre dans lequel ils apparaissent sur le FS, les éléments de la bibliothèque forment le MC :
- Une série de coefficients C sont décodés à partir des données du fichier ;
- MC <- MC | C ;
- Le paramètre k est déterminé sur la base de la terrible inégalité :
|M| * 8 / (count_full(MC) + count_ones(MC) * k_rate(k)) < k / ((1 << k) - 1); - Pris ensuite
n = (1 << k) - 1bits les moins significatifs d'éléments non nuls de MC et écrits dansa:- La fonction de hachage magique est considérée
f, représentant un mot de n bitsaen k-bitss; - si
s == 0, alors il n'y a rien à changer et l'algorithme passe aux coefficients suivants ; - Réduire la valeur absolue du coefficient responsable de
s-hé, j'ai mordu le mota; - Si à la suite de la réduction une réduction se produit (le coefficient devient 0), alors répétez l'étape depuis le début ;
- La fonction de hachage magique est considérée
- Tous les coefficients sont codés par RLE et Huffman, écrits dans les fichiers sources ;
- Le paramètre k est écrit dans le fichier archive ;
- Un hachage MD5 est calculé à partir de chaque fichier L dans l'ordre de leur emplacement d'origine et écrit dans le fichier d'archive.
Hautes technologies
La forme naïve de l'algorithme et les implémentations dans d'autres langages de haut niveau (notamment avec le garbage collection) donneraient des performances terribles, j'ai donc implémenté toutes ces complexités en C pur et effectué un certain nombre d'optimisations à la fois en termes de vitesse d'exécution et mémoire (vous n'avez aucune idée du poids de ces images sans compression, même avant DCT). Mais même ainsi, au début, la rapidité d'exécution laissait beaucoup à désirer, je ne décrirai donc pas l'ensemble du processus et des méthodes utilisées.
Le multiplateforme est réalisé en utilisant une combinaison de bibliothèques libjpeg, pcre et tinydir, pour laquelle nous les remercions. Par défaut, tout est compilé via normal make, les utilisateurs de Windows souhaitent donc installer Cygwin pour eux-mêmes ou gérer eux-mêmes Visual Studio et les bibliothèques.
L'implémentation est disponible sous la forme d'un utilitaire de console et d'une bibliothèque. Les personnes intéressées peuvent en savoir plus sur l'utilisation de ce dernier dans le fichier readme du référentiel sur Github, le lien auquel je joindrai à la fin de l'article. Et ici nous passons à une description et une démonstration du travail.
Comment l'utiliser?
Soigneusement. Les images utilisées peuvent être déplacées, renommées et copiées à volonté. Cependant, vous devez être extrêmement prudent et ne modifier en aucun cas leur contenu. Changer un bit perturbera le hachage et rendra impossible la récupération des informations.
Supposons qu'après compilation, nous obtenions le fichier exécutable f5ar. Vous pouvez analyser la taille de la bibliothèque pour calculer les possibilités de son utilisation à l'aide du drapeau -a: ./f5ar -a [папка поиска] [Perl-совместимое регулярное выражение]. Le packaging est réalisé par l'équipe ./f5ar -p [папка поиска] [Perl-совместимое регулярное выражение] [упаковываемый файл] [имя архива], et déballage à l'aide ./f5ar -u [файл архива] [имя восстановленного файла].
Démonstration de travail
Pour montrer l'efficacité de la méthode, j'ai téléchargé une collection de 225 photos de chiens absolument gratuites du service . Chacune d'elles a une qualité légèrement supérieure aux photos des utilisateurs ordinaires, mais quand même. Chacun d'eux a été réencodé à l'aide de libjpeg pour neutraliser l'impact des fonctionnalités d'encodage de la bibliothèque sur la taille globale. Pour indiquer le pire exemple de données compressibles, un fichier aléatoire de 36 mètres (un peu plus de 5 % de la taille totale) uniformément distribué a été généré à l'aide de dd.
Le processus de test est assez simple :
$ 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 une capture d'écran pour les fans
Comme vous pouvez le constater, à partir des 633 + 36 == 669 mégaoctets de données d'origine sur le disque dur, nous nous sommes retrouvés avec un 563 plus agréable, ce qui nous donne un taux de compression d'environ 1,188. Cette différence radicale s'explique par des pertes extrêmement faibles, similaires à celles obtenues lors de l'optimisation de fichiers JPEG par des méthodes classiques (telles que tinyjpg). Naturellement, lors de l'utilisation de la compression stéganographique, les informations ne sont pas simplement « perdues », mais sont utilisées pour encoder d'autres données. De plus, le nombre de coefficients « optimisés » grâce à l'utilisation de F5 est bien inférieur à celui de l'optimisation traditionnelle.
Quelles que soient les modifications, elles sont absolument invisibles à l’œil nu. Sous le spoiler ci-dessous, le lecteur peut évaluer la différence à la fois à l'œil nu et en soustrayant les valeurs du composant modifié de l'original (plus la couleur est atténuée, plus la différence est petite) :
Liens vers des images qui ne rentrent pas sur habrastorage
Original -
Modifié -
Différence -
Au lieu d'une conclusion
J'espère avoir réussi à convaincre le lecteur que de telles méthodes sont possibles et ont droit à la vie. Cependant, acheter un disque dur ou un canal supplémentaire (pour la transmission réseau) peut sembler une option beaucoup plus simple que d'essayer d'économiser de l'argent de cette manière. D’une part, c’est vrai : le développement étendu est souvent plus simple et plus fiable. Mais d’un autre côté, il ne faut pas oublier l’intense. Après tout, rien ne garantit que demain vous pourrez venir au magasin et vous acheter un disque dur supplémentaire de mille téraoctets, mais vous pouvez toujours utiliser ceux que vous avez déjà chez vous.
->
Source : www.habr.com