The Monty Hall Problem Revisited

My last post dealt with the probability curiosity referred to as The Monty Hall Problem. I though it would be useful to call out two ways of conceptualizing its highly counterintuitive solution. Neither of these concepts are mine. I simply offer them to enhance appreciation of the problem’s solution.

Concept 1

Step throught the scenarios:

Behind one door is the car, behind the other two are goats (Nanny and Fanny).

Scenario 1: The contestant initially selects the door with the car. The host then reveals Nanny. If the contestant switches doors, hu will select Fanny (lose).

Scenario 2: The contestant initially selects the door with Nanny. The host then reveals Fanny. If the contestant switches doors, hu will select the car (win).

Scenario 3: The contestant initially selects the door with Fanny. The host then reveals Nanny. If the contestant switches doors, hu will select the car (win).

Hence, switching results in a winning outcome in two out the three possible scenarios.

Concept 2

Increase the number of doors to 100. The player picks a door, then the host opens 98 of the other doors, revealing goats (they have names, but not as good as Nanny and Fanny). The host offers the contestant the opportunity to switch doors. The original odds that the contestant had of picking the door with the car behind it remain 1 in 100. Only one other door remains unopened. The odds of the car being behind that door are therefore 99 in 100.

The Monty Hall Problem

A friend of mine recently explained the Monty Hall Problem to me in a bar (what do you talk about in bars?) and while it is utterly counterintuitive, the math totally works.

Marilyn vos Savant, the person with the highest IQ ever recorded, was posed the following question in her 1990 Parade Magazine column:

Suppose you’re on a game show, and you’re given the choice of three doors. Behind one door is a car, the others, goats. You pick a door, say #1, and the host, who knows what’s behind the doors, opens another door, say #3, which has a goat. He says to you: ‘Do you want to pick door #2?’ Is it to your advantage to switch your choice of doors?

—Craig F. Whitaker, Columbia, Maryland

She responded that the contestant should switch, owing to the fact that hu had a 2/3 chance of winning by switching doors, and only a 1/3 chance of winning by staying fast.

Her response generated thousands of letters, many of them from Ph.Ds in mathematics, telling her that she was wrong.

She is not wrong.

More for fun than proof, you might enjoy playing with Steven R. Costenoble’s simulation (bottom of page, requires Java). The problem with real time simulations like these is that probability seldom bears out using small samples. For instance, everyone knows that with a fair coin and a fair toss, the probability of the coin landing heads is 50%. Toss a coin ten times and see if you get five heads and five tails. Do it a million times, however, and the results will converge on 50%.

Curious, I wrote a simulation of my own, setting it to step through the scenario a million times. The contestant switching doors resulted in winning the car 678,042 times out of a million (67.8% of the time).

Neat.

Monopoly Guy Rich

After years of referring to lotteries as “a tax on people who are bad at math,” earlier this year I set up an annual subscription to one of the multi-state lotteries (Mega Millions). For the price of $104 a year ($8.67/mo) I have a ticket registered in every drawing (two a week).

The odds of winning the jackpot are 1 in 175,711,536. The odds of winning the second prize ($250,000) are a mere 1 in 3,904,701. By comparison, my lifetime odds of dying from the ignition or melting of nightwear are 1 in 1,249,356. For the same reason that I’m playing the lottery, I’m sleeping naked:

No matter what the odds, the probability goes to zero if you don’t play (or wear nightwear).

One of my favorite blonde jokes goes like this:

A single mother, who is blonde, is also a devout Christian. Every night she prays to God, “I’m doing the best I can. Please help me give my children the security and opportunities they deserve – let me win the lottery.”

For six months, every night, she fervently prays this way. One night, overwhelmed and frustrated, she prays, “God, I go to church, I live by your teachings, I give to the collection plate even when I can’t afford it, I deserve this. If you don’t make it happen, we’re quits.”

That night The Almighty appears to her in a dream. He says, “Lady. Meet me half way. Buy a ticket.”

