When does multiple OTP encryption become insecure if new keys are permuted? ​

Question

I understand that OTP encryption fulfils perfect secrecy, meaning you can't decrypt the encrypted text to it's original plaintext (and know that this plaintext is indeed the original plaintext) unless you possess the OTP key.

Let's assume this:

• Alice creates a truly random alphabetical stream of 10 characters (key).
• The key is shared with Bob (we assume that it's secure and no one else can get knowledge of the key)
• Now Alice can encrypt a text with length $\le$ key-length
• Encrypted text is sent to Bob
• Bob can decrypt the encrypted text with the key

---

Now the "new" part:

Alice again wants to sent a message to Bob by using OTP-encryption. But instead of creating a completely new truly random OTP key, Alice permutes the previously used OTP key. This permuted key is then used for further OTP encryption/decryption. The permuted key is checked with previous keys to ensure that no encryption happens with an identical key.

We assume that Bob always receives the new (permuted) key over a secure channel and no one else (ever) knows the key. We also assume that no one else knows any plaintext messages before/after encryption/decryption.

---

Example of keys:

$k_1 = \text{gubapqrytt}$ (truly random)

$k_2 = \text{permute}(k_1) = \text{ptyaqgtbur}$

$k_3 = \text{permute}(k_2) = \ldots$

---

• Does this affect the security of OTP?

• When is the first message vulnerable to decryption by an adversary?

• Do all further keys (if none get leaked) still provide perfect secrecy?

---

EDIT:

We assume that all keys are kept secret and no keys will be leaked (no matter how unrealistic this might seem). I'm only concerned if this scheme would somehow be vulnerable to any known attacks, like frequency-analysis, since the key has always the same characters.

Answer 1

Does this affect the security of OTP?

Yes, it destroys the notion of a OTP and your system reverts to an algorithmic cipher with it's strength equivalent to the strength of the scrambling method. This becomes a permutation of the OPT, so mathematically this is noticeable due to non repetition of characters. It's difficult to compute as the plain text can change, but 10! combinations is < 4 million. Say root that to ~1900 and I'd be uncomfortable sending more than that if every message is different.

When is the first message vulnerable to decryption by an adversary?

Imagine @fgrieu's suggestion of a plain text leak. The first one. And then the next message is the same plain text, say "No change." And the larger contextual/semantic environment hasn't changed. The probability that the same message was resent must be >> 0 as all the letters are there (albeit translated). A modern adversary will not only use maths, but sociology and psychology as well.

I can't do the maths, but the certainty will quickly pile up if you keep sending "No change." There might even be a formula for this. A simple way to view it is to drop the initial OTP bit as the transpositions become fixed. All you have remaining for security is permutation (under some RNG seed?) And we don't do that.

I think that you have a sense of the answer by referring to frequency analysis yourself.

Do all further keys (if none get leaked) still provide perfect secrecy?

It follows that if the system is no longer a true OTP, perfect secrecy cannot possibly exist.

We assume that Bob always receives the new (scrambled) key over a secure channel and no one else (ever) knows the key.

Isn't this the issue with OTP systems? If this channel exists, then pure OTP is the solution rather than this derivation. As a small note, there is also the issue of message integrity to consider which seems absent from the proposed scheme - the usual OTP caveats.

Answer 2

This is an inconsequential variation on a two-time pad and falls just as readily.

Say your pad is $n$ symbols long. Fix a permutation $\pi \in S_n$ of $\{1,2,\dots,n\}$—this is determined by your $\operatorname{permute}$ operator. If the pad is $(p_1, p_2, \dots, p_n)$ and the $i^{\mathit{th}}$ message is $m_i = (m_{i,1}, m_{i,2}, \dots, m_{i,n})$, then the $i^{\mathit{th}}$ ciphertext $c_i = (c_{i,1}, c_{i,2}, \dots, c_{i,n})$ where $$c_{i,j} = m_{i,j} + p_{\pi^{i-1}(j)}.$$ Here $\pi^i(x) = \pi(\pi(\cdots \pi(x)\cdots))$ is the $i$-fold iteration of $\pi$, with $\pi^0(x) = x$.

So far this is just a restatement of your system, with specific names given to each symbol in the message, pad, and ciphertext.

If I learn the ciphertext $c_1$ of a single known message $m_1$, then I can trivially recover your pad by $$p_j = p_{\pi^0(j)} = c_{1,j} - m_{1,j},$$ and then decrypt the next ciphertext $c_2$ or any other by simply permuting the pad $(p_1, p_2, \dots, p_n)$ with $\pi$.

Obviously, if I don't know $m_1$ exactly but can narrow it down to a small set of options, then I can narrow down the $p_j$ to a small set of options too, and thus narrow down $m_2$, and so on.

In general, if the pad for the first message is $p$, the pad for the second message is $F(p)$, the pad for the third is $F^2(p)$, etc., where $F$ is a fixed function of pads (in this case, $F(p_1, \dots, p_n) = (p_{\pi(1)}, \dots, p_{\pi(n)})$), the stream cipher you get is completely broken. When $F$ is a permutation with an easily computed inverse, as it is here, a known plaintext anywhere among the messages is enough to decrypt all other messages, even prior ones.

For the same reason, $\operatorname{MD5}(k) \mathbin\| \operatorname{MD5}^2(k) \mathbin\| \cdots$ makes for a terrible stream cipher even though $\operatorname{MD5}(k \mathbin\| 1) \mathbin\| \operatorname{MD5}(k \mathbin\| 2) \mathbin\| \cdots$ is basically fine.