Recently, HR 5036 was shot down in Congress.  That bill was to provide “emergency” money to help election administrators who wished to replace paperless voting systems with optically scanned paper ballots (or to add paper-printing attachments to existing electronic voting systems).  While the bill initially received strong bipartisan support, it was opposed at the last minute by the White House.  To the extent that I understand the political subtext of this, the Republicans wanted to attach a Voter ID requirement to the bill, and that gummed up the works.  (HR 5036 isn’t strictly dead, since it still has strong support, but it was originally fast tracked as a “non-controversial” bill, and it is now unlikely to gain the necessary 2/3 majority.)

I’ve been thinking for a while about this whole voter ID problem, and I have to say that I don’t really see a big problem with requiring that voters present ID so they can vote.  This kind of requirement is used in other countries like Mexico and it seems to work just fine.  The real issue is making sure that all people who might want to vote actually have IDs, which is a real problem for the apparently non-trivial number of current voters who lack normal ID cards (and, who we are led to believe, tend to vote in favor of Democrats).

The question then becomes how to get IDs for everybody.  One answer is to put election authorities in charge of issuing special voting ID cards.  This works in other countries, but nobody would ever support such a thing in the U.S. because it would be fantastically expensive and the last thing we need is yet another ID card.  The “obvious” solution is to use driver’s licenses or official state IDs (for non-drivers).  But, what if you’ve never had a driver’s license?

As an example, here are Texas’s list of requirements to get a driver’s license.  Notice how they also require you have proof of a social security number?  If you’ve somehow managed to make it through life without getting one, and I imagine many poor people could live without one, then that becomes a significant prerequisite for getting a driver’s license.  And it’s pretty difficult to get a SSN if you’re unemployed and don’t have a driver’s license (see the Social Security Administration’s rules).

One way or another, you’re going to need your birth certificate.  Here’s how you get a copy of one in Texas.  If you don’t have any other form of ID, it’s pretty difficult to get your birth certificate as well.  You’ll either need an immediate relative with an ID to request your birth certificate on your behalf, or you’ll need utility bills in your name.  And if you’re older than 75, the state agency may not be able to help you, and who knows if the county where you were born has kept its older records properly.

It’s easy to see that somebody in this situation is going to find it difficult to navigate the bureaucratic maze.  If the only benefit they get, at the end of the day, is being allowed to vote, it’s pretty hard to justify the time and expense ($25 for the birth certificate, the social security card is free, and $15 plus hours waiting in line for the state ID card).  For potential voters who don’t have a permanent home address, this process seems even less reasonable.

The only way I could imagine a voter ID requirement being workable (i.e., having a neutral effect on partisan elections) is if there was a serious amount of money budgeted to help people without IDs to get them.  That boils down to an army of social workers digging around for historical birth records and whatever else, and that’s not going to be cheap.  However, I’m perfectly willing to accept a mandatory voter ID, as long as enough money is there to get one, for free, for anybody who wants one.  The government is willing to give you a $40 coupon to receive digital signals for an analog TV, as part of next year’s phase-out of analog broadcasts.  Why not help out with getting identification papers as part of phasing in an ID requirement?

[Sidebar: if you’re really concerned about people voting multiple times, the most effective solution has nothing to do with voter ID.  The simple, low-tech answer is to mark voters’ fingers with indelible ink.  It wears off after a while, it’s widely used throughout the world, and there’s no mistaking it for anything else.  I can’t wait for the day when I tune into my nightly newscast and see the anchor giving grief to the sportscaster because his thumb isn’t painted purple.]

I wrote previously about discrepancies in the vote totals reported by Sequoia AVC Advantage voting machines in New Jersey’s presidential primary election, and the incomplete explanation offered by Sequoia, the voting machine vendor. I published copies of the “summary tapes” printed by nine voting machines in Union County that showed discrepancies; all of them were consistent with Sequoia’s explanation of what went wrong.

This week we obtained six new summary tapes, from machines in Bergen and Gloucester counties. Two of these new tapes contradict Sequoia’s explanation and show more serious discrepancies that we saw before.

Before we dig into the details, let’s review some background. At the end of Election Day, each Sequoia AVC Advantage voting machine prints a “summary tape” (or “results report”) that lists (among other things) the number of votes cast for each candidate on that machine, and the total voter turnout (number of votes cast) in each party. In the Super Tuesday primary, a few dozen machines in New Jersey showed discrepancies in which the number of votes recorded for candidates in one party exceeded the voter turnout in that party. For example, the vote totals section of a tape might show 61 total votes for Republican candidates, while the turnout section of the same tape shows only 60 Republican voters.

