18
$\begingroup$

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.

$\endgroup$
8
  • 2
    $\begingroup$ One-time pad is secure because you only use it once. Your method uses the "unique" cipher twice on the exact same message, making it trivial to crack. $\endgroup$ Apr 2, 2018 at 15:32
  • 1
    $\begingroup$ @MichaelRichardson Counting the encryptions and decryptions, each pad gets used exactly once to encrypt, and exactly once to decrypt. But I agree, that's one way to look at the solution. Another way would be rot13(xabja-cynvagrkg nggnpx), which is utterly devastating for one-time pads. $\endgroup$
    – Bass
    Apr 2, 2018 at 15:46
  • 1
    $\begingroup$ here's the real problem from a computerized cryptography standpoint: any method by which Encrypt(B,Encrypt(A,msg)) can be decrypted with the inner key (A) first is flawed. $\endgroup$
    – NH.
    Apr 2, 2018 at 16:34
  • 2
    $\begingroup$ @NH. Seems to me that you're claiming that one-time pads are somehow flawed because they happen to have exactly that feature? $\endgroup$
    – Bass
    Apr 2, 2018 at 17:14
  • 5
    $\begingroup$ Classic quote: "beware the two-time pad" (not sure who said it first). $\endgroup$ Apr 2, 2018 at 19:34

7 Answers 7

3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Very good, thank you! (I'ma give you the check mark, because the top voted answerer couldn't be bothered to respond to my comment requesting this exact information, and nearly 4 years should have been plenty enough time for that.) $\endgroup$
    – Bass
    Feb 16, 2022 at 14:57
  • $\begingroup$ This is so nice. I just discovered this puzzle because of the renewed activity. I also love the flavour in the pads and plaintext, all the same length. $\endgroup$
    – Oliphaunt
    Feb 16, 2022 at 22:33
  • $\begingroup$ And of course the extra layer in the puzzle. Well done @Bass 👏 $\endgroup$
    – Oliphaunt
    Feb 16, 2022 at 22:36
18
$\begingroup$

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

$\endgroup$
4
  • 4
    $\begingroup$ um... spoiler blocks? $\endgroup$
    – NH.
    Apr 2, 2018 at 16:38
  • $\begingroup$ @Bass ohhh. Yes of course. Thanks. My problem was that I was mixing up those onetime pads with a different cipher type. $\endgroup$
    – Sentinel
    Apr 2, 2018 at 17:47
  • 3
    $\begingroup$ @Deusovi But now for bonus points. Given an EC bitcoin public key, how can you easily guess the private key. Please PM me the answer😉 $\endgroup$
    – Sentinel
    Apr 2, 2018 at 17:54
  • 1
    $\begingroup$ I would feel happier about awarding the tick if the answer contained, in addition to the decryptions and the excellent description of the method, a clear answer to the question "what was the secret message that Alice wanted to send to Bob", where it was found, and why Alice chose that exact place for it. $\endgroup$
    – Bass
    Apr 10, 2018 at 22:07
7
$\begingroup$

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"

$\endgroup$
4
$\begingroup$

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 :

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ So I think I understand this... the trick is that you can calculate the difference between either once-encrypted pad, and the twice-encrypted pad in order to find one of the keys? $\endgroup$ Apr 2, 2018 at 15:33
1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Interestingly, it's perfectly possible to solve the puzzle while not attacking A at all; B is just as vulnerable, and it's definitely not used twice. (Also, this is the "original" type of one-time pads, which is based on the Vigenère cipher instead of XOR, so decryption isn't exactly identical to encryption, and every element isn't it's own inverse.) $\endgroup$
    – Bass
    Apr 3, 2018 at 2:04
  • $\begingroup$ @Bass: oops, yeah, I was thinking of XOR. I've fixed the answer. $\endgroup$ Apr 3, 2018 at 21:11
0
$\begingroup$

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. CAB - CA reveals Bob's key KB and CB - KB 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.