[EM] Why We Shouldn't Count Votes with Machines

[Kristofer Munsterhjelm]

Dave Ketchum wrote:
> You claim that many fragments can be done by specialized machines. 
> AGREED, though I do not agree that they can do it any better than a 
> normal computer - which has equivalent capability.

In a technical capacity, of course not. Since a computer is 
Turing-complete, it can do anything the specialized machines can. 
However, and this is the point I've been trying to make, the specialized 
machines are simple enough that it's possible to formally prove that 
they do only what they're intended to do, and perhaps also to convince 
the voters that this is the case.

It's kind of like the difference between physics and mathematics. Doing 
tests is analogous to the hypothesis testing of physics: you can say 
that this particular machine does not exhibit any flaws that would 
compromise security, within some margin of error. However, if the 
machines are sufficiently simple, then one can use formal proving to 
show, mathematically, that there are no bugs; that the Condorcet counter 
will turn ballot records into Condorcet matrices and no more - that the 
machine with buttons on it will register votes, register them to the 
candidate shown on the display, and no more, and so on.

Now, the analogy is not total. Even a correct hardware system could be 
compromised by vendors adding backdoors to their fabrication (going 
outside of the spec) and so on, but those errors are much harder to 
conceal than simple software tinkering. Even if the software is open 
source (as you've stated that you want), knowing the full limits of the 
hardware keeps hackers out. The more complex the OS, the greater the 
chance that there's a bug: even Linux has had privilege escalation bugs, 
although they appear much less frequently than in closed-source 
software. What I'm saying here is that if you have to have machines, 
have a way of saying to, first, the experts that there is no way there 
can be an error, and second (if possible), the same to the ordinary 
voters as well.

> However, the whole task involves connecting the fragments:
>      One way is via computer capability.
>      You seem to be doing without such, so What do you have other than 
> humans HOPEFULLY correctly following a HOPEFULLY correct and complete 
> script?

That's right - the links are the weak spots. The script can be devised 
just as any programming can be, and it would be quite simple, and 
ideally reminiscent of what one does when having a manual count regime. 
The PROMs or CDs are the ballot boxes, and they're transported from one 
location to another as one would ballot boxes.

That leaves the humans. The humans may do weird things, and the ensured 
limits that the specialized hardware would have would obviously not 
apply to them. But since the script is simple, various parties can 
monitor each other. In the worst case, the transportation and 
aggregation parts of the process are as insecure as they would be for 
manual ballots.
If that is still too risky, the "ballot boxes" could be numbered and 
digitally signed prior to being distributed to the machines for writing, 
so that if any are lost or replaced, it would immediately show up as an 
error. Such a process would add steps to the script, but I think it'd be 
managable.

>> Consider a general computer. Even for general computers, it makes 
>> little sense to have the district joining software - that counts the 
>> results from various districts and sum them up in the case of a 
>> summable method - on the individual units. As such, the 
>> general-purpose computers are already specialized, only in software 
>> instead of hardware.
> 
> ???

That was simply intended to show that you don't need the full powers of 
a computer. It's convenient, but that convenience can tilt in the favor 
of manipulators or hackers as well.

>> That's true. Maybe a compromise could be using cheap computer hardware 
>> with read-only software, standardized components, and have the 
>> software not be a full OS, but instead just enough to get the job done 
>> and be provable. You'd have to rely on that there are no hardware 
>> backdoors, but the existence of such would be very unlikely, and the 
>> entire thing would have to be put inside some sort of tamper-resistant 
>> enclosure so hackers can't attach keyloggers or do similar things.
> 
> Hardware backdoors can be hard to find.  Still, if and when one is 
> found, can there not be an appropriate punishment to discourage such 
> crimes in the future?
> 
> Agreed defense against such as keyloggers is essential.
> 
> I still say OPEN SOURCE!

I was thinking more of hardware keyloggers, such as those that look like 
keyboard extension cords. Thus the computer should be tamper resistant 
so you can't just do these things. Ideally, for the cheap computer 
compromise, you'd use a cryptoprocessor (like banks use to keep their 
keys, but more general purpose) to run the actual software - perhaps an 
IBM 4758, though since I'm not a hardware expert I don't know if that 
one is sufficiently powerful to do what you want. Searching the web says 
that the 4758 has a 486 inside.

>> A chip with just enough transistors to do this task. I'm not a 
>> hardware expert, but I think it could be done by the use of a HDL like 
>> Verilog.
> 
> The chip needs to be able to find its data.

