I’m back from vacation — it was a good time. I had some thoughts about software assurance and it’s role in voting, and I thought of this analogy.

Suppose we have two bridges, built by the vendor BridgeTec. Both have the same general design — they look the same, and they use the same materials. Bridge A was built first and B was built shortly after. Some time later, the state in which bridge A was built asks some engineers to do a study. The study finds significant structural defects in the bridge and closes it down until BridgeTec fixes the problems.

BridgeTec admits to the problems but says that it’s not been shown that these problems will manifest themselves in the real world, and that bridge B is fine because “it’s a different bridge”.

Who in their right might would believe that?

Yet, thats the gist of what Diebold, Sequoia, and Hart InterCivic are saying.

To me, the very notion that “it’s different” can be used as an excuse and *anyone* can think that it is valid is confusing to me. Likewise, the idea that problems won’t manifest themselves due to procedures in the real world are almost as equally confusing — you could only really make that claim after you know what the procedures are and have justified why they will protect you.

They really should “prove” to you that it’s secure, and they could do that with assurance building activities as they are talked about in an often cited paper by Brian Snow titled “We Need Assurance!”. Right now people are operating on the principle that “it hasn’t been proven otherwise”, and that’s just flawed on so many levels. Instead we should be operating on the principle “show me why”.

While there are lots of definitions of Software Assurance, I prefer NISTs: “the planned and systematic set of activities that ensures that software processes and products conform to requirements, standards, and procedures to help achieve:

• Trustworthiness - No exploitable vulnerabilities exist, either of malicious or unintentional origin, and
• Predictable Execution - Justifiable confidence that software, when executed, functions as intended.”

Maybe the school of thought is that, indeed, they have shown it is secure by passing certification requirements. However, as Rubin has noted, the certification process isn’t really set up properly. The fact that 3 vendors have been shown to suffer from the most basic security problems only goes to show how badly the process is broken.

What we are doing, and what they really should have been doing all along, is to try to build security into the system from the beginning. Unfortunately, the cost cutting nature of the industry would never allow such a thing back then, but now we can see that they are paying for it now.

Voting is a unique large scale system intended for use by the public for a very short time. Thus, it has a need for a higher level of the assurance than other systems that are used daily by the public. With this in mind, we can add reliability, scaleability, and recoverability to our list of goals that voting systems should strive toward. These goals are not unique to voting systems, and there are many goals voting systems should meet that are not listed here, but the nature of a voting system makes these goals stand out.

Scalability

The system should scale, but when we say scale we mean many things. The first of which is that it should scale with the number of voters. There should not be an upper limit to the number of voters, and the counting processes should still finish in a reasonable amount of time after the election is complete. This should also be true for the number of candidates per race and number of races per ballot, although there is a limit to what most people are able to tolerate. Lastly, the system should not have technical limitations preventing it from implementing certain election rules such as plurality, approval voting, range voting, and rank voting systems.

Reliability

It must be more reliable and resistant to disruption than the power grid, and any voting system must support a way to continue operation without power. Barring natural disaster or violent military actions that keep voters away from the polls, the system must work.

Recoverability

There should be ways to recover as best as is possible from catastrophic failures. In many cases this is a matter of redundancy and procedures (e.g. constantly publish the current count of votes each time period). The difficulty here is that you wish to achieve recoverability without drastically affecting the rest of the system or putting a lot of responsibility on volunteers.

That’s all I have for now, and I am heading out for a vacation. For those who have been following, I look forward to reading your comments when I get back (as I am certain there are many other goals that I am missing). I think a next step for this discussion would be to make some sort of report card for systems we’ve come across. Suggestions are welcome, I hope my posts so far have got you thinking.

Verifiability is not really a goal or property of voting systems on its own. It is an added constraint on the properties we have discussed so far which many systems fail to achieve. When we say a system meets the criteria that it has verifiable coercion resistance, or that the recorded as cast property is verifiable, we mean that someone can check or audit to make sure that the property is working as the system is being used.

The question of who, how, and when is important when discussing the verifiability of any property. Recall that cast as intended means a voter is able to properly record her vote. If this property were always verifiable, then the system cannot be coercion resistant, however, we can reasonably conclude that this should be verifiable in the voting booth.

The proper recording and transmission of that vote to the counting authority is something that would be nice to be verifiable by the voter, but this is where many systems fall short. Likewise, we would want everyone to be able to verify the counting process, but that is not typically available with current technology.

Observe that there is a careful relationship between verifiability in voting systems and coercion resistance. If too many things are verifiable, then we may lose coercion resistance. The goal should be to make things as verifiable as possible without losing basic coercion resistance.

