Argthtjtr

I read that the Swiss post had an e-voting solution developed, made it possible to obtain the source code for review, and that vulnerabilities were found.

Apparently we are not talking about the inherent and well-known issues of e-voting: it can't prevent purchasing of vote, and penetration of the voter's device can allow turning a vote around. Nor are we talking about the (reportedly laughable) code quality for the IT infrastructure, or its vulnerability to Denial of Service attack.

No. It was found a cryptographic flaw of some kind, by three independent teams:

• Sarah Jamie Lewis, Olivier Pereira and Vanessa Teague: Ceci n’est pas une preuve, The use of trapdoor commitments in Bayer-Groth proofs and the implications for the verifiabilty of the Scytl-SwissPost Internet voting system (see introduction)


• Rolf Haenni: Swiss Post Public Intrusion Test: Undetectable Attack Against Vote Integrity and Secrecy (referring page).


• Thomas Edmund Haines (NTNU).

How was the proposed system supposed to work, and what was wrong with it or its implementation ?

We can stand reassured by the officials (in French): the deployed e-voting systems do not have this flaw.

Let $m_1, m_2, dots, m_n$ represent filled-out ballots in an election. We want to keep the ballots secret, but compute the vote tally, and let the public verify the vote tally.

• The poll workers see who submitted each ballot $m_i$, so we first encrypt the ballot as $c_i = E_k(m_i, rho_i)$ to conceal it from the poll worker who puts it in the pile of ballots, where $E_k(m, rho)$ is a randomized public-key encryption scheme.


