TP2 RSA déterministe et oblivious transfert

Ce TP consiste en une attaque sur l’implémentation naïve déterministe du crypto-système RSA et d’une application du crypto-système de Pailler à un protocole de communication anonyme appelé transfert inconscient (oblivious transfert 🇬🇧). Le sujet reprend les exercices 82 et 89 du livret de cours.

⚠️ Vous avez jusqu’au mardi 16 avril 13:59 pour déposer une archive avec les deux exercices complétés sur Tomuss dans la case Depot-TP2. ⚠️

Exercice 1 : recherche exhaustive sur RSA déterministe

Une voyante australienne réputée prétend avoir deviné les six numéros gagnants (compris entre 1 et 49) du prochain tirage du loto. Pour des raisons que nous n’expliciterons pas ici, elle souhaite vous en faire profiter (et seulement vous). Étant d’un naturel peu partageur, vous souhaitez sécuriser la communication. Pour ceci, vous décidez d’utiliser le cryptosystème RSA en transmettant à cette voyante une clé publique \((n, e)\) de taille 2048 bits.

  1. Sans consigne de votre part, la voyante vous envoie un chiffrement séparé pour chacun des six numéros. Expliquez pourquoi cette façon de procéder n’est pas sécurisée.
  2. Afin de pallier la faille précédente, vous suggérez à la voyante de vous envoyer un chiffrement de la concaténation \(\mathrm{mc}\) de ces 6 numéros \(x_1, \ldots , x_6\), i.e., \(\mathrm{mc} = x_1 \parallel x_2 \parallel x_3 \parallel x_4 \parallel x_5 \parallel x_6\) (en utilisant un nombre de caractères fixes pour les numéros). Par exemple si \(x_1 = 33\), \(x_2 = 12\), \(x_3 = 24\), \(x_4 = 04\), \(x_5 = 08\), \(x_6 = 13\) alors \(\mathrm{mc} = 331224040813\). En considérant qu’un attaquant écoutant le réseau dispose de ressources lui permettant d’effectuer une exponentiation modulaire \(x^e \mod n\) en une milliseconde pour tout \(x \in \mathbb{Z}_n\), estimez le temps nécessaire (en moyenne) à l’attaquant pour retrouver les six numéros par force brute. Est-ce exploitable ?
  3. Même question que la précédente en supposant que la voyante classe les numéros par ordre croissant, i.e., \(x_1 < x_2 < \ldots < x_6\). Implémenter cette attaque en explorant l’espace des tirages possibles.
  4. Revenons à la question 2. Dans l’euphorie, vous avez malencontreusement choisi \(e = 17\). Pourquoi un tel choix n’est-il pas judicieux par rapport à la taille des nombres en question ? Proposer une attaque quasi instantanée permettant à l’attaquant de retrouver les six numéros. Implémenter cette attaque.
  5. Imaginez des modifications légères au chiffrement RSA pour rendre les attaques précédents impraticables. Ce sera le sujet du prochain cours !

On utilisera le fichier de départ rsa_deterministe.py qui utilise classe TextbookRSACipher de référence du fichier TextbookRSACipher.py fourni. On donne le code qui génère des tirages du loto de taille arbitraires. Expliquer le fonctionnement de bingo_generator() et l’intérêt de count_all_bingos().

💡 Utilisez des valeurs plus petites pour BINGO_SIZE et MAX_BINGO en développement. 💡

Exercice 2 : transfert inconscient

Imaginons deux questions publiques \(Q_0\) et \(Q_1\). Alice a deux réponses secrètes \(r_0\) et \(r_1\). Bob est intéressé par la réponse \(Q_i\) avec \(i \in \{0, 1\}\) mais ne souhaite pas divulguer cette information à Alice (\(i\) est secret).

Peut-on construire un protocole de Transfert Inconscient (TI) qui garantit que \(i\) reste secret pour Alice, que \(r_{1−i}\) reste secret pour Bob et que Bob connait \(r_i\) à la fin du protocole. Autrement dit, Bob peut-il obtenir une réponse à une question qu’il souhaite garder secrète ? Nous proposons le protocole ci-après à compléter.

  1. Compléter le protocole TI en définissant \(R_i\) afin qu’il soit correct.
  2. Analyser la sécurité de ce protocole, c’est-à-dire démontrer que les secrets sont préservés.
  3. Implémenter le protocole TI. On prendra le fichier de départ oblivious.py où on suppose disposer d’un module Python MonImplementationDePailler issu du TP1.
  4. Étendre ce protocole à un nombre quelconque de questions. C’est très simple si vous avez compris le cas binaire. Mettre à jour oblivious.py en conséquence.
  5. Ce protocole peut être vu comme un protocole (inefficace) permettant de faire des requêtes sur une BD distante. L’expliquer. Que garantit-il ?

Protocole de Transfert Inconscient (TI)

  1. Bob génère \((pk, sk) \leftarrow \mathrm{Paillier.KeyGen}(\lambda)\), publie \(pk\) et envoie \(I \leftarrow \mathrm{Paillier.Encrypt}(pk, i)\) à Alice.
  2. Alice génère deux nombres aléatoires \(\alpha_0, \alpha_1 \in \mathbb{Z}_n^*\) et \(A_0 \leftarrow \mathrm{Paillier.Encrypt}(pk, 0)\) et \(A_1 \leftarrow \mathrm{Paillier.Encrypt}(pk, -1)\). Alice génère ensuite \(M_0 = \alpha_0 \circ (I \oplus A_0)\) et \(M_1 = \alpha_1 \circ (I \oplus A_1)\) ainsi que \(R_0 = \ldots\) (à définir) et \(R_1 = \ldots\) (à définir) et envoie \(R_0\), \(R_1\) à Bob.
  3. Bob calcule enfin \(r_i \leftarrow \mathrm{Paillier.Decrypt}(pk, R_i)\).

Les fonctions oblivious_transfert_query(), oblivious_transfert_response() et oblivious_transfert_check() du fichier oblivious.py correspondent aux trois étapes du protocole. Les fonctions outils int_to_str() et str_to_int() de conversion vous permettront d’échanger des chaînes et non des entiers, pour un peu plus de réalisme et de praticité.