Weaknesses in the Moscow Internet votingsystem
Pierrick Gaudry
CNRS, Université de Lorraine, Inria
Nancy, France

Joint work with Alexander Golovnev (Harvard)
Special thanks to Julia Krivonosova (TUT, Estonia)

ECC 2019, Bochum

1/37

PlanContext
Attacks on the encryption scheme
Weaknesses in the general protocol
What would be the ideal e-voting system?

2/37

What kind of election?
September 8, 2019: day of local elections in Russia.
Moscow: election of the City Parliament (Moscow Duma).
In Moscow, there is also a City Government (headed by the Mayor ofMoscow) for the executive part.

Rules:
45 members, each one elected by one district.
Around 165,000 voters in each district; 7.3 M in total;
In each district, the candidate with the largest number ofvotes gets the seat.
Internet voting experiment:
Only in 3 districts;
Any voter could register and use Internet voting;
3/37

Not exactly a peaceful context
Several protests in July / August due to rejection of opposition
candidacies.

© Putnik / Wikipedia

Up to 20,000 participants in Moscow.
4/37

Public test of the system
A public testing was organized, with a bounty program of up to
2 millions rubles (≈ $30,000).
Source code made public on GitHub.
https://github.com/moscow-technologies/blockchain-voting

Various attack scenarios were proposed.
https://www.mos.ru/upload/.../5381/Formal_Offer.pdf

5/37

Public test of the system
A public testing was organized, with a bounty program of up to
2 millions rubles (≈ $30,000).
Source code made public on GitHub.
https://github.com/moscow-technologies/blockchain-voting

Various attack scenarios were proposed.
https://www.mos.ru/upload/.../5381/Formal_Offer.pdf

No specification!

No documentation!

Rem. This is not part of a formal certification process.

5/37

Timeline of Summer 2019

Code publication

D-day
July

AugustSept

Sept 8July 17

Timeline of Summer 2019

Code publication
J. Krivonosova’s post

D-day
July

AugustSeptFirst public test
Sept 8

Aug 1

July 19
July 17

Timeline of Summer 2019

Code publication
J. Krivonosova’s post
PG’s attack

July

D-day
AugustSeptFirst public test
Sept 8

Aug 8

Aug 1

July 19
July 17

Timeline of Summer 2019

Code publication
J. Krivonosova’s post

First update

PG’s attack

July

D-day
AugustSeptFirst public test
Sept 8Aug 20Aug 8Aug 1July 19
July 17

Timeline of Summer 2019

Code publication
AG’s attack
J. Krivonosova’s post

First update

PG’s attack

JulyD-dayAugustSeptFirst public test
Sept 8Aug 24

Aug 20

Aug 8

Aug 1

July 19
July 17

Timeline of Summer 2019

Code publication
AG’s attack
J. Krivonosova’s post

First update

PG’s attack

July

D-day
AugustSeptFirst public test

Last test
Sept 8Aug 28Aug 24

Aug 20

Aug 8

Aug 1

July 19
July 17

Timeline of Summer 2019
Second update
Code publication
AG’s attack
J. Krivonosova’s post

First update

PG’s attack

July

D-day
AugustSeptFirst public test

Last test
Sept 8
Sept 6

Aug 28Aug 24

Aug 20

Aug 8

Aug 1

July 19
July 17

6/37

PlanContext
Attacks on the encryption scheme
Weaknesses in the general protocol
What would be the ideal e-voting system?

7/37

Quick recall of ElGamal
Encryption scheme: variant of ElGamal in Z/pZ, with safe
primes (Sophie Germain).
Let g be a generator, and (sk, pk = g sk ) a key-pair.
The plain ElGamal encryption of a message m is:
Encg,pk (m) = (a, b) = (g r , pkr · m) ,where r is a random (to be used only once).
The decryption using sk is:
Decg,sk (a, b) = b · a−sk = m.
If done correctly, this gives IND-CPA security.
8/37

A triple-ElGamal (encryption)
In the original scheme, there is a multi-level variant:Choose p1 < p2 < p3 , three safe primes, together with 3
generators g1 , g2 , g3 .
The keys are
sk = (sk1 , sk2 , sk3 );pk = (g1sk1 , g2sk2 , g3sk3 ),The encryption of a message m ∈ Z/p1 Z is obtained by(a1 , b1 ) := Encg1 ,pk1 (m);(a2 , b2 ) := Encg2 ,pk2 (a1 );(a3 , b3 ) := Encg3 ,pk3 (a2 ),map a1 to Z/p2 Z;
map a2 to Z/p3 Z;

