EDIT: please move to crypto (just realized it is the wrong one and "You can only post once every 40 minutes.")

Suppose I give a sufficiently long key in a secure way (in person) to Alice.

I send her a file that is XORed with the key I initally gave her. In the file, there contains the message and a new, sufficiently long key.

Alice then creates a file and XOR with the key that is contained in my message. (Alice's file contains her message and a new key)

What weaknesses are there to this approach? (Suppose too that we pad all messages with random bytes such that the file is 100 KiB in size)

  • the weakness is you still only have 100kb of pad, so you should just keep the original pad and use an EOF marker to delimit. needless "rekeying" can reveal flaws in your pad generation that might otherwise be missed. – dandavis Nov 10 '17 at 6:10
  • I'm not voting to migrate this to crypto at this point in time because I sense it would be closed there for a lack of detail. See How to Ask here and on crypto. – Tobi Nary Nov 10 '17 at 7:32

What you're describing is the perpetual-motion version of a one-time pad. It doesn't work; the space you have to share the next pad gets shorter with every message. Any given bit in a one-time pad can only be used to encrypt one bit of message.

Let's say you a gave 100KB pad ("key") to Alice. You then send her a 50KB file; this takes 50KB of your pad. You can, if you want, use the last 50KB to send a new pad.*

Alice now has only 50KB of pad that have never been used (the 50KB that were sent under the encryption of the original pad, following the file). She wants to send you a 30KB message, so she encrypts it with the never-used pad and then uses up the rest of that pad - another 20KB worth - to send you a new random pad. The rest of the message is padded out with random bytes to be the same length as the first message.

If Alice were to try using those 50KB for anything real (like more key material), she'd have to re-use part of a pad that had already been used, violating the "one-time" nature of the pad and moving it from "theoretically unbreakable" to "undergraduate homework assignment in the first week of the class" (assuming the new key material were ever itself used as a "one-time" pad).

You now only have 20KB of pad that have never been used. This is after exchanging 80KB of actual messages. It is not a coincidence that these numbers sum up to the original 100KB of pad you exchanged initially. You can't add additional entropy (randomness / unpredictable numbers) into the system except by exchanging further keys.

*As you may have noticed, there's no reason to burn 50KB, 20KB, or whatever of one-time pad sending a new one-time pad. The amount of new key material conveyed is the same as the amount of old key material made useless. You may as well just not use the leftover part of the original pad until you need it for actual message content.

Modern crypto algorithms, which are vastly more complicated than XOR (though they may use XOR as part of the full cryptographic scheme), have ways of "stretching" a key so it can encrypt data longer then itself, without exposing the key (even indirectly) the way XOR does. This is, for example, how all stream ciphers work; they take a key, and from that key they can produce a near-infinitely-long stream of pseudo-random values (that is, they look random if you don't know what they're generated from) that can be used for encryption and decryption (via XOR). The fact that you can never re-use any part of that stream isn't a big deal; it's possible to make it super long, and you can potentially send another key - that will itself get stretched to a long stream - if you get near the end. The total security of this scheme is only (at best) as good as the original key - if the original key was only 40 bits long, for example, it's only going to take at most a bit over a trillion attempts to figure out how to decrypt the entire message including the key used for the next bit - but with sufficiently long keys (128+ bits) that's usually acceptable.

It is worth noting that even modern ciphers are not necessarily as strong as their key length implies. For example, the RC4 stream cipher (which uses 128-bit keys) was recently found to be breakable (at least for the early part of the message) if you can capture a few millions or billions of bytes of messages (plus some guess-and-check, with more guessing needed for less data captured). This is because the "keystream" - the pseudo-random one-time-pad-like-data generated from a given key - was found to be not actually random enough; it has biases (a given bit was not equally likely to be zero or one) that could be discovered by examining enough encrypted text where the corresponding plaintext is known, and using the knowledge of those biases to break the encryption on ciphertext whose plaintext is not known.

  • 3
    "perpetual-motion version of a one-time pad" - nice way of summarizing the problem. – Steffen Ullrich Nov 10 '17 at 5:29

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.