L'attaque de Bleichenbacher : un oracle de padding contre RSA PKCS#1 v1.5

L’attaque de Bleichenbacher : un oracle de padding contre RSA PKCS#1 v1.5

Daniel Bleichenbacher a publié en 1998 une attaque qui n’a jamais vraiment cessé de resurgir. Elle ne casse pas RSA (Rivest–Shamir–Adleman), ne factorise aucun module et n’extrait aucune clé privée. Elle se contente d’une chose : poser au serveur, quelques dizaines de milliers de fois, une question à laquelle il ne devrait jamais répondre — « ce que je viens de t’envoyer avait-il un remplissage correct ? ». Chaque réponse retire un peu d’incertitude sur le message d’origine. Au bout du compte, l’attaquant lit le texte clair sans avoir jamais possédé la clé qui le protégeait.

Cette page monte l’ouvrage avant de le rompre : un petit service de déchiffrement RSA PKCS#1 v1.5 (Public-Key Cryptography Standards n° 1, version 1.5), écrit proprement, sur des clés de laboratoire générées pour l’occasion. Puis on l’attaque, on mesure, et on regarde ce que la brèche dit du modèle mental qui avait présidé à sa construction.

Explication du castor

Un castor ne casse jamais un barrage qu'il n'a pas bâti. La démonstration qui suit se fait donc en trois temps : on construit un service de déchiffrement complet et honnête, on casse ce qu'on vient d'élever, on en tire la leçon sur ce que la brèche révèle du raisonnement initial. C'est la signature « build + break » de ce site.

Tout le décor est monté pour l'occasion : clé RSA jetable, message inventé, machine de test. Rien de ce qui est attaqué ici n'appartient à quelqu'un d'autre, et c'est ce qui rend l'expérience refaisable chez vous.

Explication de la marmotte

Imagine un coffre-fort dont tu ne peux pas deviner la combinaison. Mais à côté du coffre, un gardien accepte de te dire, pour n’importe quel papier que tu lui glisses, si le cachet de cire est bien formé ou non. Un simple oui ou non. En glissant des milliers de papiers légèrement modifiés et en notant les réponses, on finit par reconstituer le document rangé à l’intérieur — sans jamais avoir ouvert le coffre.

→ Lire l’explication complète de la marmotte

Le Castor Intermédiaire · Expert

Ce que PKCS#1 v1.5 promettait

Le RSA brut est déterministe et malléable : chiffrer deux fois le même message donne deux fois le même chiffré, et le produit de deux chiffrés est le chiffré du produit. Pour l’utiliser comme schéma de chiffrement, il faut donc envelopper le message avant l’exponentiation. PKCS#1 v1.5 propose une enveloppe simple : le message est précédé d’un octet nul, d’un octet indiquant le type d’opération, d’une suite d’octets aléatoires non nuls, puis d’un séparateur nul.

Pour un module de k octets, le bloc à chiffrer a exactement cette forme :

00 02 [ au moins 8 octets aléatoires non nuls ] 00 [ message ]
|--|--|-------------------------------------|--|------------|
 |   |                  |                     |       |
 |   |                  |                     |       message utile
 |   |                  |                     séparateur obligatoire
 |   |                  remplissage aléatoire (jamais 00)
 |   type de bloc : 02 pour le chiffrement
 premier octet toujours nul : garantit que le bloc < module

Le premier octet nul n’est pas décoratif : il garantit que l’entier représenté par le bloc reste inférieur au module RSA. Le type 02 distingue le chiffrement de la signature. Le remplissage aléatoire, d’au moins huit octets, casse le déterminisme. Le séparateur nul permet au déchiffreur de retrouver où commence le message.

Le déchiffrement fait le chemin inverse : exponentiation avec la clé privée, puis vérification que le bloc obtenu commence bien par 00 02, qu’il contient au moins huit octets de remplissage, et qu’un séparateur nul apparaît ensuite. Si l’une de ces conditions manque, le bloc est invalide et le déchiffrement échoue.

C’est cette vérification, parfaitement légitime, qui va servir d’arme.

Construire l’ouvrage : un service de déchiffrement de laboratoire

Le décor tient en une clé RSA de 1024 bits générée localement — volontairement courte pour que l’attaque tourne en quelques minutes plutôt qu’en une nuit — et un service qui déchiffre ce qu’on lui envoie. Rien de ce montage n’existe ailleurs que sur la machine de test : la clé est jetable, le message est inventé.

