Avoiding giving up your key

| Comments (10) | TrackBacks (11) |
Tyler Cowen raises the question of how to avoid getting tortured assuming you're willing to give up a goods. A dual of this problem that has been considered in cryptography is how to pretend to give up your key.

The context here is that you've been captured by people who have your encrypted communications. All they want is for you to provide your key so they can decrypt them. You've got to provide something (you're under subpoena or they're going to torture you.) The idea in this situation is to convince them that you've cooperated without actually giving up the goods.

There are two basic strategies here:
Throw the steering wheel out the window1: Make it manifestly impossible for you to provide the key that they seek. They can still jail you for contempt or torture you but they can't actually get the information, so anything they do to you is purely a matter of revenge or deterring the next guy.

Pretend to cooperate: Provide some fake key that nevertheless produces a plausible decryption of they ciphertext.

The throw the steering wheel out the window scheme is actually used in a number of communications security contexts, where it goes by the name Perfect Forward Secrecy. The idea is that you generate a fresh Diffie-Hellman key for each communication and destroy it after the communication is over. Your long-term key is used only for authentication so even if you give it up it doesn't do the attacker any good--and the attacker can verify this by just looking at the structure of the communication protocol.

The major disadvantage of PFS is that because both parties need to generate fresh keys, it only works well in interactive contexts like Web or telephony. In a non-interactive context like e-mail you really need to have access to the recipient's long-term key, which makes PFS fairly difficult. This is even a bigger problem with had drive encryption, where you obviously need to be able to have archival access to the data.

If you want to have encryption for non-interactive or archival data you pretty much have to have some long-term key, which you must somehow destroy if you're captured. The state of the art here, as far as I know, is to have that key in some tamper-resistant container which you can cause to zeroize, either by positive action (e.g., pressing some switch) or negative action (failing to type in your PIN at some pre-programmed interval). 2. This approach sort of works, but has a number of obvious problems:

  1. Putting your key in hardware makes it harder to move around. This is more of a problem for e-mail than for hard drive encryption, where you're already stuck moving around the hard drive.
  2. It's incredibly brittle. The same properties that make it easy to destroy the key intentionally also make it easy to accidentally destroy it, in which case you're hosed.
  3. It's not fail-safe. If you're taken by surprise, you may not have time to zeroize the key and they may force you to hand over your PIN before the module times out and zeroizes.

The above-mentioned problems have created some interest in alternative solutions for non-interactive communications. The basic idea is to design an encryption system/protocol that produces multiple plausible outputs for a single ciphertext depending on the key.

So, say we have some ciphertext C, you'll have some set of keys K_1 ... K_n such that:

D(K_1,C) = M_1
D(K_2,C) = M_2
...

So, for concreteness and simplicity, say you have some real key K and then a fake key F. To decrypt things normally you use K but when you're forced to give up your key you provide F. D(F,C) is your grocery list whereas D(K,C) is the plans for your nuclear attack on Washington.

It's technically possible to build a system like this (the easy way to do it is simply to individually encrypt each plaintext and concatenate the results with a bunch of randomness so that you can claim that the fake plaintext you decrypted is the real one and that the rest of the file is randomness) but as far as I know no existing e-mail or file encryption system actually works that way. But even if you had something like this, I'm not sure it would help. Imagine yourself tied to a chair Guantanamo cell (or if you'd rather be a good guy, you've been captured by Al Qaeda) and the interrogators tell you to decrypt some file. You give them F and they decrypt your grocery list. Now, they know there's a possibility that the message contains some other plaintext 3 and they know they're not interested in your grocery list, so what's the downside to beating you up some more to see if you'll give up another key.

As I recall, when this kind of technique was discussed on Cypherpunks, the general idea was that you would have some series of progressively more sensitive plaintexts you would reveal--and that the attacker couldn't tell how many total messages there were--and that eventually the attacker would decide they'd gotten the real one. That sort of plausible deniability might work if you've been subpoenad, but I'm skeptical that it's going to work if people are willing to torture you anyway.

1. After Hermann Kahn's famous observation that the way to win at chicken is to throw your steering wheel out the window.
2. You can of course imagine social versions of this mechanism--e.g., there's some key server somehere that tries to figure out if you're giving up your key under duress, but then you've just moved the problem. This service has to be highly available and so they can presumably be captured or subpoenad.
3. One way they can tell is that the minimum size (taking compression into account) of a ciphertext that contains multiple messages must be greater than the minimum size of one which contains only a single message. Now, of course, you could have just padded out the ciphertext (say with zeros or other innocuous messages) but AFAICT there's no way of proving that until you've given up every single message. Even if it weren't possible to deterine when multiple message techniques were in use, the mere fact of there existence gives the attacker incentive to continue torturing you.

11 TrackBacks

Listed below are links to blogs that reference this entry: Avoiding giving up your key.

TrackBack URL for this entry: http://www.educatedguesswork.org/cgi-bin/mt/mt-tb.cgi/234

alicia key ticket tropicana from alicia key ticket tropicana on August 11, 2005 10:18 AM

alicia key ticket tropicana Read More

gay teen boys gay orgy gay wrestling free gay sex movies free gay pics free gay videos Read More

rape pictures rape movies rape virgin rape anal rape gay rape Read More

date rape anal rape rape sex date rape rape sex brutal rape Read More

