# TP Sécu BD partie 2

Lechevalier Pierre-Marie, Pelissier Samuel

## Introduction :

L'objectif de ce TP est de nous permettre de découvrir quelles sont les procédés permettant de stocker et de manipuler de l'information de manière confidentielle et fiable sur un système qui ne l'est pas. Ce postulat implique que les utilisateurs ne fassent jamais passer par la base de données l'information sensible en clair. Afin néanmoins d'effectuer des opérations de comparaison et d'addition dessus nous utiliserons l'Order Preserving Encryption (OPE) de [Boldyreva](https://www.cc.gatech.edu/~aboldyre/papers/bclo.pdf) et le chiffrement additif homormorphe de [Paillier](https://link.springer.com/chapter/10.1007%2F3-540-48910-X_16). Ces deux primitives mathématiques permettent respectivement la préservation de la relation d'ordre sur des données chiffrées et l'addition sur des données chiffrées. Afin de ne pas avoir à implémenter nous même ces primitives nous baserons sur des versions publiques déjà codées, [pyope](https://pypi.org/project/pyope/) pour l'ORE et le [python-paillier](https://github.com/data61/python-paillier) de data-61. Data-61 est un organisme de recherche Australien qui a toute notre confiance car il est par ailleurs responsable du dépôt MP-SPDZ dont nous avons pu attester la qualité au cours de notre projet de vote anonyme décentralisé.

### Dépendances

Pour installer les dépendances nécessaires à l'exécution du code :

`pip -r requirements.txt`

TODO > finir de mettre en palce les dépendances

### 31 - Order preserving encryption

Pour la question 31, nous avons fait le choix d'utiliser une librairie effectuant de l'Order Preserving Encryption par opposition à l'Order Revealing Encryption. En se basant sur [cette définition](https://crypto.stanford.edu/ore/) de l'Université de Stanford, l'OPE serait la version initiale de l'ORE. L'inconvénient de l'OPE est qu'en plus de révéler l'ordonnancement des valeurs chiffrées, il présenterait des informations auxiliaires sur les plaintexts stockés. L'ORE, quant à lui, détiendrait des propriétés de sécurité supplémentaires et devrait notamment pouvoir fournir une preuve de sa sécurité face à des attaques à clair connu.

Nous avons fait le choix d'une librairie OPE avant de connaître la différence entre OPE et ORE. Dans la mesure où le but de l'exercice était de faire une preuve de concept (POC) d'une base de données chiffrée préservant la relation d'ordre sans pour autant préciser le degré de sécurité à atteindre, nous n'avons pas jugé nécessaire de le modifier.

Pour notre POC, la base de données utilisée sera la suivante :

CREATE TABLE `employee` (  
        `id` int NOT NULL AUTO_INCREMENT,   
        `name` varchar(100) NOT NULL,   
        `salary` int,   
        PRIMARY KEY (`id`) 
        ) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Le but sera d'appliquer l'OPE sur la colonne salaire qui est considérée comme confidentielle.

Comme précisé en introduction, notre choix d'implémentation d'OPE s'est arrêté sur pyope une [implémentation](https://pypi.org/project/pyope/) du mécanisme de chiffrement OPE symétrique de Boldyreva décrit dans [ce papier](https://www.cc.gatech.edu/~aboldyre/papers/bclo.pdf).

Le fonctionnement retenu est le suivant :

[TODO] schéma

Le script Q31.py est exécuté entièrement côté client, ce qui permet de ne transmettre ni l'information confidentielle ni le mot de passe utilisé pour le chiffrer. Au moment d'effectuer un *insert* dans la base de données, le client fait simplement appel à la fonction `encrypt` afin d'envoyer un salaire chiffré dans la base. Lors d'un *select* sur le salaire dans la base à l'inverse le client appelle la fonction `decrypt` afin d'obtenir le résultat en clair. L'opération lui est donc totalement transparente.

# Extraits du code concernant l'OPE
self.cypher = OPE(b'azerty123') # Initialisation de L'OPE
# fonctions d'insertions et selection dans la base de donnée
def insert_data(self, name, salary):
    query = "INSERT INTO employee (name, salary) VALUES (%s, %s);"
    #encrypt() -> appel à l'OPE
    cursor.execute(query, (name, self.cypher.encrypt(salary)))
    #[...] DB stuffs

def select_employee(self, name):
    query = f"SELECT * FROM employee WHERE name='{name}';"
    cursor.execute(query)
    for (id, name, salary) in cursor:
        #Decrypt() -> appel à l'OPE
        tmp_salary = self.cypher.decrypt(salary)

Une limite observée de ce système est qu'il est nécessaire que toutes les données aient été chiffrées avec le même mot de passe pour pouvoir être comparées. Avec des valeurs très proches et des mot de passes aléatoires, au bout de seulement quelques essais on fini par tomber sur des comparaisons incohérentes :
[screenshots]

Si l'on cherche à faire correspondre a une application pratique cette méthode de chiffrement, on peut imaginer l'utiliser dans un scenario d'externalisation du stockage des données pour une entreprise ou un organisme centralisé. On ne pourra pas en revanche l'utiliser pour la création d'une base de données recueillant les données de clients indépendants les uns des autres.

### 31 bis - Order preserving encryption && Additive homomorphic encryption

Toujours en partant du postulat que l'environnement dans lequel nous stockons nos données et effectuons nos calculs sur le serveur est compromis, nous allons cette fois-ci devoir implémenter un système d'addition tout en conservant la relation d'ordre mise en place précédemment. La primitive permettant d'effectuer des calculs sur du contenu chiffré est connue depuis longtemps ; il s'agit du chiffrement homorphe. Dans le cas où les calculs à effectuer sont réduits à une seule opération, la multiplication ou l'addition par exemple, on parle de chiffrement homomorphe partiel.

Dans le cadre de notre POC, nous nous intéresserons au chiffrement additif homomorphe seul. Celui-ci a été initialement mis en lumière par [un premier article](https://link.springer.com/chapter/10.1007%2F3-540-48910-X_16) de Pascal Paillier en 1999. Cet article a depuis été l'objet d'une attention considérable, ce qui a permis l'émergence de nombreuses améliorations et implémentations du crypto-système initial.

L'implémentation que nous avons retenu, [python-paillier](https://github.com/data61/python-paillier) par data-61, est l'une d'entre elles. Durant la mise en place pratique de cette question, nous avons fait le choix de rajouter une nouvelle colonne dans la base de données de la manière suivante :

CREATE TABLE `employee` (
`id` int NOT NULL AUTO_INCREMENT,
`name` varchar(100) NOT NULL,
`salaryOPE` int,
`salaryFHE` VARCHAR(3000),
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

Le but étant de stocker à la fois l'information permettant d'ordonner le salaire et celle offrant la fonction d'addition sur deux colonnes différentes puis de les mobiliser en fonction du besoin rencontré.

Cette architecture a été retenue après avoir cherché sans succès une primitive permettant de combiner pleinement les deux propriétés. Du point de vue du client, ce système est d'ailleurs [presque](#limites-de-ce-poc) totalement transparente puisque l'ensemble des opérations se font soit sur le serveur soit sur le middleware.

Le fonctionnement des middlewares est le suivant :

TODO schéma

Tout d'abord, un fichier *frontend.py* permet au client d'envoyer des requêtes logiques simples, à l'aide de fonctions haut niveau comme *add_employee*, ajoutant un employé à la base de données, ou *display_salary_avg* récupérant la somme des salaires pour en extraire la moyenne. Ce programme est donc exécuté sur la machine locale de l'utilisateur, sans jamais se connecter directement à la base.

Pour communiquer avec le fichier *backend.py*, une API [Flask](https://www.fullstackpython.com/flask.html) a été déployée. Celle-ci utilise un ensemble de routes appelant ensuite des fonctions interrogeant la base de données. De fait, les différents calculs (comparaison, addition) sont bien effectués du côté serveur. Certaines des routes appelables sont illustrés sur les schémas ci-dessus, `/employee/add` pour l'ajout d'un nouvel utilisateur, `/salaries/compare` pour comparer le salaire de deux utilisateurs. Dans ces deux routes le middleware se contente de transmettre et éventuellement de formatter les requêtes. Ce type de comportement ne nécessite pas forcément un middleware. Pour la troisième routes illustrée, `/salaries/sum/`, en revanche la présence du middleware permet au client d'éviter d'avoir à effectuer le caclcul de l'addition homomorphe. Une fois que le middleware lui renvoie le résultat de l'addition le client n'a plus qu'a déchiffrer le résultat à l'aide de sa clé privé. Le middleware permet donc :
1. D'éviter une partie des calculs
2. D'abstraire le fonctionnement interne de la base de donnée (nottament de la séparation OPE/ PHE) en offrant à l'utilisateur une vue fonctionnelle.

En terme de chiffrement, l'utilisateur final définit une clef symétrique pour l'OPE et un couple de clefs publique/privée pour le chiffrement homomorphe. Si le premier fonctionnement permet un simple ajout de la valeur directement dans la base, le second requiert le transfert de plusieurs paramètres. Ainsi, afin de pouvoir réutiliser un objet de la librairie implémentant le crypto-système de Paillier du côté serveur, la clef publique et l'exposant doivent être transféré en plus du chiffré.

De fait, il est possible pour n'importe quel utilisateur de la base d'effectuer une comparaison sur les données liées à l'OPE. Une addition sur les chiffrés peut aussi être réalisée mais sont résultat ne pourra être déchiffré que par l'utilisateur ayant généré le couple de clefs publique/privée.

#### Limites de cette POC

Il est cependant bon de garder à l'esprit que cette abstraction n'est pas exempte de tout défaut. Il n'est par exemple pas possible de créer un nouvel utilisateur dont le salaire serait la somme de deux autres utilisateurs. Il serait possible de remplir sa colonne `salaryFHE` mais pas celle `salaryOPE` correctement. D'un point de vue utilisateur, ce genre de comportements qui n'ont pas de justification apparente peuvent passer pour une anomalie.

## 32 Attaque sur l'ORE

Les chiffrements présérvant ou même révélant la relation d'ordre laisse par défition transparaitre des informations sur l'ordancement de leur données. Cette fuite d'information rend possible certaines attaques permettant de déterminer le contenu d'une base simplement en observant les requêtes qui y entre et celles qui en sortent.
Dans le cas d'un chiffrement présérvant l'ordre (OPE), et a condition de connaitre la répartition global des valeures (ce qui est assez réaliste dans le cas d'une base stockant des salaires par ex), il a été montré qu'il est possible de reconstruire entièrement le contenu de la base considérée.

Ces attaques nécessitent que l'adversaire puisse observer un grand nombre de requête sur la base mais ce type de scénario est tout à fait envisageable

# Conclusion

Dans ce projet, nous avons pu dans un premier temps découvrir l'OPE et l'ORE et mettre en place une preuve de concept de ces technologies. Dans un second temps, nous avons pu combiner au sein d'un middleware l'OPE et le chiffrement homomorphe additif que nous connaissions déjà au moins d'un point de vue théorique. Nous avons enfin pu dans un troisième temps éprouver les limites inhérentes aux systèmes de chiffrement préservant les relations d'ordre.

Dans la réalisation de ce TP, nous avons passé un temps que nous pensons être trop important pour la recherche d'une solution inexistante. Nous avons finalement pu trouver la solution exposée dans ce compte-rendu grâce aux réponses fournies par l'enseignants. Nous pensons cependant qu'un sujet mieux cadré sur la partie 31 bis aurait permis de réduire ce temps de recherches infuctueuses.