devotee (debian vote engine): predictable RNG allows recovery of secret monikers

[Timo Juhani Lindfors <timo.lindfors@iki.fi>]

Hello,

I think I found a bug in devotee (debian vote engine) that breaks the
secrecy elections.

Devotee can be used in either public or secret mode. Leadership
elections are done in the secret mode (constitution 5.2.5). In this mode
devotee gives each voter V a secret moniker M and publishes only the
hash

H = md5(V + " " + M + "\n")

in the tally sheet. The idea here is that each voter can verify that
their vote is listed in the tally sheet but nobody else should be able
to this (except for the secretary of course).

The secret moniker M is composed of two parts:

M = T + S

where T is derived from the time when the voter first tried to cast a
vote. This can be easily predicted since the cron job that processes the
votes is run at five minute intervals.

The S part is a 8-character random string that is generated using the
perl fragment


      my @chars = (0 .. 9, 'a' .. 'z', 'A' .. 'Z');
      $alias .=  join ("", map {$chars[rand $#chars]} 1..8);

On Debian systems the rand() function of perl uses drand48() from eglibc
which implements a 48-bit LCG RNG. Calculating 2^48 md5 hashes can be
done in less than a day using GPUs [1] but this requires one to use
non-free drivers so I had to find a shortcut :-)

I noticed that devotee does not seed the RNG in any way but relies on
perl to do it automatically. According to "perldoc -f rand" perl will
seed the RNG when rand() is called for the first time. In Perl_seed() it
opens /dev/urandom, reads 4 bytes and later passes it to srand48:

#define seedDrand01(x)  srand48((Rand_seed_t)x)

So: we have a 48-bit RNG but it is seeded with only a 32-bit value!

By simulating the RNG on all possible seeds I was able to find secret
monikers that match the hashes in the tally sheet. Since Wouter already
made his vote public [2] I'll use his hash to prove that I know the
secret moniker (V = "wouter", T = "1589704", S = "WMvwdDdr", RNG seed =
0xc580689f):

$ echo wouter 1589704WMvwdDdr | md5sum
597c362e6156ec7e37b334837161da26  -

$ wget -qO - http://www.debian.org/vote/2012/vote_001_tally.txt \
 | grep 597c362e6156ec7e37b334837161da26
V: 1223                 597c362e6156ec7e37b334837161da26


$ perl -e 'my @chars=(0..9, 'a'..'z', 'A'..'Z');\
 srand(0xc580689f);\
 print(join("",map{ $chars[rand $#chars] } 1..8)."\n");'
WMvwdDdr


-Timo

[1] http://whitepixel.zorinaq.com/
[2] http://grep.be/blog/en/life/debian/dpl_2012