How to Fake Decryption

post by ohmurphy · 2024-09-05T09:18:41.586Z · LW · GW · 0 comments

This is a link post for https://ohmurphy.substack.com/p/how-to-fake-decryption

Contents

  The Basic Setup
    Background on One-Time-Pads
    The Idea
    An Example
  Caveats/Adjustments
    Bob does not know the fake key
    What about multiple block messages?
  Some interesting notes
  Possible applications
None
No comments

{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.1 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

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:

Less serious ones:

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

0 comments

Comments sorted by top scores.