retour
Lyon, le 27/10/2023
Entropie
Par pure pédanterie,
(c'est aussi un vieux fantasme)
et comme il y a quelques équations à écrire ici et là,
j'ai décidé de rédiger cet article
(dont l'intérêt est très certainement discutable)
en LaTex.
\documentclass{article}
\usepackage{comment, multicol}
\usepackage{hyperref}
\usepackage{calc,pict2e,picture}
\usepackage{textgreek,textcomp,gensymb,stix}
\setcounter{secnumdepth}{2}
\title{De l'entropie de mots de passe générés}
\author{Rédigé avec $\varheartsuit$ par Gloumouth1}
\date{2023}
\begin{document}
\maketitle
\begin{abstract}
Nous montrons dans cet article que certaines méthodes sont à éviter pour générer des mots de passe.
\end{abstract}
\section{Définitions}
Soit $S_1$, $S_2$, ..., $S_n$ n ensembles de symboles avec $n > 1$, respectant
$ \forall i, j, 1 \leq i, j \leq n, S_i \cap S_j = \emptyset $ \\
Soit $$ S = \bigcup\limits_{i=1}^{n} S_i $$
Soit $a_1$, $a_2$, ..., $a_n$ tel que $ \forall i, 1 \leq i \leq n, a_i = \text{card}(S_i) $ \\
Soit $$A = \sum_{i=1}^{n} a_i$$
Soit $B$ le nombre de symboles contenus dans le mot de passe à générer.
\section{Algorithmes}
Dans cette section nous évoquerons plusieurs algorithmes de génération de mot de passe. \\
\subsection{Algorithme 1}
La première méthode consiste simplement à tirer au sort successivement les caractères dans S.
L'entropie du mot de passe vaut ici
$$ H(P_1) = B \log_2{A} $$
\subsection{Algorithme 2}
L'algorithme de génération consiste ici à générer un nombre fixé de caractères de chaque type.\\
Soient $b_1$, $b_2$, ..., $b_n$ tels que $b_i$ le nombre de caractères de $ S_i $ contenu dans le mot de passe
généré avec cet algorithme.
Remarquons que $$B = \sum_{i=1}^{n} b_i$$
L'entropie pour le choix des caractères de l'ensemble $ S_i $ vaut $ b_i \log_2(a_i) $, donc pour les n $ S_i $,
on obtient
$ \sum_{i=1}^{n} b_i \log_2(a_i) $
Vient ensuite la position des caractères de chacun des caractères de $ S_i $. \\
Le choix pour les caractères de $S_1$ apporte l'entropie
$$ \log_2(C_B^{b_1}) $$
Le choix pour $S_2$ apporte l'entropie
$$ \log_2(C_{B-b_1}^{b_2}) $$
Le choix pour $S_3$ apporte l'entropie
$$ \log_2(C_{B-b_1-b_2}^{b_3}) $$
Plus généralement, pour $S_i$ l'apport d'entropie est de
$$ \log_2(C_{B-\sum_{k=1}^{i-1} b_k}^{b_i}) $$
L'apport entropique du choix de la position des $S_i$ dans le mot de passe est donc
$$ \log_2(C_B^{b_1} C_{B-b_1}^{b_2} C_{B-b_1-b_2}^{b_3} \ldots C_{B-b_1-b_2-\ldots-b_{n-1}}^{b_n}) $$
$$ = \log_2(\frac{B!}{b_1!(B-b_1)!}. \frac{(B-b_1)!}{b_2!(B-b_1-b_2)!}.\frac{(B-b_1-b_2)!}{b_3!(B-b_1-b_2-b_3)!}.
\ldots. \frac{(B-b_1-b_2-\ldots-b_{n-1})!}{b_n!(B-b_1-b_2-\ldots-b_n)!} ) $$
$$ = \log_2(\frac{B!}{\prod_{i=1}^n b_i!}) $$
L'entropie vaut ici $$ H(P_2) = \sum_{i=1}^{n} b_i \log_2(a_i) + \log_2{\frac{B!}{\prod_{i=1}^n b_i!}} $$
\subsection{Algorithme 3}
L'algorithme consiste ici en la génération aléatoire de caractères dont chaque type a une position fixe.
L'entropie globale vaut donc plus simplement
$$ H(P_3) = \sum_{i=1}^{n} b_i \log_2(a_i) $$
\section{Applications numériques}
Prenons le cas de la génération d'un mot de passe de longueur 17, contenant des majuscules, des minuscules et des
chiffres.
Dans ce cas
$ S_1 = \{ 'a', 'b', \ldots, 'z' \} $,
$ S_2 = \{ 'A', 'B', \ldots, 'Z' \} $,
$ S_3 = \{ '0', '1', \ldots, '9' \} $ \\
Donc
$ a_1 = 26 $,
$ a_2 = 26 $,
$ a_3 = 10 $ et
$ A = 62 $\\
Prenons les hypothèses suivantes :
$ b_1 = 13 $,
$ b_2 = 2 $,
$ b_3 = 2 $ et
$ B = 17 $\\
Les entropies valent donc
$$
\begin{align*}
H(P_1) &= 17 \log_2{62} \\
&\approx 101,22 \text{ bits} \\
H(P_2) &= 26 \log_2(13) + 26 \log_2(2) + 10 \log_2(2) + \log_2{\frac{17!}{13! \ 2! \ 2!}} \\
&\approx 90,95 \text{ bits} \\
H(P_3) &= 26 \log_2(13) + 26 \log_2(2) + 10 \log_2(2) \\
&\approx 77,15 \text{ bits} \\
\end{align*}
$$
On voit donc que l'entropie de $P_1$ dépasse les 100 bits, ce qui selon l'ANSSI (Agence nationale de sécurité des
systèmes d'information)
est considéré comme un mot de passe fort, alors que $P_2$ est moyen et $P_3$ faible selon les critères de la même
agence, bien qu'ayant la même taille et les mêmes caractères possibles.
La méthode de génération seule fait toute la différence.
\section{Conjecture}
Nous proposons la conjecture suivante :\\
$$ H(P_1) > H(P_2) > H(P_3) $$
Ce qui revient à prouver que
$$ (\sum_{i=1}^{n} b_i) \log_2(\sum_{i=1}^{n} a_i) >
\log_2((\sum_{i=1}^{n} b_i)! \prod_{i=1}^n \frac{{a_i}^{b_i}}{b_i!}) >
\log_2(\prod_{i=1}^n {a_i}^{b_i}) $$
Ou encore
$$ {(\sum_{i=1}^{n} a_i)}^{(\sum_{i=1}^{n} b_i)} >
(\sum_{i=1}^{n} b_i)! \prod_{i=1}^n \frac{{a_i}^{b_i}}{b_i!} >
\prod_{i=1}^n {a_i}^{b_i} $$
Comme vu plus haut, la deuxième inégalité peut se reformuler comme suit :
$$ \prod_{i=1}^n C_{\sum_{k=i}^{n} b_k}^{b_i} . \prod_{i=1}^n {a_i}^{b_i} > \prod_{i=1}^n {a_i}^{b_i} $$
Ce qui permet de conduire aisément au résultat, mais pour la première inégalité, on va pas s'mentir, je vois pas
trop, et j'ai la flemme.
\section{Conclusion}
L'algorithme maximisant l'entropie parmi ceux parcourus dans cet article est probablement toujours le premier,
c'est-à-dire celui
qui consiste à choisir de manière équiprobable chacun des caractères indépendemment.
S'il est mal conçu, un algorithme peut générer des mots de passe d'entropie significativement plus faible,
donc plus vulnérables à une attaque comme l'a montré une application numérique.
Cependant, il reste à en apporter la preuve dans le cas général.
\end{document}
\\
\\
Mouais, où est la bibliographie ?
Ca donne une idée du sérieux de la démarche...
En tout cas ok,
LaTeX, c'est joli.
D'autant plus joli
que le rendu est exécuté
à la volée par votre navigateur
grâce à la librairie latex.js
Par ailleurs,
Pour la déconne,
j'ai posé la question à GPT-4.
Et je dois admettre que
si on fait abstraction d'une (petite) erreur de calcul à la fin,
le raisonnement est parfatiement exact.
Et je me demande s'il n'explique pas les choses
beaucoup plus clairement que moi.
Petit calculateur que j'ai écrit : ici
Article de l'ANSSI sur la force des mots de passe : ici
retour