Crypto codes #1

From: David Mertz <voting-project_at_gnosis_dot_cx>
Date: Thu May 19 2005 - 14:31:09 CDT

On May 19, 2005, at 2:36 PM, charlie strauss wrote:
> "2) Each ballot contains (as printed strings or in a barcode):
>> for bv = ballot-id + vote-string:
>> e = encrypt(k, hash(bv))
>> print bv + hash(bv) + e
>> (3) At finalization, k is revealed publicly.
>
> If the hash function is known or knowable does not this reveal you
> ballot and provide a effective receipt? That is to say it's going to
> be fairly trivial, by crypto standards to invert the hash of a ballot
> string I would suspect.

How does the below differ from VoteHere? Hmmm... how does a goat differ
from brotherly love? I don't know how to answer those questions, they
seem like category errors. I guess the closest I can come is: "My
suggestion is a use of cryptography utterly unlike and utterly
unrelated to VoteHere's use... and neither has much to do with SSL or
PGP either."

The hash function absolutely must be a well-known and widely
implemented one. Say SHA or MD5.

Inverting SHA is not exactly practicable, is it?

Actually, that's probably not quite true. Remember the old "vote
entropy calculator" I made available? A typical ballot will not really
have all that many possible vote combinations. If it is a thousand, or
even a million, that is within the range of dictionary attacks. Even
if you add a four digit ballot-id (10000 possible numbers), that's
still dictionary attack range.

In other words, before the election even starts, Mallory can precompute
all the possible hashes. Say, for example:

  IF a voter were given random ballot-id 2395; and
  IF voter voted Jones for President; and
  IF voter voted Wang for Senator; and
  ...
  THEN the ballot hash WOULD BE 24ac4f8b

Storing a few million, or even a few billion combinations, is perfectly
possible on computers. Or recomputing them takes only a moderate
amount of CPU time (more than seconds, but not years).

But the White Hats can do all this computation just as well as the
Black Hats can. So nothing is secret in this system. Well, 'e' can't
be computed by the world until k is revealed at poll closing. But
neither White Hats nor Black Hats can do it.

Assuming both Charlie Coercer and Vicky Voter are technically
competent, there is no threat:

   Charlie Says to Vicky before the election:
   "I want you to vote, Jones/Wang/...; and I want you to
   memorize your ballot-id and ballot-hash to report to me!"

   Vicky cleverly precomputes a table:
   ballot-id 0001 + Charlie's votes --> hash = 3039ec29
   ballot-id 0002 + Charlie's votes --> hash = ad8002ca
   ....

   When Vicky gets her actual ballot with ballot-id 8345,
   she votes how she actually wants to; then Vicky looks
   up 8345 in her table; then Vicky lies to Charlie about
   what hash value appeared on her ballot (to match his
   orders)

Hmmm... that's not quite true. If Charlie also has access to the full
ballot set, he can determine that no ballot matches Vicky's purported
combination. Another reason for ballot perforation. Or at least for
not revealing full ballots to everyone. Of course, we've already
discussed the "marked vote" weakness, which does the same thing[*]

[*] For newcomers, Charlie tells Vicky: "Vote Jones for President, and
write-in 'Flazflam37' for Dog-Catcher". If Charlie has access to all
the full ballots, he can determine whether the ballot with the unique
write-in Flazflam37 actually votes Jones. Even w/o write-ins, special
combos of ranked preference or judicial confirmations can do the same
thing.

On the other hand, if Charlie understands technology but Vicky does not
(a realistic scenario--not to insinuate about the example genders--but
simply that coercers can hire programmers better than average voters
can), there's a problem:

   Charlie gives instructions as above.

   Vicky has no idea what about pre-computation,
   hashes, and all that.

   Vicky's only options are to report the actual ballot-id
   and ballot-hash, or to randomly invent values. If she
   makes up random values, the mismatch is easily detectable
   by Charlie (or Charlie's programmer).

So maybe there really is a problem here. Of course, the League of
Women Voters could publish a guide to "How to fool coercers" that had a
little online tool for creating spoof hash values to tell Charlie.
Vicky need not understand the whole thing, just fill in the form:

   Your actual ballot-id: _____
   How Coercer says you should vote:
     ______________
     ______________
     ______________
     ....
   [Compute Hash]

_______________________________________________
OVC discuss mailing lists
Send requests to subscribe or unsubscribe to arthur@openvotingconsortium.org
==================================================================
= The content of this message, with the exception of any external
= quotations under fair use, are released to the Public Domain
==================================================================
Received on Tue May 31 23:17:43 2005

This archive was generated by hypermail 2.1.8 : Tue May 31 2005 - 23:17:52 CDT