Sequoia’s explanation was that in certain circumstances, a voter would be allowed to vote in one party while being recorded in the other party’s turnout. (“It has been observed that the ‘Option Switch’ or Party Turnout Totals section of the Results Report may be misreported whereby turnout associated with the party or option switch choice is misallocated. In every instance, however, the total turnout, or the sum of the turnout allocation, is accurate.”) Sequoia’s memo points to a technical flaw that might cause this kind of misallocation.

The nine summary tapes I had previously were all consistent with Sequoia’s explanation. Though the total votes exceeded the turnout in one party, the votes were less than the turnout in the other party, so that the discrepancy could have been caused by misallocating turnout as Sequoia described. For example, a tape from Hillside showed 61 Republican votes cast by 60 voters, and 361 Democratic votes cast by 362 voters, for a total of 422 votes cast by 422 voters. Based on these nine tapes, Sequoia’s explanation, though incomplete, could have been correct.

But look at one of the new tapes, from Englewood Cliffs, District 4, in Bergen County. Here’s a relevant part of the tape:

The Republican vote totals are Giuliani 1, Paul 1, Romney 6, McCain 14, for a total of 22. The Democratic totals are Obama 33, Edwards 2, Clinton 49, for a total of 84. That comes to 106 total votes across the two parties.

The turnout section (or “Option Switch Totals”) shows 22 Republican voters and 83 Democratic voters, for a total of 105.

This is not only wrong – 106 votes cast by 105 voters – but it’s also inconsistent with Sequoia’s explanation. Sequoia says that all of the voters show up in the turnout section, but a few might show up in the wrong party’s turnout. (“In every instance, however, the total turnout, or the sum of the turnout allocation, is accurate.”) That’s not what we see here, so Sequoia’s explanation must be incorrect.

And that’s not all. Each machine has a “public counter” that keeps track of how many votes were cast on the machine in the current election. The public counter, which is found on virtually all voting machines, is one of the important safeguards ensuring that votes are not cast improperly. Here’s the top of the same tape, showing the public counter as 105.

The public counter is important enough that the poll workers actually sign a statement at the bottom of the tape, attesting to the value of the public counter. Here’s the signed statement from the same tape:

The public counter says 105, even though 106 votes were reported. That’s a big problem.

Another of the new tapes, this one from West Deptford in Gloucester County, shows a similar discrepancy, with 167 total votes, a total turnout of 166, and public counter showing 166.

How many more New Jersey tapes show errors? What’s wrong with Sequoia’s explanation? What really happened? We don’t know the answers to any of these questions.

Isn’t it time for a truly independent investigation?

UPDATE (April 11): The New Jersey Secretary of State, along with the two affected counties, are now saying that I am misreading the two tapes discussed here. In particular, they are now saying that the tape image included above shows 48 votes for Hillary Clinton, not 49. They’re also saying now that the West Deptford tape shows two votes for Ron Paul, not three.

It’s worth noting that the counties originally read the tapes as I did. When I sent an open records request for tapes showing discrepancies, they sent these tapes – which they would not have done had they read the tapes as they now do. Also, the Englewood Cliffs tape pictured above shows hand-written numbers that must have been written by a county official (they were on the tapes before they were copied and sent to us), showing 84 votes for Democratic candidates, consistent with the county’s original reading of the tape (but not its new reading).

In short, the Secretary of State talked to the counties, and then the counties changed their minds about how to read the tapes.

So: were the counties right before, or are they right now? Decide for yourself – here are the tapes: Englewood Cliffs, West Deptford.

UPDATE (April 14): Regardless of what these two tapes show, plenty of other tapes from the Feb. 5 primary show discrepancies that the state and counties are not disputing. These other discrepancies are consistent with Sequoia’s explanation (though that explanation is incomplete and more investigation is needed to tell whether it is correct). Thus far we have images of at least thirty such tapes.

California’s Secretary of State has been busy. It appears that ES&S (manufacturers of the Ink-a-Vote voting system, used in Los Angeles, as well as the iVotronic systems that made news in Sarasota, Florida in 2006) submitted its latest and greatest “Unity 3.0.1.1” system for California certification. ES&S systems were also considered by Ohio’s study last year, which found a variety of security problems.

California already analyzed the Ink-a-Vote. This time, ES&S submitted their AutoMARK ballot marking device, which has generated some prior fame for being more accessible than other electronic voting solutions, as well has having generated some prior infamy for having gone through various hardware changes without being resubmitted for certification. ES&S also submitted its M100 precinct-based tabulation systems, which would work in conjunction with the AutoMARK devices. (Most voters would vote with pen on a bubble sheet. The AutoMARK presents a fancy computer interface but really does nothing more than mark the bubble sheet on behalf of the voter.) ES&S apparently did not submit its iVotronic systems.

