Entropie d'un mot de passe: précisions demandées, et question posée

According to Jerry Khann <jerry_O_khann@freesurf.fr.invalid>:

Je crois me souvenir que l'on peut mesurer la "résistance" d'un mot
de passe grâce à son entropie: "myosotis" aurait une entropie faible
(voire nulle), tandis que "{j5k[OI1" aurait une entropie forte (voire
infinie?) car beaucoup plus difficile à "trouver par hasard" et jamais
par une "attaque via dictionnaire".

(Note : je parle ici de l'entropie telle que définie en cryptographie,
et non de l'entropie thermodynamique que connaissent les physiciens :
le nom est le même mais ça ne désigne pas du tout la même chose.)

La "vraie" définition de l'entropie est relative. En gros, elle mesure
la difficulté qu'un attaquant aurait à "deviner" le mot de passe.
Mais ça dépend pas mal de l'attaquant et de la victime, et de ce que
l'attaquant sait sur la victime. Par exemple, si la victime est un
passionné de mythologie antique du Moyen-Orient, il peut utiliser le mot
de passe "enkildu". Ce mot de passe a une entropie relativement élevée,
sauf pour un attaquant qui est au courant des goûts de la victime.

Autrement dit, il est très difficile d'évaluer l'entropie d'un mot de
passe issu d'un moyen mnémotechnique. Si on prend une très longue phrase
"classique", l'attaquant pourra essayer des dictionnaires de citations
et tous les poèmes de Verlaine (pour reprendre un exemple célèbre).


Pour obtenir un bon mot de passe, je préfère une méthode consistant
à en tirer un au hasard _puis_ à trouver le moyen mnémotechnique qui
me premettra de m'en souvenir. Il est beaucoup plus facile, alors,
d'estimer l'entropie : je sais combien de mots de passe différents
le générateur aurait pu fournir, et tous ces mots de passe sont
équiprobables. Ainsi, avec un générateur(*) qui me sort des mots de
passe de 8 caractères, où chaque caractère est une lettre minuscule, une
lettre majuscule, un chiffre, un + ou un / (64 possibilités), alors il
y a 2^48 mots possibles, d'où une entropie de "48 bits". Un attaquant
cherchant à trouver un tel mot devra en essayer en moyenne 2^47.

Mon fournisseur d'accès Internet choisit lui aussi des mots de passe
(pour les connexions ADSL notamment, et le serveur FTP pour les pages
web perso), selon le modèle "deux lettres minuscules, deux chiffres,
deux lettres minuscules, deux chiffres", ce qui fait environ 4.5
milliards de possibilités : un peu plus de 32 bits d'entropie. À
l'usage, de tels mots de passe sont faciles à retenir (comme un numéro
de téléphone, par exemple). D'ailleurs, c'est ça le truc principal pour
ne pas oublier un mot de passe : le taper souvent.


Après, tout dépend du modèle d'attaque. Pour un mot de passe protégeant
l'accès à une machine Unix sur une console ou via SSH, une entropie
de 32 bits est plus que suffisante : on est dans un cas où l'attaque
est dite "en ligne", c'est-à-dire que l'attaquant doit interroger un
système (honnête par construction) pour chaque essai. Ce système n'a
qu'à limiter arbitrairement le rythme des essais (par exemple, toujours
prendre au moins un dixième de seconde avant de répondre).

En revanche, pour un message chiffré symétriquement par mot de passe et
envoyé par mail, c'est plus dur : l'attaquant peut essayer des mots de
passe "hors ligne" et n'est limité que par la puissance de ses propres
ordinateurs. Mieux vaut une entropie d'au moins 80 bits dans ce cas, si
les données sont vraiment confidentielles.


--Thomas Pornin

(*) Sous Linux, FreeBSD ou n'importe quel unixoïde du même tonneau,
disposant d'un PRNG nommé /dev/urandom, et d'OpenSSL, voilà un tel
générateur :
dd if=/dev/urandom bs=6 count=1 2>/dev/null | openssl base64 -a -e

