Cryptanalyse des schémas de tatouage

De précédents travaux sur les liens entre tatouage et cryptographie avaient mis à jour plusieurs voies de recherche. La plus originale et la plus intéressante était, à notre avis, l'étude d'attaques structurelles sur les algorithmes de tatouage, visant non pas à lessiver le filigrane (comme le ferait une compression, une conversion numérique-analogique-numérique par exemple), mais à retrouver la clé secrète utilisée lors de son insertion. En effet, si l'attaquant réussit à estimer cette clé, alors il sera en mesure d'effacer proprement le filigrane (sans dégrader le document, et sans laisser de trace de son action), ou de modifier le message qu'il contient (accès au canal caché). Si cette approche avait été évoquée, personne n'avait abordé ce problème. Notre ambition est ainsi d'étudier la cryptanalyse des schémas les plus populaires de tatouage d'images fixes: un schéma substitutif classique (de la famille de [KZ95]) et l'ensemble des schémas reposant sur l'étalement de spectre (comme par exemple [ERTG03,CW01,PG03]. Tout d'abord, conformément au principe de Kerkhoff, nous avons supposé que l'attaquant sait quel système de tatouage a été utilisé. Nous avons ensuite suivi la même démarche que Claude Shannon lorsqu'il avait modélisé la sécurité des systèmes de chiffrement dans [Sha49]: nous nous sommes placés dans le cas où l'attaquant observe N_o documents qui ont tous été tatoués avec la même clé, mais qui peuvent contenir des messages différents ; nous avons alors étudié d'une part la quantité d'information sur la clé qui pouvait potentiellement fuir de ces observations (au sens de la théorie de l'information), et d'autre part quels moyens concrets pouvaient permettre au pirate de récupérer cette information et de reconstituer la clé. Conformément aux études cryptanalytiques, nous avons considéré différents contextes : 1) l'attaquant n'a accès qu'aux documents tatoués, 2) il a accès aux documents tatoués et aux documents originaux correspondants, et 3) il a accès aux document tatoués et aux messages qui y sont cachés. Il nous a fallu une bonne année pour résoudre la question théorique ; les outils proposés par Shannon, comme l'entropie ou l'equivocation, se sont avérés adaptés à l'étude du schéma substitutif mais pas à celui des schémas reposant sur l'étalement de spectre, pour lesquels nous avons utilisé les outils proposés par Fisher, comme la matrice d'information de Fisher. Nous avons alors pu démontrer que seul le schéma substitutif présentait une couverture parfaite (i.e. ne laissait filtrer aucune information sur la clé), et seulement dans le cas 1). Dans tous les autres cas, il y a une fuite potentielle d'information, que l'attaquant peut essayer d'exploiter. Voici le nombre d'observations à partir duquel l'attaquant a, en théorie, suffisamment d'information pour reconstituer la clé: pour le schéma substitutif, dans le cas 2) il est de log_2 N_c avec N_c la taille de la clé et du message, et dans le cas 3) de log_{2} N_v avec N_v la longueur du vecteur extrait; pour les schémas par étalement de spectre, dans le cas 1) et 3) il est de O(N_c sigma^2_x / gamma^2) avec N_c le nombre de porteuses, sigma2_x la variance du signal hôte et gamma la force d'insertion, et dans le cas 2) de O(N_c). Nous avons également démontré que la clé ne peut être complètement retrouvée que lorsque des messages sont connus ; dans les autres cas, on peut connaître toutes ses composantes, mais au signe et à l'ordre près (l'attaquant peut donc sans difficulté altérer un message, mais pas forcément inscrire celui de son choix). Enfin, nous avons élaboré des algorithmes permettant à l'attaquant de mener la cryptanalyse efficacement. Dans le cas des schémas substitutifs, les algorithmes étaient très naturels. Dans le cas des schémas par étalement de spectre, nous nous sommes appuyés sur les techniques d'analyse en composantes principales et d'analyse en composantes indépendantes. Nous avons mené des expérimentations sur des signaux synthétiques et sur de vraies images. Il est important de noter que ce travail s'adapte ensuite à toute technique similaire utilisant l'étalement de spectre, qu'elle touche des images fixes, de la vidéo ou de l'audio. [CFF04] F. Cayre, C. Fontaine et T. Furon. -- Watermarking attack: Security of WSS techniques. In: International Workshop on Digital Watermarking -- IWDW 2004, Lecture Notes in Computer Science. -- Springer-Verlag, 2004. à paraître. [CFF05] F. Cayre, C. Fontaine et T. Furon. -- A theory of watermarking security and its application to spread spectrum. IEEE Transactions on Signal Processing, 2005. -- numéro spécial "Supplement on Secure Media II", à paraître. [CW01] B. Chen et G. Wornell. -- Quantization index modulation: A class of provably good methods for digital watermarking and information embedding. IEEE Trans. on Information Theory, vol. 47, May 2001, pp. 1423--1443. [ERTG03] J. Eggers, R. Baüml, R. Tzschoppe et B.Girod. -- Scalar costa scheme for information embedding. IEEE Trans. on Signal Processing}, vol. 51, n°4, April 2003, pp. 1003--1019. [KZ95] E. Koch et J. Zhao. -- Towards robust and hidden image copyright labeling. In: IEEE Workshop on Nonlinear Signal and Image Processing, pp. 452--455. -- 1995. [PG03] S. Pateux et G. Le Guelvouit. -- Practical watermarking scheme based on wide spread spectrum and game theory. Signal Processing: Image Communication, vol. 18, April 2003, pp. 283--296. [Sha49] C.E. Shannon. -- Communication theory of secrecy systems. Bell System Technical Journal, vol. 28, 1949, pp. 656--715.