Given what I am willing or, rather, not willing to do to obtain obscene wealth, the only way I can hope to arrive at this outcome is by winning the lottery. And I would do a fabulous job at being an obscenely wealthy person. Setting aside what I would give back via worthwhile foundations and grants, I would do all the eccentric, crazy crap that we associate with the mindbogglingly well off. I would:

  • Wear a monocle.
  • Own a geisha-cooled computer.
  • Pick a fun item for my wife to collect, then surprise her on random occasions by presenting her with another one. Perhaps zoos.
  • Anonymously give a million dollars to a deserving stranger.
  • Employ an assistant of Indian heritage (who learned English at Oxford) to pop up in the aforementioned stranger’s life at opportune moments to deliver meaningful but cryptic advice.

The entertainment value that I get from fantasizing about my behavior were I to become breathtakingly flush is more than worth the $8.67 a month on lottery tickets.

Brave New Ballot

Hon. John Suchandso
Secretary of State
123 Fake Street
Anytown, AA 12345

February 26, 2007

Dear Mr. Secretary Suchandso,

My name is [REDACTED], and I write to you as a United States citizen deeply concerned about the integrity of our voting system. I am not affiliated with any organization.

Enclosed with this letter is a copy of Brave New Ballot, by Dr. Aviel Rubin. Dr. Rubin is a Professor of Computer Science and Technical Director of the Information Security Institute at Johns Hopkins University. I have provided his book to you and to each of your counterpart Secretaries of State because I found it to be a thorough, accessible resource detailing the issues surrounding electronic voting systems. I hope that you find it useful.

I served as an election officer in Henrico County, Virginia for the 2006 midterm election. It was a highly worthwhile experience that I look forward to repeating. My fellow volunteers were experienced and dedicated, and procedurally the day ran flawlessly. I was prepared for the unfortunate reality that without a paper audit trail we could not objectively prove that our precinct’s results were valid. What I was unprepared for was the meaningful percentage of voters who had serious difficulties navigating the touch screen ballots. Those who assume that familiarity with the graphical user interface is ubiquitous do a huge disservice to these voters.

I believe that we need to take a big step back and restate the problems that we were we trying to solve, then assess how well electronic voting machines actually solve them.

Our voting system should be a point of national pride, trusted and understood by all citizens, and used as the gold standard worldwide. It is far too precious a thing to entrust to proprietary black boxes produced by the private sector, whose interest in secure and accurate elections is at best secondary.

Thank you for your time and consideration.

Respectfully yours,

[REDACTED]

NOO-klee-ur

With the clown car of contenders for the 2008 presidential election emptying into the center ring, I’m keeping an ear out for how well each candidate pronounces “nuclear.” While its correct pronunciation will not be enough to secure my vote (there is still hair to consider, after all), I would be willing to turn a blind eye to a great deal from a candidate who plants that word on the mat ten times out of ten.

Candidate: My baby mulching program will break the cycle of poverty while simultaneously bolstering agriculture and our transition to biofuels, reducing our dependence on environmentally irresponsible energy sources such as fossil fuels and nuclear power.

Me: W00t! He said “nuclear!”

Am I setting the bar too goddamn high?

Visa Can Bite My Priceless Bag

You may have seen the Visa commercial “Lunch” featuring a highly efficient delicatessen, food literally flying off the grill, and everyone checking out at the register with a Visa check card without even breaking stride – all to the tune Powerhouse.

The whole operation breaks down, the commercial shows us, when some inconsiderate prick uses cash. The music comes to a calamitous halt, food crashes to the floor, people run into one another, and everyone stares at the man like he’s a herpe while the register clerk makes his change.

This is the first ad I’ve seen where cash is made out to be the bad guy, and I yell at the television every time it comes on. See, I love cash. I use it whenever possible and, despite Visa’s depiction to the contrary, my experience is that cash is still superior to electronic debit for retail transactions.

A few properties of cash that I enjoy are:

  1. It is accepted nearly everywhere.
  2. It spends even when the power is out and communications are down.
  3. My experience is that I get through most retail transactions faster than my debit card-wielding counterparts.
  4. The benefits of anonymity extend beyond privacy. Because cash transactions do not couple any of my accounts with my purchases, fewer records exist that are prone to compromise via dumpster diving, dishonest clerks or hacking.
  5. Cash is easily transferable. I can hand my wife a hundred dollars in cash without any intermediary.
  6. Cash can get things done that electronic debit cannot, e.g., slipping the maitre’d a Jackson for better/faster seating. If this is not an issue for you, I suggest that you aren’t living life to its fullest.
  7. Cash is a better deal both for retailers and customers. Retailers pay no fee (typically a flat 7.5 to 10 cents for debit, and up to a usurious 2% for credit), and customers are not at risk of discovering increasingly common point-of-sale fees on their monthly bank statements.

