Cacher les mots de passe, c’est simple… grâce à la complexité.

Les sciences informatiques de la complexité produisent des résultats concrets. Parmi leurs outils il y a les fonctions de hachage cryptographiques qui exploitent la complexité calculatoire de certaines tâches, c'est-à-dire la difficulté qu'il y a à mener de nombreuses opérations de calcul et le temps impossible à réduire qu'elles demandent.

Une fonction de hachage cryptographique est une fonction h qui associe à tout fichier F une chaîne de caractères (ou de bits) de longueur fixée h(F) = E appelée  empreinte de F, cela en vérifiant trois propriétés.

(a) Il est impossible en pratique pour un E donné de trouver un F tel que  h(F) = E ; on dit que la fonction est « à sens unique» : on passe facilement de F à E, mais pas de E à F.

(b) Si F est donné, il est impossible en pratique de trouver un F' différent tel que h(F) = h(F').

(c) Si F' est identique à F sauf pour un seul caractère, alors h(F) n'a aucun rapport apparent avec h(F').

La fonction de hachage très utilisée SHA-256 associe par exemple une suite de 256 bits à tout fichier F qu'on lui fournit en entrée et cela quelle que soit sa longueur. Voir ici.

Nous allons donnons un exemple d'utilisation des fonctions de hachages qui nous permettra de réfléchir à cette force de la complexité calculatoire ... et à ses limites.

Les mots de passe

Stocker les mots de passe d'accès à un service informatique en ligne, même si c'est vous qui gérez le service, est dangereux. Un de vos employés pourrait copier discrètement la liste des mots de passe et l'utiliser à son profit. Pire, si vos données informatiques sont mal protégées, un hacker pourrait visiter vos disques durs et s'emparer de la liste des mots de passe.

C'est pour cela qu'aucun service informatique bien conçu ne stocke la liste des mots de passe M de ses clients. On ne garde que la liste des h(M), les empreintes des mots de passe, où h est une fonction de hachage cryptographique soigneusement choisie. Quand un client se connecte, il donne son mot de passe M, le service en ligne calcule immédiatement  h(M) et le compare à celui mémorisé et associé au nom du client. Si l'empreinte est celle enregistrée, l'accès au service est accordé.

C'est là un exemple des petits miracles de la cryptologie moderne : grâce à h, sans connaître le mot de passe du client, le site vérifie que le client connaît bien son mot de passe !

Notons bien que si quelqu'un s'empare de la liste des h(M), il ne peut a priori rien en faire, car connaître un h(M) ne permet pas (en temps raisonnable) de connaître M. Ici c'est la propriété (a) des fonctions de hachage qui est utile : le sens unique.

Cette méthode de protection des mots de passe est assez bonne à la condition que les utilisateurs choisissent des mots de passe variés. Face à une liste limitée mots de passe ou choisis sans soin, voici ce que fera un pirate (ou un des employés du service en ligne) disposant de la liste des empreintes des mots de passe.

Il utilisera la méthode du pré-calcul. Il calculera le h(M) de tous les mots de passe possibles s'ils ne sont pas trop nombreux, ou le h(M) de ceux considérés comme les plus probables. Il comparera alors cette liste avec celle des h(M) volée sur le site. Pour chaque correspondance trouvée, il pourra alors en déduire le mot de passe d'un client et donc l'utiliser.

Attention à votre mot de passe

Lorsqu'on les laisse faire, les utilisateurs choisissent des mots de passe simples du type 123456, qwerty ou password. Des listes de mots de passe courants se trouvent facilement. Voici par exemple la liste des 25 plus mauvais mots de passe pour l'année 2013 (trouvée ici)

123456, password, 12345678, qwerty, abc123, 123456789, 111111,1234567, iloveyou, adobe123,
123123, admin, 1234567890, letmein, photoshop, 1234, monkey, shadow, sunshine, 12345, password1,
princess, azerty, trustno1, 000000

Il ne faut ni utiliser des mots de passe trop courants, ni même utiliser des mots de passe de 6 caractères minuscules (ils sont trop peu nombreux). Il faut au contraire faire l'effort d'utiliser des mots de passe compliqués, c'est-à-dire comportant des majuscules et des minuscules et des chiffres et des symboles spéciaux (comme +, #, *, ? , %, = , /). Un bon mot de passe sera par exemple : eK3+=Da;oA

Le hacker, à cause du temps que cela prend et de l'espace mémoire nécessaire pour stocker le résultat du calcul des h(M) qu'il essaie, ne peut pré-calculer qu'un nombre limité de h(M). Un site bien conçu offrira donc aux utilisateurs un espace de mots de passe possibles très grand (par exemple 10 caractères pris parmi 256, ce qui fait plus de 1000000000000000000000000 =10^24 mots de passe possibles) et forcera les utilisateurs à l'utiliser pleinement en refusant les mots de passe trop simples ou appartenant à des sous-classes trop petites comme celle des mots composés de 6 minuscules.

La plupart des sites utilisant des mots de passe sont, de cette façon, protégés par la difficulté d'un calcul : celui du passage de h(M) à M.

Fonctions de hachage lente

Il arrive cependant que des contraintes diverses limitent le nombre de mots de passe que le concepteur d'un site peut offrir aux utilisateurs. Pour éviter une attaque par la méthode du pré-calcul, il faut alors rendre impossible ce pré-calcul en introduisant  une autre idée. La méthode la plus simple consiste à utiliser des fonctions de hachage lentes, c'est-à-dire impossibles à calculer rapidement.

Pour cela, on part d'une bonne fonction de hachage cryptographique usuelle et on décide d'en construire une autre, h' —qui sera une fonction de hachage lente—,  en posant :

h'(M) = h(h(h(h(...(M)...))) avec  k fois l'appel à la fonction h

L'entier k est choisi de telle façon que pour un ordinateur courant le calcul itéré de la fonction h opéré k fois de suite, demande par exemple 1 seconde de temps de calcul.

Ni l'utilisateur,  ni le service  informatique ne seront gênés par cette seconde de calcul nécessaire pour passer de M à h'(M). On peut d'ailleurs fixer k pour 1/10 de seconde au lieu d'une seconde ou une autre durée qu'on jugera meilleure. En revanche, le hacker ne pourra rien faire même s'il dispose de la liste des h'(M) volée sur le site, et que les mots de passe possibles ne sont pas très nombreux, car pour lui le temps de calcul nécessaire sera rédhibitoire.

Supposons par exemple qu'il y ait seulement mille milliards de mots de passe différents autorisés (c'est assez peu) et que le site en ligne dispose d'un millier de clients ayant chacun leur mot de passe dont l'empreinte lente h'(M) est stockée. Pour avoir une chance raisonnable de découvrir un mot de passe parmi le millier de ceux dont l'empreinte est stockée, le hacker devra pré-calculer environ un milliard de h'(M) des mille milliards de mots de passe possibles. Or cela lui demanderait un milliard de secondes avec un ordinateur courrant, soit 11000 jours, soit 31 ans environ. Même avec un nombre assez limité de mots de passe possibles, la méthode de la fonction de hachage lente rend inexploitable le fichier des empreintes de mots de passe (qu'on pourrait rendre public !).

