Plausibly Deniable Encryption or How to Reveal A Key Without Revealing It

When the secret police arrested Andrea at the airport checkpoint, she thought it was a mere formality reserved for all foreign citizens. When they searched her luggage and found the USB disk with all the names and addresses of the political dissidents she was helping to flee the country, she was relieved: the disk was encrypted with a 256-bit AES key, and even a supercomputer would not crack it in a billion years. When she was strapped naked to a grill and received the first shock of 1000 volts, her nerves and muscles convulsed in panic. How long could she hold out before revealing the secret key? If she spoke, how many more people would be tortured and killed? Is there any point in cryptography if you can be made to reveal the key?

Indeed, even the best encryption algorithm in the world will not resist rubber-hose cryptanalysis: so why bother mathematically attacking an encryption algorithm, when through extortion, bribery or torture the keys of the people who use or manage it can be extracted?

It would be wonderful to be able to encrypt the information so that, if you reveal the encryption key under duress, the original sensitive information is not decrypted with it, but rather a decoy. Fortunately, this amazing form of cryptography exist; it is called plausibly deniable encryption.

Plausibly Deniable Encryption to Decrypt One Message or Another Depending on The Scenario

For instance, an encryption algorithm (E) receives as inputs a sensitive message to be protected (the clear text, m) and a short random string of bits (the key, k) and produces as an output a random-looking set of bits (the encrypted text, c) of approximately the same length as the message:

c = E_k( m )

The same message m encrypted with the same key k produces the same encrypted text c. For the sake of simplicity, in this article we will leave aside the randomly filled-in encryption that precisely avoids this determinism. Likewise, the same encrypted text c decrypted with the same k key produces the same clear text m using the corresponding decryption algorithm (D):

m = D_k( E_k( m ) )

It is in this sense that it is affirmed that encryption compromises: once you have encrypted a text m with a key k and shared the c encrypted text, the three values are indissolubly linked. If under duress you reveal k, from c you will obtain the original text m, perfectly legible by everyone. If instead of revealing the true key k, you invent any k value , then the result of decrypting c with it will be a random text and, therefore, illegible, so everyone will know that you did not confess the real key: k. Therefore, they will be able to keep coercing you until you reveal the real k.

Furthermore, the mere fact of storing or transmitting encrypted messages is in itself incriminating, depending on the scenario. To a repressive government, a bloodthirsty criminal or a jealous partner, possessing or sending encrypted information will make them suspect that there is something they want to hide. Encryption protects the confidentiality of the message but does not hide its existence. How do you get out of the way if an adversary intercepts your encrypted information and demands that you decrypt it? You neither want to reveal the encrypted information, nor can you decrypt it with a wrong key that returns unreadable text.

The aim of plausibly deniable encryption is that the same c encrypted text can be decrypted with two different keys, k₁ and k₂, resulting in two different clear texts, m₁ and m₂, both perfectly readable, but with a fascinating twist: m₁ is the sensitive text whose confidentiality you really want to protect, while m₂ is a readable and plausible text, which acts as a decoy, and which you can happily display to the satisfaction of your adversary. Both created from the same c!

How To Achieve Rudimentary Deniable Encryption Using XOR Encryption

If you think that plausibly deniable encryption is a matter of magic, you will see how a rudimentary version can be achieved through a simple example based on the one-time use notebook. Simply by using XOR operation, also known as sum module 2, which we will represent by (+). In this algorithm, it is encrypted and decrypted as follows:

Encryption à c = m (+) k

Decryption à m = c (+) k = m (+) k (+) k = m

since the XOR of a value with itself is equal to 0.

We start with two messages, the sensitive m₁ and the decoy m₂, and a secret key, k₁, as long as the longest message. The encrypted text c is calculated as:

c = m₁ (+) k₁

k₂ key is calculated as

k₂ = c (+) m₂

If c is decrypted with k₁, m₁ is obtained:

c (+) k₁ = m₁ (+) k₁ (+) k₁ = m₁

While if c is decrypted with k₂, m₂ is obtained:

c (+) k₂ = c (+) c (+) m₂ = m₂

Deniable encryption works! The adversary has no way of knowing whether m₂ was the authentic message or a fake one. Hopefully, he will be satisfied and leave the victim alone. Obviously, you can calculate as many keys and alternative messages from c as you like.

Another scenario of using deniable encryption that has nothing to do with protection against duress is to send different instructions to different recipients, but all of them contained in the same encrypted text! All recipients openly receive the same cipher text c. However, each recipient is given a different k_i key that will decode a different m_i message from the same c. Recipient 1 will get the m₁ message if he/she decrypts c with the k₁key, recipient 2 will get the m₂ message if he/she decrypts c with the k₂ key and so on. None will be able to read the other’s message. Moreover, they will not even suspect its existence.

Of course, this version would be impractical, as it requires keys as long as the messages themselves. So the cryptographers had to develop more efficient algorithms.

The Gradual Improvement of Deniable Encryption Over the Years

The first operational deniable encryption algorithm was proposed in 1997 by R. Canetti, C. Dwork, M. Naor and R. Ostrovsky, based on the following ingenious idea: imagine that the sender (Alice) and the receiver (Bob) have agreed on a certain method that allows Alice to choose in a domain an element either totally randomly or in a pseudo-random way, so that Bob can distinguish the random from the pseudo-random choice. When Alice wants to transmit a 1, she sends a pseudo-random chain; while to transmit a 0, she sends a truly random chain. Since the adversary cannot distinguish the pseudo-random element from the random one, Alice can pretend to have sent any kind of message.

Over the years, numerous deniable encryption schemes have been proposed, both for public and secret keys. These last ones can be used to encrypt large volumes of data, such as entire hard disks. A good example of these deniable encryption systems applied to disks is the multi-platform tool Truecrypt, with its volumes hidden within encrypted volumes. It is based on the pioneering work developed in 1997 by the cryptopunks Julian Assange (yes, the one from Wikileaks) and Ralf Weinmann, precisely named Rubberhose File System, in reference to the above-mentioned cryptanalysis method. Tools for deniable encryption of Android smartphone content have also been launched, such as Mobiflage or MobiCeal. The BestCrypt app provides the widest coverage, as it works on Windows, MacOS, Linux and Android.

Be Careful with Deniable Encryption, Which Can Give You Away

However, deniable encryption is not exempt from very serious risks. If your adversary is sufficiently well versed in cryptography, the mere suspicion that you are using a deniable encryption system will motivate him to continue extracting keys from you. Suppose you have used Truecrypt to encrypt the information on your disk, data that you cannot hide from a basic digital forensic investigation. Will your adversary be satisfied with the first key you reveal to him? Possibly he will continue to coerce you, with rubber-hose or other means, to reveal a second key. And a third. And a fourth… How will your adversary know that he has extracted your last key and you are not hiding another one? Deniable encryption can turn against you in a rubber-hose cryptanalysis scenario because it could incite to never stop.

In short, plausibly deniable encryption is yet another tool that cryptography places at the service of civil liberties and rights. However, in circumstances of real danger of duress, it must be used with caution.