Coercion resistance, otherwise known as voter privacy or receipt-freeness, is the inability of someone other than the voter to know how she voted. It is meant to protect each voter from the sometimes powerful outside influence of a spouse, boss, political leader, or other individual who seeks to gain legitimate political power by threat of force or other undesirable consequences for the voter. It is the key concept behind the secret ballot when it was (re)introduced in the 1800s.

Unfortunately, given an entity with enough power to control all aspects of the process, no voting system in existence fully meets this property, and it might be impossible, particularly if we expect to maintain our goals for integrity. Thus, it is debatable how strong we should make our privacy property so that it is a useful, attainable goal. At a minimum, we
should expect to be reasonably protected from 3rd party thugs that are not involved with the voting process. After that, the degree to which an insider must be involved to reliably violate a voter’s privacy and where we should draw the line is unclear because so much of a voting system’s privacy depends on the environment in which it is used.

That said, it is also important to take into account the capabilities of a voter or attacker. If we assume that a voter could have some sort of undetectable futuristic ocular implant that allows an outsider to see what she saw, how could we reasonably protect against such a thing without, of course, assuming a similarly futuristic device is available to combat this threat?

Integrity in a voting system means that votes are counted as cast and can be split into three different properties: cast as intended, recorded as cast, and counted as recorded. This split represents three (3) different phases of the transfer of intention from the voter to the counting authority: the voter’s expression of their intention, the recording device’s acceptance of that intention, and the actual counting of that intention.

Notice that the counting step and intention step are always necessary in a voting system, or we could not produce election results. We need to count, and in order to do that we must know the intention of each voter. Also, observe that dropping the intermediate step can cause problems. Suppose we count as we receive intention without recording. If we make mistakes there is no way to go back to a record to correct our count. Therefore, these three properties are necessary, but not sufficient, goals for any voting system. As we will see, most voting systems can be said to meet all three of these properties, but the degree to which they do is suspect. We attempt to formally define and discuss each property below.

Cast as Intended

This property represents the ability of the voter to properly convey her intentions, and cast her vote as she intended it to be cast. Some voting systems can achieve this property better than others, as it is in some respects an issue of usability. However, we limit this property to mean that a voter can properly transfer her intention, and not necessarily that she succeed in doing so in real world conditions.

An example of a system in which this is not possible would be one that does not always list all of the candidates in each race, or one in which there is only one spot to record a vote for two separate candidates. Using this definition there are no known systems in existence that do not meet this property (we’ll talk more about this later).

By contrast, many systems do not to support this property very well. This can be seen with the butterfly ballot. It was used in the 2000 presidential election in Florida, and is said to have cost Al Gore the U.S. presidency.

Recorded as Cast

When a vote is recorded as cast, the device used by the voter has properly recorded her intention and this record has made it to the counting authority. This can encompass a conversion from analog to digital representation, if that conversion is not an aggregation (i.e. there is no counting).

A system that weakly supports this property will faithfully record a vote as cast by the voter and will provide a mechanism for delivering it to the counting authority. Most systems are capable of this property, but the caveat of this and all of the integrity properties is that they are rarely verifiable, which we’ll discuss later.

Again, if judged on a sliding scale metric, there are many systems that would not satisfy this property very well. There are also numerous problems with automated counting of paper records where votes are not counted, and this would be a recorded as cast problem. Most notable is the “hanging chad”. In this situation, properly maintained equipment would have prevented the problems, but built up wastepaper in the machines caused them not to properly record each voter’s intentions.

Counted as Recorded

This means that from the record of votes cast, the counting authority is able to provide an accurate aggregation of the data. The counting authority can be a group of volunteers or machines, or a mix of both. The key property is that the results at this point in the process are reliably accurate, and to do so may require redundant counting by several imperfect entities to verify a proper total.

As is the case with the other two properties, some systems may achieve this property better than others. The biggest concern in this property is how easily the record can be violated. This is a problem in most systems. Paper can be altered to invalidate votes, replaced, or destroyed and digital storage is, in general, easily manipulated.

Digital Recording Electronic (DRE) devices and their memory cards have consistently been shown not to properly support even basic protection mechanisms on their records. This is particularly problematic as they typically only store aggregate counts, and not full ballots for each voter. So, some counting is done on the machine, and totals from the machine are added with those from the other machines. The cards themselves have also been shown to be easily misplaced.

Many DREs try to combat these problems with redundant storage, but there is no reason why redundant storage that can be manipulated by the same processor would solve these issues. One solution to this problem is to have independent redundant storage devices, but outside of an investigation, it is not clear how voting officials should or would deal with total mismatches on these independent storage devices. The cost of such a setup would be significant.

I want to echo Aleks’ post, and mention my gratitude to Ben Adida for his excellent summary of EVT. Unfortunately, between FEV 2007 and thesis writing, I don’t think anyone from Punchscan could work EVT to into our schedules.