Thomas Pornin <pornin@nerim.net> wrote:

[snip les explications]

Voilà un poste intéressant et pédagogique :-)
Je suis moi-même étudiant en physique et j'avais été plutôt intrigué de
lire le mot « entropie » :-)

(*) Sous Linux, FreeBSD ou n'importe quel unixoïde du même tonneau,
disposant d'un PRNG nommé /dev/urandom, et d'OpenSSL, voilà un tel
générateur :
dd if=/dev/urandom bs=6 count=1 2>/dev/null | openssl base64 -a -e

Je viens de tester.
Ça marche aussi sous MacOS X.

Est-ce que tu pourrais expliquer en quelques mots comment ça marche. Ça
me semble assez cryptique (tu me diras, c'est normal vu le forum)

--
R: Parce que ça renverse bêtement l'ordre naturel de lecture!
Q: Mais pourquoi citer en fin d'article est-il si effroyable?
R: Citer en fin d'article
Q: Quelle est la chose la plus désagréable sur les groupes de news?

According to Julien Salort <lists@juliensalort.org>:

dd if=/dev/urandom bs=6 count=1 2>/dev/null | openssl base64 -a -e

Je viens de tester.
Ça marche aussi sous MacOS X.

Ça c'est assez normal : MacOS X, en interne, est une variation sur
FreeBSD. Ce qui marche sous FreeBSD a tendance à fonctionner sous
MacOS X.

Est-ce que tu pourrais expliquer en quelques mots comment ça marche. Ça
me semble assez cryptique (tu me diras, c'est normal vu le forum)

"/dev/urandom" est un fichier "spécial" : quand on le lit, on obtient
des données aléatoires, autant qu'on veut. Le générateur est dans
le noyau ; il se nourrit sur des évènements issus du monde physique
(chronométrage précis des frappes sur le clavier, des arrivées de
paquets réseau, etc...) et rentre ces évènements dans une moulinette
cryptographique à base de MD5 ou équivalent.

"dd" est un utilitaire Unix standard qui sert à faire des read() et
des write(), c'est-à-dire lire des morceaux de fichiers et en écrire
d'autres. "if" permet d'indiquer le fichier d'entrée. "bs" donne la
taille des blocs qu'on veut manipuler. "count" donne le nombre de
blocs.

Ici, "dd if=/dev/urandom bs=6 count=1" veut dire : lis 6 octets dans
/dev/urandom et envoie-les sur la sortie standard. Le "2>/dev/null"
sert juste à rediriger les messages d'avertissement de "dd" dans le
trou noir ("dd" est assez verbeux).

Le "|" relie la sortie de "dd" avec l'entrée d'"openssl" : les 6 octets
aléatoires sont envoyés en entrée d'"openssl".

"openssl" est l'outil en ligne de commande livré avec OpenSSL, qui
est une bibliothèque cryptographique faisant beaucoup de chose (à
l'origine, du SSL, mais aussi du chiffrement symétrique, asymétrique, de
la signature, du X.509, du S/MIME...).

"base64" sert à sélectionner la fonction "encodage Base64" d'openssl.
L'encodage Base64 n'est pas de la cryptographie, mais il est utilisé
pour le courrier MIME, donc dans S/MIME, donc OpenSSL sait le gérer.
L'encodage Base64 est un moyen simple d'encoder des données binaires
en du texte : ça sert à envoyer des données binaires arbitraires sur
un médium qui ne marche bien qu'avec du texte (donc, par exemple,
des pièces jointes binaires dans un e-mail). Le principe de Base64,
c'est de transformer un groupe de 3 octets (donc 256*256*256777216
combinaisons) en un groupe de 4 caractères choisis dans une liste
conventionnelle de 64 caractères (les lettres minuscules et majuscules,
les chiffres, le '+' et le '/'). Cette transformation est une bijection,
c'est-à-dire qu'on peut faire la conversion dans l'autre sens, et tout
groupe de 4 de ces caractères est convertible (d'ailleurs, ça fait
aussi 64*64*64*64777216 combinaisons).

