How to Fake Decryption

Or how to send one message with multiple contents

Image of an enigma machine. Source: https://commons.wikimedia.org/wiki/File:Lorenz-SZ42-2.jpg?uselang=en#Licensing

{Epistemic Status: mostly just writing up an idea I came up with a while ago. I’ve done non-trivial coursework in cryptography, so I think I’ve avoided obvious errors, though there may be non-obvious ones. Consult an expert before using.}

Suppose you knew that someone was spying on your encrypted messages, what should you do? Luckily, if you’re using proper AES secure encryption, then you can mostly rest easy knowing your eavesdropper won’t be able to read your messages. This is great and successfully stops an attacker from gaining new information from your messages, but I think we can do a bit better. Specifically, we can give our attacker precise incorrect information.

The Basic Setup

Background on One-Time-Pads

One-time-pads are an essential part of modern (symmetric key) cryptography. To use one, you start with a plaintext message P and a random symmetric key K (shared with your recipient) of the same length as P (in bytes), then you encrypt your message by calculating Ciphertext (C) = P XOR K. This new ciphertext (C) now appears entirely random to anyone without the symmetric key (K), but can be deciphered by anyone with the symmetric key (K) by just calculating P = C XOR K.

The Idea

Our goal is to pretend to decrypt the original ciphertext C. To do this, we want to create a fake key FK such that we can appear to decrypt C into a fake plaintext message FP. If we substitute our fake values into the decryption equation P = C XOR K, we get FP = C XOR FK. Once we decide what we want FP to be, we can easily solve for FK by applying XOR C to both sides. This gets us FP XOR C = FK.

An example

Suppose Alice is in a secret relationship with Bob and wants to send him an encrypted note rescheduling a date they had planned. Unfortunately, their mutual friend Eve often picks up Bob’s mail for him and would notice that Alice was sending Bob an encrypted message. Though Eve would not be able to decrypt the message herself, she still might guess the truth of Alice and Bob’s relationship just from the existence of the message. To avoid this, Alice also writes a fake message (FP) to Bob about stamp collecting and constructs a fake encryption key (FK) for this fake message (FP) using the method above. Later, Alice intentionally gives Eve the fake encryption key (FK), perhaps telling her to give it to Bob. Eve, now equipped with the fake encryption key (FK), successfully decrypts the ciphertext (C) into the fake message (FP). Having seen the fake message (FP), Eve’s curiosity is sated and Alice and Bob’s secret relationship can continue uninterrupted.

Caveats/Adjustments

Some more knowledgeable readers may already be noting some simplifications and possible issues with the version of this explained above. Let’s work through and address some of these.

Bob does not know the fake key

One straightforward issue is that the fake key and fake message constructed by Alice are not automatically known to Bob. For example, if Eve had asked Bob what was in the encrypted message above, he could only guess at the fake message Alice constructed. This can be resolved if Alice and Bob agree on a fake message (FP) before the message is sent since then both Alice and Bob could construct the fake key (FK) from the ciphertext once they send/receive it.¹ Agreeing on the fake key (FK) rather than fake message (FP) beforehand is likely not possible since the fake key (FK) is a function of the ciphertext (C) which is a function of the actual message (P) and key (K). Doing this would require that the message (P) was known to both parties before the message was sent, which defeats the entire point of sending the message.

What about multiple block messages?

If you split the messages in the setup above into blocks, you start to run into the issue that every block will need to be encrypted with its own key (K_i) so that a suitable fake key (FK_i) can be constructed for that specific block based on its fake message (FP_i) and ciphertext (C_i). This becomes difficult if the encryption protocol you are attempting to imitate has known dependencies between the keys for each message (as most common network encryption does). At that point, you just have to hope that the observer (Eve) is willing to take the individual fake message keys (FK_i’s) as correct, without asking for a generating function and its parameters (nonces, parameter keys). Of course, it is important to note that the encryption cipher being imitated with the fake messages (FP_i’s) and keys (FK_i’s) does not need to match the cipher used to encrypt the true messages (P_i’s) with the true keys (K_i’s).

Some interesting notes

• This method allows you to generate as many unique fake messages as you want, so you could give different fake keys (FKs) to different actors.

• Since this method is not actually dependent on the true message’s content (P) or encryption key (K), anyone can make fake messages, not just the sender and recipient.

• Fake messages and keys can be constructed long after actual messages have been sent, so it is possible to apply this retroactively to old messages.

• As mentioned above, the encryption cipher being imitated to the adversary (Eve) does not need to match the cipher used for the true message. For example, Alice might use a Cipher Block Chaining encryption for the true messages and then tell Eve that the blocks were encrypted with a Counter (CTR) cipher where the fake keys (FK_i’s) are the output of the nonce encryptions.² Generally, the simplest encryption protocol to imitate seems likely to be a CTR cipher since it is most similar to a sequence of independent one-time pads.

• I am not certain about the security properties of the fake messages (FP) and (FK) in terms of their own independent encryption. They seem almost symmetric with the normal encryption, just using the same source of randomness, but I would assume they are insecure until proven otherwise.

• If HMACs are done using a separate integrity and/or signing key and with only the ciphertext, then they work as normal since the ciphertext is unchanged.

Possible applications

I find this idea fairly interesting from a mathematical perspective, but useful applications are less clear. Still, here are some quick thoughts on possible applications:

Serious ones:

• Masking important encrypted communication on observed networks as being innocuous for a specific adversary. These messages could disguise leaks by an insider or traffic involving important internal parties or sensitive information.

• Polluting an adversary’s information gained from encrypted communication in order to reduce other information’s credibility.

• Being able to offer more credible fake decryption of messages to an adversary. This can include faking decryption of messages between members of your own group, but it can also include faking decryption of messages between members of the adversary’s group, or between any other parties.

Less serious ones:

• This idea could work as a fun idea in a fictional universe with some cryptography. I’ve thought about including it in the novel series I eventually hope to write.

• This might be nice for making fun ‘wrong’ answers in some Capture The Flag hacking games or ARGs.

That’s it, let me know if you have any thoughts!

1. Technically Bob does not need to know the fake message (FP) before receiving the true message ciphertext (C). He just needs to know both before Eve asks him to decrypt the message.

2. To be clear, this is a lie. No nonce encryptions would actually be performed in this setup. You cannot expect to be able to find a nonce which will generate the fake keys (FK_i’s) that you want (unless you use a broken/dummy encryption algorithm on the nonces).