je m'intéresse au chiffrement SSL utilisé lors des dialogues https.
Je cherche à calculer le coût d'une attaque en brute force.
Imaginons que je possède une capture réseau https entre un client
et un serveur. L'échange s'est effectué:
Cipher : AES256-SHA
J'ai donc deux axes d'attaques en brute force:
1/ casser l'AES256 pour lire les échanges en clair
2/ casser la clé privée du serveur distant pour décoder les échanges et
trouver la clé AES.
Première question: est-ce vrai?
Je ne cherche bien évidemment pas à casser le https, je cherche à
donner des chiffres concrets sur le coût de la brute force. L'idée n'est
pas de donner dans la finesse, mais montrer de manière calculatoire
que le brute force est un mauvais choix.
Deuxième question: quelle base de calcul prendre? (existe t'il des benchs
à ce sujet?)
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Thomas Pornin
According to Kevin Denis :
J'ai donc deux axes d'attaques en brute force: 1/ casser l'AES256 pour lire les échanges en clair 2/ casser la clé privée du serveur distant pour décoder les échanges et trouver la clé AES.
Première question: est-ce vrai?
La "force brute", ça consiste à attaquer une donnée secrète en essayant toutes les combinaisons possibles. Dans le cas de SSL, il y a quelques clés symétriques, qui dérivent d'un échange de clé qui utilise un protocole d'échange de clé, en général un chiffrement asymétrique (en RSA) ou un Diffie-Hellman.
Quand le chiffrement symétrique est de l'AES-256, alors la clé symétrique correspondante fait 256 bits, donc 2^256 combinaisons. Pour un bon algorithme de chiffrement symétrique (et il semble que l'AES soit bon), quand on n'a pas tout, on n'a rien. Autrement dit, si on essaye quasiment la bonne clé, mais avec un bit changé, alors on ne remarque rien. Donc la recherche par force brute ne réussit qu'en tombant pile sur la bonne combinaison. En moyenne on essaye la moitié des combinaisons possibles avant de tomber sur la bonne, d'où 2^255 essais.
On peut essayer de faire la recherche sur la clé échangée. Si c'est du RSA, alors c'est une suite de 48 octets, dont les 4 premiers sont prévisibles (c'est l'heure courante) ; restent 44 octets aléatoires, soit 352 bits -> là, c'est encore plus difficile que pour la clé de 256 bits de l'AES.
Il y a aussi des clés de MAC. Les MAC servent à contrôler l'intégrité des messages échangés. Quand on utilise HMAC/SHA-1 (un cas courant en SSL), la clé de MAC fait 160 bits ; mais : 1. ce MAC est également chiffré donc on ne peut pas faire de recherche directe dessus (pas moyen de tester simplement si une combinaison est valide ou pas) ; 2. même si on trouve la clé de MAC, cette clé est dérivée de la clé maître (celle échangée en RSA ou DH) selon un processus non réversible, donc on n'accède pas ainsi à la clé de chiffrement symétrique.
Il est nettement plus "facile" de s'attaquer au protocole d'échange de clé. Celui-là ne peut pas utiliser les recettes usuelles du chiffrement symétrique (i.e. on mélange tout joyeusement) parce qu'un tel protocole met en jeu deux entités distinctes, et pour ça il faut de la structure mathématique. Par exemple, pour RSA, il y a un grand nombre qui est public, et qui est le produit de deux facteurs premiers (qui eux sont privés). La connaissance des facteurs en question permet de casser le système. Chercher des facteurs premiers d'un grand nombre peut se faire par force brute mais c'est absurdement inefficace. Par exemple, pour une clé RSA typique avec un grand nombre de 1024 bits, on peut représenter les deux facteurs premiers sur un peu plus que 1024 bits (voire exactement 1024 bits si on s'y prend bien). Ça fait 2^1024 combinaisons. C'est la force brute. Mais si on a un facteur on a l'autre (puisqu'on connaît leur produit). Donc en faisant une force un peu moins brute, on n'a que 2^512 combinaisons à essayer. Cette façon-là (dite "trial division") est la méthode de factorisation la plus simple, déjà connue et considérée comme inefficace par les babyloniens il y a 3500 ans. On peut faire bien mieux. Les meilleurs algorithmes de factorisation connus ne s'expriment pas vraiment en termes de "combinaisons à essayer" mais d'aucuns tentent d'établir des correspondances.
Il y a pas mal de pointeurs sur : http://www.keylength.com/ D'où l'on tire que la "force" d'une clé RSA de 1024 bits est, à la très grosse louche, équivalente à celle d'une clé de 80 bits pour un chiffrement symétrique (i.e. 2^79 combinaisons en force brute).
Je ne cherche bien évidemment pas à casser le https, je cherche à donner des chiffres concrets sur le coût de la brute force. L'idée n'est pas de donner dans la finesse, mais montrer de manière calculatoire que le brute force est un mauvais choix.
Pour cela il suffit d'un minorant. On donne des pouvoirs surhumains à l'attaquant, et on voit qu'il ne s'en tirera pas.
Exemple : soit un PC qui essaye des clés. Essayer une clé, c'est faire un chiffrement d'un bloc, ça prend quelques centaines de cycles. Mais l'attaquant est un demi-dieu de la programmation, lui il essaye une clé en un cycle. Un PC raisonnable va avoir quatre cores cadencés à 3 GHz. Mais l'attaquant a accès à la technologie de demain (ou plutôt d'après-demain) et son PC tourne à 30 GHz avec 30 cores. Un PC coûte au moins 200 EUR mais l'attaquant est le gouvernement chinois et peut avoir des PC à 10 EUR pièce, et en acheter un milliard. On suppose également que le barrage des Trois Gorges est réquisitionné pour alimenter en courant ce milliard de PC vrombissant.
Donc, voilà notre attaquant qui peut essayer pas mal de clés par seconde ; précisément, 30*30*1000000000*1000000000 (30 cores à 30 GHz, fois 1 milliard). Avec ces moyens fortement exagérés, il lui faudrait 672 secondes pour essayer 2^79 clés, donc un peu plus de 11 minutes. Pour une clé de 128 bits, donc 2^127 combinaisons, ça fait dans les 189 millions de milliards de secondes, soit à peu près 6 milliards d'années (le système solaire est vieux d'environ 4.6 milliards d'années et le soleil devrait s'éteindre dans 5 milliards d'années). Pour une clé de 256 bits, soit 2^255 combinaisons, ça prend dans les 2038 milliards de milliards de milliards de milliards de milliards d'années.
Bref, une recherche sur 80 bits semble accessible technologiquement, dans un futur pas trop éloigné, mais avec des moyens colossaux et certainement pas discrets. Le 128 bits tient beaucoup plus de la science fiction. Le 256 bits n'est pas accessible dans cet univers, pas selon des lois de la physique classique.
--Thomas Pornin
According to Kevin Denis <kevin@alinto.comNOSPAM>:
J'ai donc deux axes d'attaques en brute force:
1/ casser l'AES256 pour lire les échanges en clair
2/ casser la clé privée du serveur distant pour décoder les échanges et
trouver la clé AES.
Première question: est-ce vrai?
La "force brute", ça consiste à attaquer une donnée secrète en essayant
toutes les combinaisons possibles. Dans le cas de SSL, il y a quelques
clés symétriques, qui dérivent d'un échange de clé qui utilise un
protocole d'échange de clé, en général un chiffrement asymétrique (en
RSA) ou un Diffie-Hellman.
Quand le chiffrement symétrique est de l'AES-256, alors la clé symétrique
correspondante fait 256 bits, donc 2^256 combinaisons. Pour un bon
algorithme de chiffrement symétrique (et il semble que l'AES soit bon),
quand on n'a pas tout, on n'a rien. Autrement dit, si on essaye quasiment
la bonne clé, mais avec un bit changé, alors on ne remarque rien. Donc
la recherche par force brute ne réussit qu'en tombant pile sur la bonne
combinaison. En moyenne on essaye la moitié des combinaisons possibles
avant de tomber sur la bonne, d'où 2^255 essais.
On peut essayer de faire la recherche sur la clé échangée. Si c'est
du RSA, alors c'est une suite de 48 octets, dont les 4 premiers sont
prévisibles (c'est l'heure courante) ; restent 44 octets aléatoires,
soit 352 bits -> là, c'est encore plus difficile que pour la clé de
256 bits de l'AES.
Il y a aussi des clés de MAC. Les MAC servent à contrôler l'intégrité
des messages échangés. Quand on utilise HMAC/SHA-1 (un cas courant en
SSL), la clé de MAC fait 160 bits ; mais :
1. ce MAC est également chiffré donc on ne peut pas faire de recherche
directe dessus (pas moyen de tester simplement si une combinaison est
valide ou pas) ;
2. même si on trouve la clé de MAC, cette clé est dérivée de la clé
maître (celle échangée en RSA ou DH) selon un processus non réversible,
donc on n'accède pas ainsi à la clé de chiffrement symétrique.
Il est nettement plus "facile" de s'attaquer au protocole d'échange de
clé. Celui-là ne peut pas utiliser les recettes usuelles du chiffrement
symétrique (i.e. on mélange tout joyeusement) parce qu'un tel protocole
met en jeu deux entités distinctes, et pour ça il faut de la structure
mathématique. Par exemple, pour RSA, il y a un grand nombre qui est
public, et qui est le produit de deux facteurs premiers (qui eux sont
privés). La connaissance des facteurs en question permet de casser le
système. Chercher des facteurs premiers d'un grand nombre peut se faire
par force brute mais c'est absurdement inefficace. Par exemple, pour
une clé RSA typique avec un grand nombre de 1024 bits, on peut représenter
les deux facteurs premiers sur un peu plus que 1024 bits (voire exactement
1024 bits si on s'y prend bien). Ça fait 2^1024 combinaisons. C'est la
force brute. Mais si on a un facteur on a l'autre (puisqu'on connaît leur
produit). Donc en faisant une force un peu moins brute, on n'a que 2^512
combinaisons à essayer. Cette façon-là (dite "trial division") est la
méthode de factorisation la plus simple, déjà connue et considérée comme
inefficace par les babyloniens il y a 3500 ans. On peut faire bien
mieux. Les meilleurs algorithmes de factorisation connus ne s'expriment
pas vraiment en termes de "combinaisons à essayer" mais d'aucuns
tentent d'établir des correspondances.
Il y a pas mal de pointeurs sur : http://www.keylength.com/
D'où l'on tire que la "force" d'une clé RSA de 1024 bits est, à la
très grosse louche, équivalente à celle d'une clé de 80 bits pour
un chiffrement symétrique (i.e. 2^79 combinaisons en force brute).
Je ne cherche bien évidemment pas à casser le https, je cherche à
donner des chiffres concrets sur le coût de la brute force. L'idée
n'est pas de donner dans la finesse, mais montrer de manière
calculatoire que le brute force est un mauvais choix.
Pour cela il suffit d'un minorant. On donne des pouvoirs surhumains
à l'attaquant, et on voit qu'il ne s'en tirera pas.
Exemple : soit un PC qui essaye des clés. Essayer une clé, c'est faire
un chiffrement d'un bloc, ça prend quelques centaines de cycles. Mais
l'attaquant est un demi-dieu de la programmation, lui il essaye une clé
en un cycle. Un PC raisonnable va avoir quatre cores cadencés à 3 GHz.
Mais l'attaquant a accès à la technologie de demain (ou plutôt
d'après-demain) et son PC tourne à 30 GHz avec 30 cores. Un PC coûte au
moins 200 EUR mais l'attaquant est le gouvernement chinois et peut avoir
des PC à 10 EUR pièce, et en acheter un milliard. On suppose également
que le barrage des Trois Gorges est réquisitionné pour alimenter en
courant ce milliard de PC vrombissant.
Donc, voilà notre attaquant qui peut essayer pas mal de clés par
seconde ; précisément, 30*30*1000000000*1000000000 (30 cores à 30 GHz,
fois 1 milliard). Avec ces moyens fortement exagérés, il lui faudrait
672 secondes pour essayer 2^79 clés, donc un peu plus de 11 minutes.
Pour une clé de 128 bits, donc 2^127 combinaisons, ça fait dans les 189
millions de milliards de secondes, soit à peu près 6 milliards d'années
(le système solaire est vieux d'environ 4.6 milliards d'années et le
soleil devrait s'éteindre dans 5 milliards d'années). Pour une clé de
256 bits, soit 2^255 combinaisons, ça prend dans les 2038 milliards de
milliards de milliards de milliards de milliards d'années.
Bref, une recherche sur 80 bits semble accessible technologiquement,
dans un futur pas trop éloigné, mais avec des moyens colossaux et
certainement pas discrets. Le 128 bits tient beaucoup plus de la science
fiction. Le 256 bits n'est pas accessible dans cet univers, pas selon
des lois de la physique classique.
J'ai donc deux axes d'attaques en brute force: 1/ casser l'AES256 pour lire les échanges en clair 2/ casser la clé privée du serveur distant pour décoder les échanges et trouver la clé AES.
Première question: est-ce vrai?
La "force brute", ça consiste à attaquer une donnée secrète en essayant toutes les combinaisons possibles. Dans le cas de SSL, il y a quelques clés symétriques, qui dérivent d'un échange de clé qui utilise un protocole d'échange de clé, en général un chiffrement asymétrique (en RSA) ou un Diffie-Hellman.
Quand le chiffrement symétrique est de l'AES-256, alors la clé symétrique correspondante fait 256 bits, donc 2^256 combinaisons. Pour un bon algorithme de chiffrement symétrique (et il semble que l'AES soit bon), quand on n'a pas tout, on n'a rien. Autrement dit, si on essaye quasiment la bonne clé, mais avec un bit changé, alors on ne remarque rien. Donc la recherche par force brute ne réussit qu'en tombant pile sur la bonne combinaison. En moyenne on essaye la moitié des combinaisons possibles avant de tomber sur la bonne, d'où 2^255 essais.
On peut essayer de faire la recherche sur la clé échangée. Si c'est du RSA, alors c'est une suite de 48 octets, dont les 4 premiers sont prévisibles (c'est l'heure courante) ; restent 44 octets aléatoires, soit 352 bits -> là, c'est encore plus difficile que pour la clé de 256 bits de l'AES.
Il y a aussi des clés de MAC. Les MAC servent à contrôler l'intégrité des messages échangés. Quand on utilise HMAC/SHA-1 (un cas courant en SSL), la clé de MAC fait 160 bits ; mais : 1. ce MAC est également chiffré donc on ne peut pas faire de recherche directe dessus (pas moyen de tester simplement si une combinaison est valide ou pas) ; 2. même si on trouve la clé de MAC, cette clé est dérivée de la clé maître (celle échangée en RSA ou DH) selon un processus non réversible, donc on n'accède pas ainsi à la clé de chiffrement symétrique.
Il est nettement plus "facile" de s'attaquer au protocole d'échange de clé. Celui-là ne peut pas utiliser les recettes usuelles du chiffrement symétrique (i.e. on mélange tout joyeusement) parce qu'un tel protocole met en jeu deux entités distinctes, et pour ça il faut de la structure mathématique. Par exemple, pour RSA, il y a un grand nombre qui est public, et qui est le produit de deux facteurs premiers (qui eux sont privés). La connaissance des facteurs en question permet de casser le système. Chercher des facteurs premiers d'un grand nombre peut se faire par force brute mais c'est absurdement inefficace. Par exemple, pour une clé RSA typique avec un grand nombre de 1024 bits, on peut représenter les deux facteurs premiers sur un peu plus que 1024 bits (voire exactement 1024 bits si on s'y prend bien). Ça fait 2^1024 combinaisons. C'est la force brute. Mais si on a un facteur on a l'autre (puisqu'on connaît leur produit). Donc en faisant une force un peu moins brute, on n'a que 2^512 combinaisons à essayer. Cette façon-là (dite "trial division") est la méthode de factorisation la plus simple, déjà connue et considérée comme inefficace par les babyloniens il y a 3500 ans. On peut faire bien mieux. Les meilleurs algorithmes de factorisation connus ne s'expriment pas vraiment en termes de "combinaisons à essayer" mais d'aucuns tentent d'établir des correspondances.
Il y a pas mal de pointeurs sur : http://www.keylength.com/ D'où l'on tire que la "force" d'une clé RSA de 1024 bits est, à la très grosse louche, équivalente à celle d'une clé de 80 bits pour un chiffrement symétrique (i.e. 2^79 combinaisons en force brute).
Je ne cherche bien évidemment pas à casser le https, je cherche à donner des chiffres concrets sur le coût de la brute force. L'idée n'est pas de donner dans la finesse, mais montrer de manière calculatoire que le brute force est un mauvais choix.
Pour cela il suffit d'un minorant. On donne des pouvoirs surhumains à l'attaquant, et on voit qu'il ne s'en tirera pas.
Exemple : soit un PC qui essaye des clés. Essayer une clé, c'est faire un chiffrement d'un bloc, ça prend quelques centaines de cycles. Mais l'attaquant est un demi-dieu de la programmation, lui il essaye une clé en un cycle. Un PC raisonnable va avoir quatre cores cadencés à 3 GHz. Mais l'attaquant a accès à la technologie de demain (ou plutôt d'après-demain) et son PC tourne à 30 GHz avec 30 cores. Un PC coûte au moins 200 EUR mais l'attaquant est le gouvernement chinois et peut avoir des PC à 10 EUR pièce, et en acheter un milliard. On suppose également que le barrage des Trois Gorges est réquisitionné pour alimenter en courant ce milliard de PC vrombissant.
Donc, voilà notre attaquant qui peut essayer pas mal de clés par seconde ; précisément, 30*30*1000000000*1000000000 (30 cores à 30 GHz, fois 1 milliard). Avec ces moyens fortement exagérés, il lui faudrait 672 secondes pour essayer 2^79 clés, donc un peu plus de 11 minutes. Pour une clé de 128 bits, donc 2^127 combinaisons, ça fait dans les 189 millions de milliards de secondes, soit à peu près 6 milliards d'années (le système solaire est vieux d'environ 4.6 milliards d'années et le soleil devrait s'éteindre dans 5 milliards d'années). Pour une clé de 256 bits, soit 2^255 combinaisons, ça prend dans les 2038 milliards de milliards de milliards de milliards de milliards d'années.
Bref, une recherche sur 80 bits semble accessible technologiquement, dans un futur pas trop éloigné, mais avec des moyens colossaux et certainement pas discrets. Le 128 bits tient beaucoup plus de la science fiction. Le 256 bits n'est pas accessible dans cet univers, pas selon des lois de la physique classique.