"""Service de déchiffrement RSA PKCS#1 v1.5 — MONTAGE DE LABORATOIRE.

Ce code est délibérément vulnérable : il distingue, dans sa réponse, un bloc
au remplissage invalide d'un bloc correct. C'est exactement ce qu'un service
réel ne doit jamais faire. Clé jetable, générée pour cette démonstration.
"""

from cryptography.hazmat.primitives.asymmetric import rsa

# Clé de test : 1024 bits pour que la démonstration reste rapide. Aucune clé de
# cette taille ne doit protéger quoi que ce soit de réel (2048 bits minimum).
CLE_PRIVEE = rsa.generate_private_key(public_exponent=65537, key_size=1024)
CLE_PUBLIQUE = CLE_PRIVEE.public_key()

TAILLE_MODULE = (CLE_PRIVEE.key_size + 7) // 8  # k, en octets
MODULE = CLE_PUBLIQUE.public_numbers().n
EXPOSANT = CLE_PUBLIQUE.public_numbers().e


def dechiffrer_brut(chiffre: int) -> bytes:
    """Exponentiation privée seule, sans retrait du remplissage.

    On passe par les nombres privés plutôt que par l'API de haut niveau, qui
    refuserait justement de rendre un bloc au remplissage invalide.
    """
    nombres = CLE_PRIVEE.private_numbers()
    clair = pow(chiffre, nombres.d, MODULE)
    return clair.to_bytes(TAILLE_MODULE, byteorder="big")


def remplissage_valide(bloc: bytes) -> bool:
    """Vérification PKCS#1 v1.5 telle que la norme la décrit."""
    if len(bloc) != TAILLE_MODULE:
        return False
    if bloc[0] != 0x00 or bloc[1] != 0x02:
        return False
    separateur = bloc.find(b"\x00", 2)
    if separateur == -1:
        return False
    # Au moins 8 octets de remplissage aléatoire avant le séparateur.
    return separateur >= 10


def service_dechiffrement(chiffre: int) -> str:
    """Point d'entrée exposé. C'EST ICI QUE SE TROUVE LA FAILLE.

    La réponse distingue deux cas d'échec. Un attaquant n'a besoin de rien
    d'autre : la valeur de retour est l'oracle.
    """
    bloc = dechiffrer_brut(chiffre)
    if not remplissage_valide(bloc):
        return "400 Bad Padding"     # ← la fuite tient dans cette ligne
    return "200 OK"

Le service est correct au sens de la norme : il applique la vérification que PKCS#1 v1.5 demande, ni plus ni moins. La faille n’est pas dans le contrôle, elle est dans le fait de raconter au client comment il s’est terminé.

Explication du castor

L'ouvrage est debout, et c'est là que se joue l'honnêteté de la démonstration : ce service n'est pas un homme de paille bâclé pour tomber facilement. Il fait exactement ce que la norme demande, comme le ferait une implémentation écrite de bonne foi. Si on l'avait saboté pour rendre l'attaque plus spectaculaire, la brèche ne prouverait rien.

Casser : la question qui rend le module bavard

L’attaque repose sur une propriété élémentaire de RSA. Si c est le chiffré de m, alors pour n’importe quel entier s choisi par l’attaquant, c × sᵉ mod n est le chiffré de m × s mod n. L’attaquant peut donc fabriquer, à partir du seul chiffré intercepté et de la clé publique, une infinité de chiffrés dont il ne connaît pas les clairs, mais dont il connaît la relation avec le clair d’origine.

Il les soumet un par un. Quand le service répond 200 OK, l’information obtenue est précise : le bloc m × s mod n commence par 00 02. Autrement dit, l’entier m × s mod n est compris entre 2 × 256^(k−2) et 3 × 256^(k−2) − 1. Chaque réponse positive traduit donc une inégalité sur m, et chaque inégalité rétrécit l’intervalle des valeurs possibles.

"""Attaque de Bleichenbacher — recherche du premier multiplicateur conforme.

Seule la clé PUBLIQUE est utilisée ici : l'attaquant n'a jamais accès à d.
"""

# Bornes de l'intervalle « bloc commençant par 00 02 », en arithmétique entière.
B = 2 ** (8 * (TAILLE_MODULE - 2))
BORNE_BASSE, BORNE_HAUTE = 2 * B, 3 * B - 1


