Geekeries Informatique Non classé Physique Proba

Entropie des mots de passe

L’un des derniers xkcd illustre de façon assez intéressante une application de la théorie de l’information pour la mise au point de mot de passe. Quelques explications s’imposent (et on le verra, le cartoon est en fait quelque peu auto-contradictoire).

Petit historique pour commencer. Le lien profond entre les notions d’entropie physique et d’information est l’oeuvre de Claude Shannon dans les années 50, alors chercheur dans les légendaires Bell Labs. Bell, société de télécommunication, cherchait à répondre à une question simple : comment transmettre une information de façon à la fois fiable et économique. Le problème (mathématique et physique) est qu’il y a évidemment un fort compromis entre fiabilité de la transmission et son coût.

Par exemple, imaginez que vous soyez sur un réseau (téléphonique, internet …) fonctionnant de façon intermittente, et que vous ayez un message très important à transmettre. Une stratégie dans ce cas est, par exemple, pour l’émetteur, de transmettre un très grand nombre de fois le même message de façon identique à un récepteur, afin d’être certain que le récepteur, au fil du temps, parvienne à reconstituer le message complet. Mais évidemment, transmettre un grand nombre de fois le même message à un coût très important. Plus vous transmettez votre message, plus il a une chance d’être reçu, mais plus il vous en coûtera. Au contraire, si vous envoyez votre message une seule fois, il ne vous coûtera pas beaucoup à envoyer, mais vous avez une grande chance qu’il n’ait pas été reçu par le récepteur.

Dans cette image, pour une qualité de réseau donné (i.e. pour un taux de « bruit » dans les communications donné), il y a donc un nombre optimal de transmissions pour lequel le récepteur a reçu le message avec une forte probabilité. Le génie de Shannon est d’avoir réussi à trouver une façon de quantifier ce genre de processus très abstrait de transmission d’information, d’avoir trouvé une façon générique de calculer cet optimum.

L’idée de base est de quantifier l’information transmise à l’aide de la probabilité d’un message donné. Illustrons cette proposition avec une petite plaisanterie geek bien connue :

Un étranger est introduit à une fête entre des gens qui se connaissent très bien entre eux. L’un dit « 72 » et tout le monde se met à rire. Un autre dit « 29 » et l’audience se met à gronder. L’étranger demande alors ce qui se passe.

Son voisin lui répond : « Nous avons tellement de blagues et nous les avons racontées tellement de fois que maintenant, plutôt que de les répéter, nous les désignons par un simple nombre ». L’invité s’essaie donc à l’exercice, et après quelques mots dit « 63 ». L’audience réagit timidement.

« Que se passe-t-il, n’est-ce pas une plaisanterie ? » »

« Si, si, c’est une de nos meilleures, mais tu ne l’as pas bien racontée ».

(tiré de James Gleick, The Information)

Cet exemple illustre l’idée de base de Shannon : si on connaît grosso modo l’ensemble de base de signaux à transmettre (ici, les blagues), il est inutile de répéter le contenu de chaque blague à chaque fois. Il suffit de se mettre d’accord sur un encodage efficace, et on peut optimiser très fortement la transmission d’information. Un exemple très connu, construit plus ou moins empiriquement, est le Morse, dans lequel la longueur d’un caractère transmis est inversement proportionnel à sa fréquence : ainsi le « e », lettre la plus fréquente, n’est-il codé que par un point.

Shannon a trouvé la bonne façon mathématique de quantifier toutes ses notions. Prenons l’ensemble de tous les messages possibles, et attribuons-leur une probabilité. Alors la quantité d’information transmise est ce qu’on appelle l’entropie (de Shannon) de cette distribution de probabilité :

La raison pour laquelle on appelle cela « entropie » est que cette définition coincide exactement avec la notion d’entropie de Boltzmann en physique statistique. C’est bien sûr plus qu’une coincidence : un des liens est que l’entropie de Shannon quantifie l’incertitude a priori que le récepteur a sur la nature du message émis, c’est donc une forme de « désordre », comme l’entropie physique.

Exemple concret : imaginez que vous ayez un ensemble de deux messages à transmettre (par exemple un 0 et un 1), chacun avec une probabilité 1/2 . La quantité d’information est alors, en vertu de la formule ci-dessus (utilisant un logarithme en base 2) égale à 1. Pour désigner que c’est une quantité d’information, on ajoute toutefois une unité bien connu des geeks : le bit, mot inventé par Shannon himself dans son papier séminal de 1948.

Plus généralement, imaginons que notre ensemble de messages est 2 à la puissance N, et que chaque message est équiprobable. La formule ci-dessus nous donne qu’un tel ensemble contient N bits d’information.

