15
$\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$
  • 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$ – Michael Richardson Apr 2 '18 at 15:32
  • 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 '18 at 16:34
  • 1
    $\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 '18 at 17:14
  • 5
    $\begingroup$ Classic quote: "beware the two-time pad" (not sure who said it first). $\endgroup$ – John Coleman Apr 2 '18 at 19:34
  • 1
    $\begingroup$ Related: this crypto.se post. $\endgroup$ – internet_user Apr 3 '18 at 15:29
17
$\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
    $\begingroup$ um... spoiler blocks? $\endgroup$ – NH. Apr 2 '18 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 '18 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 '18 at 17:54
  • $\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 '18 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
    $\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$ – Adonalsium Apr 2 '18 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$
  • $\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 '18 at 2:04
  • $\begingroup$ @Bass: oops, yeah, I was thinking of XOR. I've fixed the answer. $\endgroup$ – Luis Casillas Apr 3 '18 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, privacy policy and cookie policy

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