Deniable Encryption
I ran into an interesting Reddit comment about deniable encryption and decided to spend an evening playing with it. The concept is that we have a way to encrypt a message in such a way that we can provide a key that would reveal a different message.
The idea is that if you are forced to reveal your key, you can do so, without spilling your secret. From a technical perspective, this is a truly fascinating scenario. Of course, it comes with the problem that if you’ve provided a key that doesn’t show anything the adversary is happy with, they’ll assume that there is another key.
Note: As usual when talking about cryptography, I’m at best an amateur in this area. This is strictly me having fun, don’t try to keep your Bitcoin keys here (instead, send them to me by snail mail).
In theory, there is a simple way to do so. Behold my prediction for the winner of the 2024 US election. I don’t want to reveal to you ahead of time, but here is the encrypted value:
4a/8AqOcEFzlMRP9VsLgEtXIq8+Cc11bKKp6+iR3c975qOrNtA==
After the election, I’ll share the key that will show that I properly predicted this (you should send me bitcoins at that point). Let’s commit further and show you how you can verify this, it’s really simple:
string Decrypt(string encrypted, string key) { var t = Convert.FromBase64String(encrypted); var k = Convert.FromBase64String(key); return Encoding.UTF8.GetString( t.Select((b, i) => (byte)(b ^ k[i])).ToArray() ); }
In the interest of time (and those bitcoins), I’ll let you know that the answer is either:
tsaSbMbuMDODESHNZPbAR4bozqPnECkyR8Rak1dNU4qL3Ye9mg== tsaSbMbuMDODESHNZPbAR4bozqPnECkyR8Rak1dNU5yQzI+jmg==
Voila, we are done, right? Not only did I demonstrate my ability to properly predict the future, but I was also able to show how you can use two separate keys to decrypt the same data.
This is just a property of the way I “encrypted” the data. What happened is that I took some random bytes, and when I needed to produce an answer, I XORed those bytes with the message I wanted to get and then I sent you the XORed value. When you XOR it again with the “message” you previously got, we get the output I want. In essence, that “message” you got is a one-time pad, and I can use that to send you any message I want.
This also has all the usual limitations of one-time pads, you can only send data up to the size of the key, it doesn’t protect you from the text being corrupted, and it is malleable. In other words, you have no way to ensure (cryptographically) that the message you received was actually sent by me.
Modern cryptography relies on something called AEAD (Authenticated Encryption with Associated Data), which ensures that you can send as much encrypted data as you want and ensures that no one can alter the data I receive if the decryption process is successful.
What I aim to do is create a proper way to encrypt a message and be able to retrieve it later, but also provide another key if needed. Here is the API that I have in my mind:
var output = DeniableEncryption.Encrypt( ("P@ssw0rd", "Joey doesn't share food!"), ("swordfish", "Meet at dawn by the beach to toast the new year"), ("adm1n!str@t0r", "We were on a break!"), ("Qwerty!Asdf@2024", "Bitcoin seed: lonely ghost need apology spend shy festival funds" ) );
As you can see, we are actually encrypting multiple messages here, each with its own password. The output of this code will be something like this:
OwlVWixT3NMen2vuklHsY34SEIfu+zuDKJx5UMQKEjP4GnDnSDsagUiMWxcl83kC4GRI1s64JEU7 x7vf4u15FZOw3DDzwCG71Mqatfjc7nTzAox7Cr9FtVnxqsqkIyeOVsq6yHbiP56HAlUkbu7/D3kp RrRmNtdqo5S6Dl7Y50fH492W/+/wtEhNePfWP7YhO1KsvUcnX2S4B7VKnTZbhJDhvxgTUlMK4/Cl UdQiP3H0R1CZ8ucB1mb1yP/gkwIPYA7ComAzKtM9VOviCzqP5wqzdq7KcWM2FdJH3Lqpuoi376Lr 3Dnh4FUDe8jJhU2xlNhj7O9tXPczIeeUu7GuG0FHegeHprqRc7AkKK5b5kiEN7VnQz58fk29WBAQ 2LTYrBwbDn47Sw4PybMFcl9Wy4Yuw9ElHQoZcvXGk9hAXsqWdRyRgOq8HREiuZpzvSyx5v56T2+u 3hGVeXStKfYF6T5R9w8wqPKQ8UB3/blKguQZjtJNlueXDSpJ5Jzl/7FKUCSJfK16l9NgiVpcGGLg qke4cZ1aVdpL6rsCH8uLLjEO0MVliuLjjX2VP76UrJBpTdh2uuyjaNDa6tFxQ/zx0jz5VlVbNZv+ w4KOl9jkQYk1U9VZ4K1v8IP6swZ1AOmfkWDuXmeNHlBeFk7Au0+ZDgpAJptwZrSDP2rgRgnrTlDL qN9YqSlV4Q2TBmcVmQy9+sW1aI7yHhUdzfx3wZ551BmJX0IBLJviMKm+1DglKlHfs/+BZ1fz1HR2 ygnSSq2FXMf8y8vDZRjxb54Q/4JzgvYMpq47/ukmzPgc6JcYfkLtDCNXeJ+0bUDjn5r+2I8d3DLF FbkGa6oB+um1ipAAeO5paH6aqzERtK3qEDw+nmnHW+y7BQUrQ7VRq2rmmPI2Hq8aMGcyCu5MpI97 /TXgcZDsUxFgRvA4ZQWz0UJ1ZNZOHgCRWgsAOkp1Y6zUKYwcJlhiICfUlfuj+6I2YayldANn/GR/ jn8/U4W2UXN3cAkl9AtgkxooGVQThPnAVTqo4l+EiL9X7WLo3EyaTJSNzxSSgudMQZJJJc+nYK66 A592plmhCzsvWedUeBzacE/pifyWM9DGDHqa5K75VLGV1AenIIBsUkYc44UPDLazpLSUBfTXB7LZ Tig4sHmmLvfiXrD/lH1jFKEsAdTHiYWLooxTBD0Q2COpEM6kyKkljwfko8FVpO6HRNwiyqwQCsDM xSMOO2Vk5qQVAb7VOEXN0fQjxEjSeB890XODduP6d941dqk+L1iAQK50GHk8WWCkZFn6FricVCFs 5T6fEWRj6wJlD4EISmoNVmanqAmF79Spg4YCOr3N2EbSdokf5d4ZNA7GtDFX9esbHTIPS0SiXyUx MHgS99CllTACSEpmEisu/JiEsWKHOg0oy6oCZbi9hrMbeMGGQ9jM4sIxQ20/u7dV1maut67CPN0H F5VYkRQ0/PNqhvT4Tb3CuGLndxD/nsvs9MgOOZljVZWLaF//Gdno2CNNPjnnHTuURScpcIFKMN5c 80NDgQX6kO8Hoiho7NFc61QwDCNYk1xk2qVDo9jcOaJ2zdtFWJfVavhLCNnEfWoHxzBmS4oL6Ss=
And I’m able to turn that back into the encrypted message using this code:
var msg in DeniableEncryption.Decrpyt(pwd, encrypted); Console.WriteLine(msg);
If I don’t have the password, on the other hand, it should be completely unfeasible for me to figure out what the message is. In fact, let’s try to list the requirements from such a scheme:
- With a password, I can easily decrypt the message.
- Knowing one password isn’t useful for decrypting a message using any other password.
- I cannot tell how many messages are hiding in the encrypted text.
- I cannot detect anything about the messages themselves.
I’m an amateur at best in cryptography, so I’m not going to try to construct something myself. Let’s see if I can cobble together something that would at least hold up for a bit.
I’m using real passwords, and I need to turn them into encryption keys. I’m going to be using PBKDF2 to do that, and for the encryption itself, I’ll use the AES-GCM algorithm. Here is the rough format of the output.
We start with a salt (32 bytes generated using CSRNG) which is used to feed into the PBKDF2 algorithm, then a set of offsets into the file, and the actual data itself. Note that we are always “storing” exactly 8 messages.
In practice, I’m going to allow up to 6 user-defined messages, to ensure that we always have “empty” slots. The size of the data is also meaningful, so we need to ensure that we aren’t leaking that.
What I’m doing is ensuring that we round up (by 64 bytes) the size of all the messages that we want to encrypt and ensure that each data block is of the same size. To avoid leaking even what is the exact size at 64-byte intervals, I’m writing some additional random bytes at the end.
Let’s look a bit deeper into the format of the data block itself. We start by writing the actual size of the block, then the nonce and authentication tag (important for the AES-GCM usage), and then the encrypted message. The rest is filled with random data.
You’ll note that the offsets in the overall output format and the size in the data format implies that we are leaking information about the messages we encrypted. Given that I need to know where to look for the value in the value, and I need to know the size, why am I spending so much time trying to obfuscate that?
The idea is that I actually have two levels of encryption here. When I derive the key with PBKDF2, I’m asking it to use SHA512 and give me 40 bytes of derived key material. I’m actually only using 32 bytes of those as the actual encryption key, leaving me with 8 bytes (two pairs of 4 bytes) that I can use to XOR with the offset and the length. That hides the actual offset and size (basically using some of the PBKFD2 output as a stream cipher).
It has all the usual problems of raw stream cipher, but I don’t care about malleability or authentication in this scenario. I rely on AES-GCM to handle that part of the process and just need to hide the information from other prying eyes. A man-in-the-middle attack targeting those values is going to be able to cause me to try (and fail) to decrypt a value, so I don’t think that this matters.
With all of that said, let’s look at the actual code for the encryption portion:
public static byte[] Encrypt(params (string Password, string Value)[] items) { if (items.Length > MaxUserItems) throw new ArgumentException("You are allowed up to 6 items"); if (items.GroupBy(x => x.Password).Any(x => x.Count() != 1)) throw new ArgumentException("No reusing passwords"); var totalSize = items.Max( x => Encoding.UTF8.GetByteCount(x.Value) + sizeof(int) + AesGcm.NonceByteSizes.MaxSize + AesGcm.TagByteSizes.MaxSize ); var sizeAlignedUp = (totalSize + BlockSize - 1) & -BlockSize; var additionalSizeMixed = RandomNumberGenerator.GetInt32(1, 4) * RandomNumberGenerator.GetInt32(BlockSize / 2, BlockSize); var outputBuffer = RandomNumberGenerator.GetBytes( ItemsCount * sizeAlignedUp + OffsetsBlockSize + SaltSize + additionalSizeMixed ); Span<byte> output = outputBuffer; var salt = output.Slice(0, SaltSize); var offsetsBlock = MemoryMarshal.Cast<byte, int>( output.Slice(SaltSize, OffsetsBlockSize) ); int index = RandomNumberGenerator.GetInt32(ItemsCount); foreach (var (pwd, val) in items) { ReadOnlySpan<byte> derived = Rfc2898DeriveBytes.Pbkdf2(pwd, salt, Iterations, HashAlgorithmName.SHA512, sizeof(int) + DerivedKeySize + sizeof(int) ); var plaintext = Encoding.UTF8.GetBytes(val); var requiredSize = sizeof(int) + AesGcm.NonceByteSizes.MaxSize + AesGcm.TagByteSizes.MaxSize + plaintext.Length; var offset = sizeAlignedUp * index + SaltSize + OffsetsBlockSize + RandomNumberGenerator.GetInt32(sizeAlignedUp - requiredSize); var sizeMask = MemoryMarshal.Read<int>(derived.Slice(0, sizeof(int))); offsetsBlock[index] = offset ^ sizeMask; index = (index + 1) % ItemsCount; Span<byte> mem = output.Slice(offset, requiredSize); var lenMask = MemoryMarshal.Read<int>( derived.Slice(sizeof(int), sizeof(int)) ); var mask = lenMask ^ plaintext.Length; MemoryMarshal.Write(mem, mask); var derivedKey = derived.Slice( sizeof(int) + sizeof(int), DerivedKeySize ); using var cipher = new AesGcm(derivedKey, AesGcm.TagByteSizes.MaxSize); cipher.Encrypt( nonce: mem.Slice(sizeof(int), AesGcm.NonceByteSizes.MaxSize), plaintext: plaintext, ciphertext: mem.Slice(sizeof(int) + AesGcm.NonceByteSizes.MaxSize + AesGcm.TagByteSizes.MaxSize, plaintext.Length ), tag: mem.Slice(sizeof(int) + AesGcm.NonceByteSizes.MaxSize, AesGcm.TagByteSizes.MaxSize) ); } return outputBuffer; }
We validate that the user provided us with up to 6 messages (MaxUserItems) to encrypt and that there are no repeated passwords, then we compute the size required to encrypt the longest message. We align that on 64 bytes (BlockSize) and use that to compute the actual overall buffer size. Note that we also add a bit of additional space at the end, to confuse attempts to figure out values based on size (such as the BEAST attack).
We then get the output buffer. Note that in this case, we are asking the RandomNumberGenerator class to give us a buffer that is already filled with random data. The idea is that we don’t need to worry about filling stuff up with cryptographically secured data. We start with random noise, and we add whatever meaning we need from there.
The first 32 bytes (SaltSize) are the salt, this is used to mitigate rainbow table attacks, among others. The next 32 bytes are used as the offsets array, which are used to store the location of the actual encrypted messages.
For the message we want to encrypt, we start by using PBKDF2 to derive a 40-byte cryptographic key. We are using SHA512 (which has a block size of 64 bytes) and 210,000 iterations to derive the key, per the OWASP recommendation.
We want to be unpredictable, so we aren’t writing the first element to the first offset position. Instead, we start the offset position in a random location. We figure out what is the size of the encrypted value (including the size, nonce, tag, and actual encrypted bytes) and stash that at a random location in a random offset in the output buffer.
We then take the first 4 bytes of the derived key value and XOR that with the offset of the value we’ll be writing. We are using those bytes as a stream cipher, basically. We write the encrypted offset to the offsets table. Note that in order to decrypt that, you need to re-run the PBKDF2 computation, which requires that you have the password.
The next 4 bytes (4..8) are used as a stream cipher to encrypt the length of the value we are about to encrypt. And the other 32 bytes (8..40) are used as the encryption key itself.
Note that we are “missing” things like nonce generation. We don’t need that, since the nonce buffer we point to has already been seeded with random values from a cryptographic source.
The Encrypt() does most of the work, and… this is pretty much it. There isn’t a lot of code, most of it is in how we put things together.
The decryption portion is a lot more interesting, I think, so let’s take a look at it:
public static string? Decrpyt(string pwd, byte[] encrypted) { Span<byte> mem = encrypted; var salt = mem.Slice(0, SaltSize); ReadOnlySpan<byte> derived = Rfc2898DeriveBytes.Pbkdf2(pwd, salt, Iterations, HashAlgorithmName.SHA512, sizeof(int) + DerivedKeySize + sizeof(int) ); var offsetMask = MemoryMarshal.Read<int>(derived.Slice(0, sizeof(int))); var lenMask = MemoryMarshal.Read<int>( derived.Slice(sizeof(int), sizeof(int)) ); var derivedKey = derived.Slice(sizeof(int) + sizeof(int), DerivedKeySize); var offsetsBlock = MemoryMarshal.Cast<byte, int>( mem.Slice(SaltSize, OffsetsBlockSize) ); for (int i = 0; i < ItemsCount; i++) { var offset = offsetsBlock[i] ^ offsetMask; if (offset < SaltSize + OffsetsBlockSize || offset + sizeof(int) > mem.Length) continue; var maskedLen = MemoryMarshal.Read<int>( mem.Slice(offset, sizeof(int)) ); var len = maskedLen ^ lenMask; if (len < 0 || offset + len + sizeof(int) > mem.Length) continue; using var cipher = new AesGcm(derivedKey, AesGcm.TagByteSizes.MaxSize); var outputBuf = new byte[len]; try { cipher.Decrypt( nonce: mem.Slice( offset + sizeof(int), AesGcm.NonceByteSizes.MaxSize ), ciphertext: mem.Slice( offset + sizeof(int) + AesGcm.NonceByteSizes.MaxSize + AesGcm.TagByteSizes.MaxSize, len ), tag: mem.Slice( offset + sizeof(int) + AesGcm.NonceByteSizes.MaxSize, AesGcm.TagByteSizes.MaxSize ), outputBuf); } catch (CryptographicException) { // expected, we may hit a dummy value or wrong password } return Encoding.UTF8.GetString(outputBuf); } return null; }
Here we take the first 32 bytes (the salt) and use PBKDF2 and the password to generate the derived key. Again, we are getting 40 bytes back. The first 4 bytes are the offset mask (to figure out where to look for the values, the next 4 bytes are the length mask, to figure out the length for decryption, and the last 32 bytes are the decryption key.
Without the password, we cannot get to the derived key, remember. Then we start scanning through the offsets block. For each of the items we XOR the value in the offsets with the mask. Here we have three options:
- The XORed value is completely off, which we detect and skip.
- The XORed value is correct and points to the right offset to continue the operation.
- The XORed value appears to be correct (its value in bounds). We’ll continue the operation, but fail in the next stage when we actually try to decrypt the value. This is because we are using AES-GCM, which is an AEAD (authenticated encryption) that validates (using cryptographic primitives) that the decrypted value matches the value that was encrypted. I wrote a blog post (part of a larger series) explaining this in detail.
With the offset, we can now read the masked length of the buffer, which has the same problems as the masked offset. We XOR that with the right mask and need to deal with the obvious wrong, correct, or appears to be correct but actually wrong scenario as well. We don’t really care, since we leave the actual validation to the authenticated encryption portion.
If we are able to correctly decrypt the value, we immediately return it. But if not, we’ll try with the next offset, etc. Note that for decryption, we are scanning the offsets array and attempting to check whether the key we derived from the password is able to decrypt the current value. During encryption, we randomized where everything goes, and here we can just do a simple scan and stop on the first value that was successfully decrypted.
As I mentioned, that was a lovely evening to spend on an interesting exercise. I think that this is a valid way to go about building a deniable encryption scheme. The full code is here, I would love your feedback on both the code and the actual idea.
I like that I can provide multiple passwords and messages, in a simple manner. I think that a viable use case would be to encrypt three values. Safe, honeypot, and the real deal. For example:
var output = DeniableEncryption.Encrypt( ("safe", "I don't like Mondays"), ("honeypot", "I microwave fish in the office break room and I’m not going to stop"), ("motherlode", "Bitcoin seed: armor cactus gaze off future blade artist") );
There is no way to tell whether there is a third option here, and the format is intentionally always assuming 8 “entries”, even if you provide less than the maximum. Of course, that also raises the problem of what if after you give up the motherlode, the other side still suspects there are more secrets. At this point, I’ll point you out to Mickens and a wonderful article about threat models.
Check out the code and let me know what you think about this.
Comments
I'll just leave it here: https://xkcd.com/538/
Yoohoo,
It is an excellent one, yes.
Note that in this case, you can provide more keys, and keep revealing things without exposing the motherlode.
That said, yes, you'll likely get hit by a wrench a lot.
Your "Decrpyt()" function is misspelled.
Thanks for your work! I'm not a dev so I don't know how to run this easily so I'd love to get a little software or webpage to do that with my text.
Julian Assange invented this decades ago under the name RUBBERHOSE encryption!
Thank you for introducing me to this fascinating topic, and thanks to Moscou for mentioning the Rubber Hose, that led me to the Rubber Hose cryptanalysis. Learning from you, I adapted the code to JS and have deployed a web version where in you can use it. It's accessible here:
https://44za12.github.io/
Also, I wrote an article about my journey of researching through the topic and building this app, please give me your feedback for that it would mean a lot:
https://aazar.me/beating-the-rubber-hose-cryptanalysis
Aazar,
That looks quite nice. Note however that in your implementation, you are leaking the size of the encrypted data. All you have to do is look for a period of
0000
in your hex output and you'll be able to tell how long is the string that you are encrypting. That can be used to narrow down exactly what is going on.In my implementation, I have ensured that even the length of the encrypted text is itself encrypted.
Ꮐood day I am so happy I found your site, I really found you by accident, wһuile Ι was looking on Yahoo for something eⅼse, Rеgzrdless I am heгe now and would ϳuѕt like to say cheers foг a marvelous post and a all round exciting blog (I also love the theme/design), I don’t have time to browse it all at the moment but I have saved it and also included your RSS feeds, s᧐o when I have time I will bе baϲk to read much more, Pleaѕe doо keep uᥙp the superb work.
This is common in crypto world actually. Imagine you have a fully encrypted crypto account but only to be defeated by a wrench! xkcd: wrench attack
So you could configure your encryption in a way that if another key was provided, it will unencrypt a different crypto account (with much smaller values presumably) so that the wrench attack is nullified. The attacker gets away with tiny amount of crypto and your real crypto account stays hidden.
Comment preview