Dtjytyk

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: the deployed e-voting systems can't have this flaw.

In the Swiss Post electronic voting protocol, after voters submit ballots, they are scrambled individually and shuffled together so that they cannot be traced back to voters to find who voted for whom—variously called ballot secrecy, privacy, or anonymity—before they are tallied.

But since the ballots are bits in an electronic system, not physical artifacts, it would be easy to fabricate shuffled ballots inside the magic vibrating silicon crystals in the computer that implements the shuffler. So the shuffler must also print a receipt that anyone in the world can use to verify that it is just a shuffling and not any other kind of alteration—part of universal verifiability of the election—while still keeping it secret who voted for whom.

The method of universal verifiability in the Swiss Post protocol, as in any electronic voting protocol with ballot secrecy, involves a lot of complicated math. And it turns out that the way the math was designed enables the vote shuffler to trivially forge a receipt for a fraudulent ‘shuffle’ that changes the outcome of the election.

How does it work?

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 with randomization $rho$. Randomization means the poll worker can't just check whether $c_i = E_k(b)$ for each possible ballot $b$ to recover what $m_i$ is.


• 
  

  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 to 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 or vote shuffler 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 $E_k(m, rho) := (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, of varying degrees of efficiency, to prove that what the vote shuffler sends to the vote counter to tally is, in fact, the set of $c_{pi(i)} cdot E_k(1, rho'_i)$.^‡ 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 method 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$. This is what the Scytl/Swiss Post system did.

  
  


• 
  

  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.

  
  
  

  The election authority could mitigate this by choosing commitment bases using another method, 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.

  
  

This may sound like a trivial mistake: oops, we forgot to zero a secret. But it illustrates a deeper problem.

The commitment bases $g_1, dots, g_n, h$ serve as a common reference string in a standard technique (paywall-free) for converting an interactive zero-knowledge proof system into a non-interactive zero-knowledge proof receipt like the vote shuffler is supposed to print out.

In an interactive proof system, the verifier might choose an unpredictable challenge—like which tunnel to come out of in the story of Ali Baba and the 40 thieves—which the prover must answer correctly. What if we want to make a non-interactive proof receipt that we can publish on a web site for anyone in the public to download and verify?

• In some protocols, like signature schemes such as Schnorr's derived using the Fiat–Shamir heuristic, the challenges can be replaced by a random oracle: a random function that the prover can evaluate on the transcript so far to imitate an unpredictable challenge that the verifier might have submitted, but that the prover has no control over. To instantiate such protocols, we choose a hash function like SHAKE128 that we hope has no useful properties the prover can exploit to forge fraudulent proofs.


• Similarly, in some protocols like Bayer–Groth we can use a common reference string: a predetermined bit string chosen randomly and known in advance to the verifier and prover. To instantiate such protocols, we need a system to pick a random string in advance with negligible probability that the prover can exploit properties of, like we get with FIPS 186-4 Appendix A.2.3. If the prover can influence the common reference string, the proof means nothing.
  

This is part of the security contract of a cryptosystem. To get any security out of AES-GCM, your obligation is to choose the key uniformly at random and keep it secret and never reuse it with the same nonce. To get any security out of a Bayer–Groth vote shuffler, the verifier and prover must agree in advance on a common reference string that the prover has no control over. In the Scytl system, the prover chose the common reference string. Not only did this violate the security contract, but it demonstrated a profound failure to understand the basic premises of the non-interactive zero-knowledge proof system they used.

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 review the process of how we got here 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 Swiss Post.)

_{^* 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 vote counter must also be able to prove that the tally it returns is the sum of the plaintexts of the encrypted ballots that are fed to it, which we will not address here—the specific back door under discussion here is in the vote shuffler.}

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.