Le chiffrement AES cracké
Par des chercheurs français, belges et de Microsoft : la méthode reste très complexe

Le , par Hinault Romaric, Responsable .NET
Les chercheurs de Microsoft, de l’université belge de Leuven et de l’ENS de Paris ont découvert une faille dans l’algorithme de chiffrement AES.

Le chiffrement AES (Advanced Encryption Standard) est actuellement le moyen le plus utilisé et le plus sûr pour sécuriser les transactions en ligne, les communications sans fil ou encore le stockage des données sensibles.

Les travaux des chercheurs Dmitry Khovratovich de Microsoft Research, de Andrey Bogdanov de l’Université de Leuven et de Christian Rechberge de l’Ecole Nationale Suppérieure de Paris ont été faits dans le cadre d’un projet de "cryptanalyse".

Les chercheurs ont publié une méthode d’attaque permettant de récupérer la clé secrète utilisée pour un chiffrement AES et ce de manière cinq fois plus rapide que dans les estimations des experts en raccourcissant l’algorithme AES de deux bits.

L’attaque serait applicable à toutes les versions du chiffrement AES.

Cependant, malgré la rapidité de la méthode, elle reste trèscomplexe et difficilement réalisable en utilisant les technologies actuelles. « Avec un trillion de machines, chacune pouvant tester un milliard de clés par seconde, cela prendrait plus de deux milliards d'années pour récupérer une clé AES 128 bits », expliquent les chercheurs.

L’attaque n’aurait donc pas, pour l’instant, d'implication pratique sur la sécurité des données des utilisateurs. Mais elle met fin au mythe du chiffrement AES, considéré auparavant comme incassable.

Les créateurs de l’algorithme AES auraient par ailleurs reconnu la validité de cette attaque.

Source : Le document sur l'attaque (PDF)

Et vous ?

Qu'en pensez-vous ?


Vous avez aimé cette actualité ? Alors partagez-la avec vos amis en cliquant sur les boutons ci-dessous :


 Poster une réponse