Asian moms having sex from Mom fucked a black guy on November 12, 2005 3:19 PM

Free mpegs dogs fucking moms Mature woman fucking little boys Young teen amature porn galleries Illegal mom ince... Read More

tropicana patio furniture from tropicana patio furniture on November 16, 2005 11:03 AM

tropicana patio furniture Read More

poker 780 Read More

Gratis video clip sexy Free porno sample movies clips windows media Momson film Strapon samples Read More

Home Equity Loan from Home Equity Loan on February 3, 2006 9:56 AM

Home Equity Loan Read More

10 Comments

re: (3) -- why must the ciphertext that contains multiple messages be greater than the minimum size of one which contains only one messages? If the key shares information with the messages, then I'm not sure this holds. eg the "XOR" encryption scheme, E(a,b) = bitwise(a xor b); Not great information hiding here if when you give your key, it's actually the message you're trying to hide, but surely some crypto guy could figure out a way that you could actually "hide" your message in the key, and the boob analyst looking wouldn't realize that the secret sauce is in the key, not in the message. How often do cryptanalysts take a long hard look at what data might be in the key they're given, rather than in the ciphertext?

A few years ago, some crypto papers were published on this subject, which was referred to as "deniable encryption". A lot of debate ensued, whose flavor was at least slightly reminiscent (to me, at least) of "Monty Hall problem" debates.

The bottom line, I believe, is this: there's really not much difference between hiding your encrypted secrets in innocuously encrypted secrets using "deniable encryption", hiding it steganographically in digital images or other data, or hiding it under the couch. If the bad guy can find your key and the ciphertext, then you're toast. If the bad guy can't find your key, then your ciphertext will look random to him, and what you should disguise it as depends on the purely psychological question of whether he's more likely to be fooled into not noticing it by a smokescreen of encrypted innocuous messages, higher-order bits of image pixels, or dust bunnies.

OK. To be precise, ignoring compression, the total length of all the aggregate messages must be less than or equal to the total length of the ciphertext and the keys. So, in principle you could hide the message in the key. However, in practice this isn't very likely: Encryption keys for real-world algorithms are typically very short compared to the size of the message. Thus, the amount of information available to be stored in the key is extremely limited.

So, the foolish question is: can you create a system
which is reliably decrypt-once? If you can, then combining
it with the shopping list/terror target strategy works.

You design a system that reliably destroys the origin data
when it is decrypted *and* has two possible outputs.
The (your moral value here) guys beat you into giving up a
key, decrypt the file to get your laundry list, and cannot
recover the original to try again, even if you give them a
second key.

This is fragile, obviously, in the sense that if you accidentally
use the shopping-list key yourself, you have lost the data. And
it increases the chance that the folks involved just keep beating you, trying to get you to deliver reliable data on whether there
are multiples and which is real.

Are we optimizing for protected data or fewer beatings? I
ask only for information....

Compress and encrypt the secret, and pad with padding to the size of the innocuous document.
XOR that with random data 1 to produce a fake key.
XOR the fake key with the innocuous document to produce the (now doubly) encrypted document.

For proper decryption, you need random data 1, the inocuous document, knowledge of padding, the decompressor, and the original key for the original encryption.

You must be able to persuade the enemy that use use large amounts of random data to encrypt your secrets.

It seems to me that an information theory approach is working against the captured person. You can imagine being asked "So, this message you sent has about 1000 bits of somewhat non compressible information, yet the message we decrypt from it with the key you gave us has only about 100 bits of entropy. What's in those other 900 bits?" I think the best protection from this is steganography of some sort. So the main message, which is encrypted with key one, would have some reasonable to send information like a image of the secret Acme Secret Widget. Then hidden inside the image would be a second message that, encrypted with a second key, that said "deliver to W. E. Coyote". The key point is that the you have to be able to argue that first messages was a reasonable message to send and that it used all the bits available or else folks will know there is a second message.

The problem with these systems isn't that the torturers will beat the grocery-list key out of you, realize they've been had, and then will beat the nuclear-weapons-secrets key out of you. The problem is rather that they'll beat the grocery list key out of you, then the drug-receipt key out of you, and then will go right on beating you, convinced that a little more encouragement will get the nuclear-weapons-secrets key. Other than the value of the interrogators' time, what's the downside for them? Some intel guy will be wandering around for the rest of his days, suspecting that if he'd just been a bit more careful not to kill you, he'd have finally gotten the secret out.

--John

In the setting you provide, it doesn't really matter if they get the keys or not. Presumably, since you had the information encrypted with your key, you would know most or all of it anyway (or at least the really useful parts, like the approx time and location of the nuke detonation). Destroying the key, or making it hard to get, just means they will try to extract the information out of you instead of your encrypted files. They might not even make an attempt to get your key. "Huh, his hard drive is encrypted. Let's beat the hell out of him until he tells us what we want to know, then."

As to the hardware tokens, having two PINs (one for access and one to zeroise) might be better than having an explicit erase button which presumably you will not be able to talk them into using.

The two pin solution IS the best available. If the data is stored in such a way that extraction destroys it for either keep, you're done.

And done for. As mentioned above.

I don't think it's a good assumption that a hardware token can't be broken into without zeroizing the information stored therein. You can definitely build ones that will zero the data permanently on command, but....

Leave a comment