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.
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.
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
First critical article published:
"Internet voting in Russia: how?" by Julia Krivonosova (Tallinn Universiity of Technology)
New public keys and encrypted messages published for contest on
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)
Probably DIT decide to use 256 bit unsigned integer for the keys because it is maximal supported length in Ethereum Solidity smart contract.
Full paper published.
"Breaking the encryption scheme of the Moscow internet voting system" by Pierrick Gaudry
pdf on arxiv.org
Meduza have repeated P.Gaudry decryption from the paper for last messages published Aug. 7
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.
DIT stops publishing revealed private keys and original data on
So, formally we could not compare Medusa's published private key and original messages now. But with cracked private key and known
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 (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
- 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.
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)
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.
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.
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)
- 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)
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?