Cash isn’t ideal for everything. I pay all of my bills online, for example, because the benefits of eliminating all that paper (invoices, envelopes, checks) outweigh the costs (persistent records, transaction fees). Privacy doesn’t enter into it because my identity is already coupled to the accounts that I settle electronically.

In addition, cash does not scale well – paying for a car or house in cash is inconvenient and likely to invite scrutiny by our dedicated public servants at the Internal Revenue Service, Drug Enforcement Agency and Department of Homeland Security. And earlier this year, the 8th Circuit Court of Appeals ruled that “..possession of a large amount of cash…is strong evidence that the cash is connected with the drug trade,” and the cash can legally be seized.

With their irritating commercial, Visa is attempting to create a perception that simply doesn’t live up to its claims. I will continue using cash whenever I can, for as long as it’s around, and I recommend anyone consider doing the same. The world will be a slightly cooler place for it.

Sousveillance

David Brin opens The Transparent Society by describing two cities of the near future. In City Number One:

Tiny cameras panning left and right, survey traffic and pedestrians, observing everything in open view…In this place, all the myriad cameras report their urban scenes straight to Police Central, where security officers use sophisticated image processors to scan for infractions against public order – or perhaps against an established way of thought. Citizens walk the streets aware that any word or deed may be noted by agents of some mysterious bureau.

Over in City Number Two, there are just as many cameras. However:

These devices do not report to the secret police. Rather, each and every citizen of this metropolis can use his or her wristwatch television to call up images from any camera in town.

Here a late-evening stroller checks to make sure no one lurks beyond the corner she is about to turn.

Over there a tardy young man dials to see if his dinner date still waits for him by a city fountain.

A block away, an anxious parent scans the area to find which way her child wandered off.

Over by the mall, a teenage shoplifter is taken into custody gingerly, with minute attention to ritual and rights, because the arresting officer knows that the entire process is being scrutinized by untold numbers who watch intently, lest her neutral professionalism lapse.

Brin closes the thought experiment by asking his readers, given a choice between living in one or the other city, is there any doubt which one we would choose?

I see strong evidence that we are heading for a hybrid of the two.

Both of Brin’s cities resemble practical implementations of the Panopticon. Since a citizen can never be certain that hus actions are not being monitored, hu must assume that they are. Going the way of City Number One, the UK currently sports a ratio of one CCTV camera to every fourteen people. The propagation of CCTV cameras in the United States is far less dense, but is growing in reaction to the July 7, 2005 London bombings.

City Number Two answers Juvenal’s question “Quis custodiet ipsos custodes?” Who watches the watchmen? We all do. And camera phones and YouTube are making it possible.

Over the past few months we have seen powerful examples of the potential for Sousveillance. Camera phones captured three separate incidents of excessive force on the part of Los Angeles police. A camera phone made Michael Richards’ hate-filled tantrum available for all the world to see. George Allen’s career in politics is probably over because of a single word, and the video camera that recorded it.

In a short while, only the lowest-end mobile phones will come without the capability of recording video, and Jupiter Research estimates that there are 195 million American mobile phone users today.

That’s a lot of eyes and ears.

I am not wild about the prospect (I’d rather we all just let each other the hell alone), but if we’re going to live in a society where the government and the private sector insist on training cameras on us, I prefer for them to know that we’re Shooting Back.

MrPikes, Election Officer Redux

You never forget your first time, do you? In my case it lasted 15 hours, and involved nine partners.

My day as an election officer started at 5:15 am. Our precinct was in a multipurpose room/gymnasium at an elementary school. We set up the signage, registration tables, five electronic voting machines and one demonstration unit with no problems, and opened the polls promptly at 6:00 am. Four volunteers worked the tables, one ran the demonstration unit, three managed the voting machines and two (the Chief and Assistant Chief) managed all procedural aspects of the election, and dealt with stuff like drive-up voting for those with special needs. We had good coverage.

