# A specific way for deniable encryption

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).

• 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 '14 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 '14 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 '14 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 '14 at 23:40
• @StephenTouset That's brilliant... I guess that suits me perfectly. – Shashank Sawant Apr 4 '14 at 5:33

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.

• My apologies. Yest the "The Hobbit" has to be used as one of the inputs. – Shashank Sawant Jan 21 '14 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 '14 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.

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.

In your use case, you can never actually achieve deniability, unless Bob is a competent programmer. To read the book, Bob must decrypt it somehow, but using what? If he uses a program, then the mere existence of the program will announce clearly to any attacker that deniable encryption is in use, thus making it impossible for Bob to deny hiding something. The only way out is for Bob to manually write and execute the program each time he wants to read the book, and erase all traces of the program after that. Note that Bob must have programming competency, otherwise the presence of a compiler or interpreter on his computer would again signal something hidden.

That said, if Bob really is a competent programmer, it can be quite easy to hide data in normal files, especially those that ordinarily have lots of noise, such as images or audio/video files. For example, the lower two bits of each color component of a BMP image of natural scenery are largely random, and we can quite safely use them to store data that has been encrypted using any strong encryption such that the ciphertext appears to be a random string. This allows us to hide data in about a quarter of the space occupied by each image. A typical BMP wallpaper would be about 8MB in size, so you can easily hide 2MB in it (more than enough for a typical book in text format).