Discussion :

[Stéphane le calme]

Les systèmes de chiffrement moins sécurisés que nous le pensions ?
Ils reposeraient sur une fausse supposition mathématique vieille de 65 ans

Des scientifiques américains et irlandais ont fait une avancée dans la théorie moderne de l'information, une branche des mathématiques qui a été utilisée pour démontrer la puissance des systèmes de chiffrement avant leur déploiement à grande échelle.

Le résultat de leurs recherches est que, bien que déchiffrer des fichiers demeure une tâche ardue, il est moins difficile de déduire le contenu des fichiers chiffrés qu'on pourrait l'imaginer.

La théorie de l'information reposait sur les recherches de Claude Shannon publiées en 1948 qui ont apporté l'entropie de Shannon, fonction mathématique qui, intuitivement, correspond à la quantité d'information contenue ou délivrée par une source d'information. Cette source peut être un texte écrit dans une langue donnée, un signal électrique ou encore un fichier informatique quelconque.

Du côté des algorithmes de chiffrement modernes, une analyse a révélé qu'ils supposent que ces sources d'information sont parfaitement uniformes et qu'une combinaison de données binaires de 1 et 0 est parfaitement aléatoire et imprévisible.

En réalité, ce n'est pas totalement vrai ; une partie des fichiers peut être devinée et les octets ainsi trouvés pourront créer un passage au déchiffrement brutal. « C'est toujours difficile, mais exponentiellement plus aisé que nous le pensions. » explique Ken Duffy, de la National University of Ireland (NUI), qui a coécrit les résultats de ces recherches. « Les attaquants utilisent souvent des processeurs graphiques pour scinder le problème. Vous seriez surpris de voir à quelle vitesse vous pouvez deviner des choses ».

Trois autres chercheurs du MIT et du NUI présenteront avec Duffy leurs travaux sous l'intitulé « Brute force searching, the typical set and guesswork » au Symposium International de la théorie de l'information. Par la suite, un document devrait paraître cet automne pendant la conférence Asilomar sur les Signaux et Systèmes pour démontrer que les portes faisant usage de clés magnétiques sont moins sécurisées qu'il n'y parait.

Sources : MIT, étude (au format PDF), travaux de Claude Shannon, introduction à la notion d'entropie de Claude Shannon

Et vous ?

A la lumière de ces recherches, pensez-vous que les systèmes de chiffrement soient fondamentalement moins sécurisés ?

[Kaluza]

Dans le même genre, si on s'aperçoit un jour que l'hypothèse de Riemann est fausse, ça risque de mettre une sacré pagaille dans un paquets d'algo actuellement utilisés tournant autour de la primalité...

[pvincent]

si on s'aperçoit un jour que l'hypothèse de Riemann est fausse...

