Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Consider the One-Time Pad (OTP). Suppose two parties, A and B, generate a completely random secret key in a real-life meeting, and they keep this secret. Now A wants to send some message to B using the OTP. The point is that in the OTP we can use any key only once. So we have to come up with a system to share a newly chosen key in a secret way.

Why cannot A just concatenate a new randomly generated secret key (needed for the next communication between the two parties using the OTP) to this message?

For instance, A could concatenate this new key at the beginning of the message. (Supposing they have agreed upon a fixed key-length beforehand, so that B is able to tell which is the new key and what was the "actual" message.) In this way A and B would agree on a new secret key which they can then use for their next communication.

Probably this is insecure, but I do not immediately see why…

share|improve this question
    
I'm guessing that you are hoping that C would not realise that you have concatenated the OTP-key to the message. But is that a risk you are willing to take? If C does not realise, I guess it could definitely work. –  BlackAdder Oct 11 '13 at 8:04
    
@Ricky Demer I do not understand your answer at all. Obviously I do not mean with "this message" the ciphertext - obviously why would I send the key out in the open? So, obviously, I mean to concatenate a new key to the plaintext, and then to encrypt this. Your sentence *"if "this message" is the plaintext, then that doesn't actually help, since encrypting the new secret –  user8850 Oct 11 '13 at 15:57

3 Answers 3

Let's say Alice and Bob have $c$ bits of pre-shared secret key material. Alice generates $a$ bits of new key material, concatenates it to a message $M$ that is $b$ bits long, and uses $a+b$ bits of their pre-shared key material to encrypt "message||new-key". She sends this secure message to Bob, who decrypts it with the shared key. Now they both have $a$ bits of new shared key-material, but in order to securely send those $a$ bits and the $b$ bit message $M$ they had to burn through $a+b$ bits of the previous key material. The total key material they now have to encrypt future messages is:

$c-$ (Amount spent to send "message||new-key") + $a$.

The term (Amount spent to send "message||new-key") = $a+b$, so the amount they have left is:

$c-(a+b)+a$,

$= c-a-b+a$,

$= c-b$.

So they are no better off now than if Alice had simply send the $b$ bit message $M$ alone without an appended new key.

share|improve this answer
1  
That's exactly the point. You cannot "enlarge" your key material with the approach in question. What you do is you "replace" $a$ bits of your original key material with $a$ new key-bits and consequently this is equivalent as using the $a$ bits from your original key to encrypt the next message. –  DrLecter Oct 12 '13 at 13:53
    
What if a random seed is appended to each message, and both parties use that seed with a PRNG to generate the next key? –  Hello World Aug 24 at 12:47

If "this message" is the plaintext, then that doesn't actually help, since encrypting the new secret key uses up an amount of the old pad equal to the length of the new secret key, the total length
of all "actual messages" will still be limited to the total length of the original one-time pad.

If "this message" is the ciphertext, then an eavesdropper will trivially know the new "secret" key.

share|improve this answer

If you want to store the OTP for MsgB in MsgA then the new length of MsgA = Len(MsgA) + Len(OTP).

As Ricky Demer pointed out the pad must be at least as long as the message so the new length is in effect = Len(MsgA) + Len(MsgB). So why not just arrange a OTP of Length = Len(MsgA) + Len(MsgB) and divide it up for the two messages rather than this futile nested approach?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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