and the encrypted message isMultiEnc(m) = (b1 , b2 , a3 , b3 ).
Rem. All mapping are obtained by canonical lifting to Z.
9/37

A triple-ElGamal (decryption)
Knowing sk, the operations can be reversed to decrypt m from(b1 , b2 , a3 , b3 ):a2 := Decg3 ,sk3 (a3 , b3 );a1 := Decg2 ,sk2 (a2 , b2 );m := Decg1 ,sk1 (a1 , b1 ).

map a2 to Z/p2 Z;
map a1 to Z/p1 Z;

Due to the inequality p1 < p2 < p3 , this works.

10/37

A triple-ElGamal (decryption)
Knowing sk, the operations can be reversed to decrypt m from(b1 , b2 , a3 , b3 ):a2 := Decg3 ,sk3 (a3 , b3 );a1 := Decg2 ,sk2 (a2 , b2 );m := Decg1 ,sk1 (a1 , b1 ).

map a2 to Z/p2 Z;
map a1 to Z/p1 Z;

Due to the inequality p1 < p2 < p3 , this works.
Security.
Contrary to triple-DES where the security number of operations to
break the system is squared, here it is just multiplied by 3.
Breaking the scheme is not harder than tobreak the 3 underlying ElGamal independently.
10/37

A triple-ElGamal: why?
Why? We did not get the final answer.
But we speculated . . .
All the pi ’s are chosen to be less than 256 bits.
This is enforced in the code with tests likethis.moduleP.compareTo(SOLIDITY_MAX_INT) >= 0

Solidity is the smart-contract language of Ethereum. And in thecode, there is a decryption function written in this language.
The max size of native integers is indeed 256 bits.
Looks like the authors did not have the time / the competence towrite a multi-precision library in Solidity and decided to “increasethe security” in another way. . .
11/37

A triple-ElGamal: why?
Why? We did not get the final answer.
But we speculated . . .
All the pi ’s are chosen to be less than 256 bits.
This is enforced in the code with tests likethis.moduleP.compareTo(SOLIDITY_MAX_INT) >= 0Solidity is the smart-contract language of Ethereum.
And in theinah this language.
code, there is a decryption function writtenkcin

loc!
deiB 256
The max size of native integers is indeed
ins bits.

Looks like the authors did not have the time / the competence towrite a multi-precision library in Solidity and decided to “increasethe security” in another way. . .
11/37

First attack: solve DLP

Goal: compute a discrete logs mod a p of 256 bits.
The challenge says it must be done in less than 12 hours.
Historically, first done publicly in ?? Let’s check in DLDB.

12/37

First attack: solve DLP

Goal: compute a discrete logs mod a p of 256 bits.
The challenge says it must be done in less than 12 hours.
Historically, first done publicly in ?? Let’s check in DLDB.
1995-1996 (Weber, Denny, Zayer).
Current record: 795 bits (rump session yesterday!)

How much time does it take today? (must be less than 12 hours)

12/37Computing discrete log in Z/pZ
SageMath 8.8 (uses GP/Pari internally for DLP).
Free software. Not bad for small sizes, but for 256 bits, didnot finish after 4 days.
Magma 2.24-2
Proprietary software, developed and sold by University ofSydney.
Faster than SageMath. But uses a lot of memory.
For 256 bits, 24 hours with 130 GB.
CADO-NFS (rev. 6b3746a2e).
Free software, developed (mostly) in Nancy. Based on theNumber Field Sieve algorithm.
For 256 bits, less than 10 minutes in less than 1 GB.

13/37

DLP with CADO-NFS
Running times on my 4-year old nothing-special desk PC:
key numbersk1
sk2
sk3

time
425 sec
507 sec
314 sec

Each line includes 2 runs of CADO-NFS (one for gi , one for pki );but many steps are (automatically) shared.
Rem. Variation from one key to another is not unusual forcomputations with moderately small primes.
Rem. This size was not thoroughly tested in CADO-NFS andsometimes it failed due to bad parameters in the descent phase.
This was quickly fixed for the occasion.
14/37

First fix

The first update on August 20 did:
Remove the triple-ElGamal encryption;
Upgrade the key-size to 1024 bits;
Changed the protocol, so that decryption is no longer part ofa smart-contract (oh, oh!).
Take generators in the prime-order subgroup.
The last item is the response to a side-remark that was made in
the document of the first attack.

15/37