Yes. For the sake of simplicity, I'll assume a PROM format - a CD 
interface would need an IDE translator.

Then the PROM could be set up like this:

header:
  uint32 number_of_candidates

then, for each ballot
  uint32 rank_number[number_of_candidates].

which means that if rank_number[0] < rank_number[1], then candidate 0 is 
ranked ahead of (better than) candidate 1.

Then assume that addresses contain 32-bit values. That is, you have 
something like
   0                                1         < address
   12345678901234567890123456789012 123456... < bit

First read off address 0. This gives you the number of candidates. Then 
for addresses 1 to number_of_candidates, inclusive, do the Condorcet 
counting algorithm. After you're done, go to address 1 + (number of 
candidates) to count the next ballot. Repeat until all ballots have been 
counted.

> No matter what you do, errors can happen.  Proper target is to minimize 
> them, which I claim can best be via using computers for what computers 
> can do well.

I think you can minimize further by removing the slack that could be 
used for trickery, as you can't twist something that isn't there. Hence 
my idea.

>> I'll grant the point, though, regarding malicious machines. If the 
>> entire standard is public, and the machines can be rigorously tested 
>> to be sure no tricks are being done by the manufacturers, then 
>> deliberately malicious holes should not exist. I still hold that one 
>> should engineer defensively and as simple as possible, so that the 
>> system is transparent to as many people as possible, and so that bugs 
>> either are fixed very quickly or (preferrably) don't have the room to 
>> exist at all.
> 
> Looks like what I am trying for.
> 
> Simple is a good word, as is defensively.

See above.

>>
>>> I want:
>>>      Display completed ballot, for voters to review and redo any 
>>> problems.
>>>      Record ballot on CD-R.
>>>      Open source, so the programs SHOULD be 100% correct.
>>
>> (Just a note: if the programs are simple enough, one can *know* they 
>> are correct. With provisions for unexpected OS bugs unless the OS 
>> itself is equally simple, and so on.)
> 
> When you mention OS, remember my insistence on open source.

Yes, but try proving Linux (which is what I mean by *know*). At multiple 
million lines of code, that's going to be quite a task.

The compromise option could have an open source software system that is 
simple enough, and thus would get around the problem. It wouldn't be a 
traditional OS, though (but perhaps it would lead to a formally secure 
microkernel, something that would be very interesting in "ordinary" OS 
development as well).

>> Granted, if the machine isn't hacked due to an unexpected bug. 
>> Printout-based machines could be useful even if we have provably 
>> correct machines (strongest sense of security) if the voters are very 
>> distrustful. Counting only based on the printout ensures the voter 
>> that nothing fishy is going on - because nothing fishy *can* be going on.
> 
> Our sorry history justifies distrust.
> 
> I DO NOT like printout-based machines.  To start some thinking, how about:
>      All machines have identical valid code,
>      Some have video cameras recording the ballot as the voter submits it.
>      Voters choose which machines to vote on.
>      Audit that tapes prove 100% correctness of those machines taped - 
> BETTER be.

If you use this in real elections, be prepared for voters with privacy 
complaints. If you let the voters decide which machine to use, the great 
majority would use the untaped ones. Also, the cameras would add to the 
cost of the machine. If the videotape is publically available or it's 
possible to identify voters, that could leak information to vote-sellers.

If you use it for verification purposes only, you have to be sure that 
the voters don't act differently than in the real election (so the test 
is representative). I suppose you don't need exact correspondence since 
"probabilistic flipping" algorithms would easily be detected, but it 
would fail to catch things like election-day hacking.

In any case, instead of using a literal tape, I think you'd have to 
record the video on a write-once storage medium so that it can't be 
tampered with afterwards. You would have to compress the video stream 
very heavily to fit.

What, in your opinion, is the problem with printout-based machines?

>> Use a LED with a photoresistor on the other (logging machine) end. No 
>> data can move from the voting machine to the logging machine, and so 
>> would reduce complexity significantly. Or have two in different 
>> colors, one of which is always on to detect broken cables.
>>
>> There'd still be some code to verify, though: make sure that the 
>> voting machine don't leak ballot data to the logging machine, for 
>> instance.

Oops, that should have been "No data can move from the logging machine 
to the voting machine". Of course data would have to move from the 
voting machine to the logging machine, or there would be nothing to log.