mistake Analysis on the Information-Theoretic Proof about Perfect Secrecy of OTP

Analysis on the Information-Theoretic Proof about Perfect Secrecy of OTP Yong WANG (School of Computer and Control, GuiLin University Of Electronic Technology, Guilin City, Guangxi Province, China, 541004) snipped-for-privacy@126.com Abstract: This paper analyzes the information-theoretic proofs about perfect secrecy of OPT and points out that the information-theoretic proof is not proper to prove OPT is perfectly secure. The sticking point lies in the values under different conditions are confused and the condition that ciphertext is a fixed value is not conscious. It is also pointed out that the similar mistake may take place when information theory is used to prove other propositions. Keywords: one-time-pad; cryptography; perfect secrecy; information theory; probability theory

1=2E Introduction Shannon put forward the concept of perfect secrecy and proved that one- time-pad (one-time system, OTP) was perfectly secure [1, 2]. For a long time, OPT has been thought to be unbroken and is still used to encrypt high security information. In literature [3], example was given to prove that OPT was not perfectly secure. In literature [4], detailed analyses about the mistake of Shannon's proof were given. It was proven that more requirements were needed for OTP to be perfectly secure and homophonic substitution could make OTP approach perfect secrecy [5]. Literature [6] analyzed the problem and gave ways to disguise the length of plaintext. In literature [7], the cryptanalysis method based on probability was presented, and the method was used to attack one-time-pad. Literature [4] considered an especially understanding following which OTP could be thought perfectly secure if some added conditions were satisfied. In literature [8], the especially understanding was confirmed not to be Shannon's notion. We know Shannon first proved that OTP was perfectly secure, but his proof is very simple. Detailed proofs about perfect secrecy of OTP were given by later scholars who used Shannon's proof for reference. The detailed proofs were found to be wrong for they took different conditions as the same [9]. This paper analyzes the mistake of information-theoric proof about perfect secrecy of OPT. 2=2E The information-theoric proof about perfect secrecy of OTP A majority of proofs about perfect secrecy of OPT are based on probability theory, including Shannon's, but some proofs are based on information theory [10, 11]. The information-theoric proofs can be found from textbooks and lectures. Some of the information-theoric proofs are not very clear-cut. The following is a representative proof. Theorem: The OPT is a perfect cipher for every PM. Proof: Suppose M, C and K are plaintext, ciphertext and key of one- time pad respectively. When given the plaintext and the ciphertext, then the key is uniquely determined, i.e., H(K|MC) =3D 0. Similarly, we have H(M|CK) =3D 0 and H(C| MK) =3D 0. Suppose N is the block length, then we can get H(K) =3D N. As M and K statistically independent, so we have I(M; K) =3D 0. I(K; C|M) =3D H(K)=A3=ADI(M; K)=A3=ADH(K|CM) =3D N, So I(M; C) =3D 0 holds because H(Y) =A1=DClog2 |Y| =3D N. OPT is perfect secrecy.

Fig.1 Perfect secrecy of one-time pad

