Discussion :

[Plorf]

En cryptographie, il y a plusieurs seuils qui font qu'un algorithme est considéré comme sécurisé.

Il faut que les attaques connus les plus efficaces aient un certain nombre d'opérations à effectuer au minimum.

En signature et authentification : 2^20 opérations
En chiffrement : 2^80 opérations

Si l'on arrive à faire descendre un algorithme de chiffrement en dessous de 2^80, il est considéré comme cassé.
Mais concrètement, cela ne rends pas l'algorithme inutilisable tout de suite....

[Emmanuel Deloget]

@Grimly
[joke] Ils utilisent la technique de la force brute ? [/joke]

Et bien oui ; l'attaque en question consiste à faire diminuer d'un tout petit peu plus de 2 bits(*) la complexité d'une clef, ce qui reviens à tester 126 bits au lieu de 128 - en brute force, parce qu'à l'heure actuelle, on ne sait pas attaquer AES autrement.


(*) ils annonce un facteur 5 ; 2 bits == facteur 4, 2 bits == facteur 8, donc ils ont du trouver un petit truc supplémentaire qui fait que, en moyenne 1 fois sur 4, ce sont 3 bits qui sont déjà fixés. Ou quelque chose comme ça.

@kdmbella : rassure toi, on parle d'AES 128 bits. Si ça pose problème, on peut toujours passer à AES 256, ou AES 512.

[Marauder]

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 ?

[iznogoudmc]

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.

[Emmanuel Deloget]

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é.

[iznogoudmc]

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 ?

[Emmanuel Deloget]

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.

[iznogoudmc]

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

[DonQuiche]

@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.