Encrypting a document with multiple keys, and making people accountable for those keys

Question

Hypothetical here. You have a highly sensitive file that you don't want to become public ever, other people also don't want it to be public. To reduce likelihood of being murdered you publish an encrypted version of the file on bittorrent and give the encryption keys to trusted parties ("key holders") with instructions to publish if you are killed. Then you make it publicly known that your published files are authentic. (Yes, we're talking about the Manning situation.)

You want to avoid the possibility that one key holder is compromised and does the following set of three things:

1. Publish the plaintext document
2. Use the authentication statement you have published to make the public know the plaintext is authentic (i.e. remove your plausible deniability)
3. Remain anonymous

For example, here is one way to do this.

1. Create N symmetric keys, one for each key holder
2. For each key holder, make a copy of the plaintext and prepend it with "This document was released by: " and that key holder's identity
3. Encrypt each copy with the respective symmetric key
4. Distribute keys respectively
5. Publish the full file

However, this requires N * size_of_plaintext space. This question is asking is there a more efficient way.

As a start, I have researched gpg multiple-key encryption. See https://stackoverflow.com/questions/597188/encryption-with-multiple-different-keys (thanks @terdon). GPG works as follows:

gpg --encrypt --recipient alice@example.com --recipient bob@example.com doc.txt

1. GPG picks a symmetric key (X)
2. GPG encrypts plaintext with X
3. GPG encrypts X with party keys P_alice, P_bob, ... and Alice, Bob, etc. can each decrypt one of them

This is vulnerable to the attack we want to avoid:

1. Bob uses P_bob to decrypt X
2. Bob publishes X anonymously
3. The public decrypts your published plaintext with X

Answer 1

You can publish a suitable set of cryptographic hashes of the plaintext up front. For example, by publishing the set of [MD5, SHA-1-160, SHA-3-512, RIPEMD-320] hashes of the plaintext, for anyone to find a plaintext which correctly matches all those hashes simultaneously would be exceedingly difficult. Note that such an attack would be significantly harder than a first or second preimage attack against any one of the hash algorithms involved because the same data has to hash to the correct value for all algorithms involved and make sense when read. Also, of these, according to Wikipedia at least SHA-3-512 and RIPEMD-320 are currently not known to have any attacks better than brute force against the full output space, and while MD5 has a collision attack of complexity 2^21, preimage attacks are still 2^123 which is only marginally less complex than an all-out attack on its full output space 2^128. (Basically, a collision attack is where you get to choose both inputs and are looking for a pair of different inputs which produces identical hashes such that the hash for one is also valid for the other; a preimage attack is where you have the hash and are looking for some input, preferably one that is different from the original input, which produces the given hash.) These hash values, in and of themselves, would say nothing about the plaintext data.

To further complicate an attack, you could make use of at least one cryptographic hash algorithm that is not based on the Merkle-Damgård construction with a traditional compression function (which the above listed hash algorithms, possibly with the exception of SHA-3, are), if such a beast exists; I don't know of any off the top of my head, but that does not preclude the possibility. Apparently, Keccak/SHA-3 uses a design that is at least different in some parts, which would seem to make it a good candidate for inclusion in such a set of hash algorithms.

This gives someone who at some later point in time receives a copy of the plaintext file a way to verify that it matches what you intended to be made public in the event something happened to you. In order for that person then to have a very high degree of certainty that the plaintext is authentic, that person would need only to trust the source of those hashes to be authentic (and that their own copy of the hash values has not been tampered with, which can be done in a decidedly low-tech fashion with tamper-evident seals) and that the software used to calculate the hashes on their computer does what it is supposed to (which to some degree can be independently verified by using multiple separate implementations and testing those implementations against published test vectors).

However, I don't think you can get real accountability on the part of who leaked the decryption key without distributing multiple, differently encrypted copies of the plaintext. Any multiple-key encryption scheme that does not require a separate encrypted data block for each plaintext block and recipient key would require that the plaintext is encrypted using a given key K_0 which then in turn is encrypted with each of the set of recipient keys K_1 through K_n, for n recipients, and that the complete set of encrypted master keys E(using K_n)(K_0) is included with the ciphertext. (Any time you don't want that, you need multiple ciphertexts for each plaintext, which presents an increased attack surface for an attacker which is a concern if your name is Manning or Snowden.) Hence, each recipient by necessity has access to the "master" decryption key K_0, presenting exactly the scenario you are looking to protect against.

About the only way I can think of would be to use an algorithm like DES (read on before you downvote this answer because I mention that old dinosaur) which allows for unused parity bits in the key material, set those bits unique for each recipient, and keep notes on what the parity bits were for each key recipient. (Since you would be setting these "parity" bits independent of the remaining key material rather than as actual parity and these bits have no impact on security anyway, there is no degredation of security from this.) For reasonable security a scheme like EDE 3DES could be used. However, anyone who has access to the ciphertext and knowledge of the algorithm and has some knowledge of cryptography either knows or is able to easily find out about this property of the encryption algorithm, and could set the unused/parity bits to any values they please before publishing the decryption key, negating any possible accountability measures and possibly pointing the finger at someone else.

Note that none of this presumes the use of symmetric (or for that matter asymmetric) encryption. It can be done fully with either, although a symmetric-algorithm-only approach is probably a lot more practical than an asymmetric-algorithm-only approach. It's easier (in the sense of solving the key distribution problem) and more practical (in terms e.g. of ciphertext size) to use symmetric encryption for the data and then asymmetric encryption of the decryption keys -- that is the way assymetric encryption is normally done -- but there's nothing saying you absolutely have to do it that way, and you still need to be able to trust somehow the public key that you are encrypting the decryption key to.

Answer 2

If Alice does make such a claim, you would like a way for others to verify that claim. I've always been under the impression that public-key encryption does not give much in the way of authentication, but if you somehow introduce something like a digital signature you could then verify the authenticity of the document, which would address the accountability issue.

Something like what's described here I suppose since you are using gpg: http://www.tutonics.com/2012/11/gpg-encryption-guide-part-3-digital.html

When a sender uses a public key to encrypt data for a recipient, how is the recipient supposed to know if the sender is actually who they say they are?

The public key is available for anybody to use, so there needs to be a means for that sender to unequivocally prove that the data came from them. GPG provides a way to do the above in combination with generating a signature (like a fingerprint) of the data which proves the data has not been tampered with.

Answer 3

Rather than publishing the encrypted file itself, publish a copy of your public key. Then provide each of your trusted keyholders with a plaintext copy of the document, along with a cryptographically signed (with the corresponding private key for the public key you just published) statement from yourself which both corroborates the document's legitimacy (e.g. includes a hash of the document), and mentions the name of the keyholder you are giving this statement to.

This way, any of your keyholders can leak the plaintext document; but in order to prove its legitimacy they must reveal their version of the signed statement from you, which in turn reveals their identity.

For even further protection, you could encrypt the plaintext document given to each keyholder with a key split among the keyholders using Shamir's Secret Sharing algorithm. That way, no individual keyholder can read or reveal contents of the sensitive file without collaborating with one or more of the other keyholders. With this scheme you could require any number of collaborating keyholders in order to release the document to the public, but only one of the keyholders would have to reveal their identity in order to verify the document's legitimacy.