L'entropie c'est la vie

Nous avons élu le leader du projet Debian, comme chaque année. Les résultats ont été proclamés le 15 avril (plus d’infos sur la page du vote).

Dix jours plus tard, Timo Juhani Lindfors publie une faiblesse dans le logiciel qui gère le vote et qui permet de casser le secret du vote, et ce pour tous les votes (dans la foulée : plouf l’anonymat du vote).

Pour ceux qui veulent jouer à la maison, une approximation du code source qui gère le vote est disponible. Ce n’est pas encore un paquet debian.

L’analyse du problème est amusante, et la morale en est essentiellement le titre de cette entrée. Dans la suite je ne fais que reprendre l’analyse de Timo Juhani Lindfors en y ajoutant mes propres commentaires.

Le token secret qui permet à chaque votant de vérifier que son vote a bien été pris en compte est constitué de la concaténation de l’instant auquel on prend en compte le vote (modulo 21 jours, cf. le fichier dvt-gack autour de la ligne 160) et de 8 caractères pris au hasard parmi les alphanumériques (soit 26+26+10 = 62 possibilités).

Si le vote est pris en compte à un moment parfaitement aléatoire dans cette période de 21 jours, et si les 8 caractères sont eux aussi pris au hasard uniforme, j’obtiens une borne sur l’entropie de ce token secret d’environ 69 bits. Notons déjà que le vote n’est ouvert que pendant 14 jours.

Première faiblesse: les votants ne choisissent pas leur instant pour voter de façon parfaitement aléatoire, et d’autre part l’utilisation d’un cronjob (toutes les 5 minutes) réduit encore plus l’ensemble des valeurs possibles pour ce timestamp.

Là où les choses s’effondrent, c’est dans le calcul des 8 caractères supplémentaires. Le script utilise la fonction rand de perl sans utiliser de graine particulière. Cette fonction utilise en interne drand48(), mais avec une graine de 32 bits uniquement. Comme il s’agit d’un générateur déterministe, la connaissance de ces 32 bits de graine suffit à prédire complètement la séquence des 8 caractères du token secret. On passe donc d’une entropie théorique d’environ 47 bits pour ces 8 caractères, à seulement 32 bits. En supposant que la machine n’est pas trop surchargée et que cron lance le script de vérification des votes toutes les 5 minutes exactement, on obtient maintenant une borne sur l’entropie d’environ 45 bits.

Une autre faiblesse amusante se trouve dans dvt-tally et concerne l’ordre dans lequel on affiche les votes. On commence par trier les votes par le nom réel du votant, puis on retire au hasard un nom dans cette liste pour l’afficher en premier, et ainsi de suite jusqu’à épuisement des votes. On affiche évidemment les votes masqués, mais l’utilisation de la même fonction rand sans initialisation explicite nous rend vulnérable à une attaque exhaustive. Et vu que l’anonymat du vote est déjà compromise, ce problème est juste la cerise sur le gâteau.

Quelles conclusions tirer de ce problème? Voici les miennes:

• même dans un monde idéal, l’entropie bornée par 69 bits pour le secret est insuffisante si on veut sérieusement protéger le vote individuel de chaque votant. On a longtemps recommandé 80 bits pour se placer au delà de ce qui est réaliste pour une attaque par force brute. L’amélioration des capacités de calcul amène l’ANSSI à recommander 128 bits pour résister au delà de 2020 (recommandation faite en 2010).
• l’utilisation du temps comme source d’entropie (car sa présence dans le token secret n’a pas d’autre usage) est discutable. Les évènements dépendants d’êtres humains n’ont pas tendance à se distribuer dans le temps avec l’uniformité voulue. Et si on s’attaque à mon vote à moi, il est plus raisonnable d’attaquer d’abord les instants auxquels je suis réveillés, que les autres. Si on ajoute à cela le fait que l’application ne maîtrise pas l’instant auquel elle tourne, car lancée par cron, l’utilisation du temps est simplement une mauvaise idée.
• utiliser un générateur de nombres aléatoires sans l’initialiser avec une graine revient à fermer les yeux et espérer que la voiture va magiquement éviter le mur (alors qu’on garde le pied à fond sur l’accélérateur).
• utiliser un générateur de nombre aléatoire déterministe pour des tirages successifs d’une quantité que l’on espère aléatoire est une mauvaise idée.

Ma suggestion pour corriger ces problèmes serait de calculer le token secret comme la représentation hexadécimale de 128 bits lus directement depuis /dev/urandom (ou son équivalent sur d’autres systèmes). Cela revient à un token secret de 32 caractères, ce qui reste raisonnable dans le contexte, et cela aligne la sécurité attendue dans la confidentialité de chaque vote avec les recommandations de la communauté crypto. Lire depuis /dev/urandom est raisonnablement rapide (et essentiellement négligeable dans la mesure où on vient de vérifier une signature RSA ou DSA) et suffisamment sûr aussi (et si on doute de /dev/urandom, je suppose qu’on peut jeter l’éponge sur ce système, car si le noyau n’est pas en mesure de fournir de l’entropie de qualité je me demande bien qui peut l’être).

Et pour finir, afficher les votes en triant selon le hash md5 (comme cela a été suggéré dans le fil de discussion).