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).