Comprendre la cryptanalyse sans perdre le fil pratique

Comprendre la cryptanalyse sans perdre le fil pratique

Une annonce de cryptanalyse arrive rarement sous la forme « l’algorithme est cassé ». Elle arrive sous la forme « attaque en 2⁹⁹,⁵ opérations sur la version complète, dans le modèle à clés liées », et c’est à l’administrateur de décider s’il faut migrer lundi, dans trois ans ou jamais. Ce chapitre donne la grille de lecture : ce que cherche un cryptanalyste, les grandes familles d’attaques contre les chiffrements, les fonctions de hachage et les protocoles, puis la traduction d’un résultat en décision opérationnelle.

Explication de la marmotte

La cryptanalyse ressemble au travail d’un serrurier qui étudie une serrure réputée solide pour savoir s’il existe un moyen d’ouvrir la porte plus vite qu’en essayant une à une toutes les clés du trousseau. Lire ses découvertes avec méthode permet de décider s’il faut changer la serrure demain, dans quelques années, ou simplement garder un œil dessus.

→ Lire l’explication complète de la marmotte

Que cherche un cryptanalyste

Comparer à la force brute

Toute attaque se mesure contre une référence générique. Pour un chiffrement à clé de k bits, la force brute essaie les clés une à une et coûte 2ᵏ opérations dans le pire cas. Pour une fonction de hachage de sortie n bits, trouver une préimage coûte génériquement 2ⁿ, et trouver une collision environ 2 puissance n/2 grâce au paradoxe des anniversaires. Au sens académique, une attaque « casse » l’algorithme dès qu’elle fait mieux que cette référence, même d’un facteur quatre. Ce vocabulaire explique bien des titres alarmistes : « AES cassé » a pu désigner une attaque en 2¹²⁶,¹ au lieu de 2¹²⁸, c’est-à-dire un gain d’un facteur quatre sur un travail qui reste impossible.

Réduire le coût en exploitant une structure

L’essentiel du métier consiste à trouver une régularité que l’algorithme n’aurait pas dû laisser. Dans les chiffres classiques, c’était la fréquence des lettres ; l’indice de coïncidence, qui mesure la probabilité que deux lettres prises au hasard soient identiques, révèle la longueur d’une clé périodique, et les répétitions de séquences, exploitées par Kasiski au XIXᵉ siècle, en donnent les multiples. Ces méthodes sont présentées dans Du chiffre manuel au chiffrement moderne. Dans les algorithmes modernes, les régularités sont statistiques et ténues, mais le principe n’a pas changé : trouver un biais, l’amplifier, et en tirer de l’information sur la clé.

Changer le modèle

Une autre voie consiste à donner à l’attaquant des capacités supplémentaires : choisir les clairs, obtenir des déchiffrements, faire chiffrer sous des clés liées à la clé cible, mesurer des temps d’exécution. Chaque modèle correspond à une situation réelle plus ou moins plausible. Une attaque très puissante dans un modèle irréaliste pour l’usage considéré peut n’avoir aucune conséquence ; une attaque modeste dans un modèle qui correspond exactement au protocole déployé peut être dévastatrice. La première question à poser devant un résultat est donc : quel modèle, et correspond-il à mon usage ?

Familles sur chiffrement

Différentielle et linéaire

La cryptanalyse différentielle, publiée par Biham et Shamir en 1990, étudie comment une différence fixée entre deux clairs se propage à travers les rondes. Si une différence d’entrée produit une différence de sortie donnée avec une probabilité nettement supérieure au hasard, on peut tester des hypothèses sur les sous-clés des dernières rondes en accumulant des paires. Contre DES (Data Encryption Standard) complet, elle demande 2⁴⁷ clairs choisis. La cryptanalyse linéaire, de Matsui en 1993, cherche des approximations linéaires entre bits de clair, de chiffré et de clé qui tiennent avec une probabilité biaisée ; contre DES, 2⁴³ clairs connus suffisent. Ces deux méthodes sont devenues des critères de conception : un algorithme moderne publie ses bornes de résistance, et l’AES (Advanced Encryption Standard) a été conçu pour qu’aucune caractéristique utile ne traverse plus que quelques rondes.

Meet-in-the-middle et slide

L’attaque par rencontre au milieu sépare un calcul en deux moitiés indépendantes et échange du temps contre de la mémoire : elle ramène le double chiffrement à peine au-dessus du simple, comme le détaille Choisir, combiner et migrer. L’attaque par glissement (slide attack) exploite des rondes identiques entre elles, quel que soit leur nombre ; elle sanctionne un cadencement de clé trop régulier, décrit dans Chiffrer par blocs.

