Cette thèse traite de la question de l'authenticité des photographies d'identité, partie intégrante des documents nécessaires lors d'un contrôle d'accès. Alors que les moyens de reproduction sophistiqués sont accessibles au grand public, de nouvelles méthodes / techniques doivent empêcher toute falsification / reproduction non autorisée de la photographie d'identité. Cette thèse propose une méthode de hachage pour l'authentification de photographies d'identité, robuste à l'impression-lecture. Ce travail met ainsi l'accent sur les effets de la numérisation au niveau de hachage. L'algorithme mis au point procède à une réduction de dimension, basée sur l'analyse en composantes indépendantes (ICA). Dans la phase d'apprentissage, le sous-espace de projection est obtenu en appliquant l'ICA puis réduit selon une stratégie de sélection entropique originale. Dans l'étape d'extraction, les coefficients obtenus après projection de l'image d'identité sur le sous-espace sont quantifiés et binarisés pour obtenir la valeur de hachage. L'étude révèle les effets du bruit de balayage intervenant lors de la numérisation des photographies d'identité sur les valeurs de hachage et montre que la méthode proposée est robuste à l'attaque d'impression-lecture. L'approche suivie en se focalisant sur le hachage robuste d'une classe restreinte d'images (d'identité) se distingue des approches classiques qui adressent une image quelconque

La plupart de nos activités quotidiennes sont aujourd'hui rythmées et régies par Internet, qu'il s'agisse de partage de fichiers, d'interaction sur les réseaux sociaux, de banques et de cours en ligne, ou encore de publication de blogs. En ce qui concerne le partage de fichiers, l'une des activités les plus pratiquées sur Internet, diverses solutions ont déjà été proposées, créées et implantées, pour constituer des réseaux de partage de fichiers aux performances et objectifs parfois très différents. Cette société du numérique permet le profilage des utilisateurs. Chaque information envoyée ou reçue sur Internet va ainsi traverser une série de noeuds intermédiaires jusqu'à atteindre sa destination. Un observateur pourra ainsi déterminer la provenance et la destination des paquets et de ce fait surveiller et profiler les activités des utilisateurs en identifiant le serveur auquel ils se connectent ou la durée de leur session. Parallèlement, les communications anonymes se sont développées afin de permettre aux utilisateurs d'utiliser Internet sans que leur identité ne soit nécessairement révélée.Notre contribution se veut double. Nous nous intéressons tout d'abord aux environnements de partage de fichiers hybrides en nous focalisant sur des réseaux réels largement déployés. Nous visons, au travers de cette étude, deux objectifs. Le premier consiste en l'amélioration du système d'indexation de contenu au sein de l'environnement de partage de fichiers BitTorrent. Il s'agit, plus précisément, de renforcer le système BitTorrent par le biais d'une indexation de son contenu dans la table de hachage distribuée Kad. Notre second but est d'améliorer les conditions d'accès au contenu ainsi que sa disponibilité au sein de l'environnement I2P de partage de fichiers. Nous permettons aux utilisateurs d'I2P d'accéder anonymement au contenu public de BitTorrent et nous aboutissons ainsi à un environment de partage de fichiers totalement anonyme, indexation et distribution du contenu comprises. Nous centrons ensuite notre analyse sur une meilleure compréhension des environnements anonymes par le biais d'une surveillance à grande échelle. Nous définissons les caractéristiques du réseau I2P, en visant l'intégralité de l'environnement anonyme et son large champ d'activités et de services anonymes. Nous analysons les différents aspects du réseau, comme le nombre des utilisateurs, leurs caractéristiques ainsi que le nombre de services anonymes disponibles. Au travers des mesures et évaluations réalisées à long terme sur le réseau, couplées à différentes analyses de corrélation, nous avons réussi à identifier et caractériser un petit groupe d'individus exécutant un service anonyme spécifique comme, par exemple, les habitants d'une même ville utilisant une application anonyme de partage de fichiers / Most of our daily activities are carried out over the Internet, from file-sharing and social networking to home banking, online-teaching and online-blogging. Considering file-sharing as one of Internet top activities, different architectures have been proposed, designed and implemented, leading to a wide set of file-sharing networks with different performances and goals. This digital society enables as well users' profiling. As Internet users surf the World Wide Web, every sent or received packet passes through several intermediate nodes until they reach their intended destination. So, an observer will be able to determine where a packet comes from and where it goes to, to monitor and to profile users' online activities by identifying to which server they are connected or how long their sessions last. Meanwhile, anonymous communications have been significantly developed to allow users to carry out their online activities without necessarily revealing their real identity. Our contribution is twofold. On the one hand, we consider hybrid file-sharing environments, with a special focus on widely deployed real-world networks and targeting two defined goals. The first goal is to improve content indexation in the BitTorrent file-sharing environment, enabling BitTorrent content to be indexed in the Kad distributed has table and leading to a more robust BitTorrent system. The second goal is to improve content availability in the I2P file-sharing environment. We allow I2P users to anonymously access public BitTorrent content and we obtain a fully anonymous file-sharing environment, including anonymous content indexation and anonymous content distribution. On the other hand, we focus on the understanding of anonymous environments through extensive monitoring. We characterise the I2P network, targeting the entire anonymous environment and its anonymous services. We consider different aspects of the network, such as the number of users, their characteristics as well as the number of anonymous services available. Through long-term measurements on the network and along with different correlation analyses, we are able to characterise a small group of users using a specific anonymous service, such as the users from a particular city performing anonymous file-sharing

Une fonction de hachage est une fonction prenant comme argument un élément de taille arbitraire finie et renvoyant un élément de longueur fixée. Il existe différents types de fonctions de hachage qui correspondent à autant de domaines d'utilisation. Parmi ces fonctions, les fonctions de hachage cryptographiques se distinguent par la variété des missions qui leur sont confiées et par l'exigence qui leur est faîte de respecter de nombreux impératifs de sécurité. Les fonctions de hachage cryptographiques les plus utilisées en pratiques appartiennent à la famille MD-SHA, dont les membres les plus connus sont les fonctions MD5 et SHA-1. Durant ces dernières années, de nouvelles techniques de crytptanalyses ont fait leur apparition. Ces techniques, bien que très complexes, se sont montrés si efficaces qu'elles ont conduit à l'abandon de l'utilisation des fonctions MD5 et SHA-1, et à l'ouverture d'une compétition internationale pour le développement d'un nouvel algorithme de hachage cryptographique. Les travaux de recherche que nous avons menés dans le cadre de cette thèse s'inscrivent à la fois dans une démarche d'analyse et de conception. Nous étudions les nouvelles avancées dans la cryptanalyse des fonctions de hachage, et plus particulièrement leurs mise en oeuvre dans le cadre des fonctions SHA-0 et SHA-1. Nous présentons à ce titre la meilleure attaque pratique connue à ce jour contre SHA-0 et proposons la première classification des vecteurs de perturbations utilisés par les attaques par collision contre la fonction SHA-1. Nous abordons ensuite la conception de nouvelle fonctions par le biais des fonction XOR-Hash et FSB.

Cette thèse traite de la question de l’authenticité des photographies d’identité, partie intégrante des documents nécessaires lors d’un contrôle d’accès. Alors que les moyens de reproduction sophistiqués sont accessibles au grand public, de nouvelles méthodes / techniques doivent empêcher toute falsification / reproduction non autorisée de la photographie d’identité. Cette thèse propose une méthode de hachage pour l’authentification de photographies d’identité, robuste à l’impression-lecture. Ce travail met ainsi l’accent sur les effets de la numérisation au niveau de hachage. L’algorithme mis au point procède à une réduction de dimension, basée sur l’analyse en composantes indépendantes (ICA). Dans la phase d’apprentissage, le sous-espace de projection est obtenu en appliquant l’ICA puis réduit selon une stratégie de sélection entropique originale. Dans l’étape d’extraction, les coefficients obtenus après projection de l’image d’identité sur le sous-espace sont quantifiés et binarisés pour obtenir la valeur de hachage. L’étude révèle les effets du bruit de balayage intervenant lors de la numérisation des photographies d’identité sur les valeurs de hachage et montre que la méthode proposée est robuste à l’attaque d’impression-lecture. L’approche suivie en se focalisant sur le hachage robuste d’une classe restreinte d’images (d’identité) se distingue des approches classiques qui adressent une image quelconque / This thesis addresses the question of the authenticity of identity photographs, part of the documents required in controlled access. Since sophisticated means of reproduction are publicly available, new methods / techniques should prevent tampering and unauthorized reproduction of the photograph. This thesis proposes a hashing method for the authentication of the identity photographs, robust to print-and-scan. This study focuses also on the effects of digitization at hash level. The developed algorithm performs a dimension reduction, based on independent component analysis (ICA). In the learning stage, the subspace projection is obtained by applying ICA and then reduced according to an original entropic selection strategy. In the extraction stage, the coefficients obtained after projecting the identity image on the subspace are quantified and binarized to obtain the hash value. The study reveals the effects of the scanning noise on the hash values of the identity photographs and shows that the proposed method is robust to the print-and-scan attack. The approach focusing on robust hashing of a restricted class of images (identity) differs from classical approaches that address any image

La démocratisation des ordinateurs, des téléphones portables et surtout de l'Internet a considérablement révolutionné le monde de la communication. Les besoins en matière de cryptographie sont donc plus nombreux et la nécessité de vérifier la sûreté des algorithmes de chiffrement est vitale. Cette thèse s'intéresse à l'étude d'une nouvelle cryptanalyse, appelée cryptanalyse logique, qui repose sur l'utilisation de la logique propositionnelle - à travers le problème de satisfaisabilité - pour exprimer et résoudre des problèmes cryptographiques. Plus particulièrement, les travaux présentés ici portent sur une certaine catégorie de chiffrements utilisés dans les protocoles d'authentification et d'intégrité de données qu'on appelle fonctions de hachage cryptographiques. Un premier point concerne l'aspect modélisation d'un problème cryptographique en un problème de satisfaisabilité et sa simplification logique. Sont ensuite présentées plusieurs façons pour utiliser cette modélisation fine, dont un raisonnement probabiliste sur les données du problème qui permet, entres autres, d'améliorer les deux principaux points d'une attaque par cryptanalyse logique, à savoir la modélisation et la résolution. Un second point traite des attaques menées en pratique. Dans ce cadre, la recherche de pré-Image pour les fonctions de hachage les plus couramment utilisées mènent à repousser les limites de la résistance de ces fonctions à la cryptanalyse logique. À cela s'ajoute plusieurs attaques pour la recherche de collisions dans le cadre de la logique propositionnelle. / Democratization of increasingly high-Performance digital technologies and especially the Internet has considerably changed the world of communication. Consequently, needs in cryptography are more and more numerous and the necessity of verifying the security of cipher algorithms is essential.This thesis deals with a new cryptanalysis, called logical cryptanalysis, which is based on the use of logical formalism to express and solve cryptographic problems. More precisely, works presented here focuses on a particular category of ciphers, called cryptographic hash functions, used in authentication and data integrity protocols.Logical cryptanalysis is a specific algebraic cryptanalysis where the expression of the cryptographic problem is done through the satisfiabilty problem, fluently called sat problem. It consists in a combinatorial problem of decision which is central in complexity theory. In the past years, works led by the scientific community have allowed to develop efficient solvers for industrial and academical problems.Works presented in this thesis are the fruit of an exploration between satisfiability and cryptanalysis, and have enabled to display new results and innovative methods to weaken cryptographic functions.The first contribution is the modeling of a cryptographic problem as a sat problem. For this, we present some rules that lead to describe easily basic operations involved in cipher algorithms. Then, a section is dedicated to logical reasoning in order to simplify the produced sat formulas and show how satisfiability can help to enrich a knowledge on a studied problem. Furthermore, we also present many points of view to use our smooth modeling to apply a probabilistic reasoning on all the data associated with the generated sat formulas. This has then allowed to improve both the modeling and the solving of the problem and underlined a weakness about the use of round constants.Second, a section is devoted to practical attacks. Within this framework, we tackled preimages of the most popular cryptographic hash functions. Moreover, the collision problem is also approached in different ways, and particularly, the one-Bloc collision attack of Stevens on MD5 was translated within a logical context. It's interesting to remark that in both cases, logical cryptanalysis takes a new look on the considered problems.

Avec une croissance considérable dans le domaine de la technologie multimédia et de la forte disponibilité des logiciels de traitement d'image, il est désormais facile de manipuler les images numériques. En même temps, il est devenu possible de réaliser des contrefaçons très élaborées, en laissant très peu de traces. Cela présente un grave problème, en particulier, si l'authenticité de l'image numérique est exigée. L'authentification des images devrait se baser sur leurs contenus visuels et non pas sur leurs contenus binaires. Par conséquent, pour authentifier une image, il faut tolérer quelques manipulations acceptables que pourrait subir une image telles que la compression JPEG et l'ajout de bruit Gaussien. En effet, ces manipulations préservent l'aspect visuel de l'image. En même temps un système de hachage perceptuel doit être suffisamment fragile pour détecter les manipulations malveillantes qui modifient l'interprétation du contenu sémantique de l'image comme l'ajout de nouveaux objets, la suppression ou la modification majeure d'objets existants.Dans cette thèse, nous nous intéressons aux fonctions de hachage perceptuel pour l'authentification et le contrôle d'intégrité des images numériques. Dans ce but, nous présentons tous les aspects relatifs aux fonctions de hachage perceptuel. Puis, nous exposons les contraintes qu'un système de hachage perceptuel doit satisfaire pour répondre aux exigences souhaitées au niveau de la robustesse des signatures perceptuelles. Enfin, nous présentons une méthode permettant d'améliorer la robustesse et la sécurité d'un système dehachage perceptuel. / The widespread use of multimedia technology has made it relatively easy to manipulate and tamper visual data. In particular, digital image processing and image manipulation tools offer facilities to intentionally alter image content without leaving perceptual traces. This presents a serious problem, particularly if the authenticity of the digital image is required. The image authentication should be based on their visual content and not on their binary content. Therefore, to authenticate an image, some acceptable manipulations that could undergoes an image, such as JPEG compression and Gaussian noise addition, must tolerated. Indeed, these manipulations preserve the visual appearance of the image. At the same time a perceptual hashing system should be sufficiently sensitive to detect malicious manipulations that modify the interpretation of the semantic content of the imagesuch as adding new objects, deleting or major modification of existing objects.In this thesis, we focus on perceptual hash functions for authentication and integrityverification of digital images. For this purpose, we present all aspects of perceptual hashfunctions. Then, we discuss the constraints that perceptual hashing system must satisfy tomeet desired level of robustness of perceptual signatures. Finally, we present a method toimprove the robustness and security of a system of perceptual hashing.

Dans ce mémoire nous étudions le domaine des fonctions de hachage, qui sont utilisées par de nombreux mécanismes cryptographiques. Les travaux présentés ici abordent à la fois la conception et l'analyse de la sécurité de ces fonctions. La première partie de ce mémoire est une introduction générale au domaine des fonctions de hachage. Nous décrivons la manière dont elles sont utilisées en la cryptographie et la manière de formaliser leur sécurité. Nous exposons également les principes de conception sur lesquels les fonctions de hachage les plus utilisées sont fondées. Enfin, nous évoquons la situation actuelle. La cryptanalyse différentielle a donné lieu à des attaques contre les principales fonctions de hachage. Le NIST organise actuellement une compétition de conception de fonctions de hachage (la compétition SHA-3), dans le but de définir une nouvelle norme de hachage. Dans la deuxième partie nous présentons nos travaux liés à la conception d'un candidat à cette compétition : Shabal. Nous commençons par décrire cette fonction, ainsi que les différentes évaluations de sa sécurité. En nous plaçant dans le modèle de l'indifférenciabilité d'un oracle aléatoire, nous montrons la sécurité du mode utilisé par Shabal lorsque la fonction de compression est idéalisée, puis la sécurité d'un mode plus classique lorsque cette fonction est affaiblie. Enfin, dans la troisième partie, nous abordons le domaine de la cryptanalyse de fonctions de hachage. Nous présentons la meilleure attaque connue contre RadioGatun, qui a été définie avant la compétition SHA-3 ainsi qu'une attaque contre Hamsi-256, une fonction sélectionnée pour le deuxième tour de la compétition SHA-3.

La structuration automatique de flux de télévision est un nouveau sujet de recherche, dont l'apparition est liée à l'augmentation de volume des archives de vidéos numériques de télévision. Cette thèse propose une chaîne complète de structuration, qui permet de segmenter et d'étiqueter automatiquement un flux télévisé. Les travaux présentés se divisent en quatre parties : la définition d'outils, la segmentation, l'étiquetage, et la mise à jour. Un flux de télévision est intrinsèquement répétitif. L'une des idées directrices de la thèse est de considérer les répétitions comme une aide essentielle pour la structuration, en particulier pour réaliser la distinction entre les programmes et les inter-programmes. Une méthode rapide de détection des répétitions dans des flux vidéos est proposée, permettant de gérer d'importants volumes vidéos, à partir d'une base de vidéos de référence, étiquetée manuellement. Grâce à un outil, ainsi qu'à la détection des séparations entre publicités, une segmentation en programmes/inter-programmes est réalisée. Les segments sont alors étiquetés à partir du guide des programmes, en réalisant un alignement global par dynamic time warping. Enfin, une étape de mise à jour permet de réduire la dépendance à une base de Référence manuelle, ainsi que de réduire la baisse de qualité des résultats de structuration au cours du temps.

Cette thèse traite d'algorithmique des ensembles de données en adoptant le point de vue de la combinatoire analytique. On traite ici de trois problèmes qui illustrent cette approche: les listes à sauts associées à de l'analyse asymptotique bivariée, le hachage à essai aléatoire avec pagination et le comptage probabiliste. Les listes à sauts sont une structure de données intermédiaire entre les skiplists et les arbres binaires de recherche. L'étude de cette structure a donné lieu à un problème d'asymptotique bivariée avec coalescence de singularités. Le hachage avec essai aléatoire est un algorithme qui gère les collisions d'une table de hachage. Dans le contexte étudié qui est celui de la pagination, on obtient la moyenne, ainsi que tous les moments successifs du coût de construction. Les algorithmes de comptage probabilistes originaux Loglog et Super Loglog permettent d'estimer le cardinal d'un ensemble en utilisant un kilooctet de mémoire avec une précision d'environ 3%.

Etablir un canal garantissant l'authentification de façon efficace requiert l'utilisation de nombreux outils cryptographiques. Dans ce mémoire, nous nous intéressons à la sécurité de plusieurs d'entre eux, présents à différentes étapes dans le protocole de mise en place du canal. Dans un premier temps, nous abordons l'analyse de deux protocoles qui, mis bout à bout, assurent la mise en place d'un canal authentifié, confidentiel et intègre : un algorithme d'échange de clefs authentifié et un algorithme de chiffrement authentifié. Le premier algorithme permet de générer des clefs en alliant plusieurs moyens d'authentification (biométrie, mot de passe, carte à puce). Le second est un algorithme normalisé appelé CCM. Dans un second temps, nous nous intéressons plus particulièrement à la phase d'extraction de clefs, étape charnière entre l'échange de clefs et son utilisation pour établir un canal sécurisé. Nous présentons une méthode simple pour extraire une clef symétrique d'un élément Diffie-Hellman, puis nous analysons l'utilisation d'HMAC comme fonction d'extraction de clefs. Dans un troisième temps, nous concentrons notre attention sur les fonctions de hachage, très utilisées à plusieurs niveaux du protocole. Plus précisément, nous analysons la sécurité d'un mode opératoire basé sur un algorithme de chiffrement par bloc dont on fixe la clef, puis, nous examinons des modes opératoires qui cherchent à garantir une sécurité en seconde préimage optimale.