1
$\begingroup$

How does one decrypt the many time pad:

($R$ is a random string, $C$ is ciphertext, $P$ is plaintext)

$R_0 \oplus R_1 = C_0$

$R_2 \oplus R_1 = C_1$

$P_0 \oplus R_1 = C_2$

assuming that $R_n$ are perfectly random pads, plaintext is writing and $C_n$ are the encrypted pads. The key $R_1$ is used three times but it doesn't seem like Crib Dragging (the solution I've seen described to decrypt many time pads) would work (edit: to retrieve $R_0$, $R_2$, and $P_0$ or even just $P_0$) since the other values that $R_1$ is added to are random. Is there something I'm missing?

$\endgroup$
  • 3
    $\begingroup$ Hint: rewrite "random[0] xor random[1] = cipher[0]" as "(all-zero plaintext) xor (random[0] xor random[1]) = cipher[0]". is this really a many-time pad? Do cipher[0] and cipher[1] actually carry any information, or are they in fact statistically independent from random[1]? Write down the probabilities on paper to make sure. $\endgroup$ – Thomas May 3 '15 at 5:13
  • $\begingroup$ Adding an all zero plaintext makes no sense. $R_0 and $R_2 are the information being carried by $C_0$ and $C_1$ and the goal is to retrieve them and $P_0$ or failing that retrieve just $P_0$. Since $R_0$, $R_1$, and $R_2$ are just theoretical values defined as random the probabilities should have a perfectly even distribution, $R_1$ should be statistically independent from $C_0$. $\endgroup$ – Daedalus6394 May 3 '15 at 20:58
  • $\begingroup$ Both $C_0$ and $C_1$ serve no purpose at all. In order to decrypt and retrieve $P_0$, all you need is $R_1$. So if we assume the key contains $R_1$, I can decrypt even if I only get $C_2$ and not $C_1,C_2$. Sending random things alongside actual information does not mean it is any different than the original scheme. $\endgroup$ – tylo May 4 '15 at 11:15
  • $\begingroup$ It is assumed in the one time pad that the key, in this case $R_1$ is perfectly secret and unknown. In this case that is extended to $R_n$. Note this is not a question about decryption by the intended receiver but decryption by an unintended third party. $\endgroup$ – Daedalus6394 May 4 '15 at 16:51
2
$\begingroup$

This cannot be used to compromise $P_0$. Suppose that, instead of generating $C_0$ and $C_1$ as $R_0\oplus R_1$ and $R_2\oplus R_1$, the attacker instead picked $C_0$ and $C_1$ at random from the set of bit strings the length of $C_2$. This situation is indistinguishable from yours; in both cases, $R_0$ and $R_2$ are independent and follow a uniform probability distribution, and the same is true for $C_0$ and $C_1$. If you can compromise $P_0$ in your case, you can compromise it if the sender had actually generated $C_0$ and $C_1$. But that would mean that sending two completely random strings alongside an OTP message somehow helps compromise the message. Obviously, that's not true; the attacker could otherwise create his own random strings and break the OTP that way.

$\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.