[8505] in cryptography@c2.net mail archive
Re: electronic ballots
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Tue Jan 30 18:48:43 2001
Mime-Version: 1.0
Message-Id: <v04210102b69759fa5d7a@[24.218.56.92]>
In-Reply-To: <3A706A65.FA842065@greendragon.com>
Date: Fri, 26 Jan 2001 13:23:01 -0500
To: William Allen Simpson <wsimpson@greendragon.com>,
"Cryptography (moderated)" <cryptography@c2.net>
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Content-Type: text/plain; charset="iso-8859-1" ; format="flowed"
Content-Transfer-Encoding: quoted-printable
At 1:03 PM -0500 1/25/2001, William Allen Simpson wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>
>I've been working with Congresswoman Lynn Rivers on language for
>electronic ballots. My intent is to specify the security sensitive
>information, and encourage widespread implementation in a competitive
>environment. We'd like feedback.
While it is good that you are taking the time to work with Congress=20
on this, I have a number of problems with what you have proposed.=20
I've indicated a few specifics below but here are some general=20
objections.
=46irst, and most important, it is far from a given that public key=20
cryptography can be used to build a better voting system than the=20
best paper systems that are presently in use (even assuming as true=20
the unproven mathematical foundations of the technology). There is=20
much more room for undetectable shenanigans in an electronic system=20
than in a paper system. Political leaders should understand that it=20
is not just a question of issuing the right RFP. In particular, it=20
is premature to start drafting a law.
Second, I find it unsatisfactory to review a proposed cryptosystem=20
design presented in legal language. At the very least, a careful=20
system design document, preferably with pseudo code, and a detailed=20
threat model should be presented. A working model would be better.
You should separate the performance criteria a voting system must=20
meet from the technical design.
It is not enough that a voting system be secure, or that it be=20
reviewed by experts. It's security must be evident to the average=20
voter. Otherwise it is possible to intimidate voters even if the=20
system isn't breakable. ("The boss has computer experts working for=20
him so you better vote for his candidate if you want to keep your=20
job.")
=46inally, there are those unproven mathematical foundations. Assuming=20
them true may be acceptable for message privacy or financial=20
transactions of modest size, but basing our entire political system=20
is another matter.
>
>Unlike last year's so-called "electronic signatures act", this one
>specifies real digital signatures, with definitions culled from the
>usual Menezes et alia Handbook.
I would much rather you specify specific technologies, such as FIPS=20
standards (SHA1, SHA2, AES, (it will be out soon enough), DSA, and=20
P.1363. You can always add "or demonstrated equivalent" (though I=20
wouldn't). The Handbook definitions are far too loose in legal hands.=20
System security analysis is very dependent on the exact algorithms=20
used, bit lengths, protocol etc., so I wouldn't want every vendor=20
making these choices. That would complicate security review=20
enormously. Plus, in my experience even demonstrated weakness are=20
pooh-poohed by vendors.
>
>Here's what it looks like so far (draft #1.2).
>
>Summary:
>
>Minimal requirements for conducting electronic elections. Technology and
>vendor neutral. Promotes interoperability, robustness, uniformity, and
>verifiability. Easily integrated into existing equipment and practices.
>
>Handle duplicate votes and/or denial of service through submission of
>bogus votes. Permit multiple persons to use the same machinery. Inhibit
>persons with access to the machine from fraud. Provides penalties for
>circumvention.
>
>Education & telecommunications; all computing equipment purchased for
>schools or libraries with federal money under "eRate" or other
>assistance program [cite] shall be capable of use for federal elections.
>States receiving such funds shall participate in electronic federal
>elections.
>
> =3D=3D=3D=3D
>
>Title ______ -- Electronic Election Requirements
>
>SEC. xx01. SHORT TITLE.
>
> This title may be cited as the ``Electronic Election Requirements Act''=
=2E
>
>
>SEC. xx02. DEFINITIONS. -- In this title:
>
>(A) BASE64 ENCODING -- A standard method for compact display of
> arbitrary numeric data, described in Multipurpose Internet Mail
> Extensions (MIME), Internet RFC-2045 et seq.
>
>(B) DIGITAL CERTIFICATE -- A verifiable means to bind the identification
> and other attributes of a public key to an entity that controls the
> corresponding private key using a digital signature. In this
> application, the certificate shall be self-signed, and signed by the
> appropriate authorizing state server.
>
>(C) DIGITAL SIGNATURE -- A verifiable means to bind information to an
> entity, in a manner that is computationally infeasible for any
> adversary to find any second message and signature combination that
> appears to originate from the entity. Any method used for an
> election shall ensure integrity and non-repudiation for at least ten
> years.
>
>(D) ELECTION SOFTWARE -- Applications or browser applets that display an
> electronic ballot and record the voter choices.
>
>(E) ELECTRONIC ELECTION SYSTEMS -- A collection of electronic
> components, including election software, hardware, and platform
> operating system, on both local clients and remote servers, used in
> the election.
>
>(F) MANIPULATION DETECTION CODE (MDC) -- An easily calculated function
> that indicates whether the information has been modified.
> Specifically, the output of a one-way hash function, which is
> computationally infeasible to find any second input that has the
> same output.
>
>(G) PSEUDO-RANDOM NUMBER GENERATOR (PRNG) -- A one-way function that
> generates an apparently unpredictable sequence of unique numbers,
> initialized by a random starting value (called the "seed"). Any
> method used for an election shall inhibit computational discovery of
> the sequence, by an adversary with knowledge of the algorithm and
> any previously generated numbers, for at least six months.
I find the language "for at least six months" to be very dangerous.=20
It implies that we have a variety of cryptographic components on the=20
shelf, calibrated by the time needed to break them and with cost in=20
proportion to their strength. Would that this were so! In fact we=20
have pretty much two classes of components: those we know can be=20
broken and those that (we think, hope, in rare cases have proven)=20
cannot be broken. The cost difference is minuscule. The difference=20
between 6 months and 500 years is just 10 bits. 35 bits gets you to=20
the age of the universe. There is no reason whatsoever to use=20
anything but the best we have in this application.
And where does 6 months come from? Moore's law will cut that in half=20
every Congressional election cycle anyway.
>
>
>SEC. xx10. OPERATIONAL REQUIREMENTS
>
>(A) INSPECTION -- Election software shall be open source implementations
> capable of inspection by poll watchers and election inspectors.
> Functional components shall include tamper protection by
> manipulation detection code and digital signature, which shall be
> separately published and verified.
There are a lot of reasons why open source is desirable, but it does=20
simply the job for an attacker. I have thought about some notion of=20
an obfuscating compiler, one that would insert a lot of meaningless=20
object code, branches etc. based on some pseudo-random generator, but=20
whose code would provably produce the same outcome. That might be=20
appropriate here, so attackers would have a very narrow window in=20
which to produce an effective virus or Trojan. The obfuscation key=20
would be kept secret until after the election, after which the=20
validity of the object code used could easily be checked against the=20
published source.
>
>(B) INTEROPERABILITY -- Election software shall be capable of operation
> on at least 3 multiple, independently implemented platforms. This
> applies to all functionally equivalent or interchangeable components
> of the system or process in which they are used.
>
>(C) ROBUSTNESS -- Election software shall concurrently register voter
> choices at the local client, and municipality or other regional
> voting district server(s), and state server(s), using well-known
> database transaction multi-phase commit techniques.
Better be more specific.
>
>(D) UNIFORMITY -- Display of candidates shall be substantially similar
> for each race within a state. On each display, the names of
> candidates may be randomly ordered within each race. Election
> software shall prevent overvote and undervote, and shall allow the
> voter to correct such conditions. Voters unwilling to indicate a
> choice may select "no vote". Where "none of the above" or its
> equivalent is a valid choice, "no vote" shall be a separately
> distinguished choice.
Some states (e.g. Florida) specify order on the ballot in terms of=20
party results in the last statewide election. Whether that method is=20
reasonable has nothing to with electronic voting.
Then there is the question of how that random seed is selected.
>
>(E) VERIFIABILITY -- Transactions registering voter choices shall be
> recorded in a printable textual format using US-ASCII characters.
> The first line of each transaction record shall include an audit
> number assigned each voter at the time of voting (such as a
> sequential poll book number or pseudo-random personal identification
> number). The record shall not include any other personally
> identifiable voter information. Each successive line of the record
> shall indicate the title of the race as it appears on the ballot
> display, delimited by a colon, followed by the voter choice as it
> appears on the ballot display, or the text of a write-in vote as
> typed by the voter.
>
>
>SEC. xx20. POLLING SECURITY REQUIREMENTS
>
>(A) AUTHENTICATION -- Transactions registering voter choices shall be
> authenticated by a digital certificate. The certificate shall be
> generated by the local polling machine no sooner than the opening of
> the polls. The public part of the key shall be verified to be
> unique and certified by the participating state server(s). The
> certificate shall expire no later than the closing of the polls. The
> private part of the key shall not be disclosed by the electronic
> election system, and shall be destroyed by the local polling machine
> at any time subsequent to the expiration of the certificate.
This seems impossible to verify, especially if one plans to use=20
hardware that has other uses and is therefore physically accessible=20
throughout the year.
>
>(B) AUTHORIZATION -- Registration of digital certificates by the state
> server(s) shall include at least two parts:
>
> (1) The physical location of the local polling machine, including
> the mailing address of the local election clerk responsible for
> operating the local polling station(s); and
>
> (2) A secret password. At least 14 days prior to the opening of the
> polls, the state shall pseudo-randomly generate a unique
> password assigned to each anticipated local polling machine. The
The "state" can't generate anything. Only people and machines can.=20
You have to specify how this is to be done, who is present, etc.=20
down to how the passwords get into the envelopes and what prevent=20
someone from reading the numbers through the envelope.
> seed for the pseudo-random number generator shall not be
> disclosed until after the closing of the polls. The passwords
> shall be physically printed in base64 encoding, and shall be
Why Base-64? The mixed capitalization will drive poll workers crazy=20
and many polling places will report broken machines because the can't=20
enter the password properly. Base-32 would be a much better choice.
> sent by the state to the poll operator via registered mail. The
> mail envelope(s) shall not be opened until immediately prior to
> the opening of the polls.
>
> (3) In addition, the registration transaction shall indicate the
> electronic location (that is, Internet address) of the polling
> machine, the name of the operator initiating the registration,
> and the election software manipulation detection code and
> digital signature.
>
>(C) CONFIDENTIALITY -- Electronic election systems shall provide
> confidentiality of all transactions between a local polling machine,
> and participating servers.=A0
>
>(D) INTEGRITY -- Transactions registering voter choices shall use
> digital signatures to protect against modification. The digital
> signature shall be generated at the local polling machine using its
> certificate. These digitally signed transactions shall be retained
> at every participating server. For transaction audit purposes, the
> digital signatures shall be displayed in base64 encoding, together
> with an indication of the identified polling machine and whether the
> digital signature is valid.
>
>(E) PRIVACY -- Electronic election systems shall not disclose personally
> identifiable vote choices. Any distinguishable value assigned each
> voter for the purposes of voting (such as a sequential poll book
> number or pseudo-random personal identification number) shall not be
> electronically cross-referenced with transactions, except as part of
> a transaction audit (such as a recount).
>
>(F) TRANSCRIPTION -- legacy paper ballots may be transcribed for
> electronic counting on a local polling machine designated for that
> purpose. The digital certificate shall indicate that it is used for
> transcription, and the password shall not be used for any other
> voter transactions.
>
>
>SEC. xx30. ABSENTEE SECURITY REQUIREMENTS
>
>(A) AUTHENTICATION -- Transactions registering voter choices shall be
> authenticated by a digital certificate. The certificate shall be
> generated by the absentee election software no sooner than the
> beginning of absentee registration. The public part of the key
> shall be verified to be unique and certified by the participating
> state server(s). The certificate shall expire no later than 24
> hours prior to the opening of the polls. The private part of the
> key shall not be disclosed by the electronic election system, and
> shall be destroyed by the absentee polling machine at any time
> subsequent to the expiration of the certificate.
>
>(B) AUTHORIZATION -- Registration of digital certificates by the state
> server(s) shall include at least four parts:
>
> (1) The name of the absentee voter initiating the registration;
>
> (2) A secret Personal Identification Number (PIN). At the time of
> absentee ballot application, the state shall pseudo-randomly
> generate a unique PIN assigned to the absentee voter. The seed
> for the pseudo-random number generator shall not be disclosed
> until after the closing of the polls. The PIN shall be
> displayed to the absentee voter in base64 encoding for later
> entry at the time of voting, but shall not be retained in
> storage by the absentee election software. The PIN shall not be
> disclosed to the local election clerk;
Again Base-64 is a bad choice and the procedure for how the numbers=20
are generated and get to the voter must be made clear.
>
> (3) The physical mailing address of the absentee voter. The name
> and mailing address of the absentee voter shall be
> electronically transmitted by the state to the appropriate local
> election clerk; and
>
> (4) Another secret password. Subsequent to verification of absentee
> eligibility, the local election clerk shall pseudo-randomly
> generate a unique password assigned to each absentee voter, and
> electronically transmit the password to the state server(s).
> The seed for the pseudo-random number generator shall not be
> disclosed until after the closing of the polls. The password
> shall be physically printed in base64 encoding, and shall be
> sent by the clerk to the absentee voter via regular mail.
>
> (5) In addition, the registration transaction shall indicate the
> electronic location (that is, Internet address) of the absentee
> polling machine, and the election software manipulation
> detection code and digital signature.
>
>(C) DUPLICATES -- When more than one authentic vote by the same absentee
> voter is detected, the last such vote shall supercede any earlier
> vote. An absentee voter appearing at the regular polling place shall
> supercede any earlier vote.
>
>(D) TIMELINESS -- Electronic absentee ballots shall be received and
> recorded at least 24 hours prior to the opening of the polls.
Unless there is a design issue that I don't see, that is a political questio=
n.
>
>(E) OTHER -- Except as specified in this section, all other requirements
> of section xx20 (C) to (F) apply to absentee ballots.
>
>
>SEC. xx40. PENALTIES.
>
>(A) AUTHORIZATION FRAUD -- may not disclose, exchange, or use the PIN or
> password of another voter or . Felony, need big penalty!
>
>(B) CONFIDENTIALITY -- may not circumvent confidentiality. felony,
> $5,000 per incident, 2 to 5 years jail.
>
>(C) PRIVACY -- Where transcription or transaction audit could reveal
> personally identifiable vote choices, felony (to disclose or even
> browse, see IRS for language), $1,000 per person identified, 2 to 5
> years jail.
>
>-----BEGIN PGP SIGNATURE-----
>Version: PGP 6.5.1
>
>iQCVAwUBOnBqU9m/qMj6R+sxAQHEdgP8CX478EiLL2aq7OiFfQjCRcAQc+HkXiTm
>6BoRLyI7G0yqHTiIv3L5dyGCtg+07AKnyVXyO1opvQ2JkLBQmvy3YrBeU2RKXKgi
>TCBa/JDX9Ycu+0YAnVOndbh9d9en91LGHrfHEU5mgicZ9vjpvtX/5BsQJm77Ve1A
>db0DxBT86Co=3D
>=3Db5Yo
>-----END PGP SIGNATURE-----