I spent most of the day managing the machines. Once voters checked in, they queued up and presented paper tickets to a volunteer who (after giving the voter an “I Voted!” sticker) directed them to one of two volunteers with smart cards (I was one of these). I escorted each voter to an available machine, and inserted the smart card to activate a new ballot (this procedure serves to eliminate overvoting).

Henrico County uses Advanced Voting Solutions WinVote machines, which my friend Gokmop wrote about last year. They are Windows-based tablet PCs that reside in a plastic suitcase that transforms into a booth (pictured below).

AVS WinVote

Around 9:00 am one of the machines was unplugged and taken outside to allow a drive-up voter to cast hus ballot. When the machine was returned to its station its AC jack was not re-engaged fully, and the machine was inadvertently left to run on batteries. The battery backup is supposed to last 6-8 hours. It managed about 30 minutes before shutting down. When we booted the unit back up, it was in a locked state that required a technician employed by Henrico County to come out and deal with. We were without that machine for maybe 90 minutes. It affected the queue, but I don’t think that anyone waited over 30 minutes total. This was the only glitch of the day, and I consider it minor.

Logistically things ran pretty smoothly. There were a few incidents, such as the man standing in line who had a fairly spectacular diabetic sugar crash. He was quickly and competently attended to, and went on to cast his vote. Interestingly, this incident illustrated the extent to which suspicion has come to inform my perspective. Within seconds of assessing that the man was having a sugar crash and that two of my fellow volunteers were already acting on it, I looked over my shoulder to make sure that no one was messing with any of the machines. Now, before any of my gentle readers start planning the menu for the intervention, let me say that I genuinely believe my level of suspicion still places well up in the Healthy quadrant, but it’s a good thing of which to stay mindful. If I end up wearing foil-lined underpants and arguing with mailboxes, then you can have your intervention. Mark me down for beef.

Meanwhile, back on voting day, the mood was generally pleasant. While waiting for a machine to free up, one voter joked that his sticker was not technically accurate, since he had not yet, in fact, voted. I responded that Henrico County was examining the feasibility of providing stickers that addressed the various states of voting – “I Am About To Vote!”, “I Am Voting!”, “I Voted!”. I also pointed out to him that the sticker was in fact technically accurate if he had ever voted before. Good times.

The convivial atmosphere, for me, evaporated at the machines themselves. Over the course of the day, my dismay turned to quiet anger as I saw a meaningful percentage of citizens struggle to cast their votes. The single most important lesson that I learned on election day was that way too often these slick, new electronic voting machines do not solve the problem that they were designed and purchased to solve, while creating a laundry list of new problems.

The WinVote machines are touch screen. The voter is guided through a series of screens, each corresponding to a ballot item. The voter selects hus desired candidate for each election by touching the candidate’s name. At the end there is a summary screen that displays the voter’s choices, followed by a screen that instructs the voter to press a large flashing box labeled “VOTE” to cast the ballot.

Something about the design of that screen confused a lot of voters. When they reached it they thought they were done, and they walked away from the machine without pressing the flashing box. Maybe 25 times over the course of the day, one of my fellow volunteers or I had to chase after voters to ask them to come back and complete the process. We’re not allowed to press the box ourselves – a voter who walks away without completing the final step has hus vote invalidated. During the busiest part of the day we missed one voter. We tried advising people about the final step as we were escorting them to the machines, but one has to be careful not to over inform people who might already be intimidated by doing something unfamiliar.

The entire day, right inside the entrance to the precinct a volunteer offered straightforward tutorials with a working demonstration machine. A lot of people who really would have benefited from this passed it up either because they they were too proud, or too confident, or in too much of a hurry. Whatever the reason, when they got to the actual voting machines they became our problem. Setting aside the observation that any voting system requiring a tutorial needs rethinking, we had an election to run, and we had the equipment that the county provided to run it.

We could spot those who were going to have trouble within a few seconds of them getting in front of the machines. You could see their posture change as they encountered something unexpected. It wasn’t just the elderly voters, as one might expect. Young, old, black, white, hispanic, men, women – I assisted voters across a wide demographic spectrum.

