Verifying Gentoo election results via Votrify

Gentoo elections are conducted using a custom software called votify. During the voting period, the developers place their votes in their respective home directories on one of the Gentoo servers. Afterwards, the election officials collect the votes, count them, compare their results and finally announce them.

The simplified description stated above suggests two weak points. Firstly, we rely on honesty of election officials. If they chose to conspire, they could fake the result. Secondly, we rely on honesty of all Infrastructure members, as they could use root access to manipulate the votes (or the collection process).

To protect against possible fraud, we make the elections transparent (but pseudonymous). This means that all votes cast are public, so everyone can count them and verify the result. Furthermore, developers can verify whether their personal vote has been included. Ideally, all developers would do that and therefore confirm that no votes were manipulated.

Currently, we are pretty much implicitly relying on developers doing that, and assuming that no protest implies successful verification. However, this is not really reliable, and given the unfriendly nature of our scripts I have reasons to doubt that the majority of developers actually verify the election results. In this post, I would like to shortly explain how Gentoo elections work, how they could be manipulated and introduce Votrify — a tool to explicitly verify election results.

Gentoo voting process in detail

Once the nomination period is over, an election official sets the voting process up by creating control files for the voting scripts. Those control files include election name, voting period, ballot (containing all vote choices) and list of eligible voters.

There are no explicit events corresponding to the beginning or the end of voting period. The votify script used by developers reads election data on each execution, and uses it to determine whether the voting period is open. During the voting period, it permits the developer to edit the vote, and finally to ‘submit’ it. Both draft and submitted vote are stored as appropriate files in the developer’s home directory, ‘submitted’ votes are not collected automatically. This means that the developer can still manually manipulate the vote once voting period concludes, and before the votes are manually collected.

Votes are collected explicitly by an election official. When run, the countify script collects all vote files from developers’ home directories. An unique ‘confirmation ID’ is generated for each voting developer. All votes along with their confirmation IDs are placed in so-called ‘master ballot’, while mapping from developer names to confirmation IDs is stored separately. The latter is used to send developers their respective confirmation IDs, and can be discarded afterwards.

Each of the election officials uses the master ballot to count the votes. Afterwards, they compare their results and if they match, they announce the election results. The master ballot is attached to the announcement mail, so that everyone can verify the results.

Possible manipulations

The three methods of manipulating the vote that I can think of are:

  1. Announcing fake results. An election result may be presented that does not match the votes cast. This is actively prevented by having multiple election officials, and by making the votes transparent so that everyone can count them.
  2. Manipulating votes cast by developers. The result could be manipulated by modifying the votes cast by individual developers. This is prevented by including pseudonymous vote attribution in the master ballot. Every developer can therefore check whether his/her vote has been reproduced correctly. However, this presumes that the developer is active.
  3. Adding fake votes to the master ballot. The result could be manipulated by adding votes that were not cast by any of the existing developers. This is a major problem, and such manipulation is entirely plausible if the turnout is low enough, and developers who did not vote fail to check whether they have not been added to the casting voter list.

Furthermore, the efficiency of the last method can be improved if the attacker is able to restrict communication between voters and/or reliably deliver different versions of the master ballot to different voters, i.e. convince the voters that their own vote was included correctly while manipulating the remaining votes to achieve the desired result. The former is rather unlikely but the latter is generally feasible.

Finally, the results could be manipulated via manipulating the voting software. This can be counteracted through verifying the implementation against the algorithm specification or, to some degree, via comparing the results a third party tool. Robin H. Johnson and myself were historically working on this (or more specifically, on verifying whether the Gentoo implementation of Schulze method is correct) but neither of us was able to finish the work. If you’re interested in the topic, you can look at my election-compare repository. For the purpose of this post, I’m going to consider this possibility out of scope.

Verifying election results using Votrify

Votrify uses a two-stage verification model. It consists of individual verification which is performed by each voter separately and produces signed confirmations, and community verification that uses the aforementioned files to provide final verified election result.

The individual verification part involves:

  1. Verifying that the developer’s vote has been recorded correctly. This takes part in detecting whether any votes have been manipulated. The positive result of this verification is implied by the fact that a confirmation is produced. Additionally, developers who did not cast a vote also need to produce confirmations, in order to detect any extraneous votes.
  2. Counting the votes and producing the election result. This produces the election results as seen from the developer’s perspective, and therefore prevents manipulation via announcing fake results. Furthermore, comparing the results between different developers helps finding implementation bugs.
  3. Hashing the master ballot. The hash of master ballot file is included, and comparing it between different results confirms that all voters received the same master ballot.

If the verification is positive, a confirmation is produced and signed using developer’s OpenPGP key. I would like to note that no private data is leaked in the process. It does not even indicate whether the dev in question has actually voted — only that he/she participates in the verification process.

Afterwards, confirmations from different voters are collected. They are used to perform community verification which involves:

  1. Verifying the OpenPGP signature. This is necessary to confirm the authenticity of the signed confirmation. The check also involves verifying that the key owner was an eligible voter and that each voter produced only one confirmation. Therefore, it prevents attempts to~fake the verification results.
  2. Comparing the results and master ballot hashes. This confirms that everyone participating received the same master ballot, and produced the same results.

If the verification for all confirmations is positive, the election results are repeated, along with explicit quantification of how trustworthy they are. The number indicates how many confirmations were used, and therefore how many of the votes (or non-votes) in master ballot were confirmed. The difference between the number of eligible voters and the number of confirmations indicates how many votes may have been altered, planted or deleted. Ideally, if all eligible voters produced signed confirmations, the election would be 100% confirmed.