1

This question already has an answer here:

This is an absolute noob question - so please be gentle with me! I see that similar questions have been asked - but I think mine is different!

Apart from being wasteful on storage space, what is the weakness in the following simple encryption scheme? Assume truly random means from a natural source - such as cosmic microwave background...

Use an initial one time pad created from a truly random source which is at least twice the length of any conceivable message that could be sent. Compose messages with two equal sized parts: 1) The plain text message. 2) An update to the OTP composed of truly random data. Both parts encrypted against the original OTP. When a message is received the first half is decrypted against the OTP to reveal the plain text. Then the second half is decrypted to reveal the update OTP. Replace the initial OTP with the update OTP.

It seems to me that the strength of the OTP is preserved isn't it?

No part of the OPT gets used twice against plain text - it is immediately replaced by random data. The parts of the OTP that do get reused are used against random data. Assuming the update is truly random this couldn't be used to deduce the OTP and therefore also the update, could it?

Example encryption:

  1. Bob and Alice both store initial key 9462367503982349.
  2. Alice encrypts her message "FLEE!","66676" using part of key 9462367503 and sends it to Bob.
  3. Alice changes the part of her pad used to encrypt "FLEE!" using "66676"
  4. Bob receives and decrypts back to "FLEE!","66676".
  5. Bob has received the message which is "FLEE!"
  6. Bob changes the part of his pad used to encrypt "FLEE!" using "66676"
  7. Both Alice's and Bob's pad is now 6667667503982349
  8. Bob encrypts a reply "THANKYOU", "73613451" using part of pad 6667667503982349
  9. Bob changes his pad so it reads 7361346103982349
  10. Alice receives and decrypts back to "THANKYOU", "73613451"
  11. Alice changes her pad so it reads 7361346103982349

In all cases a part of the pad is only used once to encrypt a plain text message and then it gets a replacement part. Parts of the pad are used multiple times to encrypt random data - but that doesn't matter because it doesn't reveal anything about the pad. If Eve intercepts a message the plain text part has been encrypted against a part of the pad that has only ever been used once. She would have to crack the encryption used on the random update part of the message to gain any information. The problem for Eve is that there are no clues because its a random pad encrypting random data. Every time Eve intercepts a message its been encrypted using a changed pad.

List item

marked as duplicate by Xander, Anders, Steffen Ullrich, Matthew, Gilles Dec 13 '16 at 12:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • See also this Crypto.SE question and the various questions it's marked a dupe of... – gowenfawr Dec 12 '16 at 18:32
  • To my understanding a truly random pad used multiple times to encrypt truly random data does not leak information. Using a random pad multiple times on data containing information is when it begins to leak information - and that is not what I proposed. – DSK Dec 12 '16 at 21:51
  • I think that "73613451" should become "73613461" in step 8 and 10, is that correct? – Lekensteyn Dec 12 '16 at 22:02
  • @DSK No, see my answer to the question in my previous comment to see how this becomes a two-time pad with a single extra step. – Xander Dec 12 '16 at 22:05
  • Yes, its a typo. Now I'm attempting to understand @Xanders argument - which might take some time... – DSK Dec 12 '16 at 22:28
2

Any re-use of the OTP is fatal. What you are proposing is effectively a "two-time pad" which for sure does not have the same security properties.

Attempting to model your cipher in a particular setting:

Given plaintexts Pi of k bits and an initial key K0 of 2k bits:
K0 = K0a K0b

The corresponding ciphertext is the concatenation of the encryption of the Pi and the "update OTP" K1a:
C0 = C0a C0b
C0a = K0aP0
C0b = K0bK1a

The key is updated to:
K1 = K1a K0b

In the next round we have:
C1 = C1a C1b
C1a = K1aP1
C1b = K0bK2a

Note the re-use of K0b. The key is updated to:
K2 = K2a K0b

In the next round we have:
C2 = C2a C2b
C2a = K2aP2
C2b = K0bK3a

Now we can recover:

(C0bC1b) ⊕ C1a
= (K0bK1a) ⊕ (K0bK2a) ⊕ (K1a ⊕ P1)
= (K1aK2a) ⊕ (K1a ⊕ P1)
= K2a ⊕ P1

Your cipher already fails a chosen-plaintext attack. As you can see above, one can recover the decryption key K2a if you know P1. This allows you to recover P2.

This shows why your cipher is broken.

  • The plain text is not used to change the pad at any time. The part of the key previously used for the encryption is replaced with new random data. This is not at all the same as using a pad twice. – DSK Dec 12 '16 at 21:22
  • If a plain text message of all zeros is entered then it will only reveal the part of the key that was used that one time. After the message was transmitted and received the part of the pad used gets changed to a new random value. A requirement of this scheme is that the update part of the message is truly random data - the sender doesn't get to choose it... – DSK Dec 12 '16 at 21:35
  • @DSK See the updated example, reuse is fatal, period. – Lekensteyn Dec 12 '16 at 23:02
  • Yes, it is absolutely broken. Well done. – DSK Dec 13 '16 at 8:02

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