5

I want make to a untraceable voting system that would allow registered users to vote on some sensitive issue in a way, that would make it impossible to track votes back to users in a case of database compromise (including being "compromised" by overly curious DB admin).

Detailed setup:

  1. Every user is registered, there's no completely anonymous voting.
  2. Sockpuppets, fake accounts, and the like are out-of-scope of this question - this is responsibility of registration system.
  3. Every registred user can only cast one vote (which may be anything: simple yes/no or weight or whatever).
  4. User must be able to change/delete his vote until voting is closed.
  5. It is not necessary to let user view its own vote, though it can be done in same way that deleting/changing is done.
  6. Even if somebody have access to user auth database and voting database, they must not be able to track each vote back to user (in a sense that it must not be easier that bruteforce or otherwise hack entire user account's access).
  7. All parts of system except communications are open, so there can't be hidden keys. MitM attack is out-of-scope of question, but attacker have full access to sources, auth and voting database.
  8. Users are lazy. They will not want any other voting-specific key or password. System must not require user to provide or keep locally anything except the usual login/password/key whatever they already use to login.
  9. Tampering of votes and any security issues except program<->DB communication and untraceability are much wider issue and so are out-of-scope of this question too.

I have some solutions in mind which I post as my own answer after grace period.

Oleg V. Volkov
  • 21,719
  • 4
  • 44
  • 68
  • 2
    There are methods of secure cryptographic voting discussed in Bruce Scheier's book Applied Cryptography that describe voting systems that can be secure and anonymous. However, I don't know how you can do this with revocation as you have requested. Removing the previous vote requires knowledge of the previous vote, which would mean some kind of traceability. – gaige Jun 05 '12 at 10:07
  • That's why I'm interested in not-completely-anonymous system with registration. This will also prevent multi-voting from user. – Oleg V. Volkov Jun 05 '12 at 10:11
  • 3
    Prevention of multi voting shouldn't be a problem with the cryptographic techniques, but being able to revoke a single vote after it is cast makes that problem much more difficult (I would say impossible, but there are some very good crypto folks out there that might have an idea how to do this). – gaige Jun 05 '12 at 10:13
  • You mentioned that a user should be able to change/delete his vote, but should he be able to view his answer? – Dejan Jun 05 '12 at 10:14
  • Nah, multivoting will always be a problem with anonymous voting. Nothing prevents a user from obtaining several different tokens and voting with all of them. – Oleg V. Volkov Jun 05 '12 at 10:15
  • @dDejan, no, not necessarily. It can also be done as part of deleting/changing process. I've updated the question. – Oleg V. Volkov Jun 05 '12 at 10:24
  • +1, it's an interesting question; but you're effectively asking for a way to implement (inter)national-level, on-line, voting systems, which is worth a fair bit of money. Even if someone did have _the_ answer they'd be foolish to post it. – Ben Jun 05 '12 at 10:30
  • Huh? I thought about a possible solution while I was walking from metro station to work - about 15 minutes. Question is only limited to app/DB interaction, so in real life you would also have to worry about transmission and voting location security issues, but scope of question is narrower. – Oleg V. Volkov Jun 05 '12 at 10:34
  • @OlegV.Volkov Do you allow storage of data on the client computer for the duration of the voting process? – Sergey Kalinichenko Jun 05 '12 at 10:35
  • Of course not. Nothing client-side can be considered "secure". The only thing user ever provides except the vote itself is the usual login/password pair (or login/key if you want - any kind of auth the user normally uses to log in into this system, which also does something else than running polls). – Oleg V. Volkov Jun 05 '12 at 10:36
  • Can somebody who voted to close please comment what is off-topic in question that concerns developing of very specific voting setup? Or is it already "too broad" with correct answers covering almost 100% of functionality taking only about 1000 chars? – Oleg V. Volkov Jun 06 '12 at 11:22

4 Answers4

2

Assuming the DB Admin has no access to the application code that will have the voting system, and assuming that the DB Admin viewing the votes is not an issue (just linking a vote to a person)

In your table where you store the user votes, create an extra column that will contain a salted hash of some info from the user that cast the vote (name, username, e-mail, b-day, combination of those). This is the important thing, the DB Admin should not know how the user unique value that is stored in the DB, is first generated and then encrypted.

Just assume that the user token that you came up with (name, email) is a password, and you want to store in the DB without people knowing what the actual password is. More info can be found here Best way to store password in database

So with your per user hashing/salting algorithm, each time a user wants to cast/edit or delete their vote, you can first generate the hash, then try to find a record with that hash value in the voting table, and act on it accordingly. ( insert if it doesn't exist, update if it does, and delete if the user wanted that)

Once the voting process is closed, you can even discard the hashed values for the answers for that voting process, so that there is no way ever to link the votes to users

Community
  • 1
  • 1
Dejan
  • 501
  • 5
  • 13
1

Ask the user to provide a password when casting/changing their non-traceable votes, and do the same thing that you do when you store user's authentication information (salt+one-way hash) twice: once with the salt that you have stored along with the hashed password, and once more with the salt that you have randomly generated for this specific pair of {user, poll}. A request to set or change a vote should contain these pieces:

  • User name
  • Password hash #1 for the authentication salt #1
  • Password hash #2 for the poll-specific salt #2
  • The vote itself

You use the user name and hash #1 to verify that you're getting a vote from a known user, and then store hash #2 along with the vote itself in the user votes table. The value of hash #2 and salt #2 are used to uniquely identify the vote.

Since password hash is one-way, only a person who knows a plain-text password could produce hash #2. When salt #1 is different from salt #2, even a person in possession of both databases would not be able to establish the connection back to a user casting the vote.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Pretty much exact scheme I had in mind, assuming password is the same user regularly uses to login into system. – Oleg V. Volkov Jun 05 '12 at 14:24
  • @OlegV.Volkov Keep in mind that this scheme would require you to do more work when a user changes his password: you would need to have the client side re-generate salted hashes for all votes that are still in progress. Otherwise, users would be able to cast as many votes as they want simply by changing their passwords. – Sergey Kalinichenko Jun 05 '12 at 14:28
  • Yes, of course. I was thinking about workarounds around it and so far I could only think of either: 1. complete loop over all open polls when user tries to change password, or 2. less secure but faster loop over open polls where user voted, with list of those open polls stored in fashion that CAN be tracked to user. When you don't have that much open polls at same time, speed of 2. is irrelevant. – Oleg V. Volkov Jun 05 '12 at 14:31
0

If you just want to hide it from people with DB access, use symmetric encryption with a key that is stored outside the DB.

Otherwise, you will need to assign a secret to all users, and store that secret with the vote instead of the user ID. The secret should be in some way signed by the server but not connected to the user in any way. The user can use the secret to change his vote later, and you can verify the votes because they are signed, but there is no way to connect them to users (unless the attacker has a way to observe the process of assignin the secrets).

If you don't want to inconenience users with an extra secret, you need to use the only one they already have: their password. You can use a hash created from username, password and random salt to index the votes. This is inherently insecure, as many passwords can be easily guessed; a strict password policy and a very slow hashing algorithm (such as bcrpyt) helps somewhat. E. g. if you set the bcrypt work factor so that it takes a few seconds to compute a hash, that is still acceptable for your server, but an attacker is unlikely to get more than a few million attempts at breaking the hash, which might be not enough even for a dictionary attack.

Tgr
  • 27,442
  • 12
  • 81
  • 118
0

What you want seems not possible, because the conditions exclude each other.

Either you set up good keys or you compromise security.

mit
  • 11,083
  • 11
  • 50
  • 74