# Implement deniable encryption with AES/RSA

I'm on a crypto app using OpenSSL (I'm more an implementer/cryptographer than a cryptologist), mainly as a hobby, for now.

My app will be able to encrypt a file (not a container) with symmetric or asymmetric or both encryption (sym then asym), and I want to implement "deniable encryption" (I'm in France, you should have heard about the law which has just been voted: our NSA now has all rights on internet).

My first issue is RSA: for example, when decrypting with a wrong key, it fails to leave a correct padding. So, a file won't be decrypted to a random looking badly deciphered text. I hope a symmetric algorithm will allow me to do that, but first I'm using RSA. Do any of you have an idea on how to "force" RSA to decrypt a file to a valid message (but not the cleartext), allowing a user to claim it was the right key? I assume that the protocol will be known.

If possible I would also be interested in suggestions of other methods with this "behaviour", or implementations of this.

EDIT: Precision: The cryptosystem*will be able to encrypt a cleartext with public-key (which implies symmetric encryption) OR symmetric encryption OR (minor probability) both one after the other (for i.e.: Let's say you have an already symmetric ciphered file you need to relay, you can apply a public-key encryption, which will make the file encrypted twice with probably 2 different algorithms and 2 different keys).

PS: Redirected to chat, too many comments.

• Let's use the chatroom instead ;) – Max13 Dec 14 '13 at 1:37

We need clear goals. The question asks for "plausible deniability" or "deniable encryption", and these terms needs a precise definition in a public-key context (implied by RSA). I assume that in addition to the IND-CPA and IND-CCA1 properties of a cipher, including hybrid (as implied by AES), it is desired that:

1. One without the private key can't distinguish ciphertext from random data of the same length (with the exception of data too small to be correct ciphertext considering the key size).

2. One trying to decipher ciphertext with the wrong private key get random-like output and no error message (with the exception of ciphertext too small to be correct ciphertext considering the key size).

3. Even one with the private key can not distinguish from random the ciphertext obtained by encryption with the corresponding public key of unknown random data.

I think these goals are orthogonal. (1) is most natural; (2) helps leaving interceptors clueless; (3) is useful in a context of layered encryption. The whole gives some useful level of deniability in societies where possessing random files and encryption programs designed for deniability is not objectionable.

I propose a simple scheme that I claim meet the above goals. It is close to the simplest possible form of hybrid RSA/AES encryption: use a random key to AES-encipher the bulk of the data, and use RSA to encipher that key. The only difficulty is making sure we do not leave a bias here or there. In particular, usual RSA primitives have their ciphertext with some bits biased, sometime constant, failing (1); and with the right private key, they often reveal more structure, failing (3).

The key setup is that of RSA. Users have private keys $(N,d)$, and all the corresponding public keys $(N,e)$ are made public. $n$ is the bit size of $N$, so that $2^{n-1}\le N<2^n$. I restrict to plaintext, ciphertext, and more generally data or files that are a contiguous collection of octets. Ciphertext always is exactly $\lceil(n-1)/8\rceil$ octets longer than the plaintext. Big-endian binary is used in all conversions between octets and integer.

Symmetric encryption is done using AES-128 for $128<n\le2049$, AES-192 for $2049<n\le4097$, AES-256 for $n>4097$.

The encryption procedure accepts a public key $(N,e)$ and plaintext:

• repeat the following steps..
• generate $M$ uniformly random in $\{0\dots N-1\}$;
• compute $C=M^e\mod N$, which is textbook RSA encryption;
• ..until $C<2^{n-1}$ [notes: here $C$ is uniformly random in $\{0\dots2^{n-1}\}$; in the context, the end condition means that $C$ fits in $n-1$ bits; it will take on average less than two iterations to get there];
• generate $a$ uniformly random in $\{0\dots2^{7-((n-2)\bmod8)}-1\}$ [note: in other words, generate $a$ of 7-((n-2)%8) random bits];
• let $A=a\cdot 2^{n-1}+C$ [note: that concatenates $a$ and $C$ for a total of $8\cdot\lceil(n-1)/8\rceil$ bits, when considering $a$ and $C$ as bitstrings of fixed sizes $7-((n-2)\bmod8)$ and $n-1$ bits];
• output $A$ as $\lceil(n-1)/8\rceil$ octets;
• let the low-order bits of $M$ be the AES key of the size determined by $n$;
• encipher the plaintext (if any) in AES-CTR mode with implicit zero IV, and output it.

The decryption procedure accepts a private key $(N,d)$ (possibly in another form) and data that is a putative ciphertext:

• read the first $\lceil(n-1)/8\rceil$ octets of data, forming an integer $A$ of (at most) $8\cdot\lceil(n-1)/8\rceil$ bits; if there is not enough data, terminate with error or hang;
• compute $C=A\bmod(2^{n-1})$ [note: that forms $C$ by ignoring the high-order $7-((n-2)\bmod8)$ bits of $A$, considered as a bitsring of $8\cdot\lceil(n-1)/8\rceil$ bits];
• compute $M=C^d\mod N$, which is textbook RSA decryption;
• let the low-order bits of $M$ be the AES key of the size determined by $n$;
• decipher the rest of the data (if any) using AES-CTR mode with implicit zero IV, and output it.

I do not support encryption to multiple users (a common feature of hybrid encryption), or checking that the plaintext or ciphertext is unaltered, which are antagonist with the combination of the goals.

I make no attempt to hide the length of the original data (adding some level of this is simple: for example, before encryption, append 0 to 255 random octets, and a final octet coding the random number of random octets added, which will allow removing the appropriate number of octets on decryption; goals need minor refinements).

UPDATE: I have made IND-CPA and IND-CCA1 explicit goals. IND-CCA2 is not met. Worst problem is that the cipher is extremely malleable, including to one not knowing which public key was used, and that's a weakness: an adversary guessing the plaintext (e.g. from context and ciphertext length) can replace it with another ciphertext that will decipher to any plaintext of her choice that is not longer than the original, without knowing which key is used (with knowledge of the public key, anything can be enciphered, of course). Another weakness is that the size overhead depends on the key size, and is higher than strictly necessary. It seems all this can be fixed, but with two passes for decryption and added complexity.

• Great answer thanks. Before accepting it, I need to test it, and I have to admit that I have some difficults to understand your maths (I haven't made any studies in cryptography). From top to bottom, the first thing I don't understand is "Repeat (less than twice)" which means "once" isn't it? "Until" which means "many times until condition" but your computation seems to have the same result over and over (like 1+1=2). Sorry if I misunderstand because of my lack of maths/crypto knowledge. – Max13 Dec 14 '13 at 13:09
• Sorry, I understand do...while, what I didn't understand is "less than twice" which means "once", why doing a loop? – Max13 Dec 14 '13 at 13:38
• @Max13: I have added notes and things should be clearer now. You'll need that $\lceil u/v\rceil$ is $u/v$ rounded up to next integer, that is (u+v-1)/v. Doing a loop is the simplest method to obtain $C$ with all its bits unbiased. – fgrieu Dec 14 '13 at 13:51
• It's clearer, thanks. BTW, is it limited to CTR mode? I will have a LOOOOT of fun implementing your maths with C/C++ (Actually I'm a system dev, not a cryptologist, but there is a beginning in everything ;) . Thanks for that answer anyway. – Max13 Dec 14 '13 at 14:07
• @Max13: The system would work in any mode that allows ciphertext of arbitrary size (thus including CFB or OFB, but excluding CBC or PCBC, except with the combination of ciphertext stealing and more than 16 bytes of plaintext). I used CTR because it is the fastest standard mode on modern CPUs (it allows use of any number of threads concurrently). CTR's only problem is its utter malleability. – fgrieu Dec 14 '13 at 18:20

Have you considered using a one-time pad scheme if you really want plausible deniability? Each bit of the plaintext is XORed with a bit from the secret random pad.

Even without the correct random pad or key, the ciphertext can be decrypted to all possible messages of the given length.

• If I XOR the plaintext BEFORE ciphering it, it needs 2 keys to decipher (public key/password + OTP), isn't it? It seems to be an extra layer for @fgrieu's algorithm (or any other), not another solution, am I right ? – Max13 Dec 15 '13 at 11:08
• Technically, the OTP is not a cipher. It does not allows communication (or secure storage) of arbitrarily large amount of data after an initial exchange. RSA+AES support encryption without any secret material, which is useful in the context of deniable encryption; OTP can not. – fgrieu Dec 16 '13 at 6:18