Including the next random One Time Pad as part of the encoded message?

Question

I've tried to do something very simple here, which is to encrypt a message with a one-time-pad (OTP) and include the next OTP as part of that same encrypted message. i.e. The first message consists of the actual text of the message and then the next OTP added to the end. The length of the OTP should always stay the same, so I did some simple bit manipulation to squeeze more than one character into a byte. So that means that every succesive OTP will be the same length as the original OTP.

My main question: Is the fact that the next OTP is included at a known location in every encoded message a factor that will allow decryption of the messages given a few encrypted messages? Or will it be as secure as a normal OTP?

Answer 1

Is the fact that the next OTP is included at a known location in every encoded message a factor that will allow decryption of the messages given a few encrypted messages? Or will it be as secure as a normal OTP?

Yes, that's a big problem.

You're practically transporting the (next) OTP you're adding at the end of your ciphertext in the open. Differently put: you're sharing the (next) secret unprotected and in plain sight of any potential attacker.

This is especially true when assuming we – as we usually do – respect Kerckhoffs’ principles. The attacker would know that you’re adding the next OTP to the end of the current ciphertext, and can therefore extract the next secret easily.

Even when we wouldn’t respect Kerckhoffs’ principles and keep your construction secret, it wouldn’t be too hard for an attacker who intercepted merely 2 transmissions to grasp what you’re doing… which includes that the attacker also gains the bonus of being able to simply decrypt that 2nd intercepted message, and also gaining knowledge of the next OTP you’re going to use for transmission number 3. That’s definitely not what you want…

OTP security claims

You’re somewhat violating the definition of OTP (points 2, 3, and maybe 4):

Per definition, OTP requires the “key“ to be…

1. a truly random one-time pad value,
2. generated and exchanged in a secure way.
3. at least as long as the message, and
4. only to be used once.

I’ll leave it up to personal opinion if your idea aditionally violates point 4, as that depends a bit on the individual point of view. While others might disagree, I personally see something which might be interpreted as reuse.

In the end, that doesn’t reall matter because violating points 2 and 3 is already more than enough to say that the usual OTP security claims are in no way applicable when looking at your construction.

Other problems related to your construction

Please note we’re not yet talking about potential authentication issues – for example: you need to think about an attacker intercepting your messages, modifying them, and then forwarding them without you being able to detect the modification. In most scenarios, this is disastrous. Fact is, OTP itself doesn’t handle authentication by nature… that’s where MACs come in.

TL;DR:

• Never, ever share/transmit a secret (here: next key) in an unprotected manner.
• Always think about authentication, because simply encrypting something doesn’t mean it’s safe from being forged. You should – at least – be able to detect message forgery.

---

EDIT

This edit include the comments posted to this answer, to make the answer more complete and to safeguard the infos contained so they don't vanish when comments get cleaned up (aka deleted).

OP: Hi e-sushi, thx for your detailed answer. I think perhaps you're misunderstanding. I'm not including the next OTP at the end of the cypher text, but as part of the cypher text. So basically I'm doing what Daniel described: "... padding the ends of messages with random data, encrypting (message + random), then decrypting and collecting the random data at the end, and using this later as another one time pad ...". The first pad will be exchanged in a secure way of course and all subsequent "compressed" pads will be the same length as the message. Yep, will still get to MAC thx :-)

ME: Same problem… as you're including the next OTP with the current message. So, xorring the 2nd half of message 1 with the first half of message 2 will reveal the key you included in message 1… which allows decryption of the first half of message 2.

ME: In the end, you’re having a chicken-and-egg problem (better pidgeon hole problem) there. OTP key should be 100% length of plaintext. So, you can’t add plaintext to your “next OTP“ as that would not be OTP anymore. The only solution is that you do bit fiddling which would overlap and boils down to a double-XOR… $(m \oplus nextOTP) \oplus currentOTP)$. There’s no way to create an OTP going $(m | nextOTP) \oplus currentOTP$ because $nextOTP$ and $currentOTP$ MUST have the same length. Otherwise you wouldn’t be able to transmit that next OTP. Even in an optimal case, each transmission would halve the space available to transmit the next key material.

OP: Aha, okay I see, so it's leads to the same problem as re-use of an OTP. Oh well, I thought maybe it was a nice way to get new pads distributed. Never role one's own encryption, lol. The best is just to include info of where to get the next pad in the message, or use a book, or some stream of random data seeded with a random key perhaps.

ME: @Sci Yep, which is why I mentioned that “ While others might disagree, I personally see something which might be interpreted as reuse.“ in my answer. ;) Indeed, including a hint (on the location where to find the next OTP) in your plaintext message seems more logic as it voids the issue. Related to adding a MAC to the whole thing just to make it safer and more complete – simplest would probably be a HMAC (hash-based MAC). Please see Should we MAC-then-encrypt or encrypt-then-MAC?. It's not difficult to add but you need to do it correctly.

EDIT 2

Last but not least, @tylo's comment completes it:

I think this answer has most of the essentials, but there is one misconception, which is not adressed yet: Due to the Kolomogorov complexity a real one-time-pad can not be compressed on average. And using a "compressible OTP" would not be truly random and uniform.

Answer 2

Yes, but the actual message would be limited to the size of the original one time pad. Suppose the OTP was 100 bytes, and you included a new, 50 byte OTP for use in the next message. In effect, your payload in the first message is only 50 bytes, and the next message can't be longer than 50 bytes.

Answer 3

If you are padding the ends of messages with random data, encrypting (message + random), then decrypting and collecting the random data at the end, and using this later as another one time pad, then it's OK.

But this way you are still only transferring say 10 megabytes of data for 10 megabytes of key, just the padding may be done in a way not to eat your key.

That said you may want to just pad after the message is encrypted, the only reason I can think of doing it the first way is if you have some odd attacker that after some time has access to the original keys but not recorded eavesdropping of all the communications.

Answer 4

Here's a less mathy and more philosophical reason why your system can't work. Think of what you're trying to do. You're sending out new key material encrypted with old key material, in the presence of listening adversaries. Now run it continuously. Alice could send infinite amounts of information to Bob with Eve listening, all without exchanging other key material out of band whilst claiming perfect secrecy. You would have hypothetically developed a system akin to quantum information exchange, but without the quantum bit nor the associated physics security proof.

Such improvements to the one time pad appear here from time to time. Can I securely refill a one time pad over the same connection is an example of another similar attempt.