Related-key

Les attaques à clés liées supposent que l’attaquant obtient des chiffrements sous plusieurs clés inconnues mais reliées par une relation qu’il choisit, par exemple une différence connue. En 2009, Biryukov et Khovratovich ont publié une telle attaque contre AES-256 en 2⁹⁹,⁵ opérations. Le résultat est remarquable sur le plan théorique ; il est sans effet pour un système qui tire ses clés aléatoirement et indépendamment. Il devient pertinent quand un protocole dérive des clés par simple incrément ou XOR d’une clé maîtresse, ce qui était le cas du WEP (Wired Equivalent Privacy), dont la chute tient largement à ce genre de relation.

Padding oracle

Le padding oracle, décrit par Serge Vaudenay en 2002, n’attaque pas l’algorithme de bloc mais le mode CBC (Cipher Block Chaining) et son remplissage. Si un serveur répond différemment selon que le remplissage d’un chiffré soumis est valide ou non, par un message d’erreur ou simplement par un temps de réponse, un attaquant déchiffre n’importe quel bloc en environ 128 requêtes par octet en moyenne, sans connaître la clé. POODLE (2014) contre SSL 3.0 et Lucky Thirteen (2013) contre TLS (Transport Layer Security) en sont des déclinaisons. AES n’y est pour rien, ce qui montre qu’une primitive incassable ne protège pas un protocole bavard.

Familles sur hash et protocole

Collision, préimage et multicollision

Une collision est un couple de messages distincts ayant la même empreinte ; une préimage est un message produisant une empreinte imposée ; une seconde préimage est un message différent d’un message donné mais de même empreinte. Les collisions sont toujours tombées en premier. MD5 a vu ses premières collisions publiées en 2004, puis des collisions à préfixe choisi exploitées en 2008 pour forger un certificat d’autorité, et en 2012 par le logiciel malveillant Flame pour imiter une signature de mise à jour. Antoine Joux a montré en 2004 qu’une fonction itérative de type Merkle-Damgård produit des multicollisions, 2ᵗ messages de même empreinte, pour à peine t fois le coût d’une collision ; concaténer deux empreintes de 128 bits n’offre donc pas 256 bits de résistance. Les propriétés et les familles de fonctions sont développées dans Condensés cryptographiques.

Extension de longueur

Les fonctions de la famille Merkle-Damgård, comme SHA-256, publient leur état interne final comme empreinte. Connaissant H(secret || message) et la longueur du secret, un attaquant calcule H(secret || message || remplissage || suite) sans connaître le secret. Une API qui authentifie ses requêtes par cette construction naïve se laisse donc ajouter des paramètres. HMAC, SHA-3 et les variantes tronquées comme SHA-512/256 ne sont pas concernés ; d’où la règle d’employer HMAC, présenté dans Prouver qu’un message vient du bon secret.

Rejeu, réflexion et downgrade

Les attaques de protocole n’ont souvent besoin d’aucune cryptanalyse. Le rejeu renvoie un message valide déjà observé : un ordre de virement chiffré et authentifié reste valide la deuxième fois si rien ne l’identifie comme unique. La réflexion renvoie à un participant son propre défi, pour qu’il calcule lui-même la réponse attendue de l’autre côté, ce qui fonctionne quand les deux sens utilisent la même clé et le même format. Le downgrade, ou repli forcé, manipule la négociation pour imposer une version ou un algorithme faible : FREAK et Logjam, en 2015, ont forcé des serveurs TLS à employer des paramètres « export » de 512 bits. La confusion de contexte fait accepter dans un rôle un objet signé ou chiffré pour un autre rôle. Les parades sont structurelles : nonces et compteurs contre le rejeu, clés ou étiquettes distinctes par direction, transcription authentifiée de la négociation, et liaison du contexte dans les données authentifiées.

Oracle

Plus généralement, un oracle est tout comportement observable qui dépend d’un secret : message d’erreur, temps de réponse, code HTTP, fermeture de connexion. Le padding oracle en est un cas, l’attaque de Bleichenbacher de 1998 contre le remplissage RSA PKCS#1 v1.5 un autre. Les fuites physiques et temporelles relèvent de la même logique, traitée dans Quand l’implémentation parle.

Impact pratique

Données nécessaires, coût et automatisation

