Double encryption - One Time Pad

Question

Can the security of the encryption system be improved by using double encryption with two randomly chosen keys?

By double encryption I mean using two keys $K_1$ and $K_2$, each 20-bit long, to obtain ciphertext $C = ( M ⊕ K_1 ) ⊕ K_2$.

Answer 1

The answer is we cannot improve the security of the one-time pad in this manner. Intuitively the reason is that the double one-time pad is just a less efficient one time pad.

The security of the traditional xor-based one-time pad is requires that the key $K$ is chosen uniformly at random for each message and that the key is at least as large as the message.

Because the xor operation is associative, we could re-write the double one-time pad as $C = M \oplus(K_1 \oplus K_2)$ or $ C = M \oplus K$, where $K = K_1 \oplus K_2$. Now if $K_1$ and $K_2$ are uniform, it is easy to show that $K$ is also uniform. Assuming the key and the message have length $n$

$P_K[k] = \sum_{x \in \{0,1\}^n}P_{K_1,K_2}[k_1 = x, k_2 = k \oplus k_1] = \frac{1}{2^n}$

In other words $K_1 \oplus K_2$ could be simply replaced by a single uniform key, therefore $K_1$ is enough. Moreover the double one-time pad is inefficient because it requires two xor operations.

---

Regarding cascade encryption, Maurer and Massey showed that cascade encryption is as strong as the first cipher. Matthew Green's blog post is a nice (easy to read) summary of multi-encryption security.

Answer 2

For the one-time-pad the answer is no, since it already achieves information-theoretic security (meaning that the ciphertext is statistically independent from the plaintext). So, applying it twice doesn’t add any extra security (and may actually worsen security if the second key is not independent from the first).

Answer 3

Yes, this can improve security, but only against a cryptanalytic advance in the method you used to generate one of $k_1$ and $k_2$. This is known as a cipher cascade, and there is a theorem of Maurer and Massey (paywall-free) that breaking the composition of independent stream ciphers like this is at least as hard as breaking the hardest to break of the component stream ciphers. This theorem holds in general only when the two ciphers commute, as they do in this case.

But most of the time, your concern should be focused on making sure that you don't reuse pads and that you are, overall, using cryptography responsibly. As a responsible application developer, you shouldn't be reaching for a one-time pad directly any more than you should be reaching for the letters A-E-S directly: the one-time pad model for stream ciphers and the AES pseudorandom permutation family are design principles for the internals of cryptography. You should instead use authenticated ciphers like NaCl crypto_secretbox_xsalsa20poly1305 or AES-GCM. If you put all your attention on what is just about the least interesting idea in cryptography imaginable (xor), the adversary will break everything else about your system long before they break Salsa20 or AES.

Answer 4

The intention of a good cipher is to remove all orders and bit arrangements in a plaintext and produce output ciphertext in which there is no distinguishable orders and arrangements obtainable.I mean that the ciphertext should be a uniform distribution.

By considering this remark, if we have a good encrypted output(means plaintext which is encrypted with a good encryption algorithm ex AES),we can not find bit orders on it and re-encrypting the same output is might be ineffective. In other words, imposing more security affections on the second encrypted ciphertext based on using the same cipher with another key is not remarkable, However we can not give a global rule for this.

An obvious example of this cipher types is 2DES (or even 3DES). This cipher, encrypts a plaintext with 2 different keys. Again the security of ciphertext rely on the DES structure. but we should consider that the whole system(2DES or 3DES) is vulnerable to meet-in-the-middle attack and in this situation and also the key space is not the sum of keys( k1+k2).

Therefore using ciphers in this manner is not more common. but if we want to encrypt a plaintext with two different ciphers with different keys, the whole structure gives more stamina to ciphertext against cryptanalysis.

And about One-time pad encryption, this cipher has a perfect security, so imposing another encryption with different key is waste of time and resources.