Risk of privacy breach due to the CCMs not checking the ZKP before mix-decrypting
Title: Risk of privacy breach due to the CCMs not checking the ZKP before mix-decrypting.
Brief Description/ Summary
During the tally phase, according to the specification, CCM_i takes its input from CCM_{i-1}, and it is not supposed to check the ZKP associated to the mixing and decryption made by the previous CCMs. A honest CCM_i will then mix and do the partial decryption using its private key, and send the result to CCM_{i+1}.
The danger is to offer a (partial) decryption oracle, leading to a privacy breach.
The verification of the ZKPs of the CCMs is performed by the auditors at several stages: after the CCM_3 has finished, and at the very end. The rules say that privacy should be preserved when only 1 CCM is honest. Everywhere in our discussion, we will assume that this honest CCM is CCM_2.
A first attack that does not work directly is the following:
- CCM_1 (dishonest) produces a fake list of encrypted ballots; this list contains only the ballot of Alice (the target voter of the privacy attack), maybe replicated/rerandomized to have a list that have a plausible length. This list is suffled and partially decrypted by CCM_1 (as expected) and sent to CCM_2.
- CCM_2 (honest), shuffles and partial-decrypts the list and sends it to CCM_3.
- CCM_3 (dishonest) and CCM_4 (dishonest) use their secret keys to finish the decryption of this list and get the vote of Alice.
- Later on, the auditor will detect that the ZKPs produced by CCM_1 are invalid (or inexistent).
The reason why this does not work is that CCM_4 does not have the decryption key itself. It receives it from the Electoral Board. And the Electoral Board will give the key to CCM_4 only if the Auditors have validated the checks after CCM_3 has finished.
We still believe there is a high risk, because there are various scenarios where the CCM_2 could be fooled and use its key on a wrong list of ballots, while CCM_4 gets its decryption key from the Electoral Board.
We propose a few scenarios below, in the "Impact" section.
Steps to Reproduce the Problem
N/A. The problem is in the specification.
Expected Behavior
Privacy.
Actual Behavior
Under the threat model of the Chancellery, the attacker has the ability to break privacy of several voters of her choice, without being detected.
Note that privacy depends on implementation details / practical decisions, that are not specified in the specification document.
Impact
The potential impact is high, with Alice's vote revealed to the attacker, without detection.
Scenario 1: force a replay after failure
Take again the same start as in the summary (CCM_2 is the only CCM that is honest):
- CCM_1 builds up a fake list containing only Alice's vote, mix-decrypts it and sends it to CCM_2.
- CCM_2 mix-decrypts and sends to CCM_3.
- CCM_3 mix-decrypts and sends to CCM_4.
- Auditors check the ZKPs and realise that there is a problem.
Here, the specification does not say what should be done. Maybe the whole election will be aborted and started again, possibly with a punishment imposed on CCM_1 for misbehaving. The cost would be very high: the voters would need to vote again, and the image of SwissPost would suffer a lot. It is therefore likely that the unspecified behavior will become "ok, let's decrypt the real ballot box, now". And then, CCM_4 (dishonest) will learn the decryption key from the Electoral Board, and it can send it to CCM_3 (also dishonest) who will decrypt Alice's vote. The CCM_4 is "offline", but this does not mean it can not communicate with CCM_3 in any way.
Scenario 2: multiple tallies with the same keys
We did not find the details of how the many counting circles are implemented in the system. The specification document talks only about "election event", while in the crypto proof document the only occurrence of "counting circle" is in the sentence: We assume that election administrators prevent trivial privacy breaches by selecting the counting circles appropriately.
In the CHVote specification, the terminology "election event" and "counting circle" are used, and the same keys are used for many counting circles that need to be tallied separately.
Hence, in practice, the previous scenario will actually affect several elections. Let assume here that the CCM processes several elections simultaneously, e.g. from different elections circles. More specifically, assume there are k elections: E1, ..., Ek.
- CCM1 will replace the ballots of election E1 by only the ballot of Alice, yielding an election E1'. Then CCM1 behaves normally on E1', E2, ..., Ek
- CCM2 proceeds as expected, such as CCM3.
- During the VerifyOnlineTally, the mismatch will be discovered. The only options are to either lose Alice's privacy or to lose the k elections. Indeed, in case the authorities decide to proceed, CCM4 will learn the key of the election board and will be able to decrypt Alice's ballot. Hence the pressure will be high to just proceed.
Scenario 3: fake additional elections, privacy breach UNDETECTED
Actually, CCM1 can make things worse. Let still assume that several elections are processed at the same time, namely E1, ..., Ek, all using the same keys.
- CCM1 will produce one additional election E_{k+1} that contains only Alice's ballot. CCM1 then proceeds normally on E1, ..., Ek, E_{k+1} and submits then k+1 elections to CCM2.
- CCM2 mixes and decrypts the k+1 elections.
- Since the communication channel of CCM2 is untrusted, the (k+1)th election (containing the partially decrypted ballot of Alice) will NOT be sent to any authority. It simply does not appear on any public board.
- then CCM3 proceeds as expected on the k normal elections. Note that since CCM3 is corrupted, it can take care of erasing the (k+1)th election.
- All the tests succeed and the decryption proceeds with CCM4 and the election board.
- with the key of the election board learnt by CCM4, the three dishonest CCMs can now collaborate to complete the decryption of Alice's ballot.
Note that if the attacker wishes to break the privacy of more voters (say a dozen), she may simply create more additional elections at the first step (and then again eliminate them as soon as CCM2 outputs its result).
Note also that this attack can be adapted to the case of elections using different keys.
Severity
High
Possible Solution
A possibility would be to make the specification more precise to take into account all our scenarios and make them invalid by adding more checks for the CCM and taking the risk of having to cancel elections. But leaving a risk of a decryption oracle is dangerous now (we might have missed some scenarios) and even more in the future, where modifications to the protocol and to the implementation might introduce new ways to fool a CCM.
Therefore we consider that it would be much safer to have the CCMs check the ZKP themselves before sending their output to the next CCMs. More specifically, each CCM should:
- receive the initial set of ballots, signed by the auditors
- check the ZKP corresponding to the first mix, the second one, etc. up to the CCM position.
The risk is high, also because the current proofs (computational and symbolic) have difficulties to capture this kind of attacks where, for instance, multiple elections are run in parallel with the same keys.