Un résultat publié se lit sur quatre axes. Le temps, exprimé en opérations élémentaires ou en évaluations de la primitive. La mémoire, souvent oubliée, et parfois plus contraignante que le temps. Les données : nombre de clairs connus ou choisis, nombre de requêtes à un oracle, ce qui peut être hors de portée même si le calcul est modeste. La portée : version complète ou réduite en rondes, modèle d’attaque, probabilité de succès. Une attaque sur 7 rondes d’un algorithme qui en compte 10 est un signal, pas une alerte.

Le coût se traduit ensuite en ressources réelles. 2⁶⁴ opérations représentaient un projet d’État au début des années 2000 ; c’est aujourd’hui à la portée d’un acteur bien financé disposant de GPU (Graphics Processing Unit) loués. La complexité asymptotique ne dit pas tout : les constantes, l’accès à la mémoire et la parallélisation peuvent multiplier le coût réel par mille. L’étape décisive est l’automatisation : quand une attaque devient un outil téléchargeable, son coût marginal s’effondre et sa population d’utilisateurs explose.

Marge restante et décision de migration

La marge de sécurité est l’écart entre la meilleure attaque connue et la sécurité nominale, ou entre le nombre de rondes attaquées et le nombre de rondes réel. Elle ne remonte jamais : la cryptanalyse progresse, le matériel aussi. La décision de migrer se prend quand la marge passe sous un seuil fixé à l’avance, et compte tenu de la durée pendant laquelle les données doivent rester protégées. Pour des archives à protéger vingt ans, une marge confortable aujourd’hui peut déjà être insuffisante, et la même logique gouverne la migration post-quantique.

Exemples et ateliers

Lire une annonce de collision SHA-1

En février 2017, l’équipe SHAttered publie deux fichiers PDF distincts de même empreinte SHA-1. Lecture méthodique : il s’agit d’une collision à préfixe identique, pas d’une préimage ; le coût annoncé est d’environ 2⁶³ évaluations de SHA-1, soit de l’ordre de 6 500 années-processeur et 110 années-GPU ; l’attaque est donc pratique pour un acteur doté de moyens importants. En 2020, Leurent et Peyrin publient une collision à préfixe choisi pour quelques dizaines de milliers de dollars de calcul loué, et l’appliquent à des certifications de clés PGP. Conséquence opérationnelle : toute signature apposée sur une empreinte SHA-1 d’un document que l’attaquant a pu préparer est forgeable ; un usage de SHA-1 comme simple somme de contrôle contre la corruption accidentelle n’est pas affecté de la même façon. Le NIST (National Institute of Standards and Technology) a annoncé le retrait complet de SHA-1 pour la fin de 2030.

Classer une attaque théorique

Résultat	Modèle	Données	Classement
AES-128 en 2¹²⁶,¹ (biclique, 2011)	clairs choisis	énormes	marge intacte en pratique, surveiller
AES-256 en 2⁹⁹,⁵ à clés liées	clés liées	2⁹⁹,⁵	sans effet si clés indépendantes
SHA-1 collision à préfixe choisi	aucun secret	aucune	migrer toute signature SHA-1
Padding oracle sur un service CBC	oracle d’erreur	quelques milliers de requêtes	corriger immédiatement

Rejouer un message dans un protocole jouet

import hmac, hashlib
K = b"cle-partagee"
def envoyer(ordre):
    return ordre, hmac.new(K, ordre, hashlib.sha256).digest()
def recevoir(ordre, tag):
    return hmac.compare_digest(tag, hmac.new(K, ordre, hashlib.sha256).digest())
msg = envoyer(b"payer 100 a Bob")
print(recevoir(*msg), recevoir(*msg))   # True True : le rejeu passe

Le message est parfaitement authentifié et pourtant accepté deux fois. Ajouter un compteur strictement croissant dans le message authentifié, et refuser toute valeur déjà vue, ferme la faille sans toucher à HMAC.

Plan de migration après perte de marge

Un plan tient en cinq points : inventorier les usages de l’algorithme affaibli, en distinguant ceux que l’attaque touche réellement ; fixer une date de fin d’émission de nouvelles données ; déployer l’algorithme de remplacement en lecture double ; traiter l’existant, rechiffrer ou re-signer ce qui doit encore servir ; supprimer le support ancien et vérifier qu’aucune négociation ne peut y revenir.

Pièges classiques