Election officers can assist voters, but there are rules for going about it. I couldn’t just walk up beside a voter requesting assistance and look at the ballot. That requires the voter to fill out a form that both of us sign, which is time consuming and in most cases overkill. I helped two voters that required this level of attention because they were so entirely lost. The rest of the time I would stand beside the machine and ask the voter to describe the screen in front of hum, without telling me how hu intended to vote. I had the screens memorized so it was usually a simple matter of explaining the basics of navigating around. In some cases all that was necessary was to inform the voter that the system was touch screen. I had opportunities aplenty to refine my spiel, seeing as I delivered it around 100 times.

It’s important to make it explicitly clear that I don’t think the people I’m describing are stupid. The impression I formed was that they were just entirely inexperienced with something that I happen to take for granted – the graphical user interface. In one way or another I’ve been dealing with GUIs since Dad brought home Pong when I was five. I guarantee that it was the first time for many of those whom I assisted on November 7th.

This can be a hard concept for people who are completely comfortable with GUIs to grasp. In describing my election day experiences, I’ve heard numerous responses along the lines of, “It was so easy for me. I can’t imagine anyone having trouble.” Allow me to make a blanket response to this reaction:

  1. The world is full of things that you cannot imagine.
  2. Your inability to imagine them does not make them any less true.
  3. Touch screen voting machines were designed and purchased by people who share your inability.

We do an immense disservice to a meaningful percentage of voters by forcing them use these machines. In my precinct, several voters had thoroughly awful experiences. Some felt intimidated, some felt stupid, and some felt just that one more bit detached from a world that they used to get along in just fine. Was their experience so bad that they might not vote in the next election? I certainly hope not, but it is simply wrong to expect voters to learn a completely unfamiliar technology without at having at least one compelling reason to do so.

I will ask again, “What problem were we trying to solve?”

The usual response is, “Florida, 2000.” Much was made about hanging, pregnant or dimpled chads, and the confusing butterfly ballots. A more generic way of stating the problem is to say, “The method for capturing voter intent was flawed,” and I agree completely. The Help America Vote Act passed in 2002 allocated billions of dollars to the states to fix the problem. Setting aside the Pandora’s Box of problems that the law unleashed, its primary objective remains unrealized, and postmortem articles like the Washington Post’s “Voting System Worked, With Some Hiccups” amount to little more than whistling past the graveyard.

I guess it depends on how low one sets the bar for declaring that something “worked.” Did the voting system “work” because most of the machines didn’t visibly malfunction? Did it “work” because people didn’t have to wait that much longer than they used to? Did it “work” because more voters and election volunteers than not were comfortable setting up and operating the machines? Did it “work” because at the end of the day most of the non-auditable black boxes produced totals that added up to the total number of people who checked in?

We can do so much better than this. We can start by demanding that our voting system be great, not merely good enough.

My day as an election officer was highly educational and worthwhile, and I look forward to doing it again. The people with whom I worked were top shelf – genuinely dedicated to ensuring a fair and accurate election. They were also very kind and accepting of me, a first-timer and a snot-nosed whippersnapper. We had opportunities to chat during brief lulls in the day. We talked about how good the turnout was, we compared home addresses and made fun of the new McMansion™ development nearby. We talked about past elections, and our concerns with or confidence in the new machines. Leaving the gym at 8:00 pm, I knew that whatever shortcomings our current voting system has, people like these nine were certainly not among them.

Why I Don’t Say The Pledge of Allegiance

In my last post I mentioned that whenever I’m at a venue where the Pledge of Allegiance is recited, I stand with my hands at my sides. I only mentioned it because when I wrote that post I was initially jotting down impressions and recollections while they were fresh. I included it as a detail. One of my gentle readers pointed out that without providing an explanation as to why, people would be left to fill in their own conclusions. Well, we mustn’t have that.

Why I Stand

This started in homeroom my Junior year of high school. Every morning before we went to our first class, we said the Pledge. For reasons that I’ll get to, I decided that I wasn’t going to do it anymore. When everyone else stood, I did not. The homeroom teacher was furious with me, and sent me to the office.

Neither the principal nor the vice-principal was in, but I was a regular and received assurances that one or the other would be in touch. I was on my way to get a smoke over at Chez Boys when I felt a hand on my shoulder. It was Ms. Henderson, the vice-principal.