On peut maintenant comprendre le calcul d’xkcd. Dans son dessin, chaque carré correspond à un bit d’information. Dans la première ligne, Xkcd choisit un mot « compliqué » dans l’ensemble des mots anglais (il dessine 16 bits, donc il choisit dans un ensemble de 2^16 mots). Puis il ajoute des modifs « cosmétiques » localement, mais dont le contenu informatif est relativement faible : changer une majuscule en minuscule ajoute 1 bit (puisqu’on a 2 alternatives), il ajoute quelques bits pour changer un A en 4 ou un o en 0. Et quelques bits en plus pour les caractères spéciaux au milieu, etc… Au total, il évalue l’entropie du mot de passe final à 28 bits, soit en gros un ensemble total d’environ 2^28 mots de passe possible. Ce qui reste assez petit.

Dans la deuxième ligne, Xkcd choisit 4 mots anglais parmi un ensemble courant d’environ 2^11 mots courants (environ 2000). Chaque mot compte donc pour 11 bits d’entropie, ce qui est peu comparé au cas précédent, mais le nombre de combinaisons possibles de 4 mots courants pris aléatoirement est énorme : (2^11)^4, soit 2^44 phrases de 4 mots courants, i.e. 44 bits d’entropie. En faisant la combinaison de 4 mots, on arrive donc très rapidement à un nombre de phrases possibles bien bien plus important que le nombre de mots de passe bizarroides générés précédemment. Un singe tapant à la machine a donc beaucoup plus de chances de trouver un mot de passe bizzaroide que de reproduire des séquences de 4 mots…

La dernière case de la BD pose cependant un problème. En effet, ce qui diminue mécaniquement l’entropie d’un message est sa redondance. Par xmpl vs pvz cmprndr ctt phrs qui n cmport que qqls voyelles. C’est un autre aspect mis en évidence par Shannon : le codage optimum peut exploiter la redondance des lettres, des mots, des phrases pour compresser davantage l’information. Ou, dit autrement, la quantité réelle d’information contenue est typiquement plus petite que de prime abord car la plupart des signaux comportent une part de redondance inutile. Or, le moyen mnemotechnique donné dans la dernière case est exactement un moyen d’utiliser cette redondance pour se souvenir du mot de passe. Autre exemple si vous prenez une « vraie » phrase comme mot de passe, vous n’avez de toutes évidences pas choisis les mots aléatoirement. On peut penser que c’est l’une des raisons pour lesquelles les techniciens en informatique déconseilleraient probablement de prendre des phrases de 4 mots « aléatoires » : trop de personnes prendraient de vraies phrases qui réduiraient très très considérablement l’entropie réelle des mots de passe…

Références :

Deux livres extraordinaires sur le sujet

The information, de James Gleick. Récente introduction historique à toutes ses idées, très vulgarisée. Ce fut ma lecture d’été, j’en ferai probablement une critique prochaine

The mathematical theory of Communication, de Shannon et Weaver. La référence à laquelle je reviens souvent, un peu mathématisée mais pas trop (genre niveau licence).

About the author

Tom Roud

Nanoblogger scientifique, associate professor incognito (ou presque). Suivi par @mixlamalice

5 Comments

  • La fin de l’exemple que tu prends pour illustrer l’idée de Shannon me laisse perplexe :

    “Que se passe-t-il, n’est-ce pas une plaisanterie ?” »

    “Si, si, c’est une de nos meilleures, mais tu ne l’as pas bien racontée”.

    C’est juste une boutade ou y a quelque chose à comprendre ?

  • OK, mais la conclusion ne reste-t-elle pas valable, càd composer un mot de passe à partir d’une phrase est mieux que de le faire à partir d’un seul mot !?

  • @ nqn : les deux à la fois je pense. Une boutade parce que si on code vraiment les blagues par des nombres, le ton dont on prononce le nombre n’apporte rien. Et que donc si on « raconte » mal un nombre, cela veut dire qu’il y a plus d’informations transmises que le simple nombre.

    @ médard : pour un ordi faisant de la force brute, c’est effectivement mieux (ça vient essentiellement du fait que la séquence est beaucoup plus longue). Mais on peut penser qu’un algo « intelligent » pourrait essayer de deviner des combinaisons de mots plus probables que les autres …

  • Bravo, belle explication.

    A propos de xkcd, hum, je pense qu’une des raisons pour lesquelles on recommande des mots de passe du premier type est qu’historiquement, les mots de passe sont courts…

    mais ça mérite réflexion!

Leave a Comment