home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7153 < prev    next >
Encoding:
Internet Message Format  |  1993-01-26  |  4.1 KB
  1. Xref: sparky sci.crypt:7153 alt.security.pgp:601
  2. Newsgroups: sci.crypt,alt.security.pgp
  3. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!rz.uni-karlsruhe.de!stepsun.uni-kl.de!uklirb!posthorn!vier!neuhaus
  4. From: neuhaus@vier.informatik.uni-kl.de (Stephan Neuhaus (HiWi Mattern))
  5. Subject: Re: Was Sidelnikov right???
  6. Message-ID: <neuhaus.727974150@vier>
  7. Sender: news@posthorn.informatik.uni-kl.de (News system account)
  8. Nntp-Posting-Host: vier.informatik.uni-kl.de
  9. Reply-To: neuhaus@informatik.uni-kl.de
  10. Organization: University of Kaiserslautern, Germany
  11. References: <7V2qXB1w165w@tornado.welly.gen.nz>
  12. Date: Mon, 25 Jan 1993 15:02:30 GMT
  13. Lines: 83
  14.  
  15. Hi.
  16.  
  17. I don't know if anybody of the PGP dev team has already posted it here
  18. (my newsfeed has been down for some time).  Here is a response.
  19.  
  20. The disturbing part of Simon's findings come of his using the wrong
  21. null hypothesis.  The correct hypothesis should have been:
  22.  
  23. H0: Cn is distributed normally with mean mu and std. deviation sigma,
  24.  
  25. and not
  26.  
  27. H0: Cn == mu
  28.  
  29. With this modified hypothesis, the experimental results agree much
  30. better.  In particular, 65% of the values are between mu +- sigma, and
  31. 95% of the values are between mu +- 2sigma.  Just to make myself
  32. perfectly clear: I'm not modifying the hypothesis to make the results
  33. fit, the modified hypothesis is what *ought to* happen in the case of
  34. no correlation anyway.  So no reason to worry.  Well, not about the
  35. results of *this* test, anyway.
  36.  
  37. Simon, you said that all you read was that there was an investigation
  38. going on, but no results.  The reason why I have so far not published
  39. my own findings (all negative, by the way) is that I'd like to have a
  40. complete analysis ready before publication.  I don't like to post a
  41. series of partial findings; posting the whole story at once gives me
  42. the opportunity to present my findings in a unified framework.  I'll
  43. make preliminary reports (and code) available to interested parties,
  44. of course.
  45.  
  46. I am currently investigating yet another way in which PGP's IDEA keys
  47. could be dangerously bad.  For this, I need the probability
  48. distribution of the uncertainty coefficient of y given x, U(y|x).
  49. This is defined by
  50.  
  51.     U(y|x) = (H(y|x) - H(y)/H(y))
  52.  
  53. Where H(y|x) is the entropy of y given x and H(y) is the entropy of y.
  54. Does anybody know where one might look to find an expression for
  55.  
  56.     P (U(y|x) <= u),
  57.  
  58. the probability distribution of U(y|x)?  (Maybe I'm just stupid and
  59. it's staring me right in the face.  In this case, please be patient
  60. with me. :-)
  61.  
  62. If I could do this, then we'd probably be rid of nonrandomness claims
  63. once and for all, since I could then post (or make available by other
  64. means) a program that will test if it is possible to predict (with any
  65. not-too-small degree of certainty) any bit in PGP's IDEA keys provided
  66. that one already knows any set of key bits.  Then, if somebody claims
  67. that, e.g., bit 23 depends strongly on bits 1, 29, 56, and 127, there
  68. would be an immediate way to test this.  This test should make all
  69. other tests superfluous, except of course an equidistribution test on
  70. the individual bits, which is trivial to make (it is a chi-square
  71. test).  Also, this test measures the cryptographically important
  72. thing.
  73.  
  74. In effect, we would then have established the following results:
  75.  
  76. 1. PGP's IDEA key bits are equidistributed in {0, 1}.
  77. 2. These key bits are independent in that the knowledge of any key
  78.    bits does not help in predicting any other key bits.
  79.  
  80. These tests could then be applied to the output of IDEA as well, i.e.,
  81. IDEA-encrypted files.
  82.  
  83. What more could one want?  (One could want to test the dependence of a
  84. set of key bits in one key and one bit in the next key in the
  85. sequence, but that's probably ridiculous because PGP uses the current
  86. time to seed the RNG---this is not the only thing that's used, I
  87. should add--- so any dependence would then vary from person to person,
  88. depending on his or her pattern of usage, and would probably be
  89. impossible to exploit in a general way.  Also, it does not help in
  90. cracking the first IDEA key.)
  91.  
  92. Have fun.
  93.  
  94. -- 
  95. Stephan <neuhaus@informatik.uni-kl.de>
  96. sig closed for inventory.  Please leave your pickaxe outside.
  97. PGP 2.1 public key available on request.  Note the expiration date.
  98.