"openssl base64 -a -e" sert donc à convertir l'entrée en Base64, le
résultat étant envoyé sur la sortie. Ici, mes 6 octets aléatoires
sont transformés dans 8 caractères parmi les 64 décrits ci-dessus.


"dd" est un utilitaire Unix standard mais "/dev/urandom" ne se trouve
que sous les unixoïdes libres du genre Linux ou FreeBSD (note : Solaris
s'y est mis dans les dernières versions). "openssl" n'est pas le seul
outil de conversion en Base64 (c'est même un peu le marteau-pilon pour
écraser la mouche), mais il est présent en standard sur les unixoïdes
libres en question. "recode" ou "mimencode" auraient pu être utilisés,
mais leur présence est plus aléatoire.


--Thomas Pornin

"Thomas Pornin" <pornin@nerim.net> a écrit dans le message de
news:c68d3j$15m9$1@biggoron.nerim.net...

Autrement dit, il est très difficile d'évaluer l'entropie d'un mot de
passe issu d'un moyen mnémotechnique. Si on prend une très longue phrase
"classique", l'attaquant pourra essayer des dictionnaires de citations
et tous les poèmes de Verlaine (pour reprendre un exemple célèbre).

Oui, je comprend bien: une variante de l'attaque par dictionnaire appliquée
avec un dictionnaire des citations reviendrait au même.

Cependant j'avais bien précisé "en évitant les citations trop connues", que
je transforme maintenant en "en évitant les citations". C'est à dire que je
prend une phrase d'un texte quelconque, phrase que j'apprend par coeur.

L'exemple que j'ai donné avec un pass d'une longueur >> 200 caractères:
"alorslevantlatêtesedressanttoutdeboutsursesgrandsétrierstirantsalargeépée
auxéclairsmeurtriersavecunâpreaccentpleindesourdeshuéespâleeffrayant
pareilàlaigledesnuéesterrassantduregardsoncampépouvantélinvincible
empereursécrialâcheté"
est difficile à trouver, non?

Dans ce cas là, n'avons nous pas un "pass" fort avec une forte entropie?

Merci par avance de votre réponse
(qui sont toujours extrêmement instructives, précises et détaillées)

--
Jerry Khann

Adresse invalide: retirer le bouchon _O_ et .invalid

Thomas Pornin <pornin@nerim.net> wrote:

Ça c'est assez normal : MacOS X, en interne, est une variation sur
FreeBSD. Ce qui marche sous FreeBSD a tendance à fonctionner sous
MacOS X.

Merci pour toutes ces explications très claires et pédagogiques.

--
R: Parce que ça renverse bêtement l'ordre naturel de lecture!
Q: Mais pourquoi citer en fin d'article est-il si effroyable?
R: Citer en fin d'article
Q: Quelle est la chose la plus désagréable sur les groupes de news?

According to Jerry Khann <jerry_O_khann@freesurf.fr.invalid>:

Cependant j'avais bien précisé "en évitant les citations trop connues", que
je transforme maintenant en "en évitant les citations". C'est à dire que je
prend une phrase d'un texte quelconque, phrase que j'apprend par coeur.

L'exemple que j'ai donné avec un pass d'une longueur >> 200 caractères:
"alorslevantlatêtesedressanttoutdeboutsursesgrandsétrierstirantsalargeépée
auxéclairsmeurtriersavecunâpreaccentpleindesourdeshuéespâleeffrayant
pareilàlaigledesnuéesterrassantduregardsoncampépouvantélinvincible
empereursécrialâcheté"
est difficile à trouver, non?

Ça dépend. Si je sais que la victime est fana de Victor Hugo, je pense
que je la trouverais. Il suffit, au fond, de récupérer les textes sur le
web (ça se trouve sans problème : toute sa production est passée dans le
domaine public) et de faire un joli script qui extrait des phrases et
les concatène comme ci-dessus.

L'entropie est vraiment difficile à mesurer dans ce cas-là. Peut-être
est-elle élevée. Peut-être pas. Il n'est pas raisonnable de fonder une
politique de sécurité sur de telles incertitudes.

En revanche, si vous me dites : je prends une phrase de 200 caractères,
et sur les 200, j'en choisis 5 que je tapes en majuscule plutôt qu'en
minuscule ; alors là, je peux mesurer l'entropie, parce qu'on a quelque
chose de quantifiable : les 5 caractères sont choisis au hasard et
uniformément, je n'ai donc aucun moyen de choisir un ordre d'essais
qui augmente mes chances de succès. Il y a 2168773640 combinaisons, ce
qui est un tout petit peu plus que 2^31. Ces 5 caractères fournissent
31 bits d'entropie à eux seuls, et ces 31 bits je peux compter dessus.
C'est beaucoup mieux.

Merci par avance de votre réponse (qui sont toujours extrêmement
instructives, précises et détaillées)

Ah, de la flatterie... c'est bien, continuez.


--Thomas Pornin

"Thomas Pornin" <pornin@nerim.net> a écrit dans le message de
news:c6bfnu$2o2q$1@biggoron.nerim.net...

L'entropie est vraiment difficile à mesurer dans ce cas-là. Peut-être
est-elle élevée. Peut-être pas. Il n'est pas raisonnable de fonder une
politique de sécurité sur de telles incertitudes.

Non, ce n'est effectivement qu'une piste de réflexion.

En revanche, si vous me dites : je prends une phrase de 200 caractères,
et sur les 200, j'en choisis 5 que je tapes en majuscule plutôt qu'en
minuscule ; alors là, je peux mesurer l'entropie, parce qu'on a quelque
chose de quantifiable : les 5 caractères sont choisis au hasard et
uniformément, je n'ai donc aucun moyen de choisir un ordre d'essais
qui augmente mes chances de succès. Il y a 2168773640 combinaisons, ce
qui est un tout petit peu plus que 2^31. Ces 5 caractères fournissent
31 bits d'entropie à eux seuls, et ces 31 bits je peux compter dessus.
C'est beaucoup mieux.

Je l'savais bien qu'il y avait un truc à faire avec ça!

Le seul problème c'est de se souvenir de ceux qui sont en Maj!
Mais constituer une mnémotechnique sur ces bases doit être plus
facile qu'avec des "'-è)'j=*"

