Cracking Nested One-time Pads

Question

Inspired by the famous "how to send a locked box without pre-shared keys" puzzle, I have designed a Truly Clever and Very Secure cryptographic protocol for situations where you must send a secret message, but an eavesdropper can observe the communication. It's based on the observation that one-time pad operations are "transparent" with respect to each other, and you can remove two nested encryptions in whichever order. Without further ado, let me introduce to you:

---

The Padlock Protocol

1. Alice wants to send Bob a secret message. To do so, Alice creates a one-time pad $A$, and uses it to encrypt the plaintext message $P$, obtaining the first cipher message $C_A$. In the analogous box puzzle's terms, Alice puts the message in a box and locks it with her own padlock. Alice then transmits $C_A$ to Bob.

2. Bob then generates his own one-time pad $B$, and encrypts $C_A$ with it, producing the second cipher message $C_{AB}$. In the analogy, Bob adds his own lock to the box. Bob then sends the doubly encrypted message $C_{AB}$ to Alice.

3. Alice then decrypts $C_{AB}$ using pad $A$. Or, in the analogy, Alice removes her lock from the box. This results in the third message $C_{B}$, which Alice send to Bob.

4. Finally Bob uses pad $B$ to decrypt $C_{B}$, and recovers the original message $P$. Or in the box analogy, Bob removes his own lock, which was the only one remaining on the box.

---

The puzzle

One-time pad encryption is provably secure. Every transmission was protected by at least one such encryption. Both Alice and Bob kept their pads safely stored. Also, just in case you wondered, this method works, Bob really will receive the original message.

Yet it is a very bad idea to use the Padlock Protocol for conveying secret messages on an eavesdropped channel.

You are to take the role of Eve, the eavesdropper. You have observed all the transmissions, and you know all the encrypted messages. They are, in order:

Alice to Bob ($C_A$): SPVJRQQHHPLZXJAILONXJTYOHXCIYWCAPFOXKGRRDXWUEOTAHPWQ
Bob to Alice ($C_{AB})$: LWDBZICFVCPSFVEXLRGENKCOYBOILUNIZJWQLAKKKFOIRSBSTXJU
Alice to Bob ($C_{B}$): XCMZIKNMHUXAMBPPIQMLBKENUXTEPGAPOVIGEWTGKMVIPIBZQXNH

Using no other information, you are to deduce what was the secret message that Alice wanted to send to Bob.

For unambiguity's sake, Alice and Bob used this exact variant of the one-time pad cipher with an unmodified alphabet. The puzzle would work with any one-time pad implementation, but figuring out which one they used would be just a lot of non-interesting busywork.

Answer 1

So there's already a bunch of answers that talk about how to get the "secret message" along with the one time pads, but none of them seem to point out:

The "secret" was ATTACK AT DAWN

The reason Alice decided to put the secret in the one time pad is that finding Alice's one time pad is not required to find the "secret message". Thus this is actually an example of steganography where Alice was hiding the secret somewhere insecure but unexpected.

This can be confirmed by the rest of Alice's one time pad:

OUR CRYPTO IS STUPID BUT MAYBE EVE WONT LOOK HERE ATTACK AT DAWN

Answer 2

Let $+$ and $-$ denote the "standard" arithmetic operations modulo 26 on the English alphabet, done letterwise to strings.

Here, encrypting text $T$ with a given one-time pad $P$ is simply calculating $T+P$ to get the ciphertext $X$, and decrypting reverses the process: $T=X-P$.

Note that, since $+$ is "made up of" regular mod-26 addition, it is commutative and associative. This is what gives us the ability to crack the code.

So, if the ciphertext is $X$ and the pads are $A$ and $B$, we're given $X+A$, $X+A+B$, and $X+B$. Now we can easily see how to solve it! Subtracting the first text from the second (by decrypting) gives the text

THISISMYONETIMEPADTHEREAREMANYLIKEITBUTTHISONEISMINE

With this, we can easily decrypt the remaining message and get $X$:

EVEHASBOTHTHEPLAINTEXTANDTHECIPHERANDCANDEDUCETHEPAD

And if we want, we can find the remaining one-time pad in any number of ways:

OURCRYPTOISSTUPIDBUTMAYBEEVEWONTLOOKHEREATTACKATDAWN

Answer 3

Using a Vigenere table with alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ", using messages $C_{AB}$ and $C_B$ we can deduce key $A$.

Key A = "OURCRYPTOISSTUPIDBUTMAYBEEVEWONTLOOKHEREATTACKATDAWN"

