Cryptosystème ElGamal

Conçu à partir de l'échange de clé Diffie-Hellman, le chiffrement ElGamal est une alternative libre de droit au standard RSA et qui propose, bonus, une implémentation sur courbes elliptiques.

Pour continuer notre périple en cryptographie, je vous propose d'aborder aujourd'hui le Cryptosystème de ElGamal.

sik-life @ pixabay
sik-life @ pixabay

Présenté en août 1984 par Taher Elgamal, d'où l'algorithme tiens son nom, il propose un protocole de chiffrement asymétrique construit à partir de l'Échange de clés Diffie-Hellman (Publié 8 ans plus tôt).

A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, ElGamal T. Lecture Notes in Computer Science, vol 196. (PDF).

Techniquement, il ne s’agit que d’une adaptation de Diffie Hellman où les participants se sont réparti les étapes. On ne l’utilise pas beaucoup mais comme il est compatible avec les courbes elliptiques, il est plutôt intéressant à connaître.

Principe

Diffie Hellman

Le plus simple pour comprendre ElGamal, c'est encore de partir de l'échange de clé Diffie-Hellman. Pour rappel, voici les étapes du protocole :

Schéma de Diffie Hellman
Schéma de Diffie Hellman
  1. Alice et Bob se mettent d'accord publiquement sur un groupe \((G, \times)\) et un générateur \(g\) ;
  2. Ils choisissent chacun un nombre aléatoire (leur clé secrète), \(a\) pour Alice et \(b\) pour Bob, ;
  3. Ils calculent leur partie publique et se l'envoie l'un l'autre ; Alice envoie donc \(g^a\) à Bob et reçoit \(g^b\) en retour ;
  4. Ils calculent enfin le secret partagé ; Alice calcule \(g^{b^a}\) et Bob calcule \(g^{a^b}\).
  5. Ils peuvent ensuite utiliser ce secret partagé pour sécuriser leurs communications suivantes.

ElGamal

Pour Elgamal, le protocole est le même mais comme seule Alice a besoin d'écrire à Bob, ils peuvent se répartir le protocole et prendre des initiatives.

Pour permettre à tout un chacun de lui envoyer des mots gentils, Bob se charge de la première moitié du protocole :

Bob prend l’initiative
Bob prend l’initiative

Les informations publiques (groupe, générateur et \(g^b\)) constituent la clé publique et peuvent être envoyées à l'avance à Alice ou carrément publiées sur un annuaire.

Pour envoyer un message à Bob, Alice récupère ces informations publiques et se charge de la seconde moitié du protocole :

Alice s’occupe de la suite
Alice s’occupe de la suite

Alice peut alors se servir du secret partagé (enfin, il le sera ensuite) pour chiffrer son message. Dans l'article original d'Elgamal, cette opération s'effectue dans un groupe fini additif ou multiplicatif, l'important étant qu'elle soit facilement inversible. C'est habituellement une multiplication qui est choisie.

Le secret sert de clé
Le secret sert de clé

Elle n'a plus qu'à envoyer sa partie publique et le message chiffré à Bob qui pourra le déchiffrer :

Bob calcul le secret et déchiffre
Bob calcul le secret et déchiffre

En vrai, système hybride

L'opération de chiffrement et déchiffrement est possible sur des messages arbitrairement longs mais cette opération reste plus lente que les algorithmes de chiffrement symétriques ayant une sécurité équivalente.

On aurait pu remplacer la multiplication par un algorithme symétrique, le secret partagé étant alors la clé de cet algorithme, mais l'usage en a choisi autrement (et a bien fait).

Porsche 918 (hybride), Markus_KF @ pixabay
Porsche 918 (hybride), Markus_KF @ pixabay

En effet, on préfère utiliser l'algorithme d'Elgamal, inchangé, conjointement à un algorithme symétrique. On parle alors d'algorithme hybdide. On choisi alors une clé pour chiffrer le message et c'est cette clé qui sera chiffrée avec Elgamal.

L'avantage de cette méthode, est de découpler l'algorithme asymétrique qui établi la communication (Elgamal, RSA, ...), et l'algorithme symétrique qui sécurise le contenu (AES, 3DES, ...). Il est alors possible de choisir la combinaison la plus adaptée ou de faire évoluer une partie en fonction des dernières avancées.

C'est ce qui est fait au travers des cypher suites de TLS et qui a encore été renforcé dans la version 1.3 du protocole (RFC8446).

Sécurité spécifique