Donna was an older, handsome blonde woman whom I had learned not to piss off. We were at present enjoying a shaky detente. She politely asked me what had occurred, and why I no longer wanted to say the Pledge. I explained it to her (I swear, I’ll get to it). She didn’t say anything for several moments and then – it was probably the first time someone addressed me as if I were an adult – said, “I understand. What I would ask for you to consider is that the Pledge is something that some people believe in very strongly. Out of respect for what they believe, maybe you could just stand?” A light went on as I learned that it was possible to be true to my own beliefs without being unnecessarily confrontational.

Thank you, Donna. You taught me something which still helps me to go my own way.

Why I Don’t Sing Along

It would be disrespectful for me to recite it.

Allegiance – The obligation of a subject or citizen to hus sovereign or government.

None for me, thank you. I consider my contract with the United States adequate in its current form. I pay my taxes fair and square and, in exchange, I enjoy access to infrastructure and public safety – no need to get all gushy with a bunch of talk about allegiance. I want government involved in my life as little as possible. I wouldn’t swear allegiance to my bank, so why on earth would I swear allegiance to my government?

If I were to put my hand over my heart and say the words, believing as I do, I would be showing disrespect to those who genuinely believe. It’s the same reason I don’t take communion on those occasions when I attend Catholic Mass. I do not believe in Transubstantiation, so I have absolutely no business taking communion. It would be rude.

It scares the shit out of me.

If you’re a believer, the next time the Pledge comes up, close your eyes and just mouth the words (it’s okay, the Flag will give you a pass) so you can hear what a room full of people reciting the Pledge sounds like. It sounds like a bunch of zombies saying grace before tucking into the buffet. “With liberty and *braaaiiiinnnnnnss* for all.” I’m not kidding, it freaks me out.

Deeds Not Words

Which is more important: That I recite a Pledge in which I do not believe, or that I engage (without irony) in civic-minded activities like being an election volunteer?

Origins of the Pledge

The Pledge is not the Declaration of Independence, is not the Constitution, is not the Bill of Rights. Our founders never heard of it. Wikipedia has a fascinating article on its origins. My favorite bit of history about the Pledge is the Bellamy Salute (pictured below):

Bellamy Salute

Hooboy.

Reciting the Pledge of Allegiance in a group setting imbues the gathering with a solemnity and sense of occasion that works just fine for some. I cannot engage in this ritual honestly, so I simply pay respect and leave it at that.

You got a problem with that?

MrPikes, Election Officer

Last night I attended Henrico County, Virginia’s Election Officer Training. It took an hour. I am given to understand that it might have gone longer, but apparently West Virginia was playing Louisville (Go Mountaineers!).

I decided to volunteer as an election worker for two reasons:

  1. Coming from a technical background I thought I might be helpful.
  2. I genuinely want to participate in our election process.

At 34 years of age, I stuck out like a pregnant prom queen – the average age of election workers being 70 – but I was prepared for that. I was less prepared for the Pledge of Allegiance (I politely stood, with my hands at my sides), and was even less prepared for the social aspect of the gathering. A lot of my fellow volunteers knew each other, which makes sense in retrospect, but at the time I would not have been surprised to see people begin producing casseroles.

Around 40 of us went to a separate room to receive training on the Direct Recording Electronic (DRE) voting machines. Henrico uses Advanced Voting Solutions WinVote machines, which my friend Gokmop wrote about last year.

The fact that they communicate with each other wirelessly for end-of-election tabulation still concerns me deeply. Wireless is inherently more insecure than wired, even with badass encryption, and 128-bit WEP (which is what WinVote uses) is demonstrably lame.

The training was exclusively confined to the setup and operation of the machines. Not one word was spoken about what to do when the machines malfunctioned. Presumably the Chiefs and Assistant Chiefs receive more thorough training on what to do when things go wrong, and there is always the Registrar hotline to fall back on. Still, I felt like the omission had more to do with convincing the poll workers that the machines were reliable. I saw a lot of wide eyes during our training.

Here’s a little thought experiment – imagine overhearing the following at a voting precinct using paper ballots:

Chief, this stylus won’t move. Can you come over here and unbudge it?

