Fully Homomorphic RSA : quand l’algèbre devient une surface d’attaque

Cette note propose une lecture théorique du challenge Fully Homomorphic RSA, classé en cryptographie sur Hackropole. Ce n’est pas une solution officielle ni une copie de write-up : l’objectif est de comprendre le mécanisme intellectuel que ce type d’épreuve cherche à faire manipuler.

L’idée en une image

Un chiffrement malléable ressemble à une boîte fermée dont on peut pourtant tourner les engrenages. On ne voit pas le message, mais on peut fabriquer un nouveau chiffré dont on connaît la relation avec l’ancien.

Le niveau « hardcore » ne vient généralement pas d’une formule isolée. Il vient de la nécessité de reconnaître quelle structure est exposée, puis d’écarter tout ce qui n’influence pas réellement le secret.

Le modèle mathématique

Pour RSA brut, E(m)=m^e mod n et E(m1)·E(m2)=E(m1·m2) mod n. Cette propriété n’est pas une magie homomorphe complète : c’est une structure multiplicative, souvent dangereuse lorsqu’un protocole l’expose sans padding ni contrôle.

La première discipline consiste à écrire les objets avec leur domaine : entiers, classes modulo un nombre, vecteurs sur un corps fini ou octets. Une grande partie des bugs de raisonnement vient d’une opération effectuée dans le mauvais espace.

Ce qu’il faut repérer

• Un service transforme ou combine des chiffrés fournis par l’utilisateur
• La validité d’un résultat est observable, même sous forme d’un simple bit
• Le protocole confond confidentialité du chiffré et intégrité de la requête

Ces indices ne prouvent pas encore une attaque. Ils servent à former une hypothèse testable : « si ce modèle est le bon, quelle valeur intermédiaire devrais-je pouvoir prédire ? »

Démarche d’analyse

1. Écrire les opérations autorisées comme des équations modulo n.
2. Chercher ce qui reste invariant après multiplication ou exponentiation.
3. Construire des relations connues avant de chercher la clé privée.
4. Distinguer attaque sur RSA et attaque sur le protocole autour de RSA.

À chaque étape, conserver un petit test connu. Un script qui produit un résultat plausible mais non vérifié est plus dangereux qu’une équation incomplète : il donne l’impression d’avancer.

Pourquoi le challenge devient difficile

Une épreuve avancée superpose souvent plusieurs couches : parsing, encodage, protocole et primitive. La bonne stratégie consiste à construire des invariants. Une taille doit rester constante, un point doit satisfaire son équation, une signature doit se vérifier, un état prédit doit reproduire plusieurs sorties jamais utilisées pendant l’analyse.

On peut formaliser ce réflexe ainsi :

1. Observer une relation stable.
2. Modéliser cette relation avec le moins d’hypothèses possible.
3. Prédire une nouvelle valeur.
4. Valider la prédiction sur des données indépendantes.

Fausses pistes classiques

• Tenter immédiatement de factoriser n.
• Supposer que « chiffré » signifie « authentifié ».
• Utiliser des nombres flottants pour les calculs modulaires.

La difficulté utile d’un challenge n’est pas de lancer tous les outils disponibles. Elle est de savoir quelle propriété chaque outil teste et ce qu’un échec permet réellement de conclure.

Ce que l’architecte sécurité doit en retenir

Un chiffrement sûr dans un protocole doit intégrer un schéma de padding éprouvé, une authentification et des réponses non révélatrices.

La crypto échoue rarement parce que l’algorithme central est totalement inconnu. Elle échoue aux frontières : génération d’aléa, réutilisation d’état, encodage, validation, gestion des erreurs et composition avec le protocole.

Pour aller plus loin

Reprendre le challenge en construisant d’abord un modèle miniature avec de petits paramètres. Une fois l’intuition vérifiée, remplacer progressivement les jouets par les vraies tailles. C’est plus lent pendant dix minutes et beaucoup plus rapide pendant les trois heures suivantes.