2
$\begingroup$

I understand why |one-time pad|=|message| using a normal one-time pad, but I don't understand why for perfect secrecy it must alway be that |key|>|all messages exchanged|.

What if, for example, I had |one-time pad|=n*|message| with n>1 and then used it for (for example) 2n messages with a random starting point (itself encoded at some point in the message with a 'normal' one-time pad which given it's a single number could be simply be the first part of the original OTP)?

I'm pretty sure there must be something that doesn't work, because if this was still perfectly secret then a one-time pad could be used to generate infinite one-time pads which would be useful but impossible (wouldn't everybody be using it?). So, where does the perfect encryption of the one-time pad end?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ History proves that OTPs work. History also proves that reused OTPs don't work. I wonder why people persist in trying to change the undeniable? It's like repeatedly trying to square the circle by using increasingly clever and convoluted drawing techniques and better compasses. $\endgroup$
    – Paul Uszak
    Feb 25, 2017 at 0:35
  • 1
    $\begingroup$ @PaulUszak: Bad example, since it's mathematically proven that squaring the circle is impossible, while you argue that OTP reuse is empirically unsafe. $\endgroup$
    – MSalters
    Jun 12, 2017 at 7:10
  • $\begingroup$ @MSalters It's an allegory, but I get your point. This may be worthy of a question... $\endgroup$
    – Paul Uszak
    Jun 12, 2017 at 13:58
  • $\begingroup$ A Known-plaintext attack on the second message would be pretty easy to crack this. With a normal OTP a known-plaintext attack doesn't work. $\endgroup$
    – daniel
    Jun 14, 2017 at 16:38
  • 1
    $\begingroup$ For the same reason people do still try to square the circle or think how to build a perpetual motion machine. Because they are interesting problems that can teach you a lot even if they are impossible. Also because not everyone knows better yet. $\endgroup$
    – user43032
    Jun 15, 2017 at 20:37

4 Answers 4

Reset to default
5
$\begingroup$

For perfect secrecy of any cryptosystem, it must hold that |key|≥|all messages exchanged|.

Proof by contraposition: assume |key|<|all messages exchanged|, and there exists a deterministic decryption procedure of all ciphertext exchanged and key to all messages exchanged. Knowing all messages exchanged, an infinitely powerful adversary can exclude some value of messages exchanged as impossible, violating perfect secrecy; all s/he has to do is apply said procedure to decipher the given all ciphertext exchanged with all the possible values of key, and rule out as impossible any value of all messages exchanged not obtained for any value of key. The hypothesis |key|<|all messages exchanged| implies there will exist at least one impossible value, by a counting argument.

In the case of the repeated OTP in the question, there exists attacks that can be performed by an adversary with very limited computing ability, and enough knowledge about the plaintext.

For example, assume that all the messages are long, random, and known entirely except for an unknown bit in the middle of the last message. It becomes likely and easy to find most of the key, and the starting point for all messages, and from that the single unknown plaintext bit.

There are more clever attacks that work with less hypothesis on the plaintext (like: it is mostly English words), and remain feasible in practice if there is enough ciphertext.

Improve this answer
$\endgroup$
3
  • $\begingroup$ If the messages are already known entirely except of an unknown bit then what's the point? I don't understand what you mean with that. But I think I got the point: you could with some knowledge of the messages and enough messages reverse engineer the decryption procedure. $\endgroup$
    – user43032
    Jan 19, 2017 at 18:48
  • $\begingroup$ What then if the deterministic decryption procedure was dependent on random factors? For example: you have a pad, to send a message you use a smaller pad generated by running a function with random parameters which are themselves changed every time on the main (larger) pad. Wouldn't that add enough complexity to be effectively even if not technically perfectly secret? $\endgroup$
    – user43032
    Jan 19, 2017 at 18:51
  • 2
    $\begingroup$ @RandomUser: Perfect secrecy means that it is impossible (regardless of computing power) to learn anything about the plaintext, including making a guess better than random on a single bit. In many contexts, a single bit does matter: e.g. test/real thing. My demonstration about perfect secrecy holds, without change, if the encryption is probabilistic (as many used in practice are), as long as decryption is deterministic. The security of algorithms that do not match the conditions for perfect secrecy can't be mathematically proven; or even discussed soundly without a precise description. $\endgroup$
    – fgrieu ♦
    Jan 19, 2017 at 19:19
1
$\begingroup$

It can never be safe to reuse a one time pad, regardless the "conditions". If the pad is processed or mixed in any mathematically deterministic way, there will be a mathematical relation between the pads and you don't have one time pads anymore but you have two deterministic related keys. Insecure!

The only way to reuse a pad is to take all its values and rearrange them in a truly random order. However, in that case, you simply created a new truly random one time pad, which is the same as simply creating a new one time pad.

Some (snake oil) vendors believe it's possible to use a single one time pad, distribute it to two persons and then use some key-update algorithm that "mixes" the key so that it can be used again, without having to distribute a new one time pad key. Since the keys of both users have to be re-mixed the same way, you need a deterministic algorithm which, of course, creates a relation between all used keys. Let it be clear that such schemes are NOT one time pads are NEVER unbreakable.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is your "rearrange" reuse case correct? If a 200 character OTP doesn't have the number 25 in it (randomly possible) all remixes of that pad will also not have 25 in it. Carried infinitum, is that still truly random? Can someone confirm this statistically? $\endgroup$
    – Paul Uszak
    Feb 25, 2017 at 13:28
  • $\begingroup$ With an alphabet of 2 (as any alphabet would be reduced to binary anyway) there are only 1s and 0s. A key of n digits would have 2^n possible forms. When you already have a key you can rearrange it in n! / (k! * (n-k)!) ways (k=# of 0s). It's clearly a much smaller space that may or may not be enough to compromise the security. Maybe someone could deduce the restricted key-space or the number of 1s and 0s, leading to better than random predictions. $\endgroup$
    – user43032
    Jun 15, 2017 at 20:29
0
$\begingroup$

No the priposed encryption would be very weak indeed. It is usually fairly easy to fetch the key from using a one time pad twice based on some knowledge of the plain text. Adding a rotation of a not very long key would in the worst case be n times harder then breaking a regular one time pad used twice. So regardless if what exactly you know about the plain text and how you plan to use this to break the one time pad adding a key rotation doesn't make much of a difference.

In many cases it is even simpler then that.

For example if we know part of the plain text of one message we know part if the key and can quickly scan the rotation possibilities until the section decrypted looks like a message fragment at this point you both found the rotation and already decrypted part of the message.

If for example the two messages are known to be English language but with no known section we can calculare n-gram distributions of two xored english messages. Go over the possible rotations and chosse the one when xoring the two messages gives an n-gram distribution most like the expected. We remove the rotation first and then the problem.ia reduced to a normal on time pad used twice.

If instead of two messages of length n you have many messages each with their own rotation it is still not secure even though you end up using up many more log(2n) bits for encrypting your rotation using a real one time pad.

Improve this answer
$\endgroup$
-1
$\begingroup$

If we violate the 1-time rule by a single re-use, the resulting effective key is half the length of the plaintext, and no more random than plaintext hashed against plaintext is. The cryptanalyst can XOR the 2 encrypted strings together, and thereby get the same result that XORing the 2 plaintext strings together would produce.

Example:

P: 01000001,01000010 (plaintext string -- dec 65,66 -- ASCII A,B)
K: 11101100,11101100 (repeated random string -- dec 236,236 -- ASCII ∞,∞)
P ⊕ K =
E: 10101101,10101110 (encrypted string -- dec 173,174 ASCII ¡,«)

E1 (E 1st ½): 10101101 (dec 65 ASCII ¡)  
E2 (E 2nd ½): 10101110 (dec 66 ASCII «)  
E1 ⊕ E2 = R: 00000011 (dec 3 -- ASCII Bell)

P1 (P 1st ½): 01000001 (dec 65 -- ASCII A)
P2 (P 2nd ½): 01000010 (dec 66 -- ASCII B)
P1 ⊕ P2 = R: 00000011 (dec 3 -- ASCII Bell)

It's no longer an unbreakable cipher.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't think this addresses the question, since it was not about staightforward key-reuse. $\endgroup$
    – Maeher
    Feb 17, 2018 at 15:22
  • $\begingroup$ How is it not about straightforward key reuse? If you intercept 2 messages that use the same key, you can XOR them together and get the same result that you would get if you were to XOR the 2 plaintexts together. Look at line 2 of the example and you'll see the same key re-used. $\endgroup$
    – sysprog
    Feb 17, 2018 at 19:16
  • $\begingroup$ I parsed your use of "it" to mean "this" as the antecedent, but on reflection, I think you probably meant "the question" as the antecedent. Re-using the key loses entropy, and shifting the offset adds back only the randomness of the shift value. $\endgroup$
    – sysprog
    Feb 17, 2018 at 19:23
  • $\begingroup$ Your answer is about straightforward key reuse. The question was not. The question was about some "clever" (though ultimately doomed) attempt to use a slightly longer key and randomization to sidestep the problems of key reuse. Therefore you do not answer the question. $\endgroup$
    – Maeher
    Feb 17, 2018 at 19:27
  • $\begingroup$ I think that understanding how the consequence of a sing full-length key re-use, specified as "2n" is loss of entropy of a magnitude of ½nmakes it clear why random shufflings of length <½n don't rescue from that $\endgroup$
    – sysprog
    Feb 17, 2018 at 19:43

Your Answer

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

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