Sir, can you help me? I’m trying to punch this hole, but it keeps unpunching itself.

I need another ballot. The one I was using just crumpled itself up, then burst into flames.

Um, what problem were we trying to solve again?

DRE Voting Machines

The right of voting for representatives is the primary right by which other rights are protected.
– Thomas Paine, Rights of Man, 1791

I just finished Avi Rubin’s book Brave New Ballot. I’ve been keeping up with the issues surrounding electronic voting since I read RiSC’s 2004 Red Team report (167KB pdf) on the serious, practical security vulnerabilities uncovered in Diebold’s Direct Recording Electronic (DRE) voting machines.

Aside: While researching this post I discovered that DRE is also a medical acronym for Digital (think finger) Rectal Examination. Oh my.

The State of Maryland commissioned RiSC’s review (as well as an analysis by the SAIC – 1227KB pdf) to certify the machines were credible and secure, in response to a non-commissioned paper co-published by Dr. Avi Rubin. This paper concluded that the Diebold machines were fundamentally insecure, based on analysis of source code that Diebold had inadvertently made public. The SAIC and RiSC reports went on to uncover additional, serious flaws.

In addition, just this month, Princeton researchers published yet another study (with video) that, among other problems, demonstrates that Diebold machines can be infected with a vote-altering virus, spread via the machines’ memory cards.

I find these reports fascinating reading. Some of my gentle readers may not, so I will highlight some of their findings below. Bear in mind that Diebold typically rebuts the results of unauthorized analyses of their machines by stating something to the effect that the code/machines analyzed were several generations old, no longer used by any voting precincts in the country, identify purely theoretical attacks, and so on.

I simply ask you to consider that a) the authorized reviews conducted using up-to-date machines/code confirmed that many of these flaws were still present; b) outdated or no, these flaws were at one time present in actual machines in actual, recent elections; and c) at present, we basically have to take Diebold’s word for it.

Now, the highlights:

  • The smart cards used to ensure that an individual can vote only once are easily cloned or reinitialized to allow multiple votes.
  • Supervisor PINs and passwords are either hard-coded, stored in plain text, or have defaults such as 1111. With Supervisor access, an individual could tell a machine that the election was over, clear the results, vote multiple times, or change passwords (thus locking out precinct judges).
  • The locks used to secure the machines are identically keyed, easily picked, and common. The same model of lock is used to secure jukeboxes, desk drawers and hotel minibars.
  • The algorithm used to randomize the order of the voting records (to preserve voter anonymity) is inappropriate to the task. What’s more, the programmers put the following comment in the code:

    // LCG – Linear Conguential Generator – used to generate ballot serial numbers
    // A psuedo-random-sequence generator
    // (per Applied Cryptography, by Bruce Schneier, Wiley, 1996)

    What is painful is that Schneier explicitly states in Applied Cryptography:

    Unfortunately, linear congruential generators cannot be used for cryptography; they are predictable.

  • Both the voting machine software and the Global Election Management System (GEMS) server (central tabulation server) sit atop Windows operating systems consisting of millions of lines of code and, ahem, praised by one and all for their flawless security.
  • Analysis of the GEMS server determined that it was 15 Windows patches out of date. At least one of these was a critical security patch (made available the previous year) whose exploitation gave the attacker complete control of the machine.
  • The GEMS database was written in Microsoft Access – a tinkertoy.
  • Votes can be transmitted from the precinct to the GEMS server via dialup modem. The phone number, user name, password and IP address of the server are stored in plain text in the Windows registry. With this information, an attacker could impersonate a voting machine and/or intercept and alter election results in real time.

The most significant problem with these machines is not a security flaw per se, though it greatly magnifies the impact of all other vulnerabilities. No independent, valid audit trail exists to prove that a given machine produced accurate counts. Incidentally, the same can be said for gear and lever voting machines, which went into service in 1913.

