2

A one-time pad is known to be theoritcally secure, nothing can break it. However, if the key is reused, the one time pad becomes theoritically breakable.

But even RSA is theorically breakable yet it's widely used because it's practically secure. So, is a One-Time pad with a sufficiently long looping key practically secure?

If it's secure, how long does the key need to be in order for it to become practically unbreakable on a modern PC?

If it's insecure, why? how does one break it?

An example of a looping OTP Key:

LemonLemonLemonLemon........

1
  • 4
    Your "looping one-time-pad" is known as Vigenère cipher. Many-time-pads are very weak, you can recover a lot with merely two repetitions and nearly everything with three. May 12, 2014 at 14:41

4 Answers 4

7

The one-time pad is trivially breakable if the key is reused in any way.

C1 xor C2 results in P1 xor P2 where C1 and C2 are the two pieces of ciphertext encrypted with the same key and P1 and P2 are the corresponding plaintext.

You can then recover the plaintext with the following method. You take a common word or phrase that may appear in the plaintext (such as " the ") and xor that against the result of P1 xor P2. If one of the plaintexts had the text of the crib (" the " in our example), then the result of the xor is what the other plaintext had in that position. If neither plaintext contains the text of the crib, it is very likely that the result of the xor is just gibberish.

You simply continue this technique until you recover enough of the plaintext to guess the rest from the context. This attack is known as crib dragging.

5
  • Is this practical with a long key? Say, 1KB / 1MB. May 11, 2014 at 14:29
  • 1
    @HelloWorld Yes.
    – user10211
    May 11, 2014 at 14:32
  • Thank you. I will look deep into this. What if the key size is unknown to the attacker? May 11, 2014 at 15:10
  • if the key is reused enough times the attacker would be able to find the key size anyway, without too much difficulty.
    – pacifist
    May 12, 2014 at 4:01
  • The key length is the same or bigger than the plaintext length. So practical... If you think that managing this size of keys is practical then fine, but you have other options that are less a pain in the ass. May 12, 2014 at 10:57
2

A "repeating OTP" is not only theoretically breakable, it's trivially breakable, breaking it is the homework assignment of the first lesson of a collage cryptography course.

The only reason OTP is unbreakable is that the key isn't reused, XOR encryption with a repeating key is highly vulnerable to just about any cryptanalysis tool in existence, if you know anything about the encrypted data you can get a lot of useful plain text even with just two repetitions - and with any real-world amount of data it's practically guaranteed all the data and the key are easily recoverable.

OTP is actually a bad trade off - it improves "unbreakability" (a area other system such as RSA and AES are very good at) in exchange for very complicated key management (an area where there are practically no usable solution in existence that can support the massive keys required for OTP) - so - OTP improves something we are already very very good at the cost of requiring something that doesn't exist.

2
  • 1
    If the parties to the communication will be in a position to securely exchange sufficient quantities of key material at some time before they need to exchange secrets over an insecure channel, some forms of OTP can be decoded without electronics. For example, pair the pixels on a sheet of paper and have both the encoded message and a decoding transparency print either the upper or lower pair of each pair black. Correctly overlay the transparency on the paper and the message will be readable, but the paper or transparency alone would simply have a random pattern of upper and lower dots.
    – supercat
    Jul 28, 2014 at 15:25
  • Using computers for cryptography may be more convenient, but it may be difficult to guarantee there are no side-channel attacks (e.g. adversaries with electromagnetic snooping equipment). For cases where unusual forms of OTP are sufficient, they may have some advantages in that regard: a key that never exists in electronic form cannot be intercepted electronically.
    – supercat
    Jul 28, 2014 at 15:28
1

It is trivial to find out the length of the looping key using statistical methods such as by counting the index of coincidence of the ciphertext messages. Once the length of the looping key is obtained, an attacker can simply xor a string of ciphertext with another string shifted the length of the key and the resultant xor is essentially plaintext xored with plaintext. The English language has enough redundancy for an attacker to algorithmicaly determine the plaintext of the two messages from this point.

This attack is viable for any looping key whose length is known. Increasing the size of the loop does not prevent an attacker from finding out its length, so it is fundamentally insecure to use looping keys.

You may look up Index of Coincidence to get a grasp of how the length of the looping key can be determined.

1

A one time pad, if used multiple times by repetition or "looping", is no longer a one time pad. It becomes a very weak encryption scheme with a long key.

If you insist on looping long data key structures, try looping two or more, each of different big prime number length, each incrementing in parallel. That would be slightly less trivial to crack.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .