Après avoir risqué l’Apocalypse en expliquant la différence entre chiffrer et crypter, et ne reculant devant aucun danger, j’ai décidé d’aborder aujourd’hui l’un des buzzword les plus sexy et les plus fondamentaux de la sécurité informatique, « l’entropie »…

« Nobody knows what entropy really is. »

John von Neumann d’après « Information Theory and Evolution »

L’entropie est définie initialement en thermodynamique pour quantifier le désordre dans un système et la deuxième loi stipule qu’elle ne peut qu’augmenter. Ainsi, elle évoque à la fois théorie du chaos et secrets fondamental de l’Univers. Le genre de terme utilisé par les vrais pros, ceux qui voient la matrice au delà du tissu de la réalité.

En informatique, on utilise aussi l’entropie pour quantifier le désordre, sauf qu’on parle plutôt « d’incertitude sur l’information ». On l’utilise donc chaque fois qu’on veut qualifier des mots de passes, des clés cryptographiques, des identifiants de session ou encore lorsqu’on cherche à identifier le type d’un contenu.

C’est un concept fondamental et passionnant (lors qu’on aime ce genre de chose) mais paradoxalement rarement enseigné. Vous l’entendrez donc utilisé plus ou moins hors de propos par des imposteurs qui n’ont pas vraiment compris de quoi il s’agit mais veulent briller en société en impressionnant des néophytes.

Note : J’avais déjà écrit un article sur le sujet en 2020 pour expliquer de quoi il s’agit mais alors que je le relisais (pour ensuite le traduire en anglais) je me suis rendu compte qu’il était encore trop théorique et méritait une réécriture pour le rendre plus accessible. La voici…

Qu’est-ce qu’une information ?

Pour quantifier quelque chose, encore faut-il savoir de quoi il s’agit. Vous pourriez croire que la réponse est triviale mais elle mérite des précisions pour éviter l’erreur courante qui consiste confondre « information » et « donnée ».

Pour faire simple (car ce sujet mériterait un article à part entière), la nuance est au cœur du Guide du voyageur galactique. Mais comme je vous sens pressés, voici un résumé de cette parabole :

Pensée Profonde, le deuxième plus grand ordinateur de tous les temps, mit près de sept million et demi d’années de calculs intensifs pour finalement fournir la réponse ultime : « 42 ».

Face à l’incompréhension et la frustration générale du public, Pensée Profonde précisa que le problème était qu’ils n’avaient jamais vraiment bien saisi la question et qu’un deuxième ordinateur pourrait la fournir.

Après maintes péripéties, Arthur Dent finit par la découvrir : « Six fois neuf ? Quarante-deux. » ce qui résout ainsi la grande question sur la vie, l’Univers et le reste.

Ainsi, lorsque Pensée Profonde fourni la réponse « 42 », elle est évidement incompréhensible car sans contexte, on ne sait pas de quoi il s’agit (e.g. un département, une température, une mensuration…). Cette donnée ne nous informe pas le moins du monde.

Ce n’est qu’en retrouvant la question qu’Arthur Dent donne un sens à 42, qui est ici la solution d’une équation ($x = 6 \times 9$). C’est dans cette relation à une question qu’une donnée devient une information.

Quantité intuitive d’information

Nous rentrerons dans les détails dans la suite mais pour l’instant, vous sentez déjà que toutes les réponses ne sont pas équivalentes et ne vous informent pas autant les unes que les autres. Certaines contiennent plus d’information que d’autres.

À quoi on les distingue ? L’élément déterminant, c’est le nombre d’alternatives. Plus une question a de réponses possible, plus chacune d’entre elle va vous renseigner, vous informer.

Par exemple, si vous vous demandez où une personne est née. Je peux vous donner le nom du département (90 alternatives) mais vous ne serez pas beaucoup avancé. Vous en sauriez plus avec le nom de la commune (36 528 alternatives) et encore plus avec l’adresse postale (25 million d’alternatives dans la Base d’Adresse Nationale).

De manière analogue, enchaîner des questions permet de cumuler l’information des réponses successives. Si après vous avoir dit l’endroit je vous renseigne sur la date, puis si c’était par voie basse et ainsi de suite, vous auriez de plus en plus d’information sur cet événement.

Quelle échelle de mesure ?

La quantité d’information étant dans le nombre de possibilités, pourrait-on utiliser ce nombre d’alternatives directement comme quantité d’information ?

Pour une seule question, ça marche pas trop mal. Entre le département et l’année de naissance, on sent que ces réponses se valent et effectivement les nombres de possibilités sont proches (90 départements et 100 années).

Premier problème pour s’échauffer avec les réponses qui se précisent les unes les autres. Si après vous avoir dit le département je vous dit la commune de naissance puis l’adresse, on passe de 91 départements à 36 529 communes puis 25 000 000 adresses. Avez-vous eu l’impression d’obtenir 36 438 information de plus lorsque j’ai précisé la commune ? Puis 24 963 471 informations de plus avec l’adresse ?