Second attack (by Golovnev)
Golovnev’s attack:The generator is now in a prime-order subgroup. Good!
But the messages are not. Doh!
One bit is leaked: from the ciphertext, one knows if themessage is a quadratic residue.
From the source code: encrypted message = identifier of acandidate (no random nonce).
Quite often in e-voting, one bit is the whole answer!
Typical scenario:
Two main candidates: pro-Putin vs opposition;
One has an id that is a QR, not the other.
16/37

Second fix
Getting close to the election, the situation got chaotic (at leastfrom my non-Russian speaking point of view):
The developers seemed to deny that this second attack wasreal;
Still, they silently changed the code, without updating
GitHub;A final public test was done, and from the (minified)Javascript sent to the voters, they took care of the subgroupattack;Only 2 days before the election, GitHub was updated.

17/37

PlanContext
Attacks on the encryption scheme
Weaknesses in the general protocol
What would be the ideal e-voting system?

18/37

Encryption fixed. Problem solved?
Weak encryption is one of the easiest thing to analyze fromsource code only, without spec.
For other properties, speculations based on discussions, press
articles, source code (incl. minified JS).
General impression: the whole protocol is messed up!
Privacy? X
Verifiability? very partial
Coercion resistance? X
Vote buying? X
Thanks to us, they now have a reinforced door on a house madeof cardboard.
19/37

Overview of the protocol
1. Registration / authentication.
Based on existing infrastructure for administration in Russia.
Not specific to this election.
2. Voting.
The voter connects to the server, gets the javascript, thechoice is encrypted locally with the key of the election andsent back.
3. Ballot box.
The server sends the encrypted ballots to the blockchain, withno reference to the voter, in random order.
4. End of the election.
The trustees who own the decryption key (they used Shamirsecret sharing) decrypt the ballots and put them in theblockchain as well.
20/37

Overview of the protocol
1. Registration / authentication.
Based on existing infrastructure for administration in Russia.
Not specific to this election.
2. Voting.
The voter connects to the server, gets the javascript, thechoice is encrypted locally with the key of the election andsent back.
3. Ballot box.
The server sends the encrypted ballots to the blockchain, withno reference to the voter, in random order.
4. End of the election.
The trustees who own the decryption key (they used Shamirsecret sharing) decrypt the ballots and put them in theblockchain as well.

They also publish the decryption key. (what ?!?!?!?)
20/37

Role of the encryption

In fact, for the designers:
Privacy is “guaranteed” by the server cutting the link
between ballot and voter;
Encryption is here only to protect against revealing the partial
tally during the election day.

21/37

Further remarks
On the blockchain:
No idea why they wanted to have the decryption made in asmart-contract.
The blockchain is a private one. It provides no guarantee
whatsoever.
During the election, the voters could query the blockchain via
a web server and check that their ballot was there.
Interaction with the Moscow Department of Information
Technology was frustrating:
They answered only to some of my technical questions; only
those that were not embarrassing.
I could not get any documentation or specification of theprotocol.
22/37

D-dayThey did not cancel the use of Internet voting.
In total, about 10,000 votes by Internet.
In one of the districts, the difference between the first and thesecond candidate was less than 100 votes.
A few hours after the election, the access to theblockchain was cut. (What ?!?!?!?)
Fortunately, journalists of the Meduza online newspaper (exiledin Riga) made a copy before the shutdown, with all the ballots andthe decryption key.
One of the journalists who was a voter kept track of his network
communication during the voting and could indeed check that
his ballot had been taken into account.
23/37

Impact of our findings
Main impact of our findings is not fixing the encryption.
We publicly showed that this was not the perfect scheme, asclaimed.
Large press coverage (thumbs up for Meduza!)
Moscow had to acknowledge the problems.
Hopefully made some voters skeptical and they decided to use
traditional voting.
Hopefully, they get some pressure to do a better system for thenext experiments.
Positive note: Opening (part of) the source code and doing
public testing is to be commended.
24/37

PlanContext
Attacks on the encryption scheme
Weaknesses in the general protocol
What would be the ideal e-voting system?

25/37

Too many required properties
The ideal system needs to provide (at least):

Privacy, end-to-end verifiability, coercion resistance,usability, accessibility, availability, accountability, . . .
And all of this with a well-defined and reasonable trust model.

This does not exist (yet?).
Any practical system currently needs to choose the bestcompromise for the given context.

26/37

Let’s concentrate on privacy

27/37

Secret of the vote, privacy

Informal definition: my vote should be secret.
Difficulties to make this formally precise:
The result is public (and leaks information about your vote);
Sometimes, intermediate results are public (list of ballots;tally for each district; . . . )Trust assumptions (voting device; various “trustees”)
Main tool: threshold encryption.