The results? Certification denied.

Let’s start with the letter from the Secretary to the vendor and work our way down.

ES&S failed to submit “California Use Procedures” to address issues that they were notified about back in December as part of their conditional certification of an earlier version of the system. This can only be interpreted as vendor incompetence. Here’s a choice quote:

ES&S submitted what it stated were its revised, completed California Use Procedures on March 4th. Staff spent several days reviewing the document, which is several hundred pages in length. Staff found revisions expressly called for in the testing reports, but found that none of the changes promised two months earlier in Mr. Groh’ s letter of January 11, 2008, were included.

The accessibility report is very well done and should be required reading for anybody wanting to understand accessibility issues from a broad perspective. They found:

• Physical access has some limitations.
• There are some personal safety hazards.
• Voters with severe manual dexterity impairments may not be able to independently remove the ballot from the AutoMARK and cast it.
• The keypad controls present challenges for some voters.
• It takes more time to vote with the audio interface.
• The audio ballot navigation can be confusing.
• Write-in difficulties frustrated some voters.
• The voting accuracy was limited by write-in failures.
• Many of the spoken instructions and prompts are inadequate.
• The system lacks support for good public hygiene.
• There were some reliability concerns.
• The vendor’s pollworker training and materials need improvement.

Yet still, they note that “We are not aware of any public device that has more flexibility in accommodating the wide range of physical and dexterity abilities that voters may have. The key, as always, is whether pollworkers and voters will be able to identify and implement the optimal input system without better guidance or expert support. In fact, it may be that the more flexible a system is, the more difficult it is for novices to navigate through the necessary choices for configuring the access options in order to arrive at the best solution.” One of their most striking findings was how long it took test subjects to use the system. Audio-only voters needed an average of almost 18 minutes to use the machine on a simplified ballot (minimum 10 minutes; maximum 35 minutes). Write-in votes were exceptionally difficult. And, again, this is arguably one of the best voting systems available, at least from an accessibility perspective.

Okay, you were all waiting to learn more about the security problems. Let’s go. The “red team” exercise was performed by the Freeman Craft McGregor Group. It’s a bit skimpy and superficial. Nonetheless, they say:

• You can swap out the PCMCIA memory cards in the precinct-based ballot tabulator (model M100), while in the precinct. This attack would be unlikely to be detected.
• There’s no cryptography of any kind protecting the data written to the PCMCIA cards. If an attacker can learn the file format (which isn’t very hard to do), and can get physical access to the card while in transit or storage, then the attacker can trivially substitute alternative vote records.
• The back-end “Election Reporting Manager” has a feature to add or remove votes from the vote totals. This would be visible in the audit logs, if anybody bothered to look at them, but these sorts of logs aren’t typically produced to the public. (Hart InterCivic has a very similar “Adjust Vote Totals” feature with similar vulnerabilities.)
• The high speed central ballot tabulator (the M650) writes its results to a Zip disk, again with no cryptography or anything else to protect the data in transit.
• The database in which audit records are kept has a password that can be “cracked” (we’re not told how). Once you’re into the database, you can create new accounts, delete old audit records, and otherwise cause arbitrary mayhem.
• Generally speaking, a few minutes of physical access is all you need to compromise any of the back-end tools.
• All of the physical key locks could be picked in “five seconds to one minute.” The wire and paper-sticker tamper-evidence seals could also be easily bypassed.

And then there’s the source code analysis, prepared by atsec (who normally make a living doing Common Criteria analyses). Again, the public report is less detailed than it can and should be (and we have no idea how much more is in the private report). Where should we begin?

The developer did not provide detailed build instructions that would explain how the system is constructed from the source code. Among the missing aspects were details about versions of compilers, build environment and preconditions, and ordering requirements.

This was one of our big annoyances when working on California’s original top-to-bottom review last summer. It’s fantastically helpful to be able to compile the program. You need to do that if you want to run various automated tools that might check for bugs. Likewise, there’s no substitute for being able to add debugging print statements and use other debugging techniques when you want to really understand how something works. Vendors should be required to provide not just source code but everything necessary to produce a working build of the software.

The M100 ballot counter is designed to load and dynamically execute binary files that are stored on the PCMCIA card containing the election definition (A.12) in cleartext without effective integrity protection (A.1).

