🚀 go-pugleaf

Hi.

I don't know if anybody of the PGP dev team has already posted it here
(my newsfeed has been down for some time).  Here is a response.

The disturbing part of Simon's findings come of his using the wrong
null hypothesis.  The correct hypothesis should have been:

H0: Cn is distributed normally with mean mu and std. deviation sigma,

and not

H0: Cn == mu

With this modified hypothesis, the experimental results agree much
better.  In particular, 65% of the values are between mu +- sigma, and
95% of the values are between mu +- 2sigma.  Just to make myself
perfectly clear: I'm not modifying the hypothesis to make the results
fit, the modified hypothesis is what *ought to* happen in the case of
no correlation anyway.  So no reason to worry.  Well, not about the
results of *this* test, anyway.

Simon, you said that all you read was that there was an investigation
going on, but no results.  The reason why I have so far not published
my own findings (all negative, by the way) is that I'd like to have a
complete analysis ready before publication.  I don't like to post a
series of partial findings; posting the whole story at once gives me
the opportunity to present my findings in a unified framework.  I'll
make preliminary reports (and code) available to interested parties,
of course.

I am currently investigating yet another way in which PGP's IDEA keys
could be dangerously bad.  For this, I need the probability
distribution of the uncertainty coefficient of y given x, U(y|x).
This is defined by

	U(y|x) = (H(y|x) - H(y)/H(y))

Where H(y|x) is the entropy of y given x and H(y) is the entropy of y.
Does anybody know where one might look to find an expression for

	P (U(y|x) <= u),

the probability distribution of U(y|x)?  (Maybe I'm just stupid and
it's staring me right in the face.  In this case, please be patient
with me. :-)

If I could do this, then we'd probably be rid of nonrandomness claims
once and for all, since I could then post (or make available by other
means) a program that will test if it is possible to predict (with any
not-too-small degree of certainty) any bit in PGP's IDEA keys provided
that one already knows any set of key bits.  Then, if somebody claims
that, e.g., bit 23 depends strongly on bits 1, 29, 56, and 127, there
would be an immediate way to test this.  This test should make all
other tests superfluous, except of course an equidistribution test on
the individual bits, which is trivial to make (it is a chi-square
test).  Also, this test measures the cryptographically important
thing.

In effect, we would then have established the following results:

1. PGP's IDEA key bits are equidistributed in {0, 1}.
2. These key bits are independent in that the knowledge of any key
   bits does not help in predicting any other key bits.

These tests could then be applied to the output of IDEA as well, i.e.,
IDEA-encrypted files.

What more could one want?  (One could want to test the dependence of a
set of key bits in one key and one bit in the next key in the
sequence, but that's probably ridiculous because PGP uses the current
time to seed the RNG---this is not the only thing that's used, I
should add--- so any dependence would then vary from person to person,
depending on his or her pattern of usage, and would probably be
impossible to exploit in a general way.  Also, it does not help in
cracking the first IDEA key.)

Have fun.

-- 
Stephan <neuhaus@informatik.uni-kl.de>
sig closed for inventory.  Please leave your pickaxe outside.
PGP 2.1 public key available on request.  Note the expiration date.