Apparemment l'hypothèse de Riemann a déjà excité pas mal de monde et on trouve trois types de publications dont aucune n'est validée par la communauté des mathématiciens:
(http://empslocal.ex.ac.uk/people/sta...a/RHproofs.htm)

Ceux qui disent l'avoir démontrée
Ceux qui disent avoir démontré qu'elle est fausse,
Ceux qui disent avoir démontré qu'elle est indémontrable, i.e. à prendre comme un axiome.

Il y a quand même un million de dollars US à la clé (http://fr.wikipedia.org/wiki/Probl%C...ill%C3%A9naire)

[Ekleog]

Du côté des algorithmes de chiffrements modernes, une analyse a révélé qu'ils assument que ces sources d'informations sont parfaitement uniformes et qu'une combinaison de données binaires de 1 et 0 est parfaitement aléatoire et imprévisible.

En réalité, ce n'est pas totalement vrai ; une partie des fichiers peut être devinée et les octets ainsi trouvés pourront créer un passage au déchiffrement brutal.

Euh... Si je traduis en langage usuel, ça veut dire, grosso modo, que les mauvais générateurs de nombres aléatoires sont une faille de sécurité ?

Parce que, si c'est ça, alors ce n'est pas tellement une nouveauté, et il a toujours été clairement indiqué que le PRNG est un point particulièrement faible du dispositif.

EDIT 2: Finalement, après avoir survolé l'article, c'est visiblement simplement que, si tous les messages n'ont pas la même probabilité, on peut tenter de deviner des bouts d'information petit à petit. En gros, ça se résume, si j'ai bien compris, à étendre une analyse fréquentielle à des chiffrements qui sont plus riches que le simple chiffre de césar. Après, je parle un peu sans savoir, mais il me semble que ça reste assez invraisemblable à appliquer, et qu'il n'y a pas à craindre, pour le moment, quoi que ce soit pour les méthodes de chiffrement actuelles.

EDIT 4: Cette supposition de l'extension de l'analyse fréquentielle est supportée par l'article anglais :

One implication is that an attacker who simply relied on the frequencies with which letters occur in English words could probably guess a user-selected password much more quickly than was previously thought.

« C'est toujours difficile, mais exponentiellement plus aisé que nous le pensions. »

Étant donné que la plupart des agorithmes de chiffrement (soyons vagues et ne donnons pas de nom, j'admets volontiers ne pas avoir le temps de lire les articles complets) se cryptanalysent en temps exponentiel, cette affirmation a trois sens possibles. Soit ils les cryptanalysent en temps polynomial, ce que j'aurais du mal à croire : la méthode de chiffrement serait cassée. Soit ils les cryptanalysent en temps exponentiel, avec une constante inférieure, et peuvent alors dire « exponentiellement plus aisé », car ils ont soustrait une exponentielle. Soit ils les cryptanalysent en temps exponentiel avec une constante sous l'exponentielle plus petite, ce qui me semble être le mieux qu'ils puissent faire sans déclencher un tollé monstre, et on a toujours de l'exponentielle, ce qui fait qu'avec la taille des clés, le gain est certes énorme mais probablement absolument pas suffisant pour déchiffrer en temps raisonnable.

EDIT 1: Finalement j'ai lu l'abstract, et c'est bien la troisième option qui semble être réalisée.

EDIT 3: La lecture de l'article anglais valide que c'est bien la troisième option, en disant explicitement que c'est toujours « exponentially hard ».

A la lumière de ces recherches, pensez-vous que les systèmes de chiffrement soient fondamentalement moins sécurisés ?

Je ne le pense pas. Principalement parce que le PEBKAC est la première source de faille cryptographique : il sera très souvent plus simple de molester l'utilisateur pour récupérer sa clé secrète que de casser le chiffrement.

EDIT 5: D'ailleurs, l'article anglais m'approuve :

Bloch doubts that the failure of the uniformity assumption means that cryptographic systems in wide use today are fundamentally insecure. “My guess is that it will show that some of them are slightly less secure than we had hoped, but usually in the process, we’ll also figure out a way of patching them,”

Et il ne faut pas oublier que « slightly less secure » reste probablement plusieurs centaines de fois notre durée de vie -- voire plusieurs fois la durée de vie de l'espèce humaine. (statistiques de forum, mais c'est l'ordre de grandeur qui compte, et je crois sous-estimer)

[MRick]

Ce que je comprend, ce n'est pas que les algorithmes de chiffrements soient moins costaud, mais plutôt que les techniques de déchiffrement se sont améliorées.

Face a un véritable brute force de base, les algos restent les mêmes.

Ce qui se passe, c'est qu'en mettant un peu de finesse dans les logiciels de brute-force on améliore significativement leur efficacité.


Cela revient à dire que si on connait certaines caractéristiques qui distinguent le message chiffré d'une liste de bits aléatoires, le déchiffrement est plus aisé.

Par exemple on sait très bien que si le message chiffré est du texte, les octets ayant les valeurs ASCII de "A" à "Z" et de "a" à "z" ont bien plus de chances de sortir que les autres valeurs.

Si on sait que le fichier chiffré est un exécutable DOS, on sait qu'on doit déchiffrer un "MZ" au début.

Si on sait qu'on doit déchiffrer une image JPEG, on sait ce qui doit se trouver dans les premiers octets.

Ce que je cite sont des cas particuliers, mais toujours si j'ai bien compris nos chercheurs ont démontré que ça pouvais être généralisé.
En d'autres termes, toutes les données à chiffrer possèdent des caractéristique particulières qui les distingue de la simple suite de bits aléatoires.
Ce simple fait rend leur déchiffrage un peu plus simple que ce que la théorie prévoit.

[gangsoleil]

Bonjour,

Il est aussi interessant de noter que le papier a ete publie dans une conference sur la theorie de l'information, pas dans une conference de cryptographie...

Par manque de connaissances cryptographiques dans le comite ? C'est en tout cas l'avis de B. Schneier, un ponte de la securite.

[Jérôme Collet]

La technique citée est-elle encore valable pour des documents compressés puis cryptés ?

En effet, la technique repose sur des écarts à l'indépendance entre bits successifs. Mais un tel écart est aussi une perte de place, et disparaît donc quand on compresse. D'où ma question.

[Pelote2012]

Et s'il n'y avait que dans ce domaine qu'on reste sur des théories des années 50... Même en médecine on rencontre le problème. Notemment sur certains taux en dessous duquel on vous transfuse, ils ont été mis en évidence pendant la 2nd gurerre mondial, sauf qu'aujourd'hui des étude montre que ces taux sont trop élevés, qu'on pourrait les baisser ... mais pas forcément intéressant pour tout le monde ...

J'espère qu'on ne sera pas victime de ce genre de phénomène en informatique

[n5Rzn1D9dC]

Si ça se trouve la nsa ou certaines corporations à revenus non modérés sont déjà capables de casser n'importe quel cryptage car elles disposent d'un ordinateur quantique personnel.

[Ekleog]

Si ça se trouve la nsa ou certaines corporations à revenus non modérés sont déjà capables de casser n'importe quel cryptage car elles disposent d'un ordinateur quantique personnel.

Un ordinateur quantique permettrait (en théorie) de factoriser en temps polynomial. Ce qui ne signifie absolument pas que ça serait en un temps raisonnable.

En effet, l'algorithme de Shor (le seul dont j'aie entendu parler) n'a pour l'instant pas réussi (par manque de matériel) à factoriser un nombre supérieur à 21. Et je ne crois pas qu'IBM soit une corporation à revenus modérés.

Qui plus est, je crois que l'existence d'un ordinateur quantique capable de factoriser du 2048 bits (taille minimale d'une clef RSA recommandée par gnupg), c'est-à-dire plus de 450 fois plus *longue* (et plus de 100.000.000 fois plus performant, l'algorithme de Shor étant en n³ -- « précisément », 466.27 et 101369826.40), passerait encore moins inaperçu que PRISM.

Donc arrêtons ici la théorie du complot.

[n5Rzn1D9dC]

Il y a encore peu de temps, quelqu'un qui aurait insinué que la NSA avait un tel systême d'écoute serait passé pour un parano, voir même pour un fou bon à être enfermé si il aurait découvert une preuve et qu'il en aurait parlé à une personne lambda.

Ce qui est certain c'est que si la NSA disposerait d'un ordinateur quantique (et non les proto à quelques qubits dont on entend parler depuis quelques années), on n'en saurait rien. Ca ne serait pas dans leur intêret.

Je ne sais pas si vous lisez les documents déclassés de ces agences (NSA, NASA,CIA), je ne vais pas en parler ici car ce n'est pas le sujet, mais il y a des trucs de dingue..