La menace des fuites liées aux schémas d’accès

Chiffrer les données protège leur contenu des parties non autorisées, mais le chiffrement seul ne masque pas les métadonnées sur la manière dont les données sont consultées. Les profils d’accès — c’est-à-dire quels enregistrements sont lus ou écrits, à quel moment et à quelle fréquence — peuvent révéler des informations sensibles, même lorsque les données elles-mêmes sont entièrement chiffrées. L’écart entre la confidentialité du contenu et celle des accès constitue la motivation centrale de la RAM oblivieuse.

L’analyse des profils d’accès peut révéler : les enregistrements de base de données qu’un utilisateur interroge (ce qui permet de déduire ses problèmes médicaux à partir des enregistrements consultés), les profils de communication (qui contacte qui, même si le contenu des messages est chiffré), l’activité financière (ce qui permet de déduire des stratégies d’investissement à partir des cours demandés par un utilisateur) et les habitudes comportementales (les routines quotidiennes que révèlent les heures et la fréquence des accès). Ces déductions peuvent être aussi sensibles que le contenu des données lui-même.

CryptDB (MIT, 2011) était un système influent permettant d’interroger des bases de données chiffrées. Des travaux ultérieurs de Grubbs, McPherson, Naveed, Ristenpart et Spooner (2016) ont montré que CryptDB et les schémas similaires de chiffrement préservant l’ordre divulguent des profils d’accès qui permettent des attaques par inférence. Un attaquant disposant d’un jeu de données auxiliaire sur la répartition des accès peut déduire des valeurs en clair à partir de la seule fréquence et du seul ordre des accès, même sans casser le chiffrement.

Si un service de stockage en nuage chiffré journalise les blocs de texte chiffré auxquels on accède, un adversaire peut effectuer une analyse de fréquence. Comme les utilisateurs ont tendance à accéder plus souvent aux fichiers populaires, l’histogramme des fréquences d’accès aux blocs de texte chiffré reflète la distribution des accès au texte en clair. La mise en correspondance de l’histogramme chiffré des fréquences avec des schémas d’accès connus peut permettre d’identifier les fichiers chiffrés qui correspondent aux catégories de contenu populaires.

Dans le modèle de menace honnête mais curieux (semi-honnête), le fournisseur de services en nuage respecte correctement le protocole, mais observe tous les schémas d’accès aux données du client. De nombreux fournisseurs de services en nuage journalisent légitimement les schémas d’accès à des fins de facturation, de débogage et d’optimisation des performances. Même sans intention malveillante, ces journaux créent un risque : un fournisseur de services en nuage compromis, un employé malveillant ou une assignation gouvernementale pourrait exposer des schémas d’accès sensibles.

La RAM oblivieuse (ORAM), introduite par Goldreich et Ostrovsky (1996), est une primitive cryptographique qui masque les schémas d’accès au serveur. Dans un schéma ORAM, chaque accès (lecture ou écriture) à n’importe quel emplacement mémoire génère la même distribution d’opérations visibles par le serveur, quel que soit l’emplacement réellement consulté. Un adversaire qui observe le serveur ne voit que des schémas d’accès uniformément aléatoires.

L’ORAM possède un large éventail d’applications partout où la confidentialité des schémas d’accès est nécessaire : stockage sécurisé en nuage (masquer les fichiers auxquels un utilisateur accède), requêtes oblivieuses sur des bases de données (masquer les lignes renvoyées par une requête), enclaves SGX (empêcher les canaux auxiliaires fondés sur les schémas d’accès à la mémoire de l’enclave), récupération privée d’informations (masquer l’entrée de la base de données récupérée par un utilisateur) et calcul multipartite sécurisé (masquer les schémas d’accès à l’état intermédiaire).

La solution ORAM la plus simple est évidente : pour accéder à un bloc, il faut lire et réécrire tous les blocs de l’ensemble du stockage. Cela masque le bloc consulté (chaque accès semble identique), mais entraîne un surcoût de communication de O(n) par accès logique, ce qui la rend totalement impraticable pour les grands ensembles de données. Les schémas ORAM réels cherchent à réduire ce surcoût à O(polylog n) tout en conservant une propriété d’obliviosité parfaite ou statistique.

Goldreich et Ostrovsky ont démontré une borne inférieure : tout ORAM dont le surcoût de stockage côté serveur est de O(1) doit subir un surcoût de communication d’au moins Omega(log n) par accès. Cette borne inférieure logarithmique s’applique aux ORAM déterministes. Les constructions pratiques visent un surcoût de O(log^2 n) ou de O(log n), proche de ce minimum théorique. Cette borne inférieure montre que le masquage parfait des schémas d’accès entraîne un coût inévitable.

Le chiffrement symétrique interrogeable (SSE) permet d’effectuer des recherches sur des données chiffrées. Les schémas SSE de base révèlent les schémas de recherche (les mots-clés recherchés) et les schémas d’accès (les documents renvoyés). Le SSE à confidentialité prospective masque le schéma de recherche pour les nouveaux documents, mais l’ORAM est également nécessaire pour masquer les documents auxquels on accède. La combinaison du SSE et de l’ORAM fournit la garantie de confidentialité la plus forte, mais au prix d’un coût important en performances.

L’ORAM n’est pas toujours nécessaire. La décision dépend du modèle de menace : l’adversaire observe-t-il les schémas d’accès ? Pour un stockage local avec chiffrement intégral du disque et un adversaire distant, l’ORAM peut ne pas être nécessaire. Pour un stockage en nuage dont le fournisseur n’est pas digne de confiance, l’ORAM est approprié. Le surcoût (généralement de 20 à 50 fois la bande passante) est justifié lorsque la fuite des schémas d’accès constitue une menace réelle et que la sensibilité des données justifie ce coût.

Le chiffrement du contenu des données ne masque pas les schémas d’accès, qui peuvent révéler des informations sensibles par l’analyse de fréquence et le minutage. Les fournisseurs de services en nuage des modèles honnêtes mais curieux observent les blocs de texte chiffré auxquels les clients accèdent. Les attaques CryptDB ont démontré qu’il était possible de déduire concrètement des informations à partir des schémas d’accès dans les bases de données chiffrées. L’ORAM résout ce problème en faisant en sorte que tous les accès semblent identiques au serveur. La solution triviale (tout lire à chaque accès) est impraticable en O(n) ; l’ORAM réelle atteint un surcoût de O(log^2 n).