Dans tous les cas il y a une piste de réflexion car dans la réalité,
les passwords sont à 99,999% des mots de dictionnaires ou des prénoms
et/ou sont écrits sur des supports physiques car il est difficile de
respecter les recommandations pour générer et gérer les pwd!

Merci par avance de votre réponse (qui sont toujours extrêmement
instructives, précises et détaillées)

Ah, de la flatterie... c'est bien, continuez.

Merci, Ô grand et puissant Maître

--
Jerry Khann, vil flagorneur ;-)

Adresse invalide: retirer le bouchon _O_ et .invalid

Thomas Pornin :

Après, tout dépend du modèle d'attaque. Pour un mot de passe
protégeant l'accès à une machine Unix sur une console ou via SSH,
une entropie de 32 bits est plus que suffisante : on est dans un cas
où l'attaque est dite "en ligne", c'est-à-dire que l'attaquant doit
interroger un système (honnête par construction) pour chaque
essai. Ce système n'a qu'à limiter arbitrairement le rythme des
essais (par exemple, toujours prendre au moins un dixième de seconde
avant de répondre).

Un autre procédé à la mode dans les webmails et les webforums, c'est
afficher un mot ou un chiffre sous forme d'image et demander à
l'utilisateur de le taper dans le formulaire de connexion. Le
problème, c'est que la connexion doit être réalisée par un humain
(c'est le but, en fait) et, évidemment, qu'on doit être dans un
environnement capable d'afficher les images.