Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Kurt Roeckx k...@roeckx.be writes: - md5_hex($name $alias obfuscate\n), \n; + hmac_sha256_hex($name, obfuscate), \n; part probably needs some further work. Should it be + hmac_sha256_hex($name, $alias + obfuscate), \n; This is for the dummy sheet. It only contains dummy data. I see no reason to use part of the real key to generate the a dummy hmac. Then why use hmac at all in the dummy sheet? Why not just print $name there? -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/84txnrvqbb@sauna.l.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
On Sun, Mar 31, 2013 at 01:03:52PM +0300, Timo Juhani Lindfors wrote: Kurt Roeckx k...@roeckx.be writes: - md5_hex($name $alias obfuscate\n), \n; + hmac_sha256_hex($name, obfuscate), \n; part probably needs some further work. Should it be + hmac_sha256_hex($name, $alias + obfuscate), \n; This is for the dummy sheet. It only contains dummy data. I see no reason to use part of the real key to generate the a dummy hmac. Then why use hmac at all in the dummy sheet? Why not just print $name there? I'll probably change it to use sha256_hex() instead so that it looks like the output of the hmac. Kurt -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20130331101954.ga...@roeckx.be
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
On Tue, Apr 24, 2012 at 12:56:19PM +0300, Timo Juhani Lindfors wrote: Hello, I think I found a bug in devotee (debian vote engine) that breaks the secrecy elections. I just pushed a change for this issue to my git repo at: http://anonscm.debian.org/gitweb/?p=users/kroeckx/devotee.git;a=summary I would be grateful if people can review that. I also still need to do something about the order of the votes in the tally sheet. Kurt -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20130330144109.ga2...@roeckx.be
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Kurt Roeckx k...@roeckx.be writes: I just pushed a change for this issue to my git repo at: http://anonscm.debian.org/gitweb/?p=users/kroeckx/devotee.git;a=summary I would be grateful if people can review that. commit e7f81870d1f8b18e5dcc855e9a001fab95112c0f (Fix generation of secret key for secret votes) looks otherwise ok but the - md5_hex($name $alias obfuscate\n), \n; + hmac_sha256_hex($name, obfuscate), \n; part probably needs some further work. Should it be + hmac_sha256_hex($name, $alias + obfuscate), \n; ? -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/84y5d4vs30@sauna.l.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
On Sat, Mar 30, 2013 at 05:13:23PM +0200, Timo Juhani Lindfors wrote: Kurt Roeckx k...@roeckx.be writes: I just pushed a change for this issue to my git repo at: http://anonscm.debian.org/gitweb/?p=users/kroeckx/devotee.git;a=summary I would be grateful if people can review that. commit e7f81870d1f8b18e5dcc855e9a001fab95112c0f (Fix generation of secret key for secret votes) looks otherwise ok but the - md5_hex($name $alias obfuscate\n), \n; + hmac_sha256_hex($name, obfuscate), \n; part probably needs some further work. Should it be + hmac_sha256_hex($name, $alias + obfuscate), \n; This is for the dummy sheet. It only contains dummy data. I see no reason to use part of the real key to generate the a dummy hmac. Kurt -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20130330154350.ga4...@roeckx.be
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
On Sat, Mar 30, 2013 at 05:13:23PM +0200, Timo Juhani Lindfors wrote: + hmac_sha256_hex($name, $alias + obfuscate), \n; Are you sure HMAC is immune against extension attacks on the key? You may want to append it to the name instead. Bastian -- It would be illogical to kill without reason. -- Spock, Journey to Babel, stardate 3842.4 -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20130330153213.ga12...@waldi.eu.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
On Sat, Mar 30, 2013 at 03:41:09PM +0100, Kurt Roeckx wrote: I just pushed a change for this issue to my git repo at: http://anonscm.debian.org/gitweb/?p=users/kroeckx/devotee.git;a=summary I would be grateful if people can review that. I also still need to do something about the order of the votes in the tally sheet. That has now been commited too. Kurt -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20130330170420.ga7...@roeckx.be
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
On Thu, 26 Apr 2012, Timo Weingärtner wrote: 2012-04-26, 23:23:54 Timo Juhani wrote: Raphael Geissert geiss...@debian.org writes: print hmac_sha1_hex($v, $m); Yeah that sounds promising. Now we just need to fix the code that tries to randomize the order of entries in the tally. Is that randomization really needed? Why not just sort based on the hashes? Please just short he HMAC output, you won't leak any more data that way, and it actually makes the output more usable... Also, unless there is a strong reason not to, please consider using hmac_sha256_hex(). -- One disk to rule them all, One disk to find them. One disk to bring them all and in the darkness grind them. In the Land of Redmond where the shadows lie. -- The Silicon Valley Tarot Henrique Holschuh -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/20120427225009.ga17...@khazad-dum.debian.net
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Timo Juhani Lindfors timo.lindf...@iki.fi writes:
votes in the final tally. If I knew the hashes sufficiently many (maybe
20?) voters I probably could predict the initial state of the RNG and
reverse this randomization step completely.
It seems that if you know the md5 hashes of only four people you can
already find a unique solution for the RNG seed and reverse the
randomization done for order of lines in tally.txt:
paste (grep ^V tally.txt) (perl -e'srand($SEED);@a=grep(/^
/,);while(@a){print(splice(@a,int(rand(scalar(@a))),1));}' voters.txt)
I'm not making $SEED public, I just want to point out a weakness in the
system.
--
To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: http://lists.debian.org/84ipgmg30b@sauna.l.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Timo Juhani Lindfors wrote: True. We need to both fix the RNG and use a longer moniker. M = H(CRYPT_PRNG()) for example: use Digest::SHA qw(sha1_hex); open(UR, '', '/dev/urandom') or die($!); my $rbytes; die if (sysread(UR, $rbytes, 16) 16); my $m = sha1_hex($rbytes); And while at it, stop reinventing the wheel and use a proper HMAC if that's what is wanted: use Digest::SHA qw(hmac_sha1_hex); print hmac_sha1_hex($v, $m); Then you just publish the HMAC in the tally. Cheers, -- Raphael Geissert - Debian Developer www.debian.org - get.debian.net -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/jnbv2n$g0f$1...@dough.gmane.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Raphael Geissert geiss...@debian.org writes: print hmac_sha1_hex($v, $m); Yeah that sounds promising. Now we just need to fix the code that tries to randomize the order of entries in the tally. -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/84zk9ydw5x@sauna.l.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Hi, 2012-04-26, 23:23:54 Timo Juhani wrote: Raphael Geissert geiss...@debian.org writes: print hmac_sha1_hex($v, $m); Yeah that sounds promising. Now we just need to fix the code that tries to randomize the order of entries in the tally. Is that randomization really needed? Why not just sort based on the hashes? Greetings Timo signature.asc Description: This is a digitally signed message part.
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Le 26/04/2012 19:02, Raphael Geissert a écrit : Timo Juhani Lindfors wrote: True. We need to both fix the RNG and use a longer moniker. M = H(CRYPT_PRNG()) for example: use Digest::SHA qw(sha1_hex); open(UR, '', '/dev/urandom') or die($!); my $rbytes; die if (sysread(UR, $rbytes, 16) 16); my $m = sha1_hex($rbytes); While we're at it, what about giving the possibility to the voter to contribute to the entropy of the moniker? Say, add a field to the ballot and suggest the voter to put e.g. the output of pwgen there? This would be in addition to the above code. Cheers, -- Stéphane -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/4f9a2a94.5050...@debian.org
devotee (debian vote engine): predictable RNG allows recovery of secret monikers
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
--
To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: http://lists.debian.org/84ehrdh2rg@sauna.l.org
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
* Timo Juhani Lindfors timo.lindf...@iki.fi, 2012-04-24, 12:56:
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.
Note that 8 random alphanumeric characters can have at most ~47.6 bits
of entropy. So just improving RNG wouldn't help here.
--
Jakub Wilk
--
To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org
with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org
Archive: http://lists.debian.org/20120424111600.ga7...@jwilk.net
Re: devotee (debian vote engine): predictable RNG allows recovery of secret monikers
Jakub Wilk jw...@debian.org writes: Note that 8 random alphanumeric characters can have at most ~47.6 bits of entropy. So just improving RNG wouldn't help here. True. We need to both fix the RNG and use a longer moniker. Also, I just noticed that rand() is also used to randomize the order of votes in the final tally. If I knew the hashes sufficiently many (maybe 20?) voters I probably could predict the initial state of the RNG and reverse this randomization step completely. -- To UNSUBSCRIBE, email to debian-devel-requ...@lists.debian.org with a subject of unsubscribe. Trouble? Contact listmas...@lists.debian.org Archive: http://lists.debian.org/84y5plf3yd@sauna.l.org
