Russia is looking forward to its September 2019 elections for the representatives at the Parliament of the city (the Moscow City Douma). For the first time ever, Russia will use Internet voting in its elections. The internet-based system will use blockchain developed in-house by the Moscow Department of Information Technology. Since the news broke out, security experts have been quite skeptical about the overall applicability of blockchain to elections.
Moscow’s voting system has a critical flaw in the encryption scheme
Recently, a French security researcher Pierrick Gaudry has found a critical vulnerability in the encryption scheme used in the coding of the voting system. The scheme used was the ElGamal encryption, which is an asymmetric key encryption algorithm for public-key cryptography. Gaudry revealed that it can be broken in about 20 minutes using a standard personal computer and using only free software that is publicly available.
The main problem, Gaudry says is in the choice of three cyclic groups of generators. These generators are multiplicative groups of finite fields of prime orders each of them being Sophie Germain primes. These prime fields are all less than 256-bit long and the 256×3 private key length is too little to guarantee strong security. Discrete logarithms in such a small setting can be computed in a matter of minutes, thus revealing the secret keys, and subsequently easily decrypting the encrypted data.
Gaudry also showed that the implemented version of ElGamal worked in groups of even order, which means that it leaked a bit of the message. What an attacker can do with these encryption keys is currently unknown, since the voting system’s protocols weren’t yet available in English, so Gaudry couldn’t investigate further.
Following Gaudry’s discovery, the Moscow Department of Information Technology promised to fix the reported issue. In a medium blog post, they wrote, “We absolutely agree that 256×3 private key length is not secure enough. This implementation was used only in a trial period. In a few days, the key’s length will be changed to 1024.” (Gaudry has mentioned in his research paper that the current general recommendation is at least 2048 bits).
Even after the response, Gaudry was still concerned about potential flaws caused by the recent big changes fixing the key length issue.
Gaudy concerns proved true as recently another security researcher Alexander Golovnev, found an attack on the revised encryption scheme.
The revised encryption algorithm still leaks messages
Alexander Golovnev is the current fellow for Michael O. Rabin Postdoctoral Fellowship in Theoretical Computer at Harvard University. His research reveals that the new implementation of the encryption system also leaks a bit of the message. This is caused by the usage of ElGamal where the message is not mapped to the cyclic group under consideration. This flaw can be misused for counting the number of votes cast for a candidate, which is illegal (until the end of the election period).
Golovnev says that security vulnerability is a major issue of the implemented cryptographic scheme. The attack does not recover the secret key as required by the public testing scenario but rather breaks the system without recovering the secret key.
There is no response or solution from the Moscow Department of Information Technology regarding this vulnerability.
Many people took to Twitter to express their disappointment at Moscow’s lamentable internet voting system.
A. Golovnev: "An Attack on the the Encryption Scheme of the Moscow Internet Voting System" https://t.co/W08UosUD1e
Not 256-bit but 1024-bit Sophie Germain primes this time, but does not enforce points to be quadratic residues; A trivial 90's bug in 90's crypto. https://t.co/IAmr4imprN
— mjosdwez (@mjos_crypto) August 27, 2019
As Americans lose sleep over Russians hacking U.S. democracy, city officials in Moscow are trying to cover up how a French cryptographer massacred the code for their Internet voting system. https://t.co/Rc0UY9JFY9
— Kevin Rothrock (@KevinRothrock) August 20, 2019
In 2018, Robert Mueller’s report indicated that there were 12 Russian military officers who meddled with the 2016 U.S. Presidential elections. They had hacked into the Democratic National Committee, the Democratic Congressional Campaign Committee, and the Clinton campaign. This year, Microsoft revealed that Russian hackers ‘Fancy Bear’ are attempting to compromise IoT devices including a VOIP, a printer, and a video decoder across multiple locations. These attacks were discovered in April, by security researchers in the Microsoft Threat Intelligence Center.