Or, in other words, election officials must never, ever believe the results they get from electronic vote tabulation without doing a suitable random sample of the paper ballots, by hand, to make sure that the paper ballots are consistent with the electronic tallies. (Similarly fundamental vulnerabilities exist with other vendors’ precinct-based optical scanners.)

The M100 design documentation contains a specification of the data structure layout for information stored on the PCMCIA card. The reviewer compared the actual structures as defined in the source code to the documentation, and none of the actual structures matched the specification. Each one showed significant differences to or omissions from the specification.

I require the students in my sophomore-level software engineering class to keep their specs in synchrony with their code as their code evolves. If college sophomores can do it, you’d think professional programmers could do it as well.

The user’s guide for the Election Reporting Manager describes how a password is constructed from publicly-available data. This password cannot be changed, and anyone reading the documentation can use this information to deduce the password. This is not an effective authentication mechanism.

While this report doesn’t get into the ES&S iVotronic, the iVotronic version 8 systems had three character passwords, fixed from the factory. (They apparently fixed this in the version 9 software which is now already a few years old.) You’d think they would have gone around and fixed this issue elsewhere in their software, since it’s so fundamental.

A.4 “EDM iVotronic Password Scramble Key and Algorithm”: A hardcoded key is used to obfuscate passwords before storing them in a database. The scrambling algorithm is very weak and reversible, allowing an attacker with access to the scrambled password to retrieve the actual password. The iVotronic is supported by the Unity software but is not being used for California elections.

Well, okay, maybe they didn’t fix the iVotronic passwords, then, either. Other passwords throughout the system are similarly hard-coded and/or poorly stored. And, given that, you can trivially tamper with any and all of the audit logs in the system that might otherwise contain records of what damage you might have done.

In the area of cryptography and key management, multiple potential and actual vulnerabilities were identified, including inappropriate use of symmetric cryptography for authenticity checking (A.9) and several different very weak homebrewed ciphers (A.4, A.7, A.8, A.11). In addition, the code and comments indicated that a checksum algorithm that is suitable only for detecting accidental corruption is used inappropriately with the claimed intent of detecting malicious tampering (A.1).

We’ve seen similar ill-conceived mechanisms used by other vendors, so it’s similarly unsurprising to see it here. The number one lesson these vendors should take home is thou shalt not implement thine own cryptography, particularly when the stuff they’re doing is all pretty standard and could be pulled from places like the OpenSSL library support code. And even then, you have to know what you’re doing. As Aggelos Kiayias once quipped, don’t use cryptography; use a cryptographer.

The developers generally assume that input data will be supplied in the correct expected format. Many modules that process input data do not perform data validation such as range checks for input numbers or checking validity of internal cross references in interlinked data, leading to potentially exploitable vulnerabilities when those assumptions turn out to be incorrect.

They’re talking about buffer overflow vulnerabilities. This is one of the core techniques that an attacker might use to gain leverage. If an attacker compromises one solitary memory card on its way back to Election Central, then corrupt data on that might be able to attack the tabulation system, and thus effect the outcome of the entire election. This report doesn’t contain enough information for us to conclude whether ES&S’s Unity systems are vulnerable in this fashion, but these are exactly the kinds of poor development practices that enable viral attacks.

Finally, a few summary bullets jumped out at me:

• The system design does not consistently use privilege separation, leading to large amounts of code being potentially security-critical due to having privileges to modify data.
• Unhelpful or misleading comments in the code.
• Subjectively, large amount of source code compared to the functionality implemented.

Okay, let’s get this straight. The code is bloated, the comments are garbage, and the system is broadly not engineered to restrict privileges. Put that all together, and you’re guaranteed a buggy, error-prone, security vulnerable program that must be incredibly painful to maintain and extend. This is the kind of issue that leads smart companies to start over from scratch (while simultaneously supporting the old version until the new version gets up to speed). Is ES&S or any other voting system vendor doing a from-scratch implementation in order to get it right? They’ll never get there any other way.

[Sidebar: I live in Texas. Texas’s Secretary of State, like California’s, is responsible for certifying voting equipment for use in the state. If you visit their web page and scroll to the bottom, you’ll see links for each of the vendors. There are three vendors who are presently certified to sell election equipment here: Hart InterCivic, ES&S and Premier (née Diebold). Nothing yet published on the Texas site post-dates the California or Ohio studies, but Texas’s examiners recently considered a new submission from Hart InterCivic. It will be very interesting to see whether they take any of the staggering security flaws in Hart’s system into consideration. If they do, it would be a big chance for Texas to catch up to the rest of the country. Incidentally, I have offered my services to be on Texas’s board of election examiners on several occasions. Thus far, they haven’t responded. The offer remains open.]