Ignorer une attaque parce qu’elle n’est pas encore pratique revient à attendre qu’elle le devienne pour commencer une migration qui prend des années. Déclarer un protocole mort sans lire le modèle provoque des migrations coûteuses et inutiles, et use la crédibilité nécessaire pour les vraies. Confondre complexité asymptotique et coût réel conduit à des erreurs dans les deux sens. Répondre à un bug de protocole par une clé plus longue, enfin, revient à renforcer la porte d’un coffre dont le guichetier ouvre à qui le demande poliment : un padding oracle fonctionne aussi bien avec AES-256 qu’avec AES-128.

À ne pas confondre

La cryptanalyse étudie les faiblesses d’un algorithme ou d’un protocole dans un modèle formel ; le test d’intrusion évalue un système déployé, avec ses configurations et ses erreurs humaines. Une attaque académique démontre une possibilité ; un exploit est un outil qui la réalise sur une cible réelle. La force brute ignore la structure de l’algorithme, l’attaque structurelle l’exploite. Une réduction de marge, enfin, n’est pas une compromission : elle annonce que la protection vieillit, pas qu’elle a cédé.

🐝 Ce qui arrive si on s’en passe

Sans lecture méthodique des résultats de cryptanalyse, la décision de migrer arrive au pire moment : quand l’attaque est devenue un outil automatisé plutôt qu’un article. Les messages chiffrés et les empreintes produits entre-temps ne se rattrapent pas ; une archive interceptée des années plus tôt se relit dès que le coût de l’attaque s’effondre, et un document signé au-dessus d’une empreinte sujette aux collisions peut se voir adjoindre un jumeau falsifié portant la même signature. Le calendrier de migration est alors fixé par l’attaquant, avec l’élégance d’un déménagement organisé pendant l’incendie.

🦫 Explication de la marmotte 🍫

La cryptanalyse étudie les moyens de casser un procédé de chiffrement ou une fonction de hachage, qui calcule une empreinte courte d’un message, plus vite que prévu. Le point de référence est toujours la force brute : essayer toutes les clés possibles. Une attaque n’a d’intérêt que si elle coûte moins cher que cet essai exhaustif. Pour y parvenir, le cryptanalyste exploite une régularité de l’algorithme, par exemple des différences entre deux messages qui se propagent de façon prévisible, ou bien il change les conditions de départ, en supposant par exemple qu’il obtient des chiffrements faits avec des clés liées entre elles. Sur les empreintes, il cherche deux messages qui donnent la même empreinte (une collision) ou un message qui produit une empreinte imposée (une préimage). Sur les protocoles, il rejoue un ancien message, force l’emploi d’une version plus faible, ou exploite un système qui indique si un message est valide, ce qu’on appelle un oracle. Pour juger un résultat publié, il faut lire le nombre de calculs, la mémoire, la quantité de données exigée et les hypothèses retenues. Une attaque théorique réduit la marge de sécurité sans casser immédiatement le système, mais cette marge ne remonte jamais. Quand elle devient trop mince, il faut planifier une migration. Allonger la clé ne corrige pas une erreur de conception du protocole.

À lire aussi

• Évaluer la force d’une protectionExpliquer comment raisonner en bits de sécurité, en durée de confidentialité et en coût réel d’attaque, sans réduire la décision à la longueur d’une clé.
• Transformer un bloc en chiffrement de messageExpliquer les modes opératoires, leurs fuites et leurs exigences de paramètres, puis orienter vers les modes authentifiés pour les usages modernes.
• Lire une garantie sans la surinterpréterDonner les outils pour comprendre une preuve de sécurité, une hypothèse de dureté et un modèle d’attaque, tout en rappelant leurs limites pratiques.
• Chiffrement par flot : état, compteurs et réutilisation interditePrésenter les chiffrements par flot et les générateurs de suites comme une famille utile mais très sensible à la réutilisation de flux, d’état et de nonce.

Pages voisines

La citent

• Vérifier un protocole cryptographique avec Tamarin ou ProVerif

Comprendre la cryptanalyse sans perdre le fil pratique

Elle cite

• ⇄Lien dans les deux sens :Chiffrer par blocs : de l’héritage DES à AES
• ⇄Lien dans les deux sens :Choisir, combiner et migrer les algorithmes symétriques
• ⇄Lien dans les deux sens :Du chiffre manuel au chiffrement moderne
• Quand l’implémentation parle : temps, cache, fautes et oracles
• Condensés cryptographiques : propriétés, constructions et familles
• Préparer la migration post-quantique
• Protéger une information en environnement hostile
• Prouver qu’un message vient du bon secret
• Exploiter un padding oracle CBC avec PKCS#7
• Sécurité des systèmes bancaires et financiers

⇄ : les deux pages se citent l’une l’autre.