3=2E Analysis on the proof The proof is based on information theory, so we should analysis the problem from the view of information theory. It can be seen from Shannon's formula and proof that the conditional entropy is gained from fixed joint probability distributions. The above proof confuses the probabilities and entropies under different conditions like other proofs about the perfect secrecy of OPT. As we have pointed out there were complex and crytic conditions in OTP that influenced the probability of plaintext, key and ciphertext. The proof did not realize the crytic condition that ciphertext was a fixed value (even though unknown) rather than a random variable. One would think it is not necessary to take that ciphertext was a fixed value (even though unknown) as a condition. We can see that by the following analysis. In OPT, when considering the case of encryption, the ciphertext is a random variable, in that case, the number of the possible values of cipher is infinite. It is very complex to deal with the probability distribution and the entropy of ciphertext, but if we set the possible value of ciphertext as a fixed (certain) value, then the number of the possible values is finite. When considering the case of intercepting the ciphertext, the ciphertext is a fixed value, so it is very proper to set the ciphertext as fixed value. We illustrate to show the condition that ciphertext is a fixed value influences the probability distributions of plaintext and key and thus influences the entropies: The plaintext space, ciphertext space and key space of OPT are all (0, 1) with the keys being equally likely. It is known beforehand that the prior probability P(M=3D0) =3D 0.9 and P(M=3D1) =3D 0.1. Then the probabili= ty of plaintext is P(M=3D0) =3D 0.9 and P(M=3D1) =3D 0.1 under the case of encryption. When only considering that the ciphertext is fixed (even though unknown) and all the keys are equally likely, for there is a one-to-one correspondence between all the plaintexts and keys, so the probabilities of the corresponding plaintext and key are the same. As all the keys are equally likely, so all the plaintexts are equally likely, that is, the probability of plaintext being 1 is 0.5 under that condition. As the probability distribution obtained above isn't consistent with the prior probability distribution, when the above conditions and the prior probability are both considered, the final probability distribution of plaintext should be a compromise of the two and unequal to the prior probability distribution. It is similar to the probability distribution of key when ciphertext as a fixed value is considered. The probabilities of plaintexts change when the cipher as a fixed value(even though unknown) is considered, and it is the same when ciphertext is intercepted, thus OPT is not perfectly secure as perfect secrecy implies that the posterior probability and the prior probability of plaintext are the same. We can get different probability distributions and joint probability distributions of plaintexts, keys and ciphertexts under the case of encryption and the case that the ciphertext is a fixed value. Then some of the values of Fig.1 would be different under the two cases, such as H(M). The above proof may be correct before the conclusion that OPT is perfect secrecy is gained if all values such as the entropies, condition entropies and the joint probability distributions are under the same case, but we can find that the values relative to M is under the case of encryption, that is, the case that ciphertext is not fixed and the values relative to C is obviously under the case of decryption, that is, the case that ciphertext is intercepted and fixed, for only under that case can I(M; C) =3D 0 ensure that OPT is perfectly secure. All the values in Fig.1 should be under the same case and the same joint probability distributions. But in the proof, the values are not under the same case, the covert condition that ciphertext is fixed is sometimes unconsciously considered and sometimes ignored. That results in confusion and mistake. Maybe someone would take the prior probability as the probability under the consideration that ciphertext is fixed, but we can find from the proofs about the perfect secrecy of OPT and background that it is not the view of Shannon. Detailed analysis was given in literature [8]. The proof analyzed in literature [9] also shows it is not the view of cryptographists and cryptographic community. 4=2E Conclusion This paper gives analysis on the mistake in information-theoric proof and confirms OPT is not perfect secure. Similar to other proofs, the mistake lies in the confusion of the different conditions as the same. Though OPT is not perfectly secure and not completely unimpeachable, it still has a lot of good statistical properties and can be used in cases of superior security. The similar mistakes may exist in the applications of information theory, especially in cryptography. It should be emphasized that the mistake attributes to the covert condition and the complexity of the problem, but not the mind of the famous cryptographist. Acknowledgements I would like to take this chance to express my sincere gratitude to Raymond W. Yeung for pointing out the ref. [11]. My gratitude also extends to the scholars who gave various opponent views which help me to give more comprehensive analysis and clearer statement. This work has been supported by Guangxi Science Foundation under grant 0640171 and Modern Communication National Key Laboratory Foundation under grant 9140C1101050706.

Reference [1]. Bruce Schneier, Applied Cryptography Second Edition: protocols, algorithms, and source code in C[M],John Wiley &Sons,Inc,1996 [2]. C.E.Shannon, Communication Theory of Secrecy Systems [J], Bell System Technical journal, v.28, n.4, 1949, 656-715. [3]. Yong WANG, Security of One-time System and New Secure System [J], Netinfo Security, 2004, (7):41-43 [4]. Yong WANG, Fanglai ZHU, Reconsideration of Perfect Secrecy, Computer Engineering, 2007, 33=A3=A819=A3=A9 [5]. Yong WANG, Perfect Secrecy and Its Implement [J], Network & Computer Security,2005(05) [6]. Yong WANG, Fanglai ZHU, Security Analysis of One-time System and Its Betterment, Journal of Sichuan University (Engineering Science Edition), 2007, supp. 39(5):222-225 [7]. Yong WANG, Shengyuan Zhou, On Probability Attack, Information Security and Communications Privacy, 2007,(8)=A3=BA39=A3=AD40 [8]. Yong WANG, Confirmation of Shannon's Mistake about Perfect Secrecy of One-time-pad,

[9]. Yong WANG, Mistake Analyses on Proof about Perfect Secrecy of One- time-pad, [10]. Massey, J.L., An introduction to contemporary cryptology, Proceedings of the IEEE, 1988,76 (5):533 - 549 [11]. Raymond W. Yeung, A First Course in Information Theory, Springer, 2002: 116