Second problème (qui permettra de définir une échelle) lorsqu’on cumule les questions différentes. Si après vous avoir dit le département je vous dit l’année de naissance, on passe de 100 départements possibles à 9000 couples départements et années possibles. Avez-vous l’impression d’avoir multiplié votre capital informationnel par 100 ?

Le truc, c’est que lorsqu’on pose plusieurs questions indépendantes, chaque nouvelle réponse multiplie le nombre de possibilités mais intuitivement on a plutôt l’impression que ces informations s’additionnent.

Et ça tombe bien, il y a une fonction mathématique qui transforme les produits en sommes ; le logarithme : $$\log (a \times b) = \log(a) + \log(b)$$ En utilisant le logarithme du nombre de possibilités (plutôt que ce nombre directement), la quantité d’information de chaque réponse va maintenant s’ajouter à la quantité d’information des réponses précédentes.

Pour l’exemple, voici la quantité d’information en calculant le logarithme du nombre de possibilités de réponses :

Pour vous montrer que ces quantités d’informations sont plus intuitives, voici ce qu’elles donnent pour les deux problèmes précédents :

• Lorsque les réponses se précisent. Avec le département, vous aviez 1,95 quantité d’informations. On monte à 4,56 en ajoutant la commune (qui vaut donc 2,61) ; ajouter l’adresse en ajoute enfin 2,83 de plus. Passer du département à la commune, puis de la commune à l’adresse contient à peu près autant d’information.
• Lorsque les questions s’enchaînent. Avec le département vous avez 1,95 quantités d’information et vous en ajoutez 2 avec l’année ce qui double à peu près le total.

Unité et codage

L’étape suivante est de trouver une unité de mesure. C’est à la fois une question de déterminer la signification de la mesure et des étalons comparatifs.

Par exemple, le poids dit combien c’est lourd et si je vous dit 1Kg vous pouvez comparer à une brique de lait. Si je vous dit qu’un objet est à 2m de vous ça vous dit combien c’est loin et vous pouvez visualiser la longueur d’une table.

Intuitivement, la quantité d’information désigne l’effort que ça prend pour s’en souvenir, la place que ça prend dans notre mémoire et depuis qu’on a inventé l’écriture, la place que ça prend pour l’écrire et éviter de devoir s’en souvenir.

D’où la définition plus formelle que voici :

La quantité d’information est le nombre de caractères pour la coder.

Et ce qui tombe bien, c’est que le logarithme fait exactement ça, compter le nombre de caractères pour coder un nombre d’alternatives.

Pour vous en convaincre comptez les nombres que vous pouvez écrire avec des chiffres. Si vous utilisez 2 chiffres vous pouvez écrire 100 nombres (00 à 99). De manière générale, si vous utilisez $n$ chiffres, vous écrirez $10^n$ nombres. Le logarithme, par définition, c’est le calcul inverse, sachant le résultat du calcul précédent (le nombre d’éléments codés, ici $10^n$), retrouver l’exposant (le nombre de chiffres utilisés, ici $n$).

Sur les exemples précédents, la base 10 fourni des mesures en chiffres adaptée à nos représentations :

• Les 91 départements pourraient n’utiliser que 1,95 chiffres mais comme on ne peut pas utiliser des morceaux de chiffres, on les code avec 2 chiffres (en oubliant les détails),
• Les 36529 communes pourraient n’utiliser que 4,56 chiffres mais pour la même raison, on en utilise 5.
• D’où le code commune qui en utilise deux pour le départements ($1,95$ arrondi au supérieur) et 3 pour la commune dans le département ($4,56 - 1,95 = 2,61$ qu’on peut arrondir à 3).

On peut aussi utiliser d’autres bases pour le logarithme, correspondant à d’autres alphabets. Par exemple, en base 26 on calcule la quantité d’informations en lettres et en base 2, la quantité en bits.

Informations biaisée

Il est maintenant temps de considérer une autre intuition que j’avais passé sous silence : que pour une même question, au sein du même groupe d’alternatives, certaines réponses vous paraissent porter plus d’information que d’autres.

Par exemple, prenons la commune de naissance. Ou pour être exact, la commune de résidence de la mère pour les enfants nés de 2014 à 2021 car cette statistique est publiée par l’INSEE.

Si je vous répond Paris ça ne vous étonne pas tellement (219 911 naissances comptabilisées) et vous auriez eu plus d’information si je vous avait dit Trouville (51 naissances) ou plus encore avec Gouy-les-Groseillers (1 seule naissance).

