As I write this, canvassing boards in Palm Beach and Broward Counties, Florida, are desperately trying to get manual recounts done in time for a court-imposed deadline. Countless lawsuits and countersuits launched by the Republican and Democratic adversaries are in various stages of adjudication, citizens are up in arms because they feel they have been disenfranchised by poorly-designed “butterfly ballots” and other election day mistakes, the Florida legislature has threatened to take the election into its own hands, and the U.S. Supreme Court has just agreed to add its considerable weight to the fracas.
All this because many of Florida’s counties ballot using the Hollerith punchcard, an antiquated balloting technology whose main virtue is its low price tag. On the nightly news, election officials discourse gravely on “chads,” those little bits of paper that some voters have trouble dislodging. We hear of pregnant chads, hanging chads, and dimpled chads. One election board volunteer is even accused of having eaten the chads that dropped out of the ballots he was handling.
Is this any way to run an election? I don’t think so. Fortunately, Perl can help rebuild democracy, and in this article I’ll show a simple Perl-based framework for a secure Internet-based balloting system.
Much of the inspiration for this article comes from Bruce Schneier’s magnum opus Applied Cryptography and specifically from section 6.1, “Secure Elections.” As explained there, the guiding principles of a secure election are to maintain privacy and prevent cheating. Schneier lays out six minimal requirements for a good election protocol:
Only authorized voters can vote.
No one can vote more than once.
No one can determine for whom anyone else voted.
No one can duplicate anyone else’s vote.
No one can change anyone else’s vote without being discovered.
Every voter can verify that his vote has been taken into account in the final tabulation.
Conventional paper ballots satisfy requirement 1 by voter registration, a process that ensures that only American citizens of a certain age can vote. Requirements 2 and 4 are satisfied by crossing the registered voter’s name off a list when the voter enters the polling location, and 3 is satisfied by using an anonymous ballot. The last two requirements, however, are not completely satisfied by paper ballots, and are the source of much of the uncertainty and accusations in the current election fiasco.
Schneier’s book describes several cryptographic protocols that meet these six requirements for secure elections. Some of them are quite elaborate and require new software at the voter’s side of the connection. In this article, we will use one of the simpler ones that happens to be well suited for web-based voting.
This protocol requires two independent central facilities to work, called the CEA and the CLA. The CEA is the Central Enumeration Agency (although the Bush camp might call it “Chad Eaters Anonymous”). It is responsible for collecting and tallying ballots, and for publishing the results on election night. The CLA is the Central Legitimization Agency (or “Controlling Legal Authority” in Gore-speak). It is responsible for registering and credentialing voters.
Here’s how it works:
Before the election, the CLA supervises voter registration. Each registered voter is issued a Voter Registration Number (VRN), which is simply a large random number. VRNs are issued electronically, for example, by email or floppy (see Figure 41-1).
The CLA maintains a list of all VRNs, and a list of who VRNs were issued to, in order to prevent someone from registering twice. There is no record of who a particular VRN was issued to.
Prior to election day, the CLA sends the CEA the list of VRNs.
On election day, the voter sends in an electronic ballot that contains his choices for elected office. The ballot contains his VRN from step 1.
The CEA checks that the VRN is valid, and crosses it off the list in order to prevent someone from voting twice.
The CEA generates a large random confirmation number (CN) for the voter, and uses it to enter the voter’s choices into the vote tally.
The CEA returns the CN to the voter.
After all votes have been received, the CEA publishes the outcome, along with the lists of CNs and for whom their owners voted.
The privacy of the ballot is ensured by the separation of the CLA and the CEA. One facility knows the identity of the voters, but not who they voted for. The other has access to their vote, but not their identity.
This protocol discourages election fraud in a number of ways. If a registered voter tries to vote twice, he will be caught in step 5. We can discourage non-registered voters from trying to guess valid VRNs by using large random numbers (in this example, we use 100-digit numbers).
If the CEA itself tries to cheat by stuffing the ballot box or “losing” ballots, this can be detected in step 8. By publishing a list of CNs and their votes, the protocol allows voters to check the list to make sure that their votes were tallied correctly.
There are still ways to defraud this protocol. For example, the CEA and CLA can collude to figure out the identity of a voter; if voting is being done over the Web, the CEA can use the voter’s IP address to figure out who he is. The first of these problems can be addressed by election auditors and statutory law. The second can be addressed using proxy servers or by having the balloting take place in central polling places equipped with ATM-like web browsers.
It is also important to note that the protocol described here is a slight departure from the one described by Schneier. The original protocol is built along an email model, in which the voter himself generates the CN, rather than letting the CEA do it for him.
Tallying votes is a task for a database, and this application uses MySQL to do the heavy lifting. Example 41-1 shows the schema used by the CEA’s database. In addition to managing the vote tally itself, the information in the database is used to generate the ballot on the fly. This avoids having to design a new web page for each ballot, and discourages election officials from coming up with butterfly ballots and other innovative designs.
Example 41-1. The schema used by the CEA’s database
0 #!/bin/sh 1 /usr/local/bin/mysql -f CEA <<END 2 DROP TABLE party; 3 DROP TABLE office; 4 DROP TABLE candidate; 5 DROP TABLE registration; 6 DROP TABLE tally; 7 DROP TABLE writein; 8 CREATE TABLE party ( 9 party_id INT(4) UNSIGNED NOT NULL AUTO_INCREMENT, 10 party_name CHAR(100), 11 PRIMARY KEY(party_id), 12 UNIQUE(party_name) 13 ); 14 CREATE TABLE office ( 15 office_id INT(4) UNSIGNED NOT NULL AUTO_INCREMENT, 16 office_name CHAR(100), 17 PRIMARY KEY(office_id), 18 UNIQUE(office_name) 19 ); 20 CREATE TABLE registration ( 21 registration_id CHAR(100) NOT NULL, 22 registration_used TINYINT DEFAULT 0 NOT NULL, 23 PRIMARY KEY(registration_id) 24 ); 25 CREATE TABLE candidate ( 26 candidate_id INT(4) UNSIGNED NOT NULL AUTO_INCREMENT, 27 first_name CHAR(50) NOT NULL, 28 last_name CHAR(50) NOT NULL, 29 party_id INT(4) UNSIGNED NOT NULL, 30 office_id INT(4) UNSIGNED NOT NULL, 31 UNIQUE (party_id,office_id), 32 PRIMARY KEY(candidate_id) 33 ); 34 CREATE TABLE tally ( 35 voter_id CHAR(100) NOT NULL, 36 office_id INT(4) UNSIGNED NOT NULL, 37 candidate_id INT(4) UNSIGNED NOT NULL, 38 time_voted TIMESTAMP(10), 39 UNIQUE(voter_id,office_id), 40 KEY(voter_id) 41 ); 42 CREATE TABLE writein ( 43 voter_id CHAR(100) NOT NULL, 44 office_id INT(4) UNSIGNED NOT NULL, 45 writein CHAR(100) NOT NULL, 46 time_voted TIMESTAMP(10), 47 KEY(voter_id), 48 KEY(office_id) 49 ); 50 END
party
This table lists political parties. Each party has a unique ID, numbered from 1, and a short description, such as “Republican Party.”
office
This table lists the offices that are up for grabs. Each office has a unique ID and a short description like “Town Dogcatcher.”
registration
This table lists valid VRNs. Each VRN has a small integer associated with it that indicates whether the VRN has been used in the current balloting.
candidate
This table lists information about the candidates in the
current election. Each candidate has a unique ID as well as
fields that describe who he is and what he’s running for. The
party_id
and office_id
fields describe the
candidate’s party affiliation and the office he is a candidate
for. The first_name
and
last_name
fields are
self-evident. A UNIQUE
constraint ensures that there cannot be two candidates from the
same party running for the same office. The same candidate can,
however, run for two different offices, which should make
Senator and/or Vice President Lieberman happy.
tally
This table keeps track of the vote tally. The voter_id
field corresponds to the
voter’s CN ballot confirmation number (not the VRN). The
candidate_id
contains the
voter’s choice for candidate, and office_id
contains the office the
voter wants to place him in. A UNIQUE
constraint ensures that a voter
can only vote once for a given office.
writein
This table keeps tabs on write-in candidates.
Example 41-2 gives a set of MySQL statements that insert some test values into the CEA database. There are three offices on this test ballot, including President of the United States, State Senator, and Town Dogcatcher. (No soft money was used for the selection of the various celebrities listed in this example, and I was not promised a night in the Lincoln bedroom.)
Example 41-2. MySQL statements to insert values into the CEA database
0 #!/bin/sh 1 # first the parties 2 /usr/local/bin/mysql -f CEA <<END 3 INSERT INTO party VALUES (NULL,'Republican Party')pg 4 INSERT INTO party VALUES (NULL,'Democratic Party')pg 5 INSERT INTO party VALUES (NULL,'Green Party')pg 6 INSERT INTO party VALUES (NULL,'Reform Party')pg 7 INSERT INTO party VALUES (NULL,"Socialist Worker's Party")pg 8 # now the offices 9 INSERT INTO office VALUES (NULL,'President of the United States')pg 10 INSERT INTO office VALUES (NULL,'State Senator')pg 11 INSERT INTO office VALUES (NULL,'Town Dogcatcher')pg 12 # Now the candidates 13 # Presidential candidates 14 INSERT INTO candidate VALUES (NULL,'e.e.','cummings',1,1)pg 15 INSERT INTO candidate VALUES (NULL,'Ogden','Nash',2,1)pg 16 INSERT INTO candidate VALUES (NULL,'Marilyn','Monroe',3,1)pg 17 INSERT INTO candidate VALUES (NULL,'Tennessee','Williams',4,1)pg 18 INSERT INTO candidate VALUES (NULL,'Chuck','Jones',5,1)pg 19 # State senator 20 INSERT INTO candidate VALUES (NULL,'Timothy',"O'Leary",1,2)pg 21 INSERT INTO candidate VALUES (NULL,'Abbie','Hoffman',2,2)pg 22 INSERT INTO candidate VALUES (NULL,'Ivana','Trump',3,2)pg 23 # Dogcatcher 24 INSERT INTO candidate VALUES (NULL,'John','Adams',1,3)pg 25 INSERT INTO candidate VALUES (NULL,'Morticia','Addams',2,3)pg 26 END
We won’t develop the CLA very fully in this article. The CLA should maintain a database of voter registration information, such as birth dates, addresses, and driver’s licenses. For testing purposes, we’ll generate blocks of VRNs using the program shown in Example 41-3, and load the VRNs into the database using the program, shown in Example 41-4.
Example 41-3. Generating VRNs with generate_vrns.pl
0 #!/usr/bin/perl 1 # file: generate_vrns.pl 2 use constant DIGITS => 100; 3 my $id_count = shift; 4 for (1..$id_count) { 5 my $digits = random_digits(DIGITS); 6 $digits =~ s/(.{25})/$1 /g; 7 print <<EOB; 8 --REGISTRATION-START-- 9 $digits--REGISTRATION-END-- 10 EOB 11 } 12 sub random_digits { 13 my $digits_desired = shift; 14 open(RAND,'/dev/urandom') or die "Can't open random number device: $!"; 15 my $data; 16 read(RAND,$data,$digits_desired) or die "Can't read random bytes: $!"; 17 my @digits = map {$_ % 10} unpack('C*',$data); 18 return join '', @digits[0..$digits_desired-1]; 19 }
Example 41-4. Entering VRNs with enter_vrn.pl
0 #!/usr/bin/perl -w 1 # -*- perl -*- 2 # enter_vrn.pl 3 use strict; 4 use DBI; 5 my $db = DBI->connect('dbi:mysql:CEA') or die "Can't connect: $DBI::errstr"; 6 my $stl = $db->prepare( 'INSERT INTO registration (registration_id) VALUES (?)' ) 7 or die "Can't prepare: ",$db->errstr; 8 $/ = ""; # paragraph mode 9 while (<>) { 10 chomp; 11 my ($digits) = /--REGISTRATION-START--(.+)--REGISTRATION-END--/s; 12 $digits =~ s/D//g; 13 $stl->execute($digits) or die $db->errstr; 14 } 15 $stl->finish; 16 $db->disconnect;
The generate_vrns.pl
script
generates the number of VRNs requested on the command line. The part
that does all the work is the subroutine random_digits
between lines 12 and 19. It is
critical to use a good random number generator to generate VRNs;
otherwise, valid VRNs would be too easy to guess. The Math::TrulyRandom module (available on CPAN) promises to
do this, but it hangs on my Linux system. Instead, I use the /dev/urandom device, which uses a Linux
kernel driver that generates random data from non-deterministic system
information, such as interrupts. We read the requisite number of
random bytes from the device, and then transform them into a set of
base 10 digits.
The enter_vrn.pl script shown in Example 41-4 takes a list of VRNs generated by the previous script, and enters them into the CEA database using the DBI module and its DBD::mysql driver.
Line 5 connects to the CEA database or dies with an error
message. Line 6 prepares a SQL
INSERT
statement that will add VRNs to the registration table. The code between lines
8–14 loops through the list of VRNs one paragraph at a time, extracts
the VRN information, and calls the SQL statement’s execute
method to perform the insertion.
After the last VRN is processed, we call finish
to close the SQL statement, and
disconnect
to disconnect from the
database.
The fun part is the electronic ballot generated by the CEA. Figure 41-2 shows how it looks to the voter. There are three steps to voting. In the first step, the voter makes his choices by selecting radio buttons in the ballot. Each candidate is sorted by his party and the office he is running for. There is also a text field that allows for write-ins.
In step 2, the voter enters his VRN. He can do so by cutting and pasting the VRN into a large text field, or by uploading a file provided by the CLA that contains the VRN.
When satisifed, the voter presses the VOTE button. The CEA checks that the ballot is filled out, that the voter hasn’t voted twice for candidates for the same office, and that the VRN is valid and has only been used once. If these checks are satisfied, the CEA enters the voter’s choices into the database, generates a CN, and displays the confirmation to the user (Figure 41-3).
Later, when the votes have been tallied and published, the user can go to the published results and make sure that his vote was correctly counted.
Of course, for the e-ballot to be at all secure, all communication between the voter and the CEA’s web site must use SSL, and the voter should be instructed to check the web site’s SSL certificate to make sure that it is valid.
The e-ballot is implemented by a conventional CGI script shown in Example 41-5. The listing is a bit long, but most of it is fancy formatting in the ballot section. We’ll step through it a line at a time.
Example 41-5. The vote program
0 #!/usr/bin/perl -Tw 1 # -*- perl -*- 2 use strict; 3 use CGI qw(:standard *table *Tr *dl); 4 use DBI; 5 use constant REGISTRATION_CODE_LENGTH => 100; 6 use vars qw(@CANDIDATES @PARTIES @OFFICES @CANDIDATE_NAME); 7 $ENV{PATH} = '/bin'; 8 # connect to database 9 my $DB = DBI->connect('dbi:mysql:CEA') or die "Can't connect: $DBI::errstr"; 10 ######################## 11 # create the page 12 ######################## 13 print header, 14 start_html(-title => 'Indecision 2000', 15 -bgcolor => 'white' 16 ), 17 h1({-align=>'CENTER'}, 18 img({-src=>'/icons/star.gif'}) x 3, 19 'Indecision 2000', 20 img({-src=>'/icons/star.gif'}) x 3); 21 # load global variables 22 get_globals(); 23 # If the VOTE button is pressed, validate and enter the ballot 24 if (param('VOTE') && (my $registration = validate())) { 25 enter_ballot($registration); 26 } 27 # Otherwise print the ballot 28 else { 29 generate_ballot(); 30 } 31 # end of page 32 print end_html; 33 $DB->disconnect; 34 exit 0; 35 ############################################################### 36 # get_globals() loads the @CANDIDATES, @CANDIDATE_NAME, 37 # @PARTIES and @OFFICES globals from information in the 38 # database. 39 ############################################################### 40 sub get_globals { 41 # fetch the matrix of candidates, parties and offices 42 my $query =<<END; 43 SELECT candidate_id,first_name,last_name,party_name, 44 office_name,candidate.party_id,candidate.office_id 45 FROM candidate,party,office 46 WHERE candidate.office_id=office.office_id 47 AND candidate.party_id=party.party_id 48 END 49 ; 50 my $sth = $DB->prepare($query) or die "Can't prepare: ",$DB->errstr; 51 $sth->execute; 52 while (my($candidate_id,$first,$last,$party,$office,$party_id,$office_id) 53 = $sth->fetchrow_array) { 54 $CANDIDATES[$party_id-1][$office_id-1] = $candidate_id; 55 $CANDIDATE_NAME[$candidate_id] = "$first $last"; 56 $PARTIES[$party_id-1] = $party; 57 $OFFICES[$office_id-1] = $office; 58 } 59 $sth->finish; 60 } 61 ############################################################### 62 # generate_ballot(), voting_matrix(), validation_number() and vote() 63 # create various parts of the page see by the voter 64 ############################################################### 65 sub generate_ballot { 66 print start_multipart_form; 67 voting_matrix(); 68 registration_number(); 69 vote(); 70 print end_form; 71 } 72 # This generates the table containing the ballot. 73 sub voting_matrix { 74 print img({-src=>'/icons/HandPointing.gif',-align=>'LEFT'}), 75 h2('Step 1: Fill in your E-Ballot'), 76 print 77 start_table({-cellspacing=>0,-border=>1}), 78 Tr(th(''),th(@OFFICES)); 79 for (my $party=0; $party < @PARTIES; $party++) { 80 print start_Tr,th($PARTIES[$party]); 81 for (my $office=0; $office < @OFFICES; $office++) { 82 my $candidate = $CANDIDATES[$party][$office]; 83 print td({-bgcolor=>$office %2 ? 'white' : '#E0E0E0'}, 84 $candidate ? radio_group(-name => $office, 85 -value => $candidate, 86 -labels => {$candidate=>$CANDIDATE_NAME[$candidate]}, 87 -default => '-', 88 ) 89 : ' ' 90 ); 91 } 92 print end_Tr; 93 } 94 # Handle write-ins. 95 print Tr(th(' '), 96 td([map {radio_group(-name => $_, -value => 'Write in:'). 97 textfield(-name => "writein $_", 98 -value => '', 99 -override => defined param($_) && param($_)=~/^d+$/ 100 )} (0..$#OFFICES)] 101 ) 102 ), 103 end_table; 104 } 105 # generate the field for entering voter registration number 106 sub registration_number { 107 print hr, 108 img({-src => '/icons/HandPointing.gif', -align => 'LEFT'}), 109 h2('Step 2: Enter your Registered Voter Code'), 110 blockquote( 111 b('EITHER:'), 'Cut and paste the code here:', 112 textarea(-name => 'registration_id', -rows =>4 , -cols => 70, -wrap => 'physical'), br, 113 b('OR:'), 'Select voter registration file for upload here:', br, 114 filefield(-name => 'registration_file') 115 ); 116 } 117 # generate the VOTE button 118 sub vote { 119 print hr, 120 img({-src => '/icons/HandPointing.gif', -align => 'LEFT'}), 121 h2('Step 3:','Cast your Ballot'), 122 blockquote(b(submit('VOTE'))); 123 } 124 ############################################################### 125 # validate() validates the ballot to discourage fraud 126 ############################################################### 127 sub validate { 128 # first check that the voter registration field is filled out 129 return error('The voter registration ID field is missing.') 130 unless param('registration_id') || param('registration_file'), 131 # check that the voter has voted for at least one office 132 return error('The ballot has not been filled out.') 133 unless grep {param($_) ne 'Write in:' || param("writein $_")} 0..@OFFICES-1; 134 # check that no office has more than one vote 135 for (0..@OFFICES-1) { 136 my @votes = param($_); 137 return error("You have voted for $OFFICES[$_] more than once.") if @votes > 1; 138 } 139 # recover the registration ID 140 my $registration_id; 141 if (my $fh = param('registration_file')) { 142 while (<$fh>) { 143 chomp; 144 next unless /--REGISTRATION-START--/../--REGISTRATION-END--/; 145 next unless /^d+$/; 146 $registration_id .= $_; 147 } 148 } 149 $registration_id ||= param('registration_id'), 150 $registration_id =~ s/D//g; # get rid of all non-digits 151 return error('Your registration code is the incorrect length.') 152 unless length $registration_id == REGISTRATION_CODE_LENGTH; 153 # check that this is a registered voter 154 my $sth = $DB->prepare('SELECT registration_used FROM registration WHERE registration_id=?') 155 or die "prepare registration: ",$DB->errstr; 156 my $rows = $sth->execute($registration_id); 157 return error("The registration code provided is not on the list of eligible voters.") 158 unless $rows > 0; 159 # check that registration ID has not already been used 160 my ($used) = $sth->fetchrow_array; 161 return error("That voter registration code has already been used.") 162 unless $used == 0; 163 $sth->finish; 164 return $registration_id; 165 } 166 ############################################################### 167 # enter_ballot() updates the database 168 ############################################################### 169 sub enter_ballot { 170 my $registration = shift; 171 # lock this registration number so that it can't be used again 172 $DB->do("UPDATE registration SET registration_used=1 173 WHERE registration_id='$registration' 174 AND registration_used=0")>0 175 or die "Can't update registration: ",$DB->errstr; 176 # generate a ballot ID 177 my $id = random_digits(100); 178 # prepare the SQL for regular and write-in votes 179 my $regular_vote = $DB->prepare("INSERT INTO tally VALUES('$id',?,?,NULL)") 180 or die "Can't prepare: ",$DB->errstr; 181 my $writein_vote = $DB->prepare("INSERT into writein VALUES('$id',?,?,NULL)") 182 or die "Can't prepare: ",$DB->errstr; 183 # begin user confirmation 184 print h2('Save this Information for your Records'), 185 print start_dl; 186 for my $office (0..$#OFFICES) { 187 my $selection = param($office); 188 my $writein = param("writein $office"); 189 my $candidate_name = $writein || $CANDIDATE_NAME[$selection] || '-none-'; 190 # update database with the candidate's vote 191 if ($writein) { 192 $writein_vote->execute($office+1,$writein) or die "can't update tally: ", $DB->errstr; 193 } elsif ($selection) { 194 $regular_vote->execute($office+1,$selection) or die "can't update tally: ", $DB->errstr; 195 } 196 # update confirmation page 197 print dt(b($OFFICES[$office])),dd($candidate_name); 198 } 199 print end_dl; 200 $writein_vote->finish; 201 $regular_vote->finish; 202 # show user his confirmation number 203 $id =~ s/(.{50})/$1 /; 204 print h3('Ballot Confirmation Number'),pre($id); 205 } 206 ############################################################### 207 # utilities 208 ############################################################### 209 # generate some random digits for the ID 210 sub random_digits { 211 my $digits_desired = shift; 212 open(RAND, '/dev/urandom') or die "Can't open random number device: $!"; 213 my $data; 214 read(RAND,$data,$digits_desired) or die "Can't read random bytes: $!"; 215 my @digits = map {$_ % 10} unpack('C*',$data); 216 return join '', @digits[0..$digits_desired-1]; 217 } 218 # all-purpose error message 219 sub error { 220 print p(font({-size=>'+2',-color=>'red'}, @_, br, 221 'Please correct and try again.')); 222 return; 223 }
We turn on taint checking and Perl warnings. Taint checking ensures that we will be
prevented from doing anything stupid with user-supplied input, such
as passing it to shells, and warnings alert us of uninitialized variables and the
like. We load the CGI and DBI modules. One trick to notice is that the
symbols loaded from the CGI module include *table, *Tr
, and *dl
. The asterisk means to automagically
generate functions to start and end the corresponding HTML tags,
such as start_table
to generate a
<TABLE>
tag and end_table
to generate an </TABLE>
tag.
We define a constant for the length of a valid VRN, and declare globals that will
hold various information about the ballot. @CANDIDATES
is a two-dimensional list of
candidates, in which the first dimension is the candidate’s party
affiliate and the second dimension is the office the candidate is
running for. The values of this array are candidate IDs. Each of
@PARTIES, @OFFICES
, and @CANDIDATE_NAME
map from database IDs into
human-readable labels. To adjust for the fact that 1 is the lowest
ID used in the CEA schema, we adjust each of the indexes by 1. For
example, the party_id
for the
“Republican Party” is 1, so it can be found in @PARTIES
at $PARTIES[0]
.
We set the PATH
environment
variable to a safe known value in order to satisfy Perl’s
taint-check requirements.
We call the DBI->connect
method to connect to the CEA database running on the local machine.
We don’t use any password authorization here, but in a real
application we would want to.
We emit the standard HTTP header by calling the CGI module’s
header
function, and start the
top of the HTML page by calling start_html
and h1
to generate HTML boilerplate and a
level-one header.
We call get_globals
to
initialize the four global variables that describe the current
ballot. get_globals
will make the
appropriate database calls to do this.
We call the CGI module’s param
method to look for a CGI field named
VOTE. If such a field exists, then it indicates that the user has
submitted his ballot by pressing the VOTE button. We immediately
call a subroutine named validate
,
which checks that the ballot is filled out correctly. If the ballot
checks out, it returns the user’s VRN, and we pass the VRN to a
subroutine named enter_ballot
that adds the information to the growing tally.
Otherwise, we call generate_ballot
to create the ballot that
the user sees on the page. This subroutine will be called the first
time the user loads the page, as well as when the validate
subroutine detects an error in a
previously-submitted ballot.
We call end_html
to
generate the boilerplate at the bottom of the HTML page, and
disconnect from the database. We then exit.
This subroutine is responsible for loading the global variables with information about the current election. For efficiency’s sake, it fetches all the information it needs in a single large SQL statement that retrieves each of the candidates, their party and office IDs, and the human-readable labels for candidates, offices, and parties.
We do this by passing the appropriate SQL statement to the
database’s prepare
method, and
then executing the resulting statement handle. We then loop over
each row of the returned table, populating the @CANDIDATES,
@CANDIDATE_NAME, @PARTIES
, and @OFFICES
arrays as we go. Notice how we
offset each ID by one in order to use it as an array index.
This subroutine is responsible for generating the HTML for the ballot. It calls the CGI
module’s start_multipart_form
function in order to start a fill-out form. We use this function
rather than the more common start_form
because we will be accepting a
file containing the voter’s VRN for upload, and only the
multipart-style form can accept file uploads.
We then call three functions to generate the top, middle, and
bottom of the form, and call end_form
to generate the form’s closing
tag.
This large subroutine generates the table that shows the
ballot information. Don’t be intimidated. The part of the subroutine
that does all the work is just two nested loops. The outer one loops
through parties, which become the rows of the ballot, and the inner
one loops through offices, which become the columns. Within the
inner loop, we check whether @CANDIDATES
contains a candidate for the
current party affiliation and office. If it does, we generate a
radio button whose name is the index into @OFFICES
and whose value is the candidate
ID. For the label we use the human-readable version of the
candidate’s name, derived from @CANDIDATE_NAME
.
After creating the radio buttons for standard candidates, we create a series of write-ins, one for each office. These are text fields with the name “writein X,” where X is the ID of the corresponding office.
This subroutine generates the section of the ballot that
prompts the user for his VRN. There are two fields that can be used.
One is a large text area named registration_id
, where the user can cut
and paste his VRN. The other is a file field named registration_file
, which the user can use
to upload a text file containing the VRN.
This subroutine generates a single HTML submission button labeled “VOTE”. This concludes the portion of the script that generates the e-ballot.
This is responsible for validating the voter’s submission. There are several checks on the integrity of the ballot. First we check for the easy things: whether the VRN has been filled in, and whether any of the radio buttons in the ballot have been selected (we only require a minimum of one office to be selected; it’s perfectly valid for the user to vote for some offices and enter no selection for others).
We now check for more subtle problems. Lines 134–138 verify that each office has exactly 0 or 1 votes. Although the fill-out form only allows a single candidate from each office to be selected, a malicious voter could roll his own fill-out form and try to vote for multiple candidates from the same office.
Having passed these checks, we recover the VRN. If the
registration_file
field is
present, then the user has chosen to upload a file. We call the CGI
module’s param
function to
recover a filehandle for the uploaded file, and parse out its
contents. Otherwise, if the registration_id
field is present, we use
its contents to recover a cut-and-pasted VRN.
Having recovered the VRN, we ensure that it is valid. First, we check that the VRN is the correct length. If so, we consult the database to see whether the VRN is in the registration table, and whether it is still unused. If both these tests pass, then we declare that the submitted ballot is valid and return the VRN to the caller.
When any of the tests fails, it calls a utility subroutine
named error
. The error
function displays a bold red error
message on the top of the page, and prompts the user to make
corrections and try again.
The enter_ballot
subroutine
is where the information from the ballot is collected and entered
into the database, registering the voter’s intent and keeping the
sacred flame of Democracy alight.
The first thing that we do is update the database in order to mark the VRN as used. This prevents the VRN from being used again. We do the update in a way that will cause it to fail unless the VRN is currently marked as unused, and avoids an attack based on race conditions while updating the database.
We now generate a confirmation number for the ballot by
calling random_digits
. We use the
newly-generated ID to generate two SQL insert statements, one for
regular candidates, and the other for write-ins. Each statement uses
“?” as placeholders for the office and candidate fields.
We now enter the voter’s choices into the database,
simultaneously generating a confirmation page as we do so. We loop
over the @OFFICES
array, looking
for CGI parameters corresponding either to a regular candidate for
the office or to a write-in. If we find a write-in, we recover it
and insert it into the writein table using the appropriate insert statement.
Otherwise we insert the voter’s choice into the tally table. Notice how we add 1 to the office index
in order to convert it back into the 1-based ID used in the MySQL
tables.
Each time through the loop, we print out the office and the
selected candidate, using a definition list (<DL>
) style HTML list.
At the end of the subroutine, we finish
both SQL statements, and then print
out a nicely-formatted version of the voter’s ballot confirmation
number.
We’ve already seen the random_digits
subroutine. The error
subroutine takes its arguments and
incorporates them into an HTML paragraph, using a red font and a
large font size. The subroutine explicitly returns undef
, which allows this type of idiom in
the caller:
return error('Please stop munching chads and start punching ballots') unless $is_valid;
On election night, tallying the vote is simply a matter of issuing a SQL statement to add up each candidate’s counts and grouping the results by office. Here’s one that will do the trick:
SELECT office_name,last_name,count(*) FROM office,tally,candidate WHERE candidate.candidate_id=tally.candidate_id AND candidate.office_id=office.office_id GROUP BY tally.candidate_id; +--------------------------------+-----------+----------+ | office_name | last_name | count(*) | +--------------------------------+-----------+----------+ | President of the United States | cummings | 2 | | President of the United States | Nash | 4 | | President of the United States | Jones | 1 | | State Senator | O'Leary | 5 | | State Senator | Hoffman | 1 | | Town Dogcatcher | Adams | 3 | | Town Dogcatcher | Addams | 4 | +--------------------------------+-----------+----------+
By this count Ogden Nash deserves to be the next President, Timothy O’Leary next State Senator, and Morticia Addams the next Dogcatcher. A definite improvement over this year’s choices!
Author’s Note: The algorithm presented in this article contains an important bug which was pointed out by several readers after its original publication in The Perl Journal. As it stands, a corrupt CEA can cheat by reusing certificate numbers. To see how this works, say that there are two candidates in the election, who we shall call, say, Bushnell and Lore. The CEA favors Bushnell. After it receives the first vote for Lore, it records the CN and then reissues the same CN a number of times. Each time a voter uses one of these duplicate CNs to vote for Lore, the CN drops it, and generates a bogus vote for Bushnell using a forged CN. At the end of the election, any Lore voter who checks his CN will find that his vote was correctly recorded for Lore. Voting monitors will find that the correct number of votes were recorded. But the statistics are slanted towards Bushnell, because the duplicate Lore votes were dropped.
The solution to this problem is to have the voter pick all or part of the CN, a detail that was in the original Schneier description of the algorithm, but which I dropped because it complicated the implementation (a lesson learned: in security algorithms, the details matter). By putting the CN under the voter’s control, the CEA is prevented from issuing duplicate CNs. For example, you could ask the voter to pick a number between 1,000,000 and 2,000,000. Better still you could implement a client-side service to pick a large random number at the time the fill-out form is generated. One simple implementation would use JavaScript for this purpose, but for political reasons I will leave this as an exercise to the reader.