Security Analyses of One-time System
wangyong
Yong WANG
(School of Computer and Control, GuiLin University Of Electronic
Technology ,Guilin City, Guangxi Province , China, 541004)
hel...@126.com
Abstract—Shannon put forward the concept of perfect secrecy and proved
that some kinds of cryptosystems are perfectly secure. The paper
analyzes Shannon’s proof that some kinds of cryptosystems were of
perfect secrecy and points out that Bayes’ theorem was used mistakenly
in his proof because of his mixing up the probabilities under
different conditions. An example is given to show that one-time system
is not perfectly secure and this leads to a foundation for further
study of cryptosystem’s secrecy.
Index Terms—probability, one-time system, cryptography, perfect
secrecy
I. Introduction
One-time system (one-time pad) has been thought to be unbreakable
since 1859[1]. Shannon put forward the concept of perfect secrecy and
proved that some kinds of cryptosystems, including one-time system,
are perfectly secure [2]. For a long time, its prefect secrecy is not
questioned. Recently it is found that Shannon’s attestation to prove
that one-time system is perfectly secure is false. In the literature
[3-5], Shannon’s mistake was analyzed from different aspects. One-time
pad is found not to be perfectly secure and betterment was given. In
the literature [6], the cryptanalysis method based on probability is
presented though the method cannot give certain result, and the method
is used to attack one-time pad . In this paper, the author will give
analyses on the problem.
II. Shannon’s statement and proof about perfect secrecy
Shannon defined perfect secrecy by requiring of a system that after a
cryptogram is intercepted by the enemy the a posteriori probabilities
of this cryptogram representing various messages be identically the
same as the a priori probabilities of the same messages before the
interception. The following is Shannon’s proof:
Let us suppose the possible messages are finite in number M1,…,Mn and
have a priori probabilities P(M1),…, P(Mn), and that these are
enciphered into the possible cryptograms E1…,Em by
E=TiM.
The cryptanalyst intercepts a particular E and can then calculate, in
principle at least, the a posteriori probabilities for the various
messages, PE(M). It is natural to define perfect secrecy by the
condition that, for all E the a posteriori probabilities are equal to
the a priori probabilities independently of the values of these. In
this case, intercepting the message has given the cryptanalyst no
information. Any action of his which depends on the information
contained in the cryptogram cannot be altered, for all of his
probabilities as to what the cryptogram contains remain unchanged. On
the other hand, if the condition is not satisfied there will exist
situations in which the enemy has certain a priori probabilities, and
certain key and message choices may occur for which the enemy’s
probabilities do change. This in turn may affect his actions and thus
perfect secrecy has not been obtained. Hence the definition given is
necessarily required by our intuitive ideas of what perfect secrecy
should mean.
A necessary and sufficient condition for perfect secrecy can be found
as follows: We have by Bayes’ theorem
in which:
P(M)= a priori probability of message M
PM(E)= conditional probability of cryptogram E if message M is chosen
i.e. the sum of the probabilities of all keys which produce cryptogram
E from message M.
P(E)= probability of obtaining cryptogram E from any cause.
PE(M)= a posteriori probability of message M if cryptogram E is
intercepted.
For perfect secrecy PE(M) must equal P(M) for all E and all M. Hence
either P(M)=0, a solution that must be excluded since we demand the
equality independent of the values of
P(M), or
PM(E)= P(E)
for every M and E. Conversely if PM(E)= P(E) then
PE(M)= P(M)
and we have perfect secrecy. Thus we have the result:
Theorem 1. A necessary and sufficient condition for perfect secrecy is
that
PM(E)= P(E)
for all M and E. That is, PM(E) must be independent of M.
Stated another way, the total probability of all keys that transform
into a given cryptogram E is equal to that of all keys transforming Mj
into the same E, for all Mi,Mj and E.
Now there must be as many E’s as there are M’s M’s since, for a fixed
i, Ti gives a one-to-one correspondence between all the M’s and some
of the E’s. For perfect secrecy PM(E)= P(E)≠0 for any of these E’s and
any M. Hence there is at least one key transforming any M to any of
these E’s. But all the keys from a fixed M to different E’s must be
different, and therefore the number of different keys is at least as
great as the number of M’s. It is possible to obtain perfect secrecy
with only this number of keys, as one shows by the following example:
Let the Mi be numbered 1 to n and the Ei the same, and using n keys
let
TiMj=Es
where s=i+j(Mod n). In this case we see that PE(M)=1/n=P(E) and we
have perfect secrecy. An example is shown in Fig. 1 with s=i+j-1(mod
5).
Perfect systems in which the number of cryptograms, the number of
messages, and the number of keys are all equal are characterized by
the properties that (1) each M is connected to each E by exactly one
line, (2) all keys are equally likely. Thus the matrix representation
of the system is a Latin square[2].
Fig. 1 Perfect system
III. Counterexamples for the perfect secrecy of one-time system
In order to discover the mistake and educe the below analysis, the
following counterexample is given to show that one-time system is not
perfectly secure.
Example 1: The plaintext space is M = (0, 1). According to the prior
condition that is generally the correspondence context, it is first
known that the prior probability of plaintext being 0 is 0.9, while
the prior probability of plaintext being 1 is 0.1. The ciphertext
space is C = (0, 1) and the key space is K = (0, 1) and the keys are
equally likely. The cryptoalgorithm is one-time system. Later the
information is obtained that the ciphertext is 0. When only the later
information is considered(regardless of the prior probability of
plaintext), for the fixed ciphertext, there is a one-to-one
correspondence between all the plaintexts and keys, so it can be
concluded that the plaintexts are equally likely, that is, the
probability of plaintext being 1 is 0.5. As the probability obtained
above isn’t consistent with the prior probability, the compromise is
needed. The compromised posterior probability of the plaintext would
be no more than the larger and no less than the smaller of the two
corresponding probabilities of the two conditions.
When considering the probability, the different conditions should be
distinguished. For the above example, there are mainly several
conditions, including the prior probability distribution of M, and the
condition about the cryptosystem, probability distributions of C,
probability distributions of K, and value of C. Under different
condition, we get different probability distributions of plaintext.
According to the mapping of M, K and C, the probabilities of M, K and
C are complicatedly interactional. In the above example, the
probability of plaintext changes when the ciphertext is fixed, even
though the ciphertext is unknown.
IV. Analyses of Shannon’s Mistake
We can find that Shannon had the result PE(M)=1/n in his example
above. According to the definition of perfect secrecy,
PE(M)= P(M)
We can get that P (M)=1/n, but the prior probabilities of the
plaintexts are seldom the same as 1/n. So there maybe some mistakes in
Shannon’s proof. As perfect secrecy require PE(M) = P(M) = 1/n, one-
time system is not perfectly secure unless P(M) = 1/n.
The following is the analyses of the mistakes in Shannon’s proof.
Shannon used Bayes’ theorem to prove Theorem 1 and put PE(M)= P(M)
into the equation. There is a crytic presupposition is that all the
probabilities in the equation
are under the same precondition. That is to say, in the equation, P(M)
and P(E) are the probabilities under the condition which we call prior
condition. PE(M) is the probability of M under both conditions of the
prior condition and the condition of E’s value. PM(E) is the
probability of E under both conditions of the prior condition and the
condition of M’s value.
But we can find that P(M) is the probability under the prior condition
and PE(M) is the probability under the condition that E and the key’s
probability distribution are known. The two probabilities are not
under the same prior condition. Relative to P(M), the condition of
PE(M) is not only the value of E, but also E is a fixed value, and the
mapping of M, K and C. Therefore strictly speaking, PE(M) should be
PEFG(M) if we call other condtions as F and G, so PE(M) ( strictly
speaking, PEFG(M)) cannot be put into the equation. But Shannon did
and educed the wrong conclusion. When only considering the conditions
that E and the key’s probability distribution are known, we can infer
that all the plaintexts are equally likely for one-time system gives a
one-to-one correspondence between all the M’s and some of the K’s when
E is fixed (even though unknown). But the prior probabilities of
plaintexts are seldom equally likely, so the probability isn’t
consistent with the prior probability. When considering all the
conditions, the compromise is needed. The compromised posterior
probability of the plaintext would not be the same as prior
probability, then we have the result
PE(M) ≠ P(M)
We can find that the probability distribution of M changes when
considering C is a fixed value, but not a random variable (even though
C is unknown). That is the sticking point of the mistake.
As we take the PE(M) as the probability under all the conditions, it
must be a compromise between the probabilities under the sectional
conditions. In the literature [6], we gave an algorithm to compromise
the two probability distributions. As the probabilities under each of
the two conditions are usually inconsistent, The compromise is not the
same as any of the probabilities, so we can usually get the same
result that PE(M) ≠ P(M) and one-time system is not perfectly secure
unless in particular case.
>From Shannon’s result that PE(M)=1/n, we can see Shannon completely
ignored the prior condition when he considered the posterior
probability, so that posterior probability is unilateral. We can
affirm Shannon’s mistake by using his result to get cockeyed result.
Using Shannon’s result that the given example is perfectly secure, we
can get PE(M)= P(M), as Shannon got PE(M)=1/n, so we can get P(M)=1/n.
But that is wrong for plaintexts are seldom equally likely.
What’s more, there is another crytic presupposition in Shannon’s proof
that the plaintext should all be the same in length. But usually the
plaintext cannot meet the presupposition. When the ciphertext is
intercepted, the ciphertext length is known as L. The length of all
possible plaintext must be L for one-time system; otherwise, the prior
probability is not the same as the posterior probability that is
zero.
V. Conclusion
>From the above analyses, we can find that one-time system is not
perfectly secure unless extra conditions are given. In despite of
that, it has good cryptographic property. We can take measures to
improve its security.
Reference
[1]. Bauer, F.L. Decrypted Secrets-Methods and Maxims of
Cryptology[M], Berlin, Heidelberg, Germany: Springer-verlag, 1997.
[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, Perfect Secrecy and Its Implement [J],Network &
Computer Security,2005(05)
[5]. 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
[6]. Yong WANG, Shengyuan Zhou, On Probability Attack, Information
Security and Communications Privacy, 2007,(8)：39－40