Breaking Moscow blockchain voting

September 8, 2019 is election day to Moscow City Duma for 45 available seats. Moscow Duma is an authority responsible for city budget. Planned Moscow city budget expenses for 2019 is more than 40B USD! So, it is enough to run Moscow own space program.

About 6% of voters could use online electronic system based on private blockchain over Internet as experiment. This is a first live blockchain election system in the world!

I'm omitting political aspects of the election and consider only a technical side. (Only mention that opposition candidates were not permitted to register, that cause a massive protests and arrests).

The system closely developed by Department of IT (DIT) of Moscow government and hosted on portal of Moscow mayor: mos.ru/city/projects/blockchain-vybory/ (Russian). Unfortunately, there is no published technical requirements or system descriptions. All information was gathering from different open media sources.

System architecture

Voting is open during 12 hours in a particular voting day. Voter should authenticate themselves on official Moscow mayor web-portal using login, password and SMS code. After authentication a voter pass to ballot web-form with URL randomly generated from some systems hashes. The ballot is available for voting only for 15 minutes. Re-voting is not possible.

Voter select a candidate from available candidates' list on the ballot. An integer number representing the selected candidate is encrypted by JavaScript code loaded to voter's browser. ElGamal encryption algorithm is used. Encrypted data saved to private Ethereum blockchain (Parity node) with Proof of Authority consensus. In order to make votes anonymous, a private anonymizer software is used (like a TOR proxies). All votes passing through proxy nodes for mixing and random delay. Each vote is an Ethereum transaction from one-time address with a private key erased after browser closing. After saving transaction to the Ethereum smart contact, the ballot is printing on a paper hard copy with encrypted voting data.

I'll present the voting breaking story in a chronological order.

Jul 17 (53 days before the election)

Public intrusion contest was announced with almost 30K USD award.
Initial commit on Github by a-borodenkov
moscow-technologies/blockchain-voting

The code contains Javascript files and Solidity smart contracts. DIT as well published public keys and encrypted messages as a challenge for contest. Participant should decrypt messages during 12 hours. After that private keys and original messages will published for verification.

Jul 19

First critical article published:
"Internet voting in Russia: how?" by Julia Krivonosova (Tallinn Universiity of Technology)
link

Aug 7

New public keys and encrypted messages published for contest on
github

Aug 8

Epic fail! Unbelievable that DIT developers thought that by using 3 times ElGamal encryption with 256 bit keys will be equivalent of 3x256 key strength. Pierrick Gaudry have reported that he restore private keys from public and decrypt original messages in 20 minutes on common PC. It is totally insecure.

"Breaking the encryption scheme of the Moscow internet voting system" by Pierrick Gaudry (CNRS, Inria, Université de Lorraine)
Blog post

Probably DIT decide to use 256 bit unsigned integer for the keys because it is maximal supported length in Ethereum Solidity smart contract.

Aug 14

Full paper published.
"Breaking the encryption scheme of the Moscow internet voting system" by Pierrick Gaudry
pdf on arxiv.org

Aug 16

Meduza have repeated P.Gaudry decryption from the paper for last messages published Aug. 7
Meduza (Russian)

Authority officially not agreed that the system was compromised, despite that P.Gaudry exactly complete the challenge described in public contest conditions. They insist that the system was not broken.

Aug 18

DIT stops publishing revealed private keys and original data on
github

So, formally we could not compare Medusa's published private key and original messages now. But with cracked private key and known modulos, generators you could easily calculate publicKeys and compare it. They are really the same.

for i in range(3):
    pk = pow(generators[i], meduza_k[i], modulos[i])
    print(pk)
    print(publicKeys[i])

Aug 20

The information about Moscow election system break widely spreads over Internet.
"Moscow's blockchain voting system cracked a month before election" by
ZDnet
YC news
Meduza new article.

Aug 20 (19 days before the election)

DIT take into account P.Gaudry's paper and changed their multilevel encryption scheme with 3x256 bit keys to one 1024 bit key. By the way, the 2048 bit key length is recommended today.

Security update (commit 7aa9f71)
smart-contracts/packages/crypto-lib/src/multiLevelEncryptor.js - was deleted

smart-contracts/packages/crypto-lib/src/utils.js

- const BIG_TWO = new BigInt('2');
- const SOLIDITY_MAX_INT = BIG_TWO.pow('256').subtract(BigInt.ONE);
+ const KEY_BIT_LENGTH = 1024;
+ const CRYPTO_MAX_INT = BigInt.ONE.shiftLeft(KEY_BIT_LENGTH + 1).subtract(BigInt.ONE);

P.Gaudry is awarded for a half of reward pool (about 15K USD) as a bug bounty.

Aug 24

New researcher publish a new vulnerability in ElGamal implementation. This time we could found some voting results without actual decryption! DIT developers was not aware that encrypting messages that are not quadratic residues of modulo p are vulnerable.

"An Attack on the the Encryption Scheme of the Moscow Internet Voting System" by Alexander Golovnev (Harvard University)
pdf

So, since only integer ID number of candidate is encrypted, we could investigate encrypted messages and recognize the given votes number for example for candidate with ID = 2 before election end. That is prohibited by Russian voting law.

Sep 5

Independent auditors from GolosInfo published "Results of final system testing was done on Aug 28".
Conclusion: The system usage could cause critical fails and intrusions.
Report (Russian)

Sep 6 (TWO days before the election)

DIT take into account A.Golovnev's paper and changed encryption function one more time.
Smart contract fix (commit 4cd9144)
smart-contracts/packages/crypto-lib/src/elGamal.js

-    const sharedKey = this.publicKey.modPow(sessionKey, this.moduleP);
+    const squaredData = dataAsBI.modPow(new BigInt('2'), this.moduleP);

-    const b = sharedKey
-      .multiply(dataAsBI)
+    const b = this.publicKey
+      .modPow(sessionKey, this.moduleP)
+      .multiply(squaredData)

Sep 7

Official keys generation procedure should be done not later then 6 pm on a PC with air gap. Keys should be divided into 7 parts. The parts copied to flash storages and passed to selected 7 different people. Then the private key should be erased from the PC. If one of the parts lost, the decryption impossible.

Sep 8 (Moscow City Duma election 2019!)

Several system fails was reported with the system unavailability.

Private key should be combined again from the parts not later then 8:30 pm. The private key loading to blockchain for votes decryption and manual counting.

Sep 9 (Election results revealed)

Finally 10.2K electors had voted over e-voting system, that is almost 92% (sic!) of registered e-voters. Moscow offline average voting is only 21%.

Deployed blockchain-voting system is very controversial. The system is fully under Moscow government control without possibility to monitor it. Many question are still open:

• How we can be confident that in the voting day will be used proven cryptography?
• How we can be confident that exactly the same code published on Github will be used in voting day?
• How we can check does encrypted message in the blockchain contain correct voting?
• How we can prove that there was no any fake votes injected or votes censored?
• How we can be sure that the system is not logged voter authentication info during fill in ballot?