L’idée est que sur les 6 145 484 naissances possibles (à la question « qui est cette personne née entre 2014 à 2021 »), le lieu de résidence de la mère répond en partie à la question en laissant une marge d’incertitude, un nombre d’alternatives qu’il reste à déterminer, et donc une information qu’il vous manque pour tout savoir.

Mathématiquement, on suit cette intuition ; on prend l’information disponible (logarithme du nombre des naissances) à laquelle on retranche l’information inconnue (logarithme du nombre de naissances dans la commune).

Le tableau suivant vous donne les valeurs (en bits) pour les communes de l’exemple :

Et ici encore il y a un lien avec le codage de l’information. Par rapport au code précédent à 5 chiffres (soit 16 bits), on peut compresser l’ensemble en utilisant ces nouvelles mesures pour raccourcir le codage des communes les plus fréquentes (5 bits pour Paris ce qui en fait gagner 11 à chaque fois) et allonger celui des plus rares (23 bits pour Gouy-les-Groseillers mais il ne servira qu’une fois).

Détail qui a son importance, formellement on parle en fait « d’information propre » d’un événement (e.g. « être né entre 2014 et 2021 d’une mère domiciliée à Trouville ») et plutôt que de la calculer comme la différence entre l’information totale et l’information résiduelle, on l’exprimer via la probabilité de l’événement (notée $p_x$) : $$I(x) = - \log p_x$$ Mais magie des logarithmes, c’est exactement la même chose que notre calcul précédent qui utilisait le nombre total d’alternatives (noté $n$) et le nombre d’alternatives restantes restante pour la réponse (noté $n_x$) : $$\begin{align} I(x) & = - \log p_x \\ & = - \log n_x / n \\ & = \log n - \log n_x \end{align}$$

Vous pouvez donc utiliser et considérer les deux façons de voire, elles sont équivalentes.

L’entropie, moyenne des réponses

On dispose maintenant de tous les outils nécessaires pour aborder la notion d’entropie.

C’est assez simple, plutôt que de se demander quelle information il y a dans une réponse, on se demande combien on peut espérer d’information en posant une question. Et pour ça, on va calculer la moyenne pondérée de l’information des réponses (les matheux disent « l’espérance »). $$H = \sum p_x I(x) = - \sum p_x \log p_x$$ Par exemple, si on reprend le lieu de naissance (ou plutôt le lieu de résidence de la mère des enfants nés entre 2014 et 2021) ; on peut espérer 12 bits d’information si on demande le nom de la commune et 6,15 bits d’information si on demande le département. Parfois on a la chance d’en obtenir plus (e.g. Gouy-les-Groseillers), parfois on en obtient moins (e.g. Paris) mais sur le long terme, on converge vers la moyenne.

Si vous deviez deviner quelque chose et avez le choix entre plusieurs questions, celle ayant la plus grande entropie vous donnera en moyenne plus d’information que les autres. Certains disent qu’elle est de meilleure qualité.

Et maintenant ?

L’entropie a été initialement définie pour mesurer la quantité d’information émise par un émetteur et déterminer le débit d’information de cette source. En particulier, l’entropie fourni un minimum pour la taille moyenne des informations transmise (avec moins de caractères on perdrait quelque chose).

Par exemple, même si on peut coder les noms des communes avec 5 chiffres ou 15,15 bits, si on sait qu’il s’agit du lieu de résidence de la mère, on peut descendre à une moyenne de 12,15 bits par commune. Soit un gain de 20% en moyenne. Mais on ne pourra pas faire moins sans perdre de l’information.

Pour revenir à la sécurité informatique, l’entropie permet également de mesurer la qualité d’une source d’information aléatoire car elle est maximale si les messages sont équiprobables et diminue dès que certains sont plus ou moins fréquents.

Plus l’entropie est élevée, mieux c’est. Le maximum étant atteint lorsque les réponses sont équiprobables. Attention cependant car une faible entropie est bien un signe d’un mauvais générateur mais l’inverse n’est pas vrai, des générateurs tout pourris peuvent avoir une bonne entropie sans être de qualité.

Petite précision pour ces générateurs et leur réserve d’aléatoire. En tant qu’utilisateur, c’est une source, donc on peut parler d’entropie présente dans la réserve (incertitude sur ce qu’il va me fournir). Mais du point de vue du système, les bits sont déjà là et prêts à sortir et on devrait donc parler d’information présente dans la réserve. L’usage a privilégié le point de vue de l’utilisateur.

On peut alors parler de l’entropie d’un générateur de mot de passe, d’un générateur de clés ou d’un générateur d’identifiants de sessions ce qui nous informe sur la difficulté de deviner la valeur que ces générateurs vont fournir.

Par contre, parler de l’entropie d’un mot de passe est un abus de langage qui oublie qu’il y a un générateur dans l’histoire.

Là où crypter et chiffrer permettent aux élites de se distinguer de la plèbe, l’entropie permet aux professionnels de détecter les imposteurs.