When does multiple OTP encryption become insecure if new keys are permuted? ​ 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.
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.