Discussion :

[Uther]

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.

[Emmanuel Deloget]

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.

[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 ?

[neobast]

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

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

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

[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