Moving to optical scanners that could read and tabulate counts of paper ballots was a huge improvement, but the mechanism by which voters applied their intent to the ballot was flawed (butterfly ballots, chads in various states of repose, and so on). Could the optical scanners be hacked? Certainly, but I haven’t read up on it. For all I know there could be a little man inside who takes the ballot, then presses a button that corresponds to the candidate. Perhaps the little man could be blackmailed. If elections are done right, however, the little man doesn’t matter, and here’s why:

  1. In order to sway a national election, you have to get dirt on a bunch of little men.
  2. If a precinct, county or state produced suspicious election results, election officials have paper ballots to recount manually, under the bi-partisan scrutiny of people of average or greater height.

Rubin makes this fundamental distinction in Brave New Ballot – the difference between retail and wholesale fraud. Stuffing or “disappearing” ballot boxes is retail fraud. Surreptitiously altering software subsequently placed on tens of thousands of voting machines is wholesale fraud. Another example is hacking the central server to which election results are uploaded.

And remember, with these machines, meaningful recounts are impossible.

Per the Princeton report, in the 2006 general election Diebold machines will be used in 357 counties, responsible for capturing and counting the intent of nearly 10 percent of registered voters. That’s just the Diebold machines. Overall, 34 percent of counties will use touch-screen voting systems in 2006. However, only seven states will employ machines that produce a voter verified paper audit trail (VVPAT).

Hacking voting machines (or a central server) requires intent. However, merely introducing the complexity of electronic hardware and software causes problems of its own. For example, in the 2004 presidential election, over 4,500 votes were lost in Carteret County, North Carolina due to a memory card storage problem in a machine manufactured by Unilect. In a Columbus, Ohio suburban precinct of 800 registered voters, a machine manufactured by Danaher Controls recorded 4,258 votes for one candidate.

Setting aside whether or not these issues would sway a given election, what matters is that voters’ intent was lost. Voters whose confidence in these machines is low are that much less likely to vote. And casting absentee ballots as an alternative to using the machines is a problematic solution.

Bruce Schneier enumerates four fundamental requirements of a robust voting system: Accuracy, Anonymity, Scalability and Speed. I assert that only the first two are fundamental, while the last two are gravy.

  • Accuracy – Each voter’s intent is captured. Every legitimate vote and only legitimate votes are counted.
  • Anonymity – It is not possible to couple a voter with hus vote.

Avi Rubin’s “dream voting machine” would accomplish all four of Schneier’s requirements. Rubin describes this machine as follows:

My dream voting machine would have a user interface much like a DRE, but in reality it wouldn’t be a voting machine at all. I call it a “ballot marking machine.” Voters would navigate through touch screens, just as with a DRE, and make their choices for candidates and for ballot resolutions. However, instead of clicking on Cast Vote at the end, they would select a Print Ballot option, and the machine would produce a filled-in paper ballot that the voter would be able to check for accuracy. The layout and typography of the ballots would be standardized, and the count would proceed completely independently from the the ballot-marking process, in some cases even by hand. One possible variation would use optical scanners to count the ballots, provided that the manufacturer of the scanners had no ties of any kind to the manufacturer of the ballot-marking machine. Similarly, scanners outfitted with audio output could assist blind voters, who would feed their marked ballot into the machine for verification. The marked paper ballots could be retained by election officials and used for recounts, either in cases of actual dispute or as part of a random spot-checking system…The ideal machine would have all the useful features of a DRE but would improve upon it in several key ways. It would allow for meaningful recounts of voter intent and would make it incredibly difficult for a vendor to rig an election. Most significantly, the system would provide citizens with the confidence that their votes were recorded and transmitted accurately and could not be altered after the fact.

Our voting system is hugely important. It should be a point of national pride, trusted and understood by all citizens, and used as the gold standard worldwide. It is far too precious a thing to entrust to proprietary machines produced by companies whose interests are primarily financial.

Recommendations

If we’re going to use DREs, these criteria must be met:

  • The software of every DRE and tabulation server put into service must be subjected to transparent, independent peer review. A method must exist to verify that the code on a given machine matches what was reviewed.
  • DREs must produce a paper ballot that each voter can use to verify hus intent was recorded accurately. The ballots comprise the official count, not the machine totals.
  • Machines fail and require power. In the event of a catastrophic failure, every voting precinct must have an adequate backup supply of paper ballots and a printout of registered voters.

If you are disenfranchised by your state’s voting system, please write your Congressional representatives. For more information on current proposed legislation, visit verifiedvoting.org.