• 
  

  The vote counter, who knows the secret key, then takes the pile of encrypted ballots, decrypts them, and tallies the results.

  
  
  
  
  
  • Since the poll worker could pass along who voted in which order, we enlist the aid of a vote shuffler to shuffle the votes into the order $c_{pi(1)}, c_{pi(2)}, dots, c_{pi(n)}$ for a secret permutation $pi$.^†
    
  
  
  • 
    

    Since the vote counter could eyeball $c_{pi(i)}$ to discern whether it is the same as $c_j$ and thereby recover what $pi$ is, we also ask the vote shuffler scramble each vote without changing the ballot it conceals.

    
    
    

    If $E_k$ is homomorphic in the message and randomization, meaning $$E_k(m_1 m_2, rho_1 + rho_2) = E_k(m_1, rho_1) cdot E_k(m_2, rho_2),$$ then we can scramble the votes by $$c'_i = c_{pi(i)} cdot E_k(1, rho'_i) = E_k(m_{pi(i)}, rho_{pi(i)} + rho'_i)$$ for secret randomization $rho'_i$.^† Then we pass $c'_1, c'_2, dots, c'_n$ on to the vote counter.

    
    
  
  
  
  


• 
  Members of the public only have their own receipts $c_i$, which without the private key are indistinguishable from one another and from the $c'_i$. To have confidence that the vote counter isn't fraudulently changing the outcome of the election by replacing $m_i$ by some malicious $hat m_i$, the system must be verifiable to members of the public.^‡
  

The canonical example of a homomorphic randomized public-key encryption scheme is Elgamal encryption $(m, rho) mapsto (g^rho, k^rho cdot m)$ where $g, k, m in G$ are elements of a group $G$ in which discrete logs are hard, and the secret key for $k$ is the exponent $x$ such that $k = g^x$. Here multiplication of ciphertexts $(a, b) cdot (c, d)$ is elementwise, $(a cdot c, b cdot d)$.

There have been many systems over the years to prove that what the vote counter tallies is, in fact, the set of $c_{pi(i)} cdot E_k(1, rho'_i)$, of varying degrees of efficiency. One of them is Bayer–Groth (full paper). There's a lot of cryptidigitation building on decades of work to make an efficient non-interactive zero-knowledge proof—a receipt that any member of the public can use offline to verify that the $c'_i$ are in fact the $c_{pi(i)} cdot E_k(1, rho'_i)$, without learning what $pi$ or the $rho'_i$ are.

The key part in question is the use of Pedersen commitments to commit to exponents $a_1, a_2, dots, a_n$ with randomization $r$ by sharing the commitment $$operatorname{commit}_r(a_1, a_2, dots, a_n) := g_1^{a_1} g_2^{a_2} cdots g_n^{a_n} h^r,$$ where the group elements $g_1, g_2, dots, g_n, h in G$ are independently chosen uniformly at random.

The commitment itself gives no information about $(a_1, a_2, dots, a_n)$ without $r$ because all commitments are equiprobable if $r$ is uniform—that is, Pedersen commitments are information-theoretically hiding. But the commitment and randomization $r$ enable anyone to verify the equation for any putative $(a'_1, a'_2, dots, a'_n)$ to get confidence that they are the $(a_1, a_2, dots, a_n)$ used to create the commitment in the first place: if you could find a distinct sequence $(a'_1, a'_2, dots, a'_n) ne (a_1, a_2, dots, a_n)$ and randomization $r'$ for which $$operatorname{commit}_r(a_1, a_2, dots, a_n) = operatorname{commit}_{r'}(a'_1, a'_2, dots, a'_n),$$ then you could compute discrete logs of $h$ and $g_i$ with respect to one another—a pithy summary of which is that Pedersen commitments are computationally binding under the discrete log assumption. (Proof: If $g_1^{a_1} h^r = g_1^{a'_1} h^{r'}$, then $log_{g_1} h = frac{a'_1 - a_1}{r - r'}$.)

The Bayer–Groth shuffler uses Pedersen commitments to commit to one $pi$ and to the randomization values $rho'_i$ in the receipt that the public can use to verify the set of votes submitted to the vote counter. If the vote shuffler could lie and claim to use a permutation $pi$, while they actually use a function that repeats some votes and discards others, then they could fraudulently change the outcome of the election. The Lewis–Pereira–Teague paper goes into some details of how this works.

• 
  

  One way to look at this reliance on Pedersen commitments is that the discrete logarithm problem seems hard, so we just have to choose the commitment bases $g_1, dots, g_n, h$ independently uniformly at random.

  
  
  

  The obvious way to pick group elements independently uniformly at random is to pick exponents $e_1, dots, e_n, f$ independently uniformly at random and set $g_1 := g^{e_1}, dots, g_n := g^{e_n}, h := g^f$.

  
  


• 
  

  Another way to look at this is holy shit, the exponents $e_1, dots, e_n, f$ are a secret back door, knowledge of which would enable the vote shuffler to commit essentially arbitrary vote fraud—just like the Dual_EC_DRBG base points.

  
  
  

  One way to mitigate this would be to choose the commitment bases another way, like FIPS 186-4 Appendix A.2.3, which probably makes it difficult to learn the back door exponents, and which can be verified; this is allegedly what Scytl has elected to do to fix the issue, although I have no idea whether they have published the hash preimages necessary to conduct the verification.

  
  

The public evidence is unclear about whether the authors knew this would serve as a back door, and the Lewis–Pereira–Teague paper cautions that this could be a product of incompetence rather than malice—the technical nature of the flaw was known internally since 2017 (archived) but it's unclear the whether consequences were understood. It could have been incompetence on the part of NIST that they adopted Dual_EC_DRBG—NIST recognized early on that there was something fishy about the base points and was told not to discuss it by NSA.

The first order of business is not to argue about whether the software vendor Scytl was malicious or incompetent, but to be taken seriously enough by election authorities to demand real scrutiny on designs, not a sham bug bounty hampered by an NDA just before deployment, and to ensure that designs with back doors like this must never even come close to being deployed in real elections because they enable extremely cheap arbitrarily massive unverifiable vote fraud.

(One can argue whether the larger problems arise from undetectable centralized fraud in electronic voting; distributed fraud in voting by mail; or voter suppression by gerrymandering, felony disenfranchisement, and closure of polling stations. One can argue about other IT issues, about the importance of paper trails and mandatory risk-limiting audits, etc. Such arguments should be had, but this question is not the forum for them—consider volunteering as an election worker instead or talking to your parliament! This question is specifically about the technical nature of the misapplication of cryptography, whether negligent or malicious, by Scytl and SwissPost.)

_{^† We assume that there is an omniscient mass surveillance regime monitoring the every action of the vote shuffler to ensure they do not collude with anyone else to reveal secret ballots. The omniscient mass surveillance regime is also honest and would never dream of colluding with anyone themselves—not wittingly.}

_{^‡ We assume that the public consists entirely of people with PhDs in cryptography, like the country of Switzerland.}

The problem was the poor design of the scheme, specifically the part for universal verifiability.

As the paper Ceci n’est pas une preuve states:

To guarantee anonymity of the votes the scheme makes use of mixnets which rely on the shuffle proof by Bayer and Groth (a generalisation of Pedersen commitments), which then further relies on the discrete logarithm assumption.

Commitment schemes that rely on the discrete log assumtion can be called trapdoor commitment schemes, because they rely on the fact that no one can learn the discrete log. This is perfectly okay, but:

The concrete problem arose from the fact that in the design of this scheme the commitment parameters are generated randomly. This random parameter is the actual secret used to get the discrete logarithm. Furthermore it can't be guaranteed that this value is then safely deleted from the memory. This ultimately breaks the commitment scheme.

So, an adversary can exploit this problem by for example compromising this PRNG by weakening the randomness of the PRNG.

On the question about if this problem was introduced intentionally they said (on page 9):

Nothing in our analysis suggests that this problem was introduced deliberately. It is entirely consistent with a naive implementation of a complex
cryptographic protocol by well-intentioned people who lacked a full understanding of its
security assumptions and other important details. Of course, if someone did want to
introduce an opportunity for manipulation, the best method would be one that could
be explained away as an accident if it was found. We simply do not see any evidence
either way.