4
$\begingroup$

Suppose a message $M$ was encrypted with a one-time pad. If we learned the first half of the original text is some substring $s$, would we have a better chance of cracking the rest of the message?

Is this true or false? I know that OTP is unbreakable in theory but with the knowledge of the first portion of the string, would this help us?

$\endgroup$
1
$\begingroup$

In theory no, there will be no better chance.

The key must be at least as long as the original text. The key must have high entropy (simply said, it should be random enough). Then revealing any part of the original text has no effect on the decryption.

In practice, if the process is realized improperly, there can be some issues:

  • If the key is shorter that the original message.
  • If the key is not random enough.
  • If the the OTP generator is not random enough and the attacker knows a lot of other OTPs produced by this generator.
|improve this answer|||||
$\endgroup$
  • $\begingroup$ Say we have a key as long as the original text, why is it still not a better chance? Can you explain that please? $\endgroup$ – vexen231 Jan 31 at 20:59
  • $\begingroup$ The OTP encryption is done by XOR of two bytes: one message byte and one key byte. There are no block operations. Key parts are not involved in any rotations or substitutions unlike other methods. For instance, if you change one byte in an AES key, it will change the whole encrypted message. It means, many bytes of the encrypted message are connected with the byte of the key. That's why knowing a part of the message can give some information about the key. But... $\endgroup$ – mentallurg Jan 31 at 21:13
  • $\begingroup$ ... but in the OTP each byte of the encrypted message is connected exactly with one byte of the key. No matter how many bytes of the original message you know, there is no relation between them and the remaining key bytes. And thus there is no way to calculate the remaining part of the key, and thus no way to decrypt the remaining part of the message. $\endgroup$ – mentallurg Jan 31 at 21:16
  • $\begingroup$ The answer blindly assumes that all plaintext consist of uniformly random symbols, which goes straight against both theory and practice, ancient and modern! $\endgroup$ – fgrieu Jan 31 at 22:21
  • 1
    $\begingroup$ Maybe you should mention: If anything other than a TRNG is used to create the pad, it is not an "OTP" (although some people make the mistake to call steam ciphers of all sorts "OTP"). $\endgroup$ – tylo Feb 1 at 17:37
1
$\begingroup$

The OTP part of the question is a distraction from the main point: it depends heavily on hypothesis on the plaintext if learning a sub-string of it helps towards finding the rest of the plaintext.

For plaintext consisting of independent symbols, no, learning a substring does not help towards guessing the rest. Argument: use of the OTP implies that we can't learn anything from the ciphertext. That leaves the given plaintext substring as the only information about the plaintext. Because symbols are independent, revealing some is of no help to guess the others.

For other type of plaintext, including as in practice and as considered in standard theoretical hypothesis, yes it can help, possibly heavily. Illustration: for plaintext known to be a 14-symbols English word, learning that it starts with HYPOTHE helps a lot towards guessing that the rest is TICALLY.


Note: if the question was to be read as: does knowledge of the OTP ciphertext help to guess the end of the message knowing its start?, the answer is no, under the assumption that the pad was uniformly random and not reused.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ 1) CPA could be relevant for OTP if password could be reused. But if password is reused, it is not OTP. As I wrote, if it is implemented improperly, there can be different problems that help to recover the password. Your statement about CPA implies that password is used more than once and thus implies that OTP is implemented improperly. Yes, this is one more example. 2) Restoring / guessing the unknown part based on the known part has nothing to do with the OP. Your text is correct, but this an answer to some other question, not to the OP. $\endgroup$ – mentallurg Jan 31 at 23:32
  • $\begingroup$ @mentallurg: you are correct that CPA does not apply to OTP., and I removed that part of the answer (I was considering a modified CPA where the oracle has to choose which of two messages chosen by the attacker is encrypted, and then some of the message that was chosen gets revealed). I still think that I'm answering the question the OP asks, but clearly we are not reading it the same way. You are (correctly) answering: does knowledge of the OTP ciphertext help to guess the end of the message knowing its start? $\endgroup$ – fgrieu Feb 1 at 6:53

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.