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$.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ An ideal one time pad already has perfect security, you can't just get twice as perfect. The second layer doesn't add much. $\endgroup$– NatanaelApr 10, 2019 at 21:20
-
$\begingroup$ $C = (M \oplus K_1) \oplus K_2 = M \oplus K^\prime$ where $K^\prime = K_1 \oplus K_2$. $\endgroup$– Future SecurityApr 11, 2019 at 18:13
-
$\begingroup$ Was the title changed? OTP doesn't match the given answers - this shows a severe lack of understanding of what was asked probably. $\endgroup$– tyloFeb 27, 2023 at 20:43
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
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.
answered Apr 10, 2019 at 22:35
-
$\begingroup$ The last paragraph is unnecessary and misleading. $\endgroup$– tyloFeb 27, 2023 at 20:39
-
$\begingroup$ @tylo, would you mind clarifying which part of text you are referring to, and what is the issue with it? $\endgroup$ Mar 21, 2023 at 10:44
-
$\begingroup$ The question doesn't ask about stream ciphers or any other concatenation (other than OTP) as it is written right now. Maybe the question was different back then, when you wrote the answer. $\endgroup$– tyloMar 21, 2023 at 11:54
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
4
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.
answered Apr 11, 2019 at 3:37
-
$\begingroup$ Er, now we have an answer that relies on the associativity and now yours that relies on commutation. I'm again at a loss; are they compatible notions in this case or is one of the two answers using the wrong property? I'd guess the other answer nailed it, but I've been wrong before on this. $\endgroup$– Maarten Bodewes ♦Apr 11, 2019 at 9:39
-
$\begingroup$ @MaartenBodewes, the case of double xor is an instance of the commutation property, since we could first xor with the second key and then xor with the first key and obtain the same result. $\endgroup$ Apr 11, 2019 at 9:53
-
1$\begingroup$ my first comment isn't actually helpful.. What I wanted to say is that, because of the associativity of xor we get a commutative multi-encryption. i.e $C = (M \oplus K_1) \oplus K_2 = M \oplus (K_1 \oplus K_2)$ by associativity, and $C = M \oplus (K_2 \oplus K_1)$ by commutative property of xor finally, $C = (M \oplus K_2) \oplus K_1$ by associativity. $\endgroup$ Apr 11, 2019 at 10:13
-
$\begingroup$ The theorem applies to any pair of ciphers $E$ and $E'$ such that $E_k \circ E'_{k'} = E'_{k'} \circ E_k$, i.e. any ciphers that commute. You can prove this for stream ciphers by the associativity and commutativity of xor. $\endgroup$ Apr 11, 2019 at 21:34
$\begingroup$
$\endgroup$
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.
answered Apr 10, 2019 at 21:31
-
1$\begingroup$ I'm not convinced that reencrypting the output of AES cannot strengthen the ciphertext in case weaknesses are found. For 2DES: even 2DES is more secure than single DES. It is not as strong as it should be given the doubling of the key size (which is actually also true for 3DES, only less so). So I'm finding myself disagreeing with a large portion of the answer (and agreeing with the last two sections). $\endgroup$– Maarten Bodewes ♦Apr 10, 2019 at 22:53
-
$\begingroup$ It is true that 2DES or 3DES is more secure than DES, but by imposing security in this case, we make it vulnerable to more obvious attack namely " meet-in-the-middle". In other words, this way of securing has its own costs. About encrypting a text two time with AES, we can not deny that reencryptying strengthens the output but again has its own costs and is not common as we have not seen 2AES or 3AES. $\endgroup$ Apr 11, 2019 at 6:37
-
$\begingroup$ Right, but I think in that case the word "useless" is at least overdoing it. I'd say cascading two ciphers may be useful if they provide non-perfect encryption. It's not that uncommon either. $\endgroup$– Maarten Bodewes ♦Apr 11, 2019 at 8:54
-