EUF-CMA : Existential Unforgeability under Chosen-Message Attack
Cryptographie
EUF-CMA : Existential Unforgeability under Chosen-Message Attack, infalsifiabilité existentielle sous attaque à messages choisis. « La signature que personne ne sait imiter, pas même au bas d'un message absurde, après en avoir obtenu autant qu'il voulait sur des messages de son choix », par analogie avec un notaire qui paraphe tout ce qu'on lui présente sans que quiconque parvienne jamais à reproduire son paraphe sur une feuille de plus.
Le jeu : L'adversaire obtient des signatures, ou des étiquettes de code d'authentification de message, sur les messages de son choix, adaptés au fil des réponses. Il gagne s'il produit un couple message-signature valide pour un message qu'il n'a jamais fait signer, quel qu'en soit le contenu, même dénué de sens. EUF désigne cette infalsifiabilité existentielle, CMA l'attaque à messages choisis.
Origine : La notion est formalisée par Goldwasser, Micali et Rivest en 1988. Elle est aujourd'hui l'exigence de base pour les signatures (RSA-PSS, ECDSA, Ed25519, ML-DSA) et pour les codes d'authentification de message comme HMAC ou CMAC.
Version forte : SUF-CMA, l'infalsifiabilité forte, interdit aussi de fabriquer une nouvelle signature valide pour un message déjà signé. ECDSA ne l'offre pas : si (r, s) est valide, (r, n - s) l'est aussi. Cette malléabilité a gêné Bitcoin, qui identifiait les transactions par un condensé incluant la signature, jusqu'à l'imposition de valeurs s basses puis l'arrivée de SegWit.
Ce qu'elle ne dit pas : EUF-CMA garantit qu'un message signé vient du détenteur de la clé, rien de plus : ni qu'il est récent, ni qu'il est destiné au bon serveur, ni qu'il n'a pas déjà été présenté. L'horodatage, le contexte et l'unicité restent à la charge du protocole.
Ce qui arrive si on s'en passe
Une signature ou un code d'authentification qui n'atteint pas EUF-CMA laisse un attaquant fabriquer des messages acceptés sans posséder la clé, par exemple en combinant des signatures légitimes obtenues sur des messages anodins ; c'est ce que permet la signature RSA brute, multiplicative, sans remplissage. À l'inverse, se croire protégé par EUF-CMA contre le rejeu est une erreur classique : un ordre de virement signé reste valide la deuxième fois. Il faut une primitive prouvée, comme RSA-PSS, Ed25519 ou HMAC, et un protocole qui lie chaque message à son contexte et à un numéro unique.
Explication de la marmotte
Une signature électronique sert à prouver qu'un message vient bien de son auteur. Pour vérifier qu'elle est solide, on imagine un tricheur qui peut faire signer autant de messages qu'il veut par la vraie personne. S'il ne parvient malgré tout jamais à fabriquer une signature valide pour un nouveau message, la signature est dite EUF-CMA. Cela n'empêche pas de renvoyer une deuxième fois un vieux message signé, et il faut s'en protéger autrement.
Où ce terme est utilisé
- Lire une garantie sans la surinterpréter (2 occurrences)