Comme tous les algorithmes, ElGamal a aussi ses petits problèmes spécifiques.

Nonce Re-use

Lorsqu'Alice veut envoyer un message à Bob, elle doit générer un nombre aléatoire secret \(a\) spécifique pour le message à envoyer.

Elle pourrait bien sûr réutiliser la clé précédente, voir utiliser sa clé secrète mais ce faisant, elle mettrait en péril la sécurité de tous ses échanges.

En effet, admettons qu'Alice envoie deux messages \(m_1\) et \(m_2\) à Bob en utilisant le même nombre aléatoire \(a\). Bob n'ayant pas changé sa clé publique, le secret partagé (\(K = g^{b^a}\)) sera le même pour le chiffrement des deux messages :

\[ \begin{align} m_1' & = m_1 . K \\ m_2' & = m_2 . K \end{align}\]

Admettons maintenant qu'une attaquante (Eve) ai mis la main sur un message en clair... (prenons \(m_1\)). Le problème, c’est qu’ainsi, elle pourra s’en servir pour déchiffrer tous les autres messages entre Alice et Bob.

\[ \begin{align} m_1' / m_2' & = (m_1 . K) / (m_2 . K) \\ m_2 & = m_1 . m_2' / m_1' \end{align}\]

Ce qui peut arriver plus souvent qu'on le croit... L'attaque Krack sur le WPA2 suit cette même logique (même si le chiffrement utilisé est différent). Forcer les clients WIFI à utiliser un nonce plusieurs fois puis, grâce à la connaissance (partielle) d'un message clair, déchiffrer les autres.

Notez que dans ce cas, Eve peut aussi retrouver le secret partagé \(K\) :

\[ \begin{align} K & = m' / m \end{align}\]

Heureusement, même en possession des parties publiques et du secret partagé, obtenir les clés privées reste difficile puisqu'il s'agit de résoudre le problème du logarithme discret.

En fait, il s'agit de résoudre le problème de Diffie-Hellman qui en l'état actuel de nos connaissance est aussi difficile que celui du logarithme discret.

Attaque sur le chiffré

Tel que défini et utilisé, ce chiffrement possède la propriété de malléabilité : il est possible, dans un certaine mesure, de modifier le message clair en n'opérant que sur le chiffré.

Précisément, l'opération de chiffrement étant une multiplication, multiplier le chiffré par une constante a le même effet que si la multiplication avait eu lieu sur le clair :

\[ \begin{align} n . m' & = n . m . K = (n . m)' \end{align}\]

Si Elgamal est utilisé pour chiffrer un message, et que Eve à la possibilité d'intercepter les communication, elle peut alors modifier le contenu même des messages et en fonction des contextes, en changer le sens à son avantage.

Pour éviter ce type d'attaque, on peut soit ajouter un système de signature au messages ou le gérer directement dans le protocole comme c'est le cas avec Cramer-Shoup.

Si El Gamal est utilisé pour chiffrer une clé symétrique, cette faiblesse n’est plus très pertinente puisque changer la clé symétrique rendra le message illisible, ce que Eve aurait tout aussi bien pu obtenir en remplaçant le message par des données aléatoires.

Enfin, il faut noter que cette propriété n'est pas spécifique à El Gamal mais touche aussi d'autres protocoles comme RSA ou dans une moindre mesure le mode CBC.

Et après ?

Au moment de sa publication, RSA était couvert par un brevet (brevet US4405829A, valable uniquement aux US car déposé après une publication) et la communauté a été bien contente d'accueillir un nouvel algorithme libre de droits. GnuPG, le clone libre de PGP implémente donc ce cryptosystème pour les échanges de messages.

Par contre, El Gamal ne propose pas nativement de méthode de signature. Il n'est donc pas utilisable pour certaines applications comme SSL/TLS pour lesquels RSA garde l'avantages, surtout depuis l'expiration du brevet en septembre 2000.

D’un autre côté, comme on peut implémenter Elgamal sur n'importe quel groupe fini, une version sur courbes elliptique a pu voir le jours (i.e. implémentée dans GnuPG) et propose, à taille de clé équivalente, une sécurité largement supérieure.

Pour terminer, voici les recommandations de l'ANSSI (via son Référentiel Général de Sécurité) en matière de longueur de clés pour les chiffrements asymétriques :

En vrai, on utilise rarement ElGamal, mais sa filiation avec Diffie-Hellman le rend facilement compréhensible et lui permet une implémentation via courbes elliptiques, plutôt à la mode et bien pratique.