How to prove a symmetric encryption scheme provides perfect secrecy?

I learned in class that in order to achieve perfect secrecy, the source of the plaintext $\mathcal{P}$ needs to be independent from the source of the encryption key $\mathcal{K}$. We also learned that this is always the case for independent sources: $H(\mathcal{P}) \le H(\mathcal{K})$, but that it shouldn't be used as an exhaustive proof, because in the case where you have a high-entropy key but it is badly designed (such as having different lengths for each code word), you could still derive a lot of information from attempted decryption.

We saw an example where someone used a coin to determine a random key composed of 16 bits to mask a plaintext composed of 4 digits coded into 4 bits each (using xor logic). In this case, $H(\mathcal{P}) = 13.2877$ (there are 10000 possible combinations of digits), and $H(\mathcal{K}) = 16$, so the inequality holds.

Suppose now that 8 bits of the key are generated randomly, and then just copied over for the remaining 8 bits. The key source and the plaintext source now become dependent, however only if the "hacker" knows that the key was copied twice over (because it is technically a possible outcome). The inequality doesn't hold anymore either because $H(\mathcal{K}) = 8$. I'm assuming that this encryption scheme fails to provide perfect secrecy, but I remain unconvinced because of my previous argument of the conditional state of this "copied" key. In this case, is there a better way to provide a proof other than the two methods mentioned above?

• Do you suppose the attacker has access to the encryption scheme? – Jean-François Gagnon Apr 4 '16 at 17:07
• @Jean-FrançoisGagnon Yes, he knows what method is used, just not the key. However, I just realised that I made a major mistake in the question, let me re-word it – Andres Stadelmann Apr 4 '16 at 17:08
• @Jean-FrançoisGagnon I just reread the theory, and it only talks about the entropy of the source of the encrypted text rather than the source of the key, clearly this changes things, but I'm really confused as to what is going on now (because it does talk about high entropy keys at a certain point...) – Andres Stadelmann Apr 4 '16 at 17:12

2 Answers

Xor-ing the first half of the encrypted message with the second gives the same result as xor-ing the first and second half of the original message. (When the key is duplicated). This contradicts perfect secrecy as some information can be obtained from the cyphertext.

• If the attacker doesn't know that the key is copied, he won't be able to use this to his advantage. Is this a valid counter-example? – Andres Stadelmann Apr 4 '16 at 17:29
• No, the attacker is assumed to know everything about the process, just not the key that was used. – bmm6o Apr 4 '16 at 18:16

Jean-François Gagnon's answer is fine and would serve as an obvious proof that this scheme does not provide perfect secrecy.

Now the fault in your thought process is actually that an attacker doesn't know that the key is "copied". This is a simple form of a key schedule which is assumed to be known to the attacker along with the encryption and decryption routines (commonly called $\operatorname{GenKey()}$). If you assume that the key schedule is part of the secret key, then cryptanalysis of any cipher gets extremely hard and in fact you could proof the many-time pad (with the key $1$) perfectly secure as "an attacker has no way to know we always used $1$ as key bit".