At the end of his post, Ben makes a good point,

I remain a little bit disheartened by the continuing gap between the crypto and applied security crowds. The crypto folks (me included) need to do a better job pitching this stuff, especially now that there’s an opening to improve the technology in places like California.

We have at least three interest groups that strongly oppose electronic voting machines. As pointed out, there is the software security crowd. There is the the crypto crowd, of which we are a part. And there is the black box voting crowd, who oppose essentially any role for technology. As voting is a political problem, it requires a political solution, and good politics always involves coalition building between groups who don’t always agree on everything, but can at least agree on the specific issue at hand.

I’m not exactly sure how to bridge the gap. However I will say that from Punchscan’s perspective, we need all three. Punchscan is fundamentally a cryptographic system, and through cryptography we are able to eliminate trusted computing at the polling places. But we still need trusted computing for tallying to protect privacy. And so there is a role for software security experts. We also need voters to check their receipts, and this can be augmented with voting advocacy groups, like BBV, collecting copies of receipts at the polling place exits and diligently checking them.

For a multipart discussion, i’d like to talk about the goals of a voting system. Intuitively, the goal behind any good voting system is to accurately produce a result, but while this is common sense, it is vastly oversimplified — what exactly does “accurately” mean, and how is that accomplished? Others have tried to put this into context with witty anecdotes like this:

The purpose of voting is not to convince the winner that he or she has won, but to convince the losers that they have lost. reference

In other words, a successful voting system will prevent legal challenges or armed takeover of the state in which it was used by the losers. However, this too seems oversimplified. Just because the losers know they lost does not exempt their supporters from being convinced otherwise, or not caring, and causing problems anyway. There are many examples of democratically elected governments being overthrown, and election fraud is a common accusation of the overthrowers, even if it is completely unfounded. The best thing a voting system could do is convince everyone of the results, wether they are voters, candidates, or people wholly unaffiliated with the election. This may not prevent a coup, but it will not give it legitimacy it would otherwise enjoy.

We adopt a similar philosophy. The goal of our ideal voting system is that if it works properly it should deny any legitimacy to claims of foul play, however, we also add that it should provide significant proof if such foul play exists. From this, we conclude that a good voting system will strive for accuracy and transparency, and we create more specific properties that voting systems should have keeping these two high level ideas in mind.

There is not yet a standard set of properties or goals that voting systems must meet, so we instead list the 3 key properties and goals that were the focus while building the Punchscan system, with an eye for keeping things transparent and accurate. Those properties are integrity, coercion resistance and verifiability, and I will discuss these and other goals in a future post.

Our colleague Ben Adida offers an interesting recap in his blog of this week’s EVT conference in Boston.

VoComp judge and voting systems researcher Josh Beneloah presented a ballot casting protocol and touched on the issue of usability; the ability to cast a vote the way you intend to. Ben explains Josh “mentioned VoComp to point out that there seems to be a dilemma between verification and usability: can we make it look identical to a DRE?”

This brings up an excellent point, because a point we tried to make at VoComp was that usability includes two aspects;

• accuracy
• feel goodness

and more importantly that one does not necessarily imply the other. But I think people have got it in their heads that something that feels easy to use makes it more accurate. But it doesn’t require much conscious thought to push a button. So what if a DRE is less accurate even if people think it’s easy to use? Isn’t accuracy the more important attribute? Somehow I doubt people feel that way.

Kinda like the 80’s architectural trend of putting little shutters on windows - it doesn’t really do what it’s supposed to, but who cares if it looks cool?

I mentioned in a recent post that in talking to a Diebold rep at last month’s VoComp he stated to me that their voting machines store ballots in memory in random order. I had indicated my skepticism to him at the time.

Now I read that in fact the Diebold AccuVote-TSX actually does “record votes in the order in which they are cast, and (it) records the time that each vote is cast.”

I will give the gentleman the benefit of the doubt that he was misinformed.

Alternatively in a cryptographic voting system such as Punchscan, the thing that records your vote only ever sees an encrypted version. So it doesn’t matter if they get stored in order.

UPDATE: Looks like we weren’t the only ones they were telling that lie too.

While this was written during the last cycle of discovered exploits in electronic voting machines, John Allen Paulos hit the nail on the head,

Elections and electronic voting machines invite consideration of the following thought experiment. You go to your local voting station, walk into the booth, pull the curtain, and see a well-dressed man standing inside with a little note pad. He asks whom you’re voting for, appears to record what you say in his note pad, tells you he’ll add your vote to his running total, thanks you, and asks you to send the next voter into the booth. Whatever objections you have to this voting scenario should be reserved for the more familiar one involving Diebold and other voting machines.