Avatar de DonQuiche DonQuiche - Expert confirmé https://www.developpez.com
le 23/08/2011 à 11:34
Citation Envoyé par Uther  Voir le message
Pour faire cela avec une seule machine il faut encore multiplier la puissance par 10^18 (une seule machine au lieu d'un trillard), ce qui donne une amélioration totale de facteur 7,0008 x 10^31

Il faudra log2 (7,0008 x 10^31) paliers de de 18 mois d'évolution technique soit environ 1904 mois (plus de 158 ans)."

Bref on est a l'abri pour encore quelque temps.

Sauf si des processeurs quantiques dédiés au cryptage sont mis au point. Ou sont déjà au point et en service, ce qui ne serait pas si surprenant, non ?
Avatar de Uther Uther - Expert éminent https://www.developpez.com
le 23/08/2011 à 12:04
C'est pour ça que je précise bien que mes calculs ne sont pas d'une fiabilité a toute épreuve, car il dépendent sur une approximation de la loi de Moore elle même assez vague et qu'il est fort probable qu'elle soit remise en cause dans les années a venir, notamment peut-être par l'arrivée des processeurs quantiques.

Pour les processeurs quantiques, ça fait partie ce ces technologie qu'on nous promet pour dans moins de dix ans depuis vingt ans. Je préfère ne pas trop faire de conjectures sur leur avenir.
Avatar de Emmanuel Deloget Emmanuel Deloget - Expert confirmé https://www.developpez.com
le 23/08/2011 à 21:16
Citation Envoyé par Uther  Voir le message
C'est pour ça que je précise bien que mes calculs ne sont pas d'une fiabilité a toute épreuve, car il dépendent sur une approximation de la loi de Moore elle même assez vague et qu'il est fort probable qu'elle soit remise en cause dans les années a venir, notamment peut-être par l'arrivée des processeurs quantiques.

Pour les processeurs quantiques, ça fait partie ce ces technologie qu'on nous promet pour dans moins de dix ans depuis vingt ans. Je préfère ne pas trop faire de conjectures sur leur avenir.

(apparté)

Et des toute façon, leur fonctionnement même rends caduque le problème à priori NP-complet qui est à la base de nombre d'algorithmes de crypto moderne (y compris AES) : la factorisation des grands nombres premiers (trouver A et B premier lorsque A*B est un très, très, très grand nombre). Il est théoriquement possible d'effectuer cette opération en O(1) sur un ordinateur quantique (et en pratique, elle a été réalisé pour un nombre de quelques bits, si je ne m'abuse). Les systèmes basés sur des courbes elliptiques sont peut-être sauf, mais j'en doute (au passage, c'est quelque chose que j'aimerais bien coder ça).

Du coup, dès que ceux-ci entreront dans la danse, il faudra de toute façon revoir toutes la crypto moderne.
Avatar de Marauder Marauder - Membre régulier https://www.developpez.com
le 24/08/2011 à 9:08
Nan mais lol !

" Avec un trillion de machines, chacune pouvant tester un milliard de clés par seconde, cela prendrait plus de deux milliards d'années pour récupérer une clé AES 128 bits »,

Ils appellent ça "casser une clé" eux ?
Avatar de neobast neobast - Membre à l'essai https://www.developpez.com
le 24/08/2011 à 10:26
Citation Envoyé par sevyc64  Voir le message
158 ans à l'échelle informatique, c'est gigantesque.
Il y a 40 ans seulement, l'informatique n'existait quasiment pas. Le chiffrement s'il existait devait pas se faire sur plus de 8 ou 16bits.

Aujourd'hui AES sur 128 bits est "crackable" et sera donc craké probablement dans le mois à venir. On sait que des solution plus puissante comme SHA256 et SHA512 possèdent très certainement des failles qui, lorsqu'elles seront découvertes et exploitées pourront servir à cracker l'algorithme. Ce n'est qu'une question de temps, mais certainement pas de décennies.

Alors dans 158 ans, AES sera cracké mais surtout abandonné depuis bien longtemps.
D'ailleurs l'informatique existera-t-elle toujours dans 158 ans ?


Cracké dans les mois à venir... Je pense que l'AES a encore de bon jours devant lui....

Ensuite, lorsque vous parler de SHA256 et SHA512 comme "solution plus puissante", je me permets de rectifier.
SHA256 et SHA512 sont des fonctions de hashage, en aucun cas ce ne sont des algorithmes de chiffrement comme l'AES.

Mais malgré cette avancé de 2 bits... il faut encore faire 2^126 tests... pour une clef .... Je pense qu'on a encore du temps....
Avatar de iznogoudmc iznogoudmc - Membre habitué https://www.developpez.com
le 24/08/2011 à 14:13
Holaaaaaaaaaaa !!! On se calme !!!!

Cette attaque permet de trouver la clef d'AES-128 en seulement 2^126,1 opérations contre 2^128 pour une attaque par force brute (source WP).

Donc en résumé, à moins que la brute force soit très con et teste les clefs dans l'ordre, ET que la clef est un nombre supérieur à 2^126,1.....la brute force à BEAUCOUP de chances de trouver la clef AVANT cet algorithme.
Avatar de Emmanuel Deloget Emmanuel Deloget - Expert confirmé https://www.developpez.com
le 24/08/2011 à 15:28
Citation Envoyé par iznogoudmc  Voir le message
Holaaaaaaaaaaa !!! On se calme !!!!

Cette attaque permet de trouver la clef d'AES-128 en seulement 2^126,1 opérations contre 2^128 pour une attaque par force brute (source WP).

Donc en résumé, à moins que la brute force soit très con et teste les clefs dans l'ordre, ET que la clef est un nombre supérieur à 2^126,1.....la brute force à BEAUCOUP de chances de trouver la clef AVANT cet algorithme.

heuh... Sans vouloir t'offenser, je me demande si tu comprends réellement la problématique. Selon toi, par quoi (quelle clef) devrait commence un algo de cassage brute force ?

C'est pas une question d'être un nombre > 2^126 ou pas - et rien ne dit que les 2 bits éliminés soient les bits de poids fort.

Quand on essaie de casser un algo de crypto, on cherche à éliminer des bits afin de réduire la complexité de l'attaque. Une faiblesse dans un algo de crypto va faire que pour un bit particulier (ou une série de bits), soit l'impact sur le cryptage est connu, soit cet impact est nul. la cryptanalyse cherche à découvrir ces bits. Une fois leur position connue, il suffit de ne pas les considérer dans une attaque brute force et hop, le tour est joué.
Avatar de iznogoudmc iznogoudmc - Membre habitué https://www.developpez.com
le 24/08/2011 à 16:05
Citation Envoyé par Emmanuel Deloget  Voir le message
heuh... Sans vouloir t'offenser, je me demande si tu comprends réellement la problématique. Selon toi, par quoi (quelle clef) devrait commence un algo de cassage brute force ?

Alors soit je comprends très mal, soit "clef de 128 bits" signifie que la clef est un nombre codé sur 128 bits, non ?

Donc en attaque brute force, je vais devoir tester tous les nombres pouvant être codés sur 128 bits, un peu comme si je cherchais à ouvrir un cadenas "à chiffres" en tentant toutes les combinaisons offertes par ses n rouleaux, non ?

Donc, en prenant comme exemple un cadenas à 3 rouleaux, et que le code choisi soit 857 ; même en tentant tous les codes en partant de 000 (ce qui est vraiment stupide...), j'aurai réussi en 858 tentatives (et non pas 1000 !). Donc si je suis face à un compétiteur qui a "un algorithme infaillible en 900 coups au lieu de 1000", ma brute force aura quand même gagné.
Et maintenant, si je prends n cadenas, il y a fort peu de chances qu'il y en ait une majorité donc le code soit supérieur à 900, il y en aura même beaucoup avec des codes très inférieurs à 800, 700, voire encore moins.... Donc brute force gagne, encore plus largement, non ?

Et maintenant j'améliore mon brute force : je saute 000, 001, 002, (...), 111, 222, (...) pour ne les tester qu'à la fin..... ce qui fait que dans mon exemple, je n'aurais pas testé 858 combinaisons, mais encore moins (donc brute force gagne encore plus largement).

J'ai tout compris ?
Avatar de Emmanuel Deloget Emmanuel Deloget - Expert confirmé https://www.developpez.com
le 24/08/2011 à 17:03
Citation Envoyé par iznogoudmc  Voir le message
Alors soit je comprends très mal, soit "clef de 128 bits" signifie que la clef est un nombre codé sur 128 bits, non ?

Donc en attaque brute force, je vais devoir tester tous les nombres pouvant être codés sur 128 bits, un peu comme si je cherchais à ouvrir un cadenas "à chiffres" en tentant toutes les combinaisons offertes par ses n rouleaux, non ?

Donc, en prenant comme exemple un cadenas à 3 rouleaux, et que le code choisi soit 857 ; même en tentant tous les codes en partant de 000 (ce qui est vraiment stupide...), j'aurai réussi en 858 tentatives (et non pas 1000 !). Donc si je suis face à un compétiteur qui a "un algorithme infaillible en 900 coups au lieu de 1000", ma brute force aura quand même gagné.
Et maintenant, si je prends n cadenas, il y a fort peu de chances qu'il y en ait une majorité donc le code soit supérieur à 900, il y en aura même beaucoup avec des codes très inférieurs à 800, 700, voire encore moins.... Donc brute force gagne, encore plus largement, non ?

Et maintenant j'améliore mon brute force : je saute 000, 001, 002, (...), 111, 222, (...) pour ne les tester qu'à la fin..... ce qui fait que dans mon exemple, je n'aurais pas testé 858 combinaisons, mais encore moins (donc brute force gagne encore plus largement).

J'ai tout compris ?

Non. Ton raisonnement est faussé d'un part parce que tu penses savoir quelque chose à propos de la clef à trouver - ce n'est pas le cas - et d'autre part parce que tu confonds deux notions.

K opérations est le nombre max d'opérations nécessaire pour trouver le résultat ; ça n'a rien à voir avec le nombre d'opérations réelles à effectuer. Tu peux trouver le résultat en une opération avec une probabilité de 1/K (c'est assez faible si K=2^128...). Comme tu peux tomber dans un cas spécial qui nécessite le nombre max d'opérations avant de trouver le résultat. Ce qui est important c'est que la recherche peut potentiellement nécessiter K opérations, pas qu'il y a une faible chance d'obtenir le résultat avant.

Ce qu'il faut noter, c'est que du point de vue de ton attaque, le nombre que tu doit trouver 0 <= N < K est un nombre au hasard. Tu ne le connais pas, et tu ne connais pas ses propriétés. Ca peut être n'importe laquelle des valeurs que tu va tester. Tu ne peux pas deviser d'un moyen pour le trouver. Si tu reprends ton analogie du cadenas - très bonne puisqu'il s'agit exactement du même cas - alors quel que soit l'algorithme que tu utilises pour choisir la prochaine valeur que tu va tester, il existe au moins un cas ou le code va te demander de tester toutes les combinaisons.

Dans ton cas spécifique, qu'est-ce qui te dis que celui a qui appartient le cadenas n'a pas, par le plus grand des hasards, choisi la combinaison qui va te nécessiter de tester les 1000 combinaisons possibles ?

Pour simplifier, prenons une clef codée sur 2 bits (donc K=4 valeurs, 0, 1, 2, 3).

J'ai exactement 24 parcours possible de ces 4 valeurs : 0,1,2,3 ou 0,2,1,3, 0,3,1,2,... Si j'en choisi un quelconque, alors ce parcours - comme tous les autres - teste 3 valeurs avant de tester la dernière. Il suffit que ma clef de cadenas soit égal à cette valeur et mon algorithme de force brute a nécessité toutes les combinaisons possibles et imaginables (soit 4). Bien sûr, il existe un parcours qui va trouver ma clef en 1 coup, ou 2, ou 3, mais dans ce cas, le même parcours nécessitera un nombre différent de coup si ma clef change.

Le premier résultat de cette analogie est qu'il n'existe aucun parcours permettant de trouver une valeur au hasard entre 0 et 3 inclus de manière systématique en moins de 4 coups.

Peut-on choisir le parcours à effectuer en fonction de la valeur à deviner ? Non, parce que ça voudrait dire qu'on connait déjà la valeur à découvrir, ce qui est un peu contraire à l'énoncé. Du coup, on a notre second résultat : tous les parcours sont considérés comme équivalents, et tu te bornes à en prendre un au hasard.

Maintenant, le cadenas a une faiblesse : lorsque ma clef est 2 ou 3, il se comporte de la même manière. Du coup, mon algorithme de cassage du cadenas est simplifier : au lieu de parcourir 4 valeurs pour être sûr d'avoir la bonne réponse, je n'ai plus que 3 à en parcourir. Donc en moyenne, je vais pirater des cadenas beaucoup plus rapidement. Plus jamais je n'aurais besoin de tester les 4 valeurs possibles. Au lieu d'avoir 1 chance sur 4 d'ouvrir le cadenas au premier coup, j'ai maintenant 1 chance sur 3.

La faiblesse découverte est du même ordre : elle divise par 5 le nombre d'opérations nécessaire pour être sûr, dans tous les cas de figure, de trouver la clef AES qui a permis de crypter un bloc d'information. L'attaque continue d'être effectuée en brute force.
Avatar de DonQuiche DonQuiche - Expert confirmé https://www.developpez.com
le 24/08/2011 à 17:08
@iznogoudmc
Pour compléter...
Pourquoi devrais-tu tester 111 et 222 à la fin ? Ce sont des clés tout aussi probables que 12155456487892161.
Tu ne peux rien sauter, les clés sont équiprobables à moins que tu ne puisses prouver le contraire.
Avatar de iznogoudmc iznogoudmc - Membre habitué https://www.developpez.com
le 24/08/2011 à 17:16
Citation Envoyé par Emmanuel Deloget  Voir le message
La faiblesse découverte est du même ordre : elle divise par 5 le nombre d'opérations nécessaire pour être sûr, dans tous les cas de figure, de trouver la clef AES qui a permis de crypter un bloc d'information. L'attaque continue d'être effectuée en brute force.

OK, merci pour les explications.
Du coup j'ai compris d'où vient mon erreur : c'est de n'avoir pratiquement retenu que la phrase « Avec un trillion de machines, chacune pouvant tester un milliard de clés par seconde, cela prendrait plus de deux milliards d'années pour récupérer une clé AES 128 bits » : comme il manque les deux mots "au maximum", je m'étais mis à déduire (beaucoup trop vite) que leur attaque n'était pas un moyen d'éviter à la brute force de devoir tester toutes les combinaisons, mais nécessitait bel et bien ce nombre d'opérations de calcul.

Même si dans la pratique je maintiens que la simplification est (encore ?) trop faible pour rendre cette attaque d'une quelconque utilité, je reconnais que j'ai l'air idiot sur ce coup : ça m'apprendra à lire trop vite
Offres d'emploi IT
Expert décisionnel business intelligence H/F
Safran - Ile de France - Évry (91090)
Architecte électronique de puissance expérimenté H/F
Safran - Ile de France - Villaroche - Réau
Data scientist senior H/F
Safran - Ile de France - Magny-les-Hameaux (Saclay)

Voir plus d'offres Voir la carte des offres IT
Contacter le responsable de la rubrique Accueil