Admin CliCours
Protection cryptographique des bases de données :
conception et cryptanalyse
Protection cryptographique des données externalisées
Pour diverses raisons, de plus en plus de données sont externalisées. Cela peut être dans le but de rendre ces données accessibles depuis n’importe quel terminal informatique comme dans le cas du « cloud computing », ou simplement à cause d’un besoin de profiter de compétences externes. Mais externaliser ainsi des données ne signifie pas toujours que l’on souhaite les divulguer aux personnes les gérant pour nous. Il se peut aussi que l’on désire être capable de s’assurer de leur intégrité. Ces situations nécessitent donc une protection cryptographique des données. Un des aspects prépondérant pour les utilisateurs de telles solutions est néanmoins la facilité d’accéder à ces données externalisées. En particulier, il est rare qu’un utilisateur souhaite accéder à toutes ses données. Généralement, il voudra seulement en récupérer ou en modifier une partie. Par exemple, lorsque l’on regarde ses emails, il est fréquent de ne vouloir lire que les emails non lus, sans pour autant devoir télécharger l’intégralité de tous nos emails. Il faut donc un chiffrement ayant une granularité relativement fine. Un exemple similaire est le cas du chiffrement de disque dur où il n’est pas acceptable de déchiffrer l’intégralité du disque pour chaque lecture ou écriture. C’est pour cela que dans ce cas, le chiffrement est généralement effectué au niveau de chaque secteur du disque. Mais cette granularité ne doit pour autant pas être la source de nouvelles attaques. En particulier, un attaquant ne doit pas être capable de permuter des secteurs chiffrés, de déterminer si des secteurs sont identiques, ou de permettre la détection de fichiers tatoués (« watermarked »). Ces nouvelles contraintes ont donné lieu à de nouveaux concepts ; notamment les chiffrements par blocs adaptables, ou des modes opératoires avec protection d’intégrité. Après une présentation de ces techniques cryptographiques, nous décrirons quelques particularités caractéristiques des bases de données qui vont conditionner le choix de la solution cryptographique utilisée pour les proté7 8 CHAPITRE 1. PROTECTION CRYPTOGRAPHIQUE ger. En particulier, les bases de données agrègent des données selon une forte structure particulière, qui jouera nécessairement un rôle important lors du chiffrement, et ont aussi une fonctionnalité supplémentaire qui est la possibilité d’effectuer des requêtes efficaces sur les données. Nous décrirons donc le fonctionnement de ces mécanismes. 1.1 Cryptographie 1.1.1 Propriétés classiques requises Avant de décrire les propriétés de sécurité requises pour les chiffrements symétriques, il convient de définir dans un premier temps ce type d’algorithme. Un schéma de chiffrement symétrique est constitué d’une paire d’algorithmes : l’algorithme de chiffrement E et l’algorithme de déchiffrement D. Étant donné un message M et une clef K, son chiffré se déduit comme ceci : C = E (K, M) = EK(M). Pour retrouver le message clair à partir du chiffré C, de la clef K et de l’algorithme de déchiffrement D, on procède comme suit : M = D (K, C) = DK(C). Ces systèmes s’appellent aussi chiffrements à clef secrète, car l’unique clef utilisée est le secret partagé entre les utilisateurs. D est nécessairement déterministe, c’est-à-dire qu’à un couple (C, K) il associe un unique message M. Par contre, rien n’impose a priori à E de l’être, et, comme nous le verrons plus tard, ce ne sera généralement pas le cas. C’est-à-dire qu’il est possible que plusieurs chiffrés correspondent à un couple (M, K) fourni à E, dans le cas où il serait randomisé ou pourvu d’un état interne. Dans ce cas, il réalise une expansion sur la taille du chiffré. Il existe de nombreux niveaux de sécurité en cryptographie s’appliquant à ce type d’algorithmes de chiffrement. Les principaux sont les suivants. Définition 1 (Non-inversibilité, voir par exemple [Poi02], OW : one-wayness). Soient un algorithme de chiffrement non-inversible E et un message clair M. Il est impossible de trouver M à partir de E(K, M) sans connaître K. Définition 2 (Sécurité sémantique [GM84], IND : indistinguishability). Soit un adversaire ayant une puissance de calcul polynomiale, c’est-à-dire qu’il ne peut faire qu’un nombre polynomial de calculs, et un chiffré. Un chiffrement sûr sémantiquement assure que l’attaquant ne peut déduire aucune information sur le clair à partir du chiffré. 1.1. CRYPTOGRAPHIE 9 La notion de sécurité sémantique transpose donc la notion de « sécurité parfaite » de Shannon au contexte où l’adversaire a une puissance de calcul limitée. Définition 3 (Non-malléabilité [DDN00], NM : non-malleability). Soient E un algorithme de chiffrement non-malléable, M un message clair, et C = E(K, M) le chiffré de M. Alors aucun attaquant polynomial ne peut dériver un deuxième chiffré C 0 = E(K0 , M0 ) tel que M et M0 soient reliés. Les propriétés précédentes peuvent être étudiées dans différents contextes, en fonction du type de données (clairs, chiffrés correspondants) contrôlées par l’attaquant. On distingue classiquement plusieurs modèles d’adversaires : • attaque à clairs choisis (CPA : chosen plaintext attack) : une attaque à clairs choisis est une attaque où l’attaquant peut obtenir le chiffré de tout message clair de son choix, soit grâce à une clef publique, soit via un oracle de chiffrement ; • attaque à chiffrés choisis (CCA : chosen ciphertext attack) : une attaque à chiffrés choisis est une attaque où l’attaquant a accès à l’oracle de déchiffrement et peut ainsi demander le déchiffrement de tout chiffré de son choix ; il existe deux variantes d’attaques à chiffrés choisis : – attaques non-adaptatives (CCA1) : l’accès à l’oracle est uniquement autorisé avant que l’attaquant reçoive le challenge, – attaques adaptatives (CCA2) : l’accès à l’oracle est ici illimité dans le temps. Figure 1.1 – Relations entre les notions de sécurité [BDPR98] NM-CPA NM-CCA1 NM-CCA2 IND-CPA IND-CCA1 IND-CCA2 OW-CPA Légende : → : implication prouvée 9 : non implication prouvée 10 CHAPITRE 1. PROTECTION CRYPTOGRAPHIQUE La figure 1.1 présente les relations entre ces notions de sécurité [BDPR98]. Il en découle que le niveau de sécurité minimum acceptable est IND-CPA, alors que le meilleur est IND-CCA2 (que nous noterons dorénavant INDCCA) et NM-CCA2. Dans le but de bien clarifier le contexte, nous allons donc redéfinir précisément les notions IND-CPA et IND-CCA. Définition 4 (IND-CPA [BR05]). Considérons un adversaire qui choisit deux messages de même longueur en un temps polynomial et après un nombre de requêtes polynomial à l’algorithme de chiffrement. Seulement l’un des deux messages clairs est chiffré et son chiffré est donné à l’adversaire. Ce dernier a le droit d’interroger l’algorithme de chiffrement avec n’importe quel message. Le schéma de chiffrement est considéré IND-CPA si cet adversaire ne peut pas décider avec une probabilité significativement plus grande que 1 2 lequel des deux messages a été chiffré. Cette définition implique que le chiffrement doit être non déterministe, c’est-à-dire que deux messages identiques chiffrés successivement n’auront pas le même chiffré. Il y a essentiellement deux façons d’atteindre ce but. La première est de rendre le chiffrement aléatoire. Pour cela l’algorithme de chiffrement doit générer une valeur aléatoire qui est utilisée lors du chiffrement. Elle sera nécessaire pour le déchiffrement et induit donc une expansion du message chiffré par rapport au message clair. L’autre solution consiste à considérer une fonction de chiffrement avec un état interne, c’est-à-dire que la fonction a un état interne qui se met à jour après chaque chiffrement utilisant la même clef. La valeur de cet état étant aussi nécessaire au déchiffrement, cette solution implique aussi une expansion. Définition 5 (IND-CCA [BR05]). Considérons un adversaire qui choisit deux messages chiffrés de même longueur en un temps polynomial. Seulement l’un des deux messages chiffrés est déchiffré et son clair est donné à l’adversaire. Il a le droit d’interroger l’algorithme de déchiffrement avec n’importe quel message, hormis les deux qu’il a choisis. Le schéma de chiffrement est considéré IND-CCA si cet adversaire ne peut pas décider avec une probabilité significativement plus grande que 1 2 lequel des deux messages a été déchiffré. En cryptographie symétrique, les modèles d’adversaire peuvent être raffinés. Il existe des variantes de ces attaques, par exemple dans lesquelles l’adversaire a accès à l’algorithme de chiffrement tout au long de l’attaque, mais n’a accès au déchiffrement que lors de la phase des choix des deux messages clairs. Les relations entre ces variantes ont été établies par Katz et Yung [KY00a]. Dans le cadre de la cryptographie symétrique, Bellare et al. [BDJR97] ont redéfini l’indistinguabilité par d’autres objectifs de sécurité (LOR, FTG et ROR).
Primitives de chiffrement symétrique
Les algorithmes de chiffrement à flot et par blocs constituent les deux grandes classes de primitives symétriques. La distinction entre ces deux classes n’est pour autant pas toujours aisée. Habituellement, le chiffrement à flot désigne les algorithmes opérant sur des blocs de clair de taille relativement petite (généralement un bit, un octet ou un mot) au moyen d’une transformation qui varie au cours du temps. Par opposition, un algorithme de chiffrement par blocs applique la même fonction à différents blocs dérivés du clair, qui sont de taille plus conséquente, typiquement 64, 128 ou 256 bits [MvOV97]. Nous distinguerons donc deux briques de base du chiffrement symétrique : • les générateurs pseudo-aléatoires, • les chiffrements par blocs. Ce sont deux objets mathématiques distincts qui sont utilisés de diverses manières. Par exemple, il est possible d’utiliser un chiffrement par blocs pour fabriquer un générateur pseudo-aléatoire, grâce à des modes opératoires adéquats que nous verrons plus loin. Intuitivement, ces deux types de chiffrement nous seront utiles. En effet, les bases de données contiennent des champs de taille variable, pouvant être aussi petits qu’un bit ou tout aussi bien en faire plusieurs centaines. Cela nous incite à considérer ces deux types de chiffrement comme étant d’intérêt pour atteindre notre but. Chiffrement à flot Dans la suite de ce document nous limiterons l’utilisation du terme chiffrement à flot aux seuls algorithmes synchrones, ceci étant en partie motivé par le fait que les chiffrements à flot auto-synchronisants sont plus ou moins tombés en désuétude. Définition. Un algorithme de chiffrement à flot synchrone consiste à combiner le clair avec une suite binaire de même longueur, la suite chiffrante. Notons s = (st) t≥0 cette suite qui est engendrée par un automate à états finis, appelé générateur pseudo-aléatoire, de façon indépendante à la fois du clair et du chiffré. Le rôle de ce générateur est de produire à chaque moment t un bloc de m bits, st , qui est fonction de son état interne xt . Le générateur peut se décomposer en trois fonctions, comme cela est décrit à la figure 1.2 : • une procédure d’initialisation qui, à partir de la clef secrète et d’un vecteur d’initialisation public, calcule l’état initial du générateur, x0. Cette étape peut parfois être scindée en deux phases. La première, le chargement de clef, consiste en un calcul d’une valeur ne dépendant que de la clef. La seconde, appelée injection d’IV ou de re-synchronisation, détermine alors l’état initial du générateur à partir de la valeur obtenue précédemment et de l’IV. Ce découpage permet de gagner du temps lors d’un changement de l’IV sans changement de clef, ce qui est fréquent, par exemple lors de l’utilisation d’un protocole de communication pour lequel la longueur des paquets échangés est relativement petite, comme par exemple pour les communications téléphoniques, ou dans le contexte des bases de données où les champs peuvent être très petits et les IV varient d’un champ à l’autre et d’une mise à jour à l’autre. • une fonction de transition, notée T, qui fait passer l’état interne du générateur de l’instant t à l’instant (t + 1). En général, cette fonction est fixe, mais il se peut qu’elle varie avec la clef, l’IV, voire même avec le temps.
Introduction |
