You need to have a shared secret with the government beforehand.
The simplest way I can think of is to have two confirmation passwords for the vote: one that means "validate my vote", one that means "I've been coerced". These passwords are used for nothing else, and so the coercer cannot verify that you used the correct password.
That was quick! You've spoiled all the fun :)
I've orginally wanted to use the discussion here to ramp up the puzzle to the next level, but given that you've already solved it, here we go:
What if, instead of coercer, there was malware on your computer/phone. Would we be still able to prevent malicious parties to mess with the election results?
The malware cannot know which password you used either. It could withhold your vote, but it wouldn't know when to do so.
It could however redirect a vote for a candidate to another.
A low-tech solution would be to define a secret identifier per voter per candidate, then print the identifiers for a voter on a sheet and physically mail it to them. You then need to enter both the candidate identifier and the "intent password". The malware wouldn't know about your identifiers, unless the malware authors run a sophisticated mail-interception scheme.
Another way: using something similar to the "bank calculators" (that generate tokens based on challenges and on your debit/credit card) to combine the candidate and the intent password. This allows for candidates to have public identifiers.
However, I'm not sure these solutions are "fully online" in the way you meant.
The first suggestion won't work in the real life The mail can be intercepted, the coercer could just force you to hand him the paper etc.
The second suggestion goes straight to the essence of the problem though! It looks like that solution may be pretty much secure.
The assumption though is that the "calculator" is a low tech device that cannot be infected by malware. So, to make the puzzle harder, let's now assume that the calculator may be infected. Or someone may simply steal the calculator from you and replace it be a replica that would record your password.
What then?
The issue there is that the solution to untrusted hardware is to apply a knowledge-hiding transform. So far, all of the ones proposed here have been based on shared secrets.
With your password solution, it hides a coercion signal.
With Norswap's solution, it prevents redirection by hiding which choice was made. (In the bank calculator variant, it just encapsulates the shared secret in the device).
The issue there is that arbitrarily saying "And what if _that_ is infected" results in an infinite regression. None of the computationally-secure knowledge-hiding transforms are simple enough to do reliably by hand without either reference material (the letter, which as you pointed out is interceptible) or a device (which basically encapsulates the reference material or its generation process).
However, there are some interesting cases if we reduce the problem space a bit by showing that the token _cannot_ be infected, and making replacement detectable.
First of all, the token really just needs to perform one operation: MAC(shared_key, text). This is incredibly simple, and if you presume a fixed-size text can be pure hardware - no risk of infection.
Second, there's actually a simple solution to the steal-and-replace problem: Prior to use, the user inputs a challenge and it must reply correctly. Supporting this is similarly simple in pure hardware - if it stores four (post-MAC) challenges and four responses, that's a small buffer of memory elements and a comparator - but a replacement device could not reply correctly. This relies on the user checking, but that's kind of an issue with any such system.
Third, make generating a value with the token take a tuple of (passphrase, value-to-hide). This passphrase then acts as the coercion signal from your solution.
Now, a token that records the password will give an incorrect challenge (alerting the user) and doesn't have the MAC key (making it useless to coerce them into using it, since they'll give it the coercion signal too, which the attacker will faithfully type into the real device).
To clarify: The passphrase in "third" is treated as part of the text in "first" - to show why this works, let's look at the state space an attacker (resp. the govt) must search to detect coercion.
The government has one valid MAC key, and one valid (human-memorable) shared passphrase. The attacker has neither.
The MAC key on the client side is in the device, and the passphrase is in their head.
Now, MAC(key, pass || candidate) is a bijection from candidate to an indistinguishable value in the ROM (which allows us to ignore collisions), so the government just checks if it's in the set of valid values.
Under the ROM, any other pass will result in an input that does not match the set, and thus can be discarded - so no explicit coercion passphrase is needed because all passphrases other than the valid one will serve the purpose.
Doing this with standard assumptions rather than the random oracle model would take more skill (and space) than I have, though :P
Using the man in the middle as a proxy for sending the coercion signal. Devious! I like it.
That nice idea seems a bit redundant in your solution though, given that attacker trying to create a replica would fail at implementing pt.2 and thus wouldn't even try to steal and replace the original device.
Anyway, let's make the challenge even harder: What if the attacker has a hidden camera installed in your flat or a keylogger on your device?
Why wouldn't the first solution work?
Even if the coercer obtains the sheet, it only allows him to choose on which candidate you'll cast your vote; but you still can use the password to signify that you were coerced and he'd be none the wiser. And it solves the infection problem :)
The big issue I see is that if the attacker can intercept the sheet, he could replace the identifier of the candidate that he thinks you'll vote for (or simply, the identifier of the most popular candidate) by the identifier of another presumably-evil candidate.
Ah! Nevermind! With the sheet, the attacker can record the identifier for his candidate then send it to your infected computer, and since you input your valid password directly, he has all he need to cast a vote in favor of his chosen candidate.
As for the calculator, to clarify:
- you enter your validity or coercion password
- you enter the candidate (public) identifier
- the calculator returns a combination of both
So there is not shared secret in the device at all.
Interestingly, if the passwords are chosen uniformly at random, then something as simple as a Ceasar's cipher works. And if you apply it by hand, you remove all attack vectors (well - people can't manipulate your vote, but if they infected your voting device, they can still suppress if of course, but I don't think there's anything you can do about that short of checking at a separate, known-to-be-safe, location that your vote was registered with the correct ID (= the combination of public candidate ID and chosen password)).
But assuming doing the combination by hand is out of the question, I see two potential issues:
- The calculator has an antenna and can send your password to the attacker.
- The calculator always returns the combination of your password with a constant known by the attacker; when you input this ID on your computer, the attacker can recover your password, then use it to send a vote for another candidate.
In general, I don't think it's possible to prevent attacks if (1) any device can be hacked and (2) you don't want to apply some kind of combination by hand or remember one secret ID per candidate (assuming you get the ID safely — in the same way you get the valid and corced passwords).
There _is_ a shared secret; the MAC key is burned into the device. Thus, a different person's device (even with the same passphrase) would fail. It's two-factor authentication.
Also, @sustrik, the proxied coercion signal is needed for if they are trying to coerce you to use your real device (among other things). It binds the coercion signal to the authenticated fob, preventing a TOCTTOU attack where they record the valid output from the (non-passphrased) fob (if they borrow it, or coerce you, or if it _didn't_ have a per-device MAC key) and then combine it with an eavesdropped passphrase you use later on.
Regarding the harder challenge, the camera's actually relatively simple - make the screen generate noise in the infrared that obscures the text (digital camera sensors pick up much more IR than human eyes, which is nice to exploit - try pointing a TV remote at your phone's camera, and watch that nice bright flash).
And regarding the keylogger, I'm still presuming that the fob is designed incredibly simply with a hardware-only design spec - a minimal solution (that also doesn't expose anything for a camera to catch) is a scroll-wheel-like bit to scroll through characters, and clicking it moves to the next cell. Hold it down to hash.
(And a computer-side keylogger or infected computer does nothing, because the fob's output is the only content of the vote, and is indistinguishable from random)
Here, I mocked up what I imagine the fob looking like - it won't let me insert a URL or image, but it's in my homedir at ~eternaleye/votefob.png on the "dev" subdomain on the Exherbo linux distro site.
(Gah, forgot to illustrate challenge/response. That's denoted by the leftmost box being fully lit as a prompt to enter a challenge, and the rightmost will be fully lit for the response. This limits them to 60 chars each, but that's not really an issue. Fully-lit cells are not a value selectable by scrolling, so it's not spoofable. The currrently-focused cell blinks.)
The calculator doesn't need to have a MAC key or even do MAC. Like I said, if it just applies ceasar's cipher, it works as well (and the shift is the candidate public identifier, so even that is not burned into the device — you supply all inputs and the machine just avoids the tedium of doing hand computation).
Ah, I think we're optimizing for different things. I'm designing it with the viewpoint "If I was going to implement this IRL, what would I do to ensure it's secure against the listed threats" rather than viewing it as literally a cryptopuzzle.
For instance, a Caesar cipher (or equivalently, xor) of the passphrase and the candidate is only secure if the password is used once and *never* again - it's the classic one-time pad.
If it's used again, then the adversary can deduce the secret as a function of the two candidates. (In xor, if you xor the ciphertexts you get the xor of the plaintexts, since the key cancels. An equivalent method exists for Caesar ciphers.)
This is especially plausible because the set of possible messages is very limited.
The reason I chose a MAC (under the random oracle model specifically - something like poly1305 doesn't have the right security properties) is specifically because that kind of attack is then infeasible. The fob producing a pseudorandom function over all of its inputs is actually critical to the security guarantees I wanted.
And while the system would _work_ without the fob having a unique device key burned into it, it'd be less robust.
(Plus, "uniformly random passwords" is one of those assumptions that simplifies everything but _never_ actually happens. You'd have to apply some-sort of key-stretching function, which you'd want to be something well-reviewed… something like PBKDF2, which is iterated applications of a MAC that is presumed to be a PRF, the exact primitive I chose for the fob.)
The solution I thought of was: you and the government agreed on a number K that the coercer does not know. If there are N choices, you give a number M between 1 and N which means that you actually want to vote for candidate number (M + K) % N.
My solution above only works against a coercer (if you know he is here), not an invisible man in the middle (who could vote with the same shift).
However, if you generalize and replace the shared secret by a random permutation of the voter list instead, even a MITM wouldn't be able to exploit this to his advantage if he doesn't know what you intended to vote, and even if he does he could just make sure to replace your vote by somebody else.
It is even possible to do better. For instance with 3 candidates a permutation would be:
A -> B ; B -> C ; C -> A
but we could use an input space N times larger than the number of candidates. For instance, with N = 3 :
A -> B ; B -> C ; C -> A ; D -> A ; E -> C ; F -> A ; G -> B ; H -> C ; I -> B
If N is large enough then anything the MITM would do would basically only amount to canceling your vote.
Even physical voting can be coerced, even with voting booths. I don't remember the technical name, but here is the method:
The bad guy steals one single voting paper, before the elections. Then, if he wants Alice vote for someone, he gives that voting paper to her, already marked for that candidate. She then goes to vote, and inside the booth she hides the new voting paper without signing it. She than puts the old, pre-signed paper into the box. When she goes out, she give the new blank voting paper to the bad guy. At this point he can verify that she had voted for his candidate: the voting paper is blank, so she must have used the pre-signed one for her vote. The bad guy can now sign this new voting paper and give it to someone else, using the same method.
This method is extremely difficult to stop, since only one blank voting paper is needed.
Signalling coercion via alternative channel, thus invalidating bogus vote is a great idea.
I'd like to propose multiple channels idea, with IoT growing and such… voting booth/pc being one of channels.
Here it is:
As part of my research of candidates I have to give them "favor points"… Imagine I do it securely all the time, flooding my candidates standing with my "favor points" mini-votes. Top dog wins, properly tie breaking, of course. If I'm coerced and not happy, I simply subtract few "favor points" :)
I think I am a little late to this party… but I just recently found your blog and wanted to give my thoughts on the problem.
If we assume that your machine is infected with malware, I do not think any token based scheme could possibly work. If we go with the worst case scenario, the entire OS is taken over you would still need to provide the machine with the token's number thus making it able to corrupt your vote. There is no way I can see that you can prevent a bad machine from corrupting your vote without the user cryptographically signing their input before it gets to the machine. This seems like a poor solution for a general user.
It seems like we shouldn't care about a correct vote reaching the voting system, since we can re-vote as many times as we like. Instead, we should simply validate that our correct vote was received. Upon submission, the backend voting system could take your answers + your ID, sign this value, and present the entire thing as a QR code to the user. The user could take a picture of this QR code and have an App on their phone that validates it (aka, checks the signature and presents what the votes were).
- The system could still require a password to actually submit votes, it simply adds a validation process at the end.
- If the person used their coerced password when submitting, the same QR code would be returned. This would prevent the attacker from knowing which password was used.
- The local malware cannot fake the QR code unless it also has control of your phone. I think it would be impractical for an attacker to control enough phone/computer pairs to make an impact.
- This scheme does not require a secure exchange of anything between the citizen and the government prior to voting.
- As far as usability goes, this becomes very easy because the security side aspects are non-invasive to the process and entirely optional (two things people love).
- It works as long as the private key of the voting system remains private.
I really like this question, but I think it is important to point out that no system can every be completely secure, but you can make it difficult to the point where changing enough votes would be impractical. Even with our current process votes could be purchased because the voter could simply wear a button camera to prove what happened inside the booth.