Notons que dans toutes ces histoires, c'est la complexité des calculs qui protège.

Dans l'absolu, celui qui connaît l'empreinte d'un mot de passe peut essayer tous les mots de passe possibles jusqu'à tomber sur la bonne empreinte. C'est seulement en pratique que c'est impossible. Dans le cas de la méthode du pré-calcul des empreintes ou dans le cas de la méthode de la fonction de hachage lente, en théorie encore la protection est très mauvaise car trouver les mots de passe n'est pas rendu impossible mais seulement long. À chaque fois ce sont les longs temps de calcul qui protègent... du moins pour celui qui ne dispose que des ressources courantes.

Démonstrations mathématiques manquantes

Notons aussi que les méthodes décrites ici, comme le plus souvent en cryptographie mathématique, ne sont pas prouvées sûres. Les fonctions de hachages utilisées aujourd'hui sont réputées bonnes du fait d'un consensus entre spécialistes. Mais ce consensus n'est pas une démonstration mathématique et les propriétés exigées des fonctions de hachages mentionnées plus haut sont seulement conjecturées et testées... autant que c'est possible.

Si l'état de l'art admis est celui de tous les hackers possibles sur terre alors les méthodes décrites ici par l'usage de h ou de h' et basées sur la complexité des calculs à effectuer sont convenables. En revanche, si certains disposent de moyens de calcul très supérieurs à ce qui est considéré comme courant, ou disposent des connaissances mathématiques beaucoup plus avancées que celles publiques sur ces questions, alors les systèmes de protection utilisés aujourd'hui pour les mots de passe sont illusoires.

C'est une bonne idée de faire reposer la sécurité des systèmes informatiques sur la complexité de certaines tâches de calcul, encore faudrait-il qu'on soit vraiment certain que ces tâches sont complexes pour tout le monde, et cela, la science cryptographique ne l'assure pas. Dans un monde où des milliers de mathématiciens travaillent pour la NSA (National Security Agency) des Etats-Unis (et d'organismes du même type au service d'autres pays) sans jamais rendre public ce qu'ils trouvent, et où la puissance de calcul que ces agences ont à leur disposition est plusieurs ordres de grandeur au-dessus de celle des utilisateurs courants, il n'est pas raisonnable de croire absolument sûres les méthodes décrites ici. Tout juste doit-on espérer que même si nos mots de passe sont identifiés, on n'en fait qu'un usage limité, seulement pour nous espionner, mais pas pour vider nos comptes bancaires !

Bibliographie

• Jean-Paul Delahaye, Preuves de travail, Pour la science, n°438, avril 2014.
• Wikipedia, Fonction de hachage ici