Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I read the summary of deniable encryption on wikipedia:
https://en.wikipedia.org/wiki/Deniable_encryption

Then I read a question, by doom123 on security.SE:
https://security.stackexchange.com/questions/34684/truly-deniable-encryption

But I had a subtly different problem which can be stated as follows:

  1. Alice wants to send Bob the book "Mocking Jay" which is banned in Bob's country.
  2. Alice encrypts "Mocking Jay" to data MJ with the password P1.
  3. Using another book of similar size (or by trimming a larger book), say the "The Hobbit", she processes the data MJ and computes password P2.

The solution to this problem will allow Bob to claim that he maintains a copy of "The Hobbit" (assuming that "The Hobbit" is not banned of course), while being able to read "Mocking Jay". The solution, in theory, should also allow Bob to plausibly deny that there's any other copy hidden in the data "MJ" other than "The Hobbit"; or like the aforementioned security.SE question, should allow "MJ" to hold any number of copies (and thus any number of passwords), providing Bob the excuse of acknowledging only one copy that he has the knowledge of.

The answer provided by the user lynks to the question posed by doom123 solves the problem for storing data on a hard-disk. Is there a general solution to this problem?

UPDATE 1 With regards to the answer provided by fgrieu I am slightly modifying the question. Is it possible to add a third layer (and an arbitrary number of further layers) of such encryption? What I mean is, with Mocking Jay, The Hobbit, and Silmarillion (assuming that the books are roughly the same in size) as inputs, is it possible to create an encrypted output say MJTHSI? I am alright with the passwords being the output as well. Decrypting with password P1 will reveal Mocking Jay. If rubber-hose is used password P2 can also be given up revealing The Hobbit (with the intention of ultimately protecting Silmarillion which can be revealed using P3).

share|improve this question

migrated from security.stackexchange.com Jan 20 at 23:04

This question came from our site for Information security professionals.

    
One of your requirements can not be fulfilled: Deniability that there is something else in the data. Under the assumption someone is threatening you with a stick and makes you decrypt your data, he will notice what kind of encryption scheme is used. As soon as he realizes it is deniable encryption, he will probably hit you just for even trying to hide data from him. –  tylo Jan 22 at 17:29
    
@tylo There is no special encryption scheme used in order to get deniability, you would still use AES, Serpent, Twofish, etc. Provided the encryption is random, when looking at the encrypted container containing the Hobbit or whatever, there would be no way to differentiate between two different portions of encrypted data. As it would all look like random data. If it's unencrypted, the outlying container wouldn't know anything about the inner container, and would just look like the full space for that container. –  rfelsburg Jan 23 at 21:18
    
That does not work. Deniable encryption can only be achieved by encryption schemes designed this way. It is not an additional layer on top. For AES, you would have to be able to find a key (1 for every block) to a given ciphertext and the 2nd plaintext you want to encrypt. But AES is designed so that this attack is impossible in practice. –  tylo Jan 24 at 13:22
    
What about the "trivial" solution, which is to use a stream cipher where the full keystream $\left|k\right| = \left|m\right|$ is used, and $c = k \oplus m$? You can then compute an alternate keystream $k'$ for any other text $m'$ of equal length by $k' = c \oplus m'$. –  Stephen Touset Apr 3 at 23:40
    
@StephenTouset That's brilliant... I guess that suits me perfectly. –  Shashank Sawant Apr 4 at 5:33

3 Answers 3

I understand the question as asking for a method such that:

  • after step 3., we'll have a reasonably small password P2;
  • deciphering MJ using P1 will give "Mocking Jay";
  • deciphering MJ using P2 will give "The Hobbit", or a meaningful extract of that, at least comparable in size to MJ;
  • MJ is produced at step 2. without "The Hobbit" as input.

By an entropy argument, that's impossible; for that would imply that the amount of information necessary to go from "Mocking Jay" to "The Hobbit" (or a meaningful extract thereof) can be summed-up in the short password P2.

Update: a possibility is that "The Hobbit" (or a meaningful extract thereof) is embedded in the decoding program, but that brings back the problem stated in the last paragraph of the present answer.


Remove the requirement that MJ is produced without "The Hobbit" as input, and it becomes possible. We can devise an encryption process with input ("Mocking Jay", P1), ("The Hobbit", P2), or more generally any arbitrary collection of literary work and distinct associated passwords, producing a ciphertext; and a matching decryption procedure accepting ciphertext and password, that will produce the appropriate work for the password, and an error (or garbage) for other passwords. The system can be resistant to cryptanalysis and key search, even for relatively short passwords, if we accept that the decryption procedure requires a few seconds, which enables password stretching using e.g. scrypt.

Thanks to data compression, the ciphertext can be smaller than "The Hobbit" (I assume "Mocking Jay" is smaller). We can even think of reusing the compression dictionary built from "The Hobbit" to compress "Mocking Jay", so that the ciphertext is of size more comparable to a mediocre compression of "The Hobbit", if we accept that P2 is necessary in addition to P1 to read "Mocking Jay", or equivalently that P1 is some extension of P2, or that the cipher protecting "The Hobbit" is of mediocre security.

Update: I have no implementation in mind, but this is a relatively simple matter with competent use of data compression, key stretching, and symmetric cryptography.

Huge problem is: an intelligent person caring to analyses the decryption procedure or the file format specification will likely understand that it is intended for deniable encryption, and then the risk is high that rubber-hose cryptanalysis will be used; something that would be avoided if the original problem could be solved; but it can't.

share|improve this answer
    
My apologies. Yest the "The Hobbit" has to be used as one of the inputs. –  Shashank Sawant Jan 21 at 21:02
    
@Shashank Sawant: the question is interesting as is; if the production of the ciphertext MJ could be without the "The Hobbit" as input (it can't, except if "The Hobbit" is hard-coded in the deciphering code), the system would allow deniability; if both "The Hobbit" and "Mocking Jay" are input in the production of the ciphertext MJ, the system is feasible, but then there's the problem stated in my last paragraph. –  fgrieu Jan 21 at 21:36

Alice must send enough data for both Mocking Jay and The Hobbit. But there may be a plausible reason for all that data.

  1. Alice encrypts Mocking Jay using a method that produces ciphertext indistinguishable from random.
  2. Alice appends random data to that ciphertext to bring it to the length of The Hobbit (presumed at least as long as Mocking Jay).
  3. Alice sends Bob the augmented ciphertext XORed with (the plaintext of) The Hobbit.
  4. Separately, Alice sends the augmented ciphertext of Mocking Jay.
  5. Bob keeps both files, and can read The Hobbit by XORing them together.
  6. Bob can read Mocking Jay by decrypting the Mocking Jay ciphertext.

Bob's cover story is that Alice sent him a bootleg copy of The Hobbit, using a one-time pad to ensure security.

share|improve this answer

fgrieu addressed the entropy argument (hard to fit The Hobbit without expanding the input/output too much).

I would like to point out following details:

  • Extra data added in in compression etc. may still appear to to somebody analyzing the output (steganography)
  • Asymmetric cryptography contains many bits that are random by the specification, for instance, some hybrid scheme based on RSA-KEM-KWS (with RSA-2048) would contain 256 random bytes.

My advice would be to make a good use of the random bytes. It is easy to hid reference, such as "The Hobbit, page 4" or "Let's meet at my apartment 11PM today, door code is 8068.". Of course, you need to use suitable encryption, but no adversary without the key is supposedly able to distinguish short encrypted ciphertext and truly random bytes.

Worse than best or usual compression, unuseful extra bytes (other than usual padding), etc. will raise suspicion.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.