28/37

Threshold encryption is not enough
How to cut the link voters ↔ ballot before decryption?
Crypto means:homomorphic encryption
verifiable mixnets
multi-party computation
Non-crypto means:servers should forget a lot of data (often in contradiction withredundancies / backups / ...)
Rem. Perfect forward secrecy vs PQ resistance.
Both care about an attack in the future, when crypto might get
broken. No deployed system is PQ-resistant today.

29/37

How to be private wrt my computer?
Sometimes used as the final argument by anti-evoting zealots.

This is not possible!

30/37

How to be private wrt my computer?
Sometimes used as the final argument by anti-evoting zealots.

This is not possible!
Yes it is. At least in theory.
But will need an additional channel or computing device.
In Switzerland, they receive some paper voting material bypost (but they don’t use it for this property);
If the voter has two devices (one PC and one Smartphone),this opens many possibilities, especially with scanning
QR-codes.
Security goal: none of your device knows your vote, unless they
are both infected by pieces of malware that can communicate.
(See e.g. BeleniosVS, a not-implemented variant of Helios.)
30/37

Summary of privacy properties for 2 systems

Enc
HeliosMoscown trust.
–Cut link
voter-vote
Hom.
non-crypto

HeliosMoscow

Privacy
wrt device
NoNo

Privacy
wrt server
Yes/NoNo

Cut link
voter-ballot–
non-crypto

Forward sec.
wrt pub data
Yes/NoYes

31/37

Another very difficult property:

Coercion resistance

32/37

Coercion resistanceInternet voting is remote voting. Coercion is built-in!
Typical cases:Threat: “Vote like this or you’ll have problems, you know. . . ”
Vote buying: “I sell my vote for $50; who wants to buy it?”
Family voting: “Hey wife and kids! Let’s vote! Gimme yourcredentials!”Rem. In all postal voting systems that I know, the problem exists
as well.
In some contexts (like, yes, Moscow Duma election), the risk ishigh. (I heard some plausible stories; but no direct testimony.)

33/37

Coercion resistance: how?
Main hypothesis: the voter will have a period of time where she
can vote freely.
Sometimes also require a period of time where the voter is free before theelection opens.

Main idea: allow the voter to lie.
E.g. in Civitas, the voters can create by themselves fake voting
material. The corresponding ballots will be blindly removed in thetally, with a ZKP that everything was done in the appropriate way.
Current state-of-the-art: this works in theory, but hard to makeit practical (see survey at E-Vote-Id 2019).
Personal conclusion: don’t use internet voting (yet) in a context
where coercion is a concern.
34/37

More properties

Verifiability. I should be sure that my vote is taken into
account, and that everything went smoothly.
Usability. Not all votes have a Master in Crypto...
Accessibility. In principle, e-voting could be more friendly tovoters with disabilities than paper voting. Or not...
Availability. Backups, redundancy, resistance to DoS.
Accountability. In case of problem (a verification fails),
being able to tell who cheated is often very important.

35/37

Combining everything?
Unfortunately, not realistic, with current state of the art.
Things that can help:
Having an electronic ID card helps for eligibility (cf Estonia);
If we can afford sending paper material by post, this can help
for verifiability and privacy w.r.t voting device (cfSwitzerland);If the voters have several independent devices, this can help
for verifiability and privacy w.r.t voting device (cf BeleniosVS);
A blockchain might be a convenient way to implement a
public append-only board;
If all the voters have a degree in crypto AND are willing toread the documentation and to follow the protocol, life ismuch simpler.
36/37

IACR recent elections with Helios
Helios has a lot of nice properties . . . but is assumes that voters are
doing their job.
Questions:Who participated in the IACR 2019 election?

37/37

IACR recent elections with Helios
Helios has a lot of nice properties . . . but is assumes that voters are
doing their job.
Questions:Who participated in the IACR 2019 election?
Did you check that your ballot was present in the publicboard? When?

37/37

IACR recent elections with Helios
Helios has a lot of nice properties . . . but is assumes that voters are
doing their job.
Questions:Who participated in the IACR 2019 election?
Did you check that your ballot was present in the publicboard? When?
Did you use the “Audit” feature to check if you were notcheated by your machine?

37/37

IACR recent elections with Helios
Helios has a lot of nice properties . . . but is assumes that voters are
doing their job.
Questions:Who participated in the IACR 2019 election?
Did you check that your ballot was present in the publicboard? When?
Did you use the “Audit” feature to check if you were notcheated by your machine?
If you audited, did you put a random vote for the audited
ballot? (how?)

37/37