Quels problèmes et solutions cryptographiques ?

Ces dernières années, les scandales impliquant le vol ou la perte de données confidentielles se sont multipliés. En novembre 2007, au Royaume-Uni, deux cédéroms contenant les données fiscales de 25 millions de Britanniques ont été égarés. Même chose au Chili, où les données personnelles de 6 millions de citoyens se sont retrouvées diffusées sur Internet après le piratage de plusieurs systèmes d’informations de l’Etat chilien. Deux exemples qui montrent bien que les protections classiques des systèmes d’informations risquent souvent de s’avérer trop faibles contre un pirate fortement motivé par les données détenues. Pourtant, il n’y a pas de fatalité. La plupart de ces événements fâcheux auraient pu être évités si les bases de données avaient été stockées sous forme chiffrée. Mais comment ?

Manipuler des bases de données chiffrées… sans déchiffrer

L’administrateur d’une base de données sensible est souvent réticent à son chiffrement intégral pour des raisons pratiques. En effet cela signifie une sécurité accrue mais au prix d’un sacrifice de fonctionnalité.

Le problème d’une base de données protégée par chiffrement est qu’il est délicat d’effectuer des recherches ou des opérations mathématiques sur son contenu. Il faut alors déchiffrer les éléments en jeu, effectuer l’opération, puis chiffrer à nouveau le résultat. Ceci pose à la fois des problèmes de performances, en raison des étapes de chiffrement et déchiffrement, mais également de sécurité car les données sont manipulées en clair pendant un certain laps de temps. Afin de remédier à cet inconvénient, les cryptographes se sont penchés sur ce que l’on nomme le « cryptocomputing », l’art de calculer avec des données chiffrées. Les opérations que l’on peut souhaiter effectuer sont nombreuses : recherche d’un élément ou d’un mot clé, comparaison d’éléments, opérations mathématiques comme l’addition ou la multiplication…

Le cas des opérations mathématiques est sans doute l’un des plus intéressants, et les exemples d’applications où l’on doit pouvoir calculer sur des éléments chiffrés sont légions. C’est le cas notamment du vote électronique : il faut pouvoir ajouter les votes de chaque individu qui ont été collectés sous forme chiffrée, sans les déchiffrer et déchiffrer seulement une fois le total calculé. Autre exemple : le traitement statistique de données personnelles : comment permettre à l’INSEE de calculer la moyenne des revenus d’une classe d’individus sans connaître le revenu de chacun d’eux ?

Prenons le cas simple du cryptosystème à clé publique RSA, dont nous rappelons brièvement le fonctionnement. Chaque utilisateur possède une clé publique connue des autres utilisateurs et une clé privée connue de lui seul. La clé publique est constituée d’un couple (n,e) où n est le produit de deux grands nombres premiers p et q (la taille de n est typiquement de 1.024 ou 2.048 bits), et e est un nombre premier avec (p-1)*(q-1). La clé privée est le couple (n,d) où d a la particularité que pour tout nombre M compris entre 0 et n-1 : (M^e)^d=M mod n.

Ce cryptosystème permet deux fonctionnalités, le chiffrement et la signature. Ainsi, pour chiffrer un message M à destination d’un utilisateur dont la clé publique est (n,e), on calcule : C=M^e mod n, et on lui envoie C.

Le destinataire peut alors retrouver M en calculant : M=C^d mod n.

Le chiffrement RSA permet de multiplier entre eux des éléments chiffrés. En effet, si C est le chiffré correspondant au clair M, et C’ le chiffré correspondant au clair M’, alors le chiffré correspondant au clair M*M’ est : (M*M’)^e mod n = M^e * M’^e mod n = C*C’ mod n.

On peut donc calculer le chiffré correspondant à M*M’ sans connaître M ni M’, mais seulement à partir de leurs chiffrés. On dit que RSA est homomorphique par rapport à la multiplication.

Aujourd’hui, de nombreux systèmes de chiffrement à clé publique sont homomorphiques par rapport à la multiplication (le cryptosystème d’El Gamal par exemple) ou à l’addition (comme le cryptosystème de Paillier). En revanche on ne connaît pas à l’heure actuelle de système de chiffrement qui soit homomorphique à la fois par rapport à l’addition et la multiplication. La construction d’un tel cryptosystème (ou éventuellement la preuve qu’il est impossible d’en construire un) constitue à l’heure actuelle l’un des sujets les plus importants en cryptographie, car il permettrait de manipuler de façon arbitraire des données chiffrées.

Une autre fonctionnalité fortement désirable est de pouvoir rechercher un élément dans une base de données chiffrée. Considérons le cas d’un serveur d’e-mails dans lequel, pour des raisons de respect de la vie privée de l’utilisateur, les e-mails sont stockés sous forme chiffrée. Lorsque l’utilisateur veut consulter les e-mails contenant un mot-clé, il doit rapatrier l’ensemble de la base de données sur son terminal, la déchiffrer et effectuer la recherche, ce qui est potentiellement problématique pour une plate-forme à faibles capacités comme un téléphone mobile. Existe-t-il un moyen pour permettre au serveur d’effectuer la recherche sans lui apprendre autre chose qu’un certain nombre de mails contiennent ou non le mot-clé ?

