home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7154 < prev    next >
Encoding:
Internet Message Format  |  1993-01-26  |  7.6 KB
  1. Xref: sparky sci.crypt:7154 alt.security.pgp:602
  2. Path: sparky!uunet!olivea!decwrl!waikato.ac.nz!comp.vuw.ac.nz!cavebbs!tornado!sai
  3. From: sai@tornado.welly.gen.nz (Simon McAuliffe)
  4. Newsgroups: sci.crypt,alt.security.pgp
  5. Subject: The Sidelnikov Saga... Now he's wrong again.
  6. Message-ID: <D0F1XB1w165w@tornado.welly.gen.nz>
  7. Date: 26 Jan 93 11:52:00 GMT
  8. Organization: Tornado BBS, Wellington, New Zealand.
  9. Lines: 193
  10.  
  11. A while ago, I wrote:
  12.  
  13. > It looks like _THIS_IS_ what Dr. Sidelnikov also did, and it means one
  14. > of three things:  (ranked in order of likelihood as I see it)
  15. >
  16. >    1)  Both Dr. Sidelnikov and I stuffed up.
  17. >
  18. >    2)  This correlation test isn't appropriate for this situation.
  19. >
  20. >    3)  Something funny is going on and either the RNG is badly
  21. >        implemented or IDEA has a problem.
  22. >
  23. > Number 1 sounds like the most likely and number 3 is just plain scary.
  24.  
  25. After looking at things more closely, I have decided that both number 1
  26. and number 2 are true.  This is not to say that a correlation test is
  27. not suitable, but that the correlation test performed was meaningless.
  28.  
  29. The correlation formula posted recently makes good sense, but looking at
  30. the formula for the mean, you can't help feeling something is wrong.
  31.  
  32.                     1
  33.            mu  =  -----,  n >= 2
  34.                   n - 1
  35.  
  36. Correlation is basically a fairly simple idea.
  37.  
  38.             |       .     .        |                 .    |         .
  39.             | .  .            .  . |                      |  .
  40.             | .  . .          . .  |               .   .  |      .
  41.          . .|  .                .  | .                    |.
  42.   ----------+----------  ----------+----------  ----------+----------
  43.     .  .   .|                      |  . .        .  .   . |       .
  44.    .     .  |                      |..      .         .   | .
  45.      .      |                      |  .     .      .      |     .
  46.             |                      |     .                |
  47.  
  48.      Correlation ~1         Correlation ~-1        Correlation ~0
  49.  
  50. Very roughly and informally, when the data is plotted as above
  51. correlated data tends to form fuzzy lines.  A positive gradient gives a
  52. positive correlation and a negative gradient gives a negative
  53. correlation.  In our situation the correlation is close to 0, we are
  54. just trying to decide if it is close enough.
  55.  
  56. Okay, back to the formula for the mean.  Substituting n = 2 into the
  57. equation yields mu = 1.  Really?!  Lets now imagine placing two points
  58. on our graph.  The correlation measures how good a line forms between
  59. all the points.  With only two points there is a perfect line.  Given
  60. any two random (continuous) points connected by a line we must either
  61. have a positive gradient or a negative gradient (assuming a probability
  62. of 0 of them being horizontally or vertically adjacent).  If the
  63. gradient is positive we have a correlation of 1, and if the gradient is
  64. negative we have a correlation of -1, therefore the expected value
  65. (mean) of the correlation for n = 2 is
  66.  
  67.      mu = P(gradient is -ve) * -1 + P(gradient is +ve) * -1
  68.  
  69.         = -0.5 + 0.5
  70.  
  71.         = 0
  72.  
  73. Not only does the working above show this to be true, but intuitively
  74. you would expect random numbers to be completely uncorrelated and
  75. therefore have a correlation value of 0.  Why then does the formula give
  76. a value of 1?  This is the maximum possible value of correlation, how
  77. can we have a maximum as the mean?!
  78.  
  79. This problem is also true for n = 3, n = 4 and upwards, it just becomes
  80. less ridiculous for larger n.
  81.  
  82. Correlation values range from -1 to +1.  A formula which is always
  83. positive must be a little worrying in this case.  Should the correlation
  84. be biased towards positive?  Why so?  Why not negative? The random
  85. variables are supposedly from a uniform distribution. The mean simply
  86. _MUST_ be 0 for a truely random source.  Not just "nearly random."  For
  87. any given random sample, we won't actually get a value of 0, but the
  88. expected value (the mean) is _EXACTLY_ 0. If this were not true, there
  89. would never really be any random numbers.
  90.  
  91. So I think we can assume that the given equation is not really what it
  92. was intended to be.  I don't know what Knuth's book really says because
  93. I don't have it, but perhaps there was something lost in the posting of
  94. it?
  95.  
  96. If we take the square of the correlation values, then the mean variation
  97. from 0 seems to be roughly equal to this function.  This hasn't been
  98. tested of course, but there is a tendency there.  Perhaps then, this is
  99. what the equations are (the mean deviation from the mean of the squared
  100. correlation).  That's not the impression I got from the posting.  Never
  101. mind, in any case it isn't particularly useful.
  102.  
  103. I now know why my last test gave such suprising results.  Time to try a
  104. different approach.
  105.  
  106. We can still use the correlation data obtained earlier (see my last
  107. post).  Following is a list of the correlation values I used last time.
  108. These values are still valid as they do not involve the dubious
  109. correlation mean and standard deviation.  Each correlation value is
  110. taken from an independent sample of 1048576 bytes (524288 byte pairs).
  111.  
  112.     -0.000151
  113.      0.001282
  114.     -0.001413
  115.      0.001116
  116.      0.001013
  117.     -0.002072
  118.      0.000340
  119.     -0.001034
  120.     -0.001972
  121.     -0.000230
  122.      0.000508
  123.     -0.000425
  124.      0.002383
  125.     -0.001605
  126.      0.000506
  127.      0.002695
  128.     -0.001196
  129.      0.000450
  130.      0.000016
  131.      0.002822
  132.  
  133. We now wish to construct a hypothesis test with the null hypothesis
  134.                   _
  135.               H0: x  =  mu   (ie the data is random)
  136.  
  137. and the alternative
  138.                   _
  139.               H1: x =/= mu   (the data is _not_ random)
  140.  
  141.  
  142. The test statistic is,
  143.                          _
  144.                          x - mu
  145.                t  =  -------------
  146.                       s / sqrt(n)
  147.                 _
  148. where the mean, x is
  149.                   _
  150.                   x = 0.0001517
  151.  
  152. and the sample standard deviation, s is
  153.  
  154.                   s = 0.001463
  155.  
  156. As mentioned above, the mean correlation, mu is 0 for random data.
  157.  
  158. So we now have,
  159.  
  160.             t  =          0.0001517
  161.                    ---------------------
  162.                     0.001463 / sqrt(20)
  163.  
  164.                =    0.4634
  165.  
  166. This test statistic should approximate a t distribution with n - 1 = 19
  167. degrees of freedom.  So, to test H0 for truth at the alpha = 5% level,
  168. we require that
  169.  
  170.                0.4634  <   t      (19)
  171.                             0.05/2
  172.  
  173.         =>     0.4634  <   2.093
  174.  
  175. Which is obviously true, so at the 5% level we do not have enough
  176. evidence to reject H0.  In fact, for this test we have an observed
  177. significance level of 64.8% so we can clearly see that H0 cannot be
  178. rejected and we can safely assume that the data is indeed random[ish]
  179. (at least as far as a contiguous byte correlation test is concerned).
  180.  
  181. Of course what I have done here does not show that the random numbers
  182. are "cryptographically strong" it only shows that Dr. Sidelnikov's claim
  183. of "strong correlation between contiguous bytes" is false. He probably
  184. made the same mistake I made earlier!  There's nothing to say I didn't
  185. make more mistakes of course.  It wouldn't suprise me at all.  That's
  186. why you're here - to find my mistakes. :)
  187.  
  188. There may still be correlation between other bits.  I believe somebody
  189. is working on this area as we speak however.  There may also be other
  190. weaknesses in IDEA which result in weak random numbers. I imagine some
  191. people are working in this area too.
  192.  
  193. Anyway, I hope this is of more interest than my last balls-up.  And I
  194. hope that this isn't another one...  :-)
  195.  
  196.  
  197. Disclaimer:  As I said in my last post, I am not a statistician
  198.              by any stretch of the imagination.  Don't take what
  199.              I say as gospel.
  200.  
  201.  
  202.     Sai  (e-mail sai@tornado.welly.gen.nz)
  203.          (s-mail PO Box 3598 Wellington, New Zealand)
  204.