Vous êtes sur le site public du Cert-IST
Faille dans le chiffrement CFB d'OpenPGP

Date :15 Avril 2005

Publication: Article

Plusieurs éditeurs (SuSE, Mandrake, ...) ont sorti ce mois-ci des correctifs pour leurs implémentations du protocole de chiffrement "OpenPGP". Ces correctifs concernent une faille divulguée au mois de février, pour laquelle le Cert-IST n'a pas jugé utile de publier d'avis (car sa mise en oeuvre est complexe pour un résultat très limité). Cette faille permet, dans certaines circonstances, de décoder partiellement un message intercepté. Elle est détaillée dans cet article.

OpenPGP et le mode CFB ("Cipher-FeedBack")

Le protocole de chiffrement de message OpenPGP, implémenté dans plusieurs applications comme PGP, GnuPG, Hushmail, est décrit dans la RFC 2440. Il utilise une variante du mode CFB pour crypter les données.

    Le mode CFB standard

Le mode CFB standard est décrit dans le document ANSI X9.52.
Pour chiffrer un message M, il le découpe en blocs de 8 ou 16 octets : M1, M2, ... Mi, ... Mn.
Puis il utilise un bloc aléatoire V pour calculer n blocs chiffrés C1 à Cn depuis les blocs M1 à Mn, de la manière suivante :

    C1 = Ek(V) + M1
    C2 = Ek(C1) + M2
    .............................
    Cn = Ek(Cn-1) + Mn

    (où Ek() représente le chiffrement avec la clé K, et '+' représente un 'ou exclusif')

Enfin il construit le message chiffré par concaténation des n blocs C1 à Cn.

    La variante utilisée par OpenPGP

OpenPGP utilise une variante du mode CFB standard, pour savoir si la clé utilisée lors du déchiffrement d'un message est correcte après avoir déchiffré les deux premiers blocs de ce message. Cette technique appelée "quick check" est particulièrement appréciable dans le cas de traitement de messages volumineux.
C'est l'implémentation de cette technique qui comporte la vulnérabilité décrite dans ce présent article.

Cette implémentation consiste à chiffrer un premier bloc aléatoire B, puis un second comprenant les deux derniers octets de B, puis à enchaîner sur le cryptage des blocs du message. Après déchiffrage des deux premiers blocs, il suffit de contrôler de le second bloc correspond au deux derniers octets du premier bloc pour s'assurer que la clé est correcte.

Le principe de l'attaque

L'attaque permet à une personne malveillante qui intercepte une message codé avec OpenPGP, de décoder une partie (les 2 premiers octets de chaque bloc) de ce message.
Ce paragraphe ne présente pas les calculs effectués, ceux-ci sont détaillés dans l'article de Serge Mister et Bobert Zuccherato (voir l'url à la fin de cet article).

L'attaque n'est réalisable que si les pré-requis suivants sont vérifiés :

  1. l'attaquant doit pouvoir soumettre un message chiffré à une entité (appelée "oracle") qui lui indique si le contrôle "quick check" sur le message est positif.
  2. l'attaquant doit connaître les deux premiers octets du message qu'il veut décrypter (leurs valeurs "en clair").
    Remarque : le protocole OpenPGP accomplit plusieurs traitements sur le message avant de le chiffrer. Aussi les premiers octets du message en clair correspondent à des informations (tag, longueur du message) dont l'attaquant peut facilement deviner la valeur parmi une petite quantité de possibilités

Le principe d'attaque est alors le suivant :

  • Dans un premier temps l'attaquant cherche à trouver les deux derniers octets du bloc aléatoire B qui servent au contrôle "quick check". Appelons les X.
    Pour cela l'attaquant construit une version du message chiffré dont il modifie les deux premiers blocs C1 et C2 :
    • Le premier bloc C1 est calculé de façon à ce qu'il permette de déduire X, en connaissant les deux premiers octets du message en clair (cet aspect est complexe et n'est pas détaillé ici)
    • Le bloc, C2 lui va être déterminé expérimentalement comme décrit ci-dessous.
      L'attaquant présente tout d'abord à l'oracle un premier message modifié avec C2 = "0000". Si l'oracle répond que le "quick check" est négatif, alors l'attaquant incrémente C2 et présente le nouveau message à l'oracle. L'attaque se poursuit jusqu'à ce que l'oracle réponde que  le "quick check" est positif pour le message présenté. Sur cette base, l'attaquant peut alors calculer X.
      Remarque : l'attaquant doit présenter en moyenne 32768 requêtes à l'oracle avant de pouvoir trouver la valeur de C2 lui permettant de calculer X.
  • Lorsqu'il a trouvé la valeur des octets X l'attaquant peut utiliser une méthode similaire pour retrouver les deux premiers octets de chaque bloc du message en clair.
    Remarque : pour chaque bloc l'attaquant doit présenter en moyenne 32768 requêtes à l'oracle avant de pouvoir calculer les deux premiers octets de ce bloc.

Discussion de l'attaque

Cette attaque nécessite en moyenne, pour un message crypté de n blocs, (n-1)*32768 requêtes à l'oracle.
Outre une mise en oeuvre lourde, nécessitant du temps (2h par bloc avec un Pentium à 1,8GHz), cette contrainte interdit l'utilisation d'un oracle humain.
L'oracle doit donc être une machine "hypothétique" qui par le type de message d'erreur retourné, ou son temps de réponse permet de connaître le résultat du "quick check".

Cette attaque ne permet de décrypter que les deux premiers octets de chaque bloc, soit 25% du message dans le cas de blocs de 8 octets ou 12,5% dans la cas de blocs de 16 octets.
Or dans la plupart des cas le texte chiffré a préalablement été compressé, et l'obtention de 25 ou 12,5% d'un texte compressé n'est pas un résultat exploitable.

Les deux parades possibles pour cette attaque :

  • de ne pas utiliser le contrôle "quick check" (avec l'inconvénient d'avoir à déchiffrer complètement un message pour savoir si sa clé est correcte),
  • de compresser systématiquement les messages avant de les chiffrer (car le résultat de l'attaque n'est alors pas exploitable, cf. ci-dessus).

Conclusion

Cette attaque constitue pour nous une faille théorique difficile à mettre en oeuvre ("oracle hypothétique") et facilement contournable en compressant les données avant de les chiffrer (ce qui est déjà fait dans la majorité des implémentations d'OpenPGP).
Ces conclusions ont amené le Cert-IST à présenter ce problème dans cet article plutôt que dans un avis de sécurité.

Toutefois le groupe de travail d'OpenPGP soucieux de la crédibilité de leurs protocoles de chiffrement envisage de faire évoluer celui-ci afin de mettre en oeuvre un "quick check" sécurisé.

Pour plus d'information :