Circuit ORAM et performances pratiques

L’ORAM en circuit, proposée par Wang, Chan et Shi (2015), a été conçue pour réduire au minimum le surcoût de bande passante tout en restant simple à implémenter dans les cadres de calcul sécurisé (circuits brouillés et partage de secrets). Son innovation principale consiste à réduire la taille des compartiments à Z = 2 blocs (contre Z = 5 pour l’ORAM par chemin), divisant ainsi la bande passante par deux tout en conservant une probabilité d’échec négligeable. La procédure d’éviction a été repensée pour pouvoir s’exprimer sous la forme d’un petit circuit booléen.

Dans l’ORAM par chemin avec Z = 5, la probabilité de débordement de la réserve est maîtrisée en plaçant plusieurs blocs par compartiment afin de prendre en charge l’attribution aléatoire des blocs aux chemins. L’ORAM en circuit démontre que Z = 2 suffit lorsqu’une procédure d’éviction déterministe (éviction en profondeur d’abord) est utilisée plutôt qu’une éviction aléatoire. Cela divise par deux le stockage du serveur et le surcoût de communication par rapport à l’ORAM par chemin avec les mêmes paramètres de sécurité.

L’ORAM en circuit a été spécifiquement conçue pour disposer d’une procédure d’éviction pouvant être exprimée sous la forme d’un circuit booléen efficace. Dans les protocoles de calcul sécurisé (circuits brouillés, SPDZ), l’accès à l’ORAM lui-même doit être évalué de façon oblivieuse : le serveur qui effectue le calcul ne doit pas apprendre quel emplacement mémoire est consulté. Le circuit d’éviction déterministe et simple de l’ORAM en circuit est bien plus efficace à transformer en circuit brouillé que la procédure d’éviction de l’ORAM par chemin.

Pour une base de données de N blocs de taille B octets, l’ORAM en circuit nécessite 2 * log N * B octets par accès (lecture et écriture d’un chemin avec Z = 2 blocs par compartiment). Pour N = 2^20 blocs de 4 Ko chacun, cela représente 160 Ko par accès, contre 400 Ko pour l’ORAM par chemin (Z=5). Le surcoût de bande passante par rapport au texte en clair est d’environ 40 fois pour les paramètres courants, contre 100 fois pour l’ORAM par chemin.

Oblix (Misra, Schlegel, Sherwood, Tsudik, 2018) utilise l’ORAM en circuit pour créer des versions oblivieuses de structures de données de haut niveau : listes chaînées oblivieuses, dictionnaires oblivieux (tables de hachage) et files de priorité oblivieuses. Ces structures permettent d’effectuer des calculs oblivieux sur des données dynamiques sans révéler les schémas d’accès. Oblix s’exécute dans des enclaves Intel SGX et vise l’intersection privée d’ensembles ainsi que les requêtes privées sur des bases de données.

TaoStore (Sahin, Zhu, Gunter, Borisov, 2016) étend Path ORAM pour prendre en charge des accès asynchrones à haut débit en traitant plusieurs requêtes ORAM en parallèle et en regroupant par lots les évictions de chemins. En combinant les accès au même chemin, TaoStore atteint un débit (requêtes par seconde) nettement supérieur à celui des constructions ORAM synchrones, ce qui le rend adapté aux serveurs de stockage en nuage accueillant de nombreux clients simultanés.

Obladi (Crooks, Park, Alvisi, Iyengar, 2018) met en place un système complet de stockage transactionnel reposant sur Path ORAM. Obladi prend en charge les transactions ACID sur un stockage chiffré qui dissimule les schémas d’accès. Il introduit l’exécution différée : les transactions sont regroupées en époques, puis exécutées de manière à dissimuler les enregistrements précis auxquels on a accédé pendant chaque époque. Obladi s’exécute comme un mandataire de confiance entre les clients et un système de stockage en nuage non fiable.

Pour un ORAM de 1GB (262,144 blocs de 4KB) déployé sur AWS, avec un client accédant aux blocs par Internet, la latence de Path ORAM est d’environ 50-200ms par accès (principalement en raison du temps aller-retour nécessaire aux accès aux compartiments, pour lesquels log N = 18). Des récupérations parallèles des compartiments permettent de réduire cette latence. Pour les applications SGX locales utilisant ORAM en RAM, la latence se situe entre 1 et 10ms par accès, ce qui convient à de nombreuses applications de calcul sécurisé.

Le surcoût de bande passante d’ORAM dépend fortement des schémas d’accès. Pour un ORAM de stockage en nuage de 1TB avec des blocs de 1MB, chaque accès transfère environ 25MB (surcoût de 25x pour les 25 niveaux, avec log N = 25). Pour les petits blocs de 4KB, le surcoût par accès est moindre en nombre absolu d’octets, mais plus élevé en termes relatifs. Les organisations qui déploient ORAM doivent prévoir une amplification de la bande passante de 20-50x et s’assurer que leurs liaisons réseau et leurs coûts de sortie du nuage en tiennent compte.

Une solution de remplacement d’ORAM pour assurer la confidentialité des accès est le matériel de confiance : Intel SGX ou AMD SEV fournit un environnement d’exécution de confiance dans lequel même le système d’exploitation hôte ne peut pas observer le calcul ni les schémas d’accès à la mémoire, avec des défenses appropriées. SGX sans ORAM laisse néanmoins fuiter vers le matériel les schémas d’accès au niveau des pages ; ORAM au sein de SGX est donc nécessaire pour assurer une protection complète. Par rapport à un ORAM seul, le matériel de confiance réduit le surcoût de bande passante, mais exige de faire confiance au fabricant du matériel et à la chaîne d’approvisionnement.

ORAM est approprié lorsque l’adversaire observe les schémas d’accès côté serveur (fournisseur de services en nuage, colocataire), que la sensibilité des données justifie un surcoût de bande passante de 20-50x et que le schéma d’accès lui-même révélerait des informations sensibles. Pour la plupart des applications, un chiffrement standard associé à une gestion rigoureuse des clés suffit. ORAM est un outil spécialisé pour les scénarios exigeant un haut niveau de sécurité : analyse de données médicales, apprentissage automatique privé, systèmes de négociation financière et bases de données des forces de l’ordre.

Circuit ORAM réduit la taille des compartiments à Z=2 (contre Z=5 pour Path ORAM), divisant par deux la bande passante grâce à une éviction déterministe en profondeur d’abord. Il est conçu pour être utilisé au sein d’un calcul sécurisé par circuit brouillé. Le surcoût pratique est une amplification de la bande passante de 40x pour les paramètres courants. Les systèmes de production comprennent Oblix (SGX et structures de données à accès dissimulé), TaoStore (ORAM à haut débit avec traitement par lots) et Obladi (ORAM transactionnel). ORAM au sein de SGX est nécessaire, car SGX seul laisse fuir les schémas d’accès au niveau des pages.