Using the same table, since we have Key $A$ we can decode $C_A$ to get the plain text.

$P$ = "EVEHASBOTHTHEPLAINTEXTANDTHECIPHERANDCANDEDUCETHEPAD"

And for fun, Key $B$ is:

Key $B$ = "THISISMYONETIMEPADTHEREAREMANYLIKEITBUTTHISONEISMINE"

Answer 4

The answer is

EVE HAS BOTH THE PLAIN TEXT AND THE CIPHER AND CAN DEDUCE THE PAD

Let $m_i$ be the leter of the message, $a_i$ the letter of Alice pad and $b_i$ the leter of Bob pad. The first message is $m_i + a_i$, the second is $m_i + a_i +b_i$ and the third is $m_i + b_i$.

To decipher you can do first message + last message - second message : $(m_i + a_i) + (m_i + b_i) - (m_i + a_i +b_i) = m_i$

Here is an Excel sheet showing the details :

Answer 5

I used some Python code to convert the encrypted messages to numbers, then subtracted them.

Answer

EVEHASBOTHTHEPLAINTEXTANDTHECIPHERANDCANDEDUCETHEPAD

# one-time pads
A = ''
B = ''

# Plaintext message P
P = ''

# Cipher text, Alice to Bob
Ca = 'SPVJRQQHHPLZXJAILONXJTYOHXCIYWCAPFOXKGRRDXWUEOTAHPWQ'

# Cipher text, Bob to Alice
Cab = 'LWDBZICFVCPSFVEXLRGENKCOYBOILUNIZJWQLAKKKFOIRSBSTXJU'

# Cipher text, Alice to Bob
Cb = 'XCMZIKNMHUXAMBPPIQMLBKENUXTEPGAPOVIGEWTGKMVIPIBZQXNH'

# Ca = A + P
# Cab = Ca + B
# Cb = Cab - A
# P = Cb - B

# Ca = A + P
# Cab = Ca + B
#   B = Cab - Ca


# Cb = Cab - A
# P = Cb - B
#   P = Cb - (Cab - Ca)
#   P = Cb - Cab + Ca

# Translate the letters to numbers (65-90
# alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
l_Ca = [ord(x) for x in Ca]
l_Cab = [ord(x) for x in Cab]
l_Cb = [ord(x) for x in Cb]

P = [l_Cb[x] - l_Cab[x] + l_Ca[x] for x in range(0, len(Ca))]

# Adjust for the letters outside of the A-Z range
Q = list()
for x in P:
    if x > 90:
        Q.append(x - 26)
    elif x < 65:
        Q.append(x + 26)
    else:
        Q.append(x)

# Turn the numbers back into characters
Q = [chr(x) for x in Q]

print(Q)

Answer 6

Alice is using her pad $A$ twice, first to compute the value $C_A$, and then once more to compute $C_B$. The relationship between these values is known to Eve, who can exploit it to trivially recover $A$ and $P$.

One time pads are based on modular addition, which means that it has a commutative group structure. Using the symbol $+$ for the group operation, $-X$ for the inverse of element $X$, and writing $X - Y$ for $X + (-Y)$, we have the following equations:

$$ \begin{align} C_A &= P + A \\ C_{AB} &= C_A + B \\ C_B &= C_{AB} + A \end{align} $$

The third equation is key, because it relates the unknown $A$ to the two known values $C_{AB}$ and $C_B$. Which means Eve can solve that third equation for $A$, and use it to compute its value:

$$ A = C_B - C_{AB} $$

She also can solve the first equation for $P$:

$$ P = C_A - A $$

And since she knows the values of $C_A$ and $A$, she can compute $P$ as well now.

Answer 7

As other answers have already described, the cryptographic attack used is to determine the difference between one message and the next to obtain the contents of the "two-time pad". We don't initially know what key Alice used because we haven't seen the plaintext yet, but we know Bob's plaintext - it's the message that Alice encrypts in the first step. C_AB - C_A reveals Bob's key K_B and C_B - K_B gets back to the original message C.

Alice's message was:

EVEHASBOTHTHEPLAINTEXTANDTHECIPHERANDCANDEDUCETHEPAD

Here's how JavaScript can subtract the characters of one message from another (full code here).

var aa = a.charCodeAt(0);
var bb = b.charCodeAt(0);
var cc = ((aa - bb + 26) % 26);
var c = String.fromCharCode(c + 'A'.charCodeAt(0));

As a technical detail, this specific code will always produce upper-case ASCII/UTF-8 results due to the use of 'A'; you could sophisticate by choosing the final offset based on the starting case of each letter.