def oracle(chiffre_modifie: int) -> bool:
    """Un seul bit d'information par appel : le remplissage tenait-il ?"""
    return service_dechiffrement(chiffre_modifie) == "200 OK"


def chercher_premier_multiplicateur(chiffre: int) -> tuple[int, int]:
    """Étape 2a de l'article de 1998 : trouver le plus petit s conforme.

    On part de s = ceil(n / 3B) — en dessous, aucun produit ne peut retomber
    dans l'intervalle visé — et on incrémente jusqu'à ce que l'oracle accepte.
    Retourne le multiplicateur trouvé et le nombre de requêtes consommées.
    """
    s = -(-MODULE // BORNE_HAUTE)  # division entière arrondie au supérieur
    requetes = 0
    while True:
        candidat = (chiffre * pow(s, EXPOSANT, MODULE)) % MODULE
        requetes += 1
        if oracle(candidat):
            return s, requetes
        s += 1


def reduire_intervalle(bornes: tuple[int, int], s: int) -> list[tuple[int, int]]:
    """Étape 3 : traduire « m×s commence par 00 02 » en bornes sur m.

    Pour chaque r tel que l'encadrement reste cohérent, m est coincé entre deux
    valeurs. L'intervalle de départ se scinde parfois, puis les branches mortes
    disparaissent au fil des itérations suivantes.
    """
    a, b = bornes
    nouvelles = []
    r_min = (a * s - BORNE_HAUTE) // MODULE
    r_max = (b * s - BORNE_BASSE) // MODULE
    for r in range(r_min, r_max + 1):
        borne_a = max(a, -(-(BORNE_BASSE + r * MODULE) // s))
        borne_b = min(b, (BORNE_HAUTE + r * MODULE) // s)
        if borne_a <= borne_b:
            nouvelles.append((borne_a, borne_b))
    return nouvelles

Sur le montage ci-dessus, la première étape consomme à elle seule quelques dizaines de milliers de requêtes. L’intervalle initial couvre l’ensemble des blocs commençant par 00 02 ; il se réduit ensuite de moitié à chaque multiplicateur trouvé, jusqu’à ce que ses deux bornes coïncident. À cet instant, l’attaquant tient m — le bloc complet, remplissage compris — et n’a plus qu’à retirer l’enveloppe pour lire le message.

L’ordre de grandeur historique est d’un million de requêtes pour une clé de 1024 bits ; les variantes publiées depuis descendent nettement en dessous selon le bavardage exact de l’oracle. Ce nombre est la seule véritable défense qu’offrait l’implémentation d’origine, et c’est une défense qui s’évapore dès que le service répond vite et sans limite de débit.

Ce que la brèche révèle

Le service de laboratoire vérifiait correctement le remplissage. Il n’avait aucun bug d’implémentation au sens habituel, aucun dépassement de tampon, aucune erreur de calcul. Il a été rompu parce que son auteur — moi, en le montant — supposait implicitement qu’un message d’erreur précis est une bonne pratique. C’est vrai partout, sauf ici : un déchiffreur asymétrique est le seul composant d’un système où l’utilisateur ne doit jamais apprendre pourquoi son entrée a été rejetée.

Explication du castor

C'est le temps qui distingue le castor du simple briseur. Il connaît son barrage, il sait ce qu'il avait supposé en le montant, et il sait maintenant ce qu'il aurait dû supposer. La brèche n'est pas le résultat : elle est l'instrument de mesure. Ce qu'on retient d'un ouvrage rompu, ce n'est pas qu'il était mauvais, c'est l'hypothèse précise qui l'a fait céder — ici, « un bon message d'erreur aide l'utilisateur ».

Trois conséquences, dans l’ordre où elles comptent.

L’oracle n’a pas besoin d’un message d’erreur pour exister. Une différence de temps de réponse suffit, et c’est ce qui a fait durer l’attaque un quart de siècle. Les variantes ROBOT (Return Of Bleichenbacher’s Oracle Threat, 2017) ont trouvé des piles TLS (Transport Layer Security) qui distinguaient les deux cas par une alerte différente, un délai mesurable, ou une connexion fermée plutôt que maintenue. DROWN (2016) exploitait un serveur SSLv2 partageant la même clé qu’un service TLS moderne : l’oracle n’était même pas sur le service attaqué.

La contre-mesure conforme est contre-intuitive. Le RFC 5246 impose que le serveur, en cas de remplissage invalide, poursuive le handshake avec un secret pré-maître aléatoire généré à l’avance, jusqu’à l’échec de vérification final. Le client reçoit une erreur, mais toujours la même, au même endroit, après le même travail. On ne corrige pas Bleichenbacher en améliorant le message d’erreur : on le corrige en refusant de distinguer les cas, y compris dans le temps d’exécution.

Le schéma lui-même a été remplacé. RSA-OAEP (Optimal Asymmetric Encryption Padding), normalisé dans PKCS#1 v2, dispose d’une preuve de sécurité contre l’attaque à chiffré choisi adaptatif — exactement le modèle dans lequel opère Bleichenbacher. TLS 1.3 est allé plus loin en retirant purement et simplement l’échange de clés par chiffrement RSA : le handshake repose désormais sur Diffie-Hellman éphémère, ce qui supprime le composant vulnérable au lieu de le durcir. C’est la leçon la plus solide de cette histoire : un mécanisme qu’on doit protéger par une implémentation à temps constant parfaite est un mécanisme dont il vaut mieux se débarrasser.

Vérifier son propre parc

Trois questions à se poser sur un service qui déchiffre du RSA, dans cet ordre.

Le service accepte-t-il encore les suites de chiffrement à échange de clés RSA ? Si oui, la surface existe, indépendamment de la qualité de l’implémentation. Un scan de la configuration TLS répond en quelques secondes ; retirer ces suites règle la question définitivement.

Le service partage-t-il une clé avec un autre point d’entrée, plus ancien ou moins surveillé ? C’était le cœur de DROWN, et c’est le cas de figure qu’un inventaire de certificats détecte : la même clé publique présentée par deux services dont un seul a été durci.

L’implémentation distingue-t-elle un remplissage invalide d’un échec ultérieur — dans le code de retour, dans le journal, ou dans le temps de réponse ? Les deux premiers se lisent ; le troisième se mesure, avec suffisamment d’échantillons pour sortir du bruit réseau, ce qui reste le contrôle le plus long à mener.

🦫 Explication de la marmotte 🍫

Quand un ordinateur veut envoyer un secret à un serveur, il le met dans une enveloppe verrouillée avec la « clé publique » du serveur. N’importe qui peut fermer cette enveloppe, seul le serveur peut l’ouvrir avec sa clé privée. Jusque-là, tout va bien.

Avant de fermer l’enveloppe, on ne se contente pas d’y glisser le secret : on ajoute autour du papier de remplissage, tiré au hasard, selon une mise en forme très précise. Deux raisons à cela. D’abord, le hasard fait que deux enveloppes contenant le même secret ne se ressemblent pas. Ensuite, la mise en forme précise permet au serveur de vérifier, en ouvrant, que l’enveloppe est bien conforme et non une bricole envoyée par un plaisantin.

Le problème est là. Quand le serveur reçoit une enveloppe mal formée, il a envie de le dire : « ton remplissage est incorrect ». C’est poli, c’est utile pour déboguer, et c’est une catastrophe. Un attaquant qui a intercepté une enveloppe qu’il ne sait pas ouvrir peut la modifier légèrement — sans savoir ce qu’il y a dedans — et l’envoyer au serveur. Le serveur répond « conforme » ou « pas conforme ». Un seul mot, mais un mot qui apprend quelque chose sur le contenu. En recommençant des centaines de milliers de fois, avec des modifications choisies méthodiquement, l’attaquant reconstitue le secret entier. Il n’a jamais eu la clé privée, il n’a jamais forcé le coffre : il a juste posé beaucoup de questions à quelqu’un de trop serviable.

La parade est étrange à première vue : le serveur doit faire semblant. Quand il reçoit une enveloppe mal formée, il ne le dit pas — il continue comme si tout allait bien, avec un faux secret inventé sur place, et l’échange échoue plus tard, exactement de la même manière que dans les autres cas d’erreur. L’attaquant ne voit plus aucune différence, donc n’apprend plus rien. Et depuis, on a surtout changé de méthode : les connexions sécurisées récentes n’envoient plus du tout ce genre d’enveloppe, ce qui règle le problème à la racine.