Une réponse positive a été apportée par un groupe de chercheurs de Berkeley [1]. Leur schéma, légèrement plus complexe qu’un algorithme de chiffrement classique, est représenté sur la Figure 1. L’astuce consiste à procéder à un masquage du chiffré par un générateur pseudo-aléatoire (ceci évite également qu’un même mot en clair corresponde au même mot chiffré, ce qui donne une information importante à un attaquant).

Chaque mot M est tout d’abord chiffré avec un chiffrement par blocs classique E sous une première clé secrète Kcb pour obtenir le chiffré X. Les n-m premiers bits de X, dénotés L, sont utilisés pour dériver, à l’aide d’une seconde clé secrète Kder, une sous-clé K. Parallèlement un générateur de nombres pseudo-aléatoires est utilisé avec une troisième clé secrète Kg pour donner un bloc de n-m bits S. Ce bloc est ensuite haché avec la sous clé K pour obtenir un bloc T de m bits. La paire (S,T) est alors ajoutée à X pour obtenir le chiffré final C. Pour effectuer la recherche d’un mot M, l’utilisateur envoie au serveur la paire (X,K) correspondante. Le serveur n’a alors qu’à calculer C’ xor X pour chaque chiffré C’ contenu dans la base de données, en déduire S’ et T’ et vérifier que T’=H(K,S’), ce qui indiquera qu’il s’agit bien du mot recherché. Remarquons que le serveur n’apprend rien sinon que le mot recherché par l’utilisateur se trouvait bien aux positions identifiées dans la base de données, et ne connaît pas même le clair recherché.

Figure 1. Procédé de chiffrement permettant une recherche de mot-clé sans déchiffrer.

Remarquons que le serveur n’apprend rien sinon que le mot recherché par l’utilisateur se trouvait bien aux positions identifiées dans la base de données.

Et les bases de données respectueuses de la vie privée ?

Une problématique complémentaire est celle du respect de la vie privée de l’utilisateur d’une base de données publiquement accessible. Par exemple, un investisseur peut vouloir consulter le cours d’une action précise sans dévoiler laquelle. Autre exemple : celui de laboratoires qui utilisent une banque de données pharmaceutiques ou de brevets mais ne veulent pas révéler les molécules ou les inventions sur lesquelles ils travaillent. Dans tous ces cas, il est souhaitable que l’utilisateur puisse accéder à l’information contenue dans la base de données sans que le serveur sache quelle donnée précise l’intéressait.

Pour cela, les cryptographes ont construit des schémas dits de « Retrait d’Informations Privé » (abrégé en PIR pour l’anglais « Private Information Retrieval« ). Remarquons que c’est le retrait qui est privé (dans le sens où le serveur de données ne peut savoir à quel élément l’utilisateur a accédé), et non l’information, qui elle est publique. Il ne faut pas confondre ce genre de schéma avec une procédure d’anonymisation, lors de laquelle le serveur sait quelle donnée il a transmis, mais sans connaître l’identité de l’utilisateur. Au contraire, dans un schéma de PIR, le serveur sait que l’utilisateur A a récupéré une information dans la base, mais ne sait pas quelle information.

On peut montrer mathématiquement que si la base de données est unique et que le détenteur de cette base de données possède une puissance de calcul infini, alors la seule façon de procéder de manière parfaitement sûre est que l’utilisateur demande l’intégralité de la base de données. Ceci s’avère totalement impraticable dès que la base de données est grande ou fréquemment mise à jour. Cependant des solutions non triviales et peu coûteuses en communication existent lorsque la base de données est répliquée sur plusieurs serveurs, et que l’on suppose que les serveurs ne vont pas collaborer entre eux pour découvrir la requête de l’utilisateur [2], ce qui est souvent une hypothèse peu vraisemblable si c’est une même entité qui gère tous les serveurs.

Fort heureusement, les cryptographes sont parvenus à mettre au point des protocoles marchant avec un serveur unique [3]. Ces protocoles reposent sur des problèmes calculatoires difficiles. La situation est analogue à celle du chiffrement, où l’on peut montrer que pour obtenir une confidentialité parfaite contre un attaquant possédant une puissance de calcul infini, la clé doit être aussi longue que le message. Alors qu’en faisant l’hypothèse qu’un attaquant ne saura jamais résoudre un problème difficile (typiquement le problème de la factorisation ou du logarithme discret), on peut construire des systèmes de chiffrement au moins aussi sûrs que le problème est difficile à résoudre, comme le système de chiffrement à clé publique d’El Gamal. Toutefois, les protocoles actuellement connus sont encore coûteux en termes de calculs. Mais il s’agit d’un domaine de recherche actif et l’on peut s’attendre à l’obtention de schémas pratiques prochainement.

Par Yannick Seurin, Ingénieur de recherche en cryptographie

Notes

[1] D.X. Song, D. Wagner, et A. Perrig, Practical Techniques for Searches on Encrypted Data, IEEE Symposium on Security and Privacy, p. 44–55, 2000.
[2] B. Chor, O. Goldreich, E. Kushilevitz, et M. Sudan, Private Information Retrieval, FOCS 1995, p. 41–51, 1995.
[3] E. Kushilevitz et R. Ostrovsky, Replication is not needed: Single database, computationally-private information retrieval, FOCS 1997, p. 364–373, 1997.