home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7059 < prev    next >
Encoding:
Internet Message Format  |  1993-01-21  |  8.5 KB
  1. Xref: sparky sci.crypt:7059 alt.security.pgp:583
  2. Path: sparky!uunet!munnari.oz.au!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: Was Sidelnikov right???
  6. Message-ID: <7V2qXB1w165w@tornado.welly.gen.nz>
  7. Date: Thu, 21 Jan 93 23:03:17 +1300
  8. Organization: Tornado BBS, Wellington, New Zealand.
  9. Lines: 189
  10.  
  11. After reading Dr. Sidelnikov's analysis of PGP I, along with many other
  12. crypt/pgp readers thought something must be wrong with his analysis and
  13. since nobody else seemed to be doing much other than saying it was being
  14. verified I decided to have a look myself.
  15.  
  16. Now I'm no statistics expert, in fact quite the opposite, so please
  17. excuse any blunders and try to forgive the rather informal treatment I
  18. give the problem.
  19.  
  20. PGP has three random number generators.  One of these is based on timing
  21. between keystrokes and I didn't look at this one.  I haven't looked at
  22. the code, but I guess it uses 4 bits from each 16 bit 8253 (PC version)
  23. timing value (since you need to enter twice as many keystrokes as random
  24. bytes you get from it).  And if the low 4 bits are used, I guess they're
  25. fairly random, and the MD5 hashing must help things along nicely too.
  26. In any case, I ignored all of this.
  27.  
  28. There are also two other random number generators.  One of these is not
  29. intended to be even remotely secure, in fact it is probably just about
  30. one of the simplest and least random of any RNG you have ever seen;
  31.  
  32.     static int randseed=0; /* used only by pseudorand() function. */
  33.     int pseudorand(void)
  34.     /*      Home-grown 16-bit LCG pseudorandom generator. */
  35.     {       randseed = (randseed*31421 + 6927) & 0xffff;
  36.             return (randseed);
  37.     }       /* pseudorand */
  38.  
  39. This random number generator is used when the "pool" of good random
  40. numbers from the first RNG (mentioned above) runs out.  However the
  41. number of values in the pool is alway sufficient for key generation etc
  42. so this RNG is never called for anything important. It will be called at
  43. several points when overwriting information in memory etc etc.
  44.  
  45. A function  randombyte()  returns a random number from the pool of good
  46. numbers or it returns a weak pseudo RN if the pool is empty.
  47.  
  48. I decided that perhaps Dr. Sidelnikov had seen this function
  49. randombyte() and decided that it was PGP's RNG and tested this one.  Of
  50. course without initialising the pool of numbers this function would
  51. return the terrible weak numbers.  This seemed to explain to me why PGP
  52. was failing the tests.
  53.  
  54. In fact this random number generator is so poor that it simply repeats a
  55. permuted sequence of 256 bytes over and over.  I tested the linear
  56. correlation and found it to be 0.016750.  Aha! Terrible!  Okay, that
  57. must be what Dr. Sidelnikov did.
  58.  
  59. In any case, I decided to check the third RNG as well (I was bored and
  60. there was always a chance he did test this after all).  The third RNG is
  61. used for creating random session keys for encryption of messages with
  62. IDEA.  The RNG itself uses IDEA to generate the random numbers.  In
  63. order to simulate PGP conditions fairly closely I generated my test data
  64. in blocks of 16 random bytes (as PGP does) just in case this has some
  65. effect.  For each collection of data, I generated 65536 blocks giving
  66. files of 1048576 (1 meg) in size and I created 20 such files.  This
  67. required a small change to crypto.c so that instead of rewriting the
  68. file each time, it stored it in main memory.  For each file, the "truely
  69. random" key timing random number generator was called for the initial
  70. seed value.
  71.  
  72. >     - the  sequence  of  random numbers has strong prevalences on
  73. > bytes (up to 0.05 ...  0.1 on material of 10000 byte) and  strong
  74. > correlation dependence between contiguous bytes;
  75.  
  76. Strong prevalences?  I assumed this to mean certain characters showed up
  77. more than others.  I found this hard to believe, since this must surely
  78. show some kind of weakness in IDEA so I tested this first:
  79.  
  80. I'm not sure how statistically valid my tests are, but I used a Chi^2
  81. goodness-of-fit-test to check if each occurence of byte values matched
  82. the flat distribution it should have.  Each byte should have occured
  83. 4096 times in a perfectly flat distribution. The following table shows
  84. the results and the observed significance level of the test (Chi^2 with
  85. 255 degrees of freedom).
  86.  
  87.        Roughness   | OSL (Chi^2(255))
  88.        ------------+-----------------
  89.        258.034668  |  43.51%          (high values in the OSL column
  90.        265.982422  |  30.54%           mean a good fit.  For testing
  91.        278.838379  |  14.60%           at level x%, any value >x
  92.        239.045898  |  75.56%           means the test is passed).
  93.        276.901855  |  16.54%
  94.        286.939941  |   8.25%
  95.        247.055176  |  62.78%
  96.        252.427734  |  53.38%
  97.        268.672363  |  26.62%
  98.        239.907715  |  74.29%
  99.        211.188477  |  97.90%
  100.        292.719238  |   5.22%
  101.        229.750977  |  87.02%
  102.        263.931152  |  33.71%
  103.        278.236816  |  15.18%
  104.        271.500977  |  22.82%
  105.        253.606934  |  51.27%
  106.        278.595215  |  14.84%
  107.        237.597168  |  77.61%
  108.        252.171875  |  53.83%
  109. Mean = 259.155249 --> 41.59%   (Can I really do this?  No?  Ooops...)
  110.  
  111. Well I'm not going into more detail on this one, but a hypothesis test
  112. at the 5% level (or 1%) shows the data to fit a flat distribution quite
  113. nicely.  So what did Sidelnikov mean?  Who knows...
  114.  
  115. Oh well so much for that, but what about the "strong correlation." This
  116. seems to be what has more people worried.  I decided to check this out
  117. next.  I had seen the correlation test a while ago, but didn't know the
  118. formula so I used the one posted. I had enormous trouble getting this to
  119. work because of the typo's but after looking at some books myself I
  120. found the correct formula in a statistics textbook (of course a
  121. correction has been posted now but a bit late).  Anyway, plugging in the
  122. numbers to the other formulae posted gives:
  123.  
  124.     mu    = 0.000001907
  125.     sigma = 0.001381073
  126.     for n = 524288  (half a meg)
  127.  
  128. So, we want to do some hypothesis tests something along the lines of;
  129.  
  130.   H0n: Cn  =  mu   (null hypothesis)
  131.   H1n: Cn =/= mu   (alternative hypothesis)
  132.  
  133. Following are the tests for each of the 20 sample files.  The table
  134. shows the correlation value, the normalised/standardised value and
  135. corresponding significance level.
  136.  
  137. We expect a critical value fairly near 0 when standardised if H0 is to
  138. be accepted.
  139.  
  140.         C     |  Crit +/-  |  Two sided OSL
  141.     ----------+------------+--------------
  142.     -0.000151 |  -80.1672  |  0.0000 (Ouch!  The OSL should be high
  143.      0.001282 |  671.1347  |  0.0000  if we want to accept H0)
  144.     -0.001413 | -741.8161  |  0.0000
  145.      0.001116 |  584.1032  |  0.0000
  146.      0.001013 |  530.1017  |  0.0000
  147.     -0.002072 |-1087.3206  |  0.0000
  148.      0.000340 |  177.2572  |  0.0000
  149.     -0.001034 | -543.1117  |  0.0000
  150.     -0.001972 |-1034.8920  |  0.0000
  151.     -0.000230 | -121.5858  |  0.0000
  152.      0.000508 |  265.3373  |  0.0000
  153.     -0.000425 | -223.8215  |  0.0000
  154.      0.002383 | 1248.3735  |  0.0000
  155.     -0.001605 | -842.4790  |  0.0000
  156.      0.000506 |  264.2887  |  0.0000
  157.      0.002695 | 1411.9508  |  0.0000
  158.     -0.001196 | -628.0461  |  0.0000
  159.      0.000450 |  234.9287  |  0.0000
  160.      0.000016 |    7.3886  |  0.0000
  161.      0.002822 | 1478.5351  |  0.0000
  162.  
  163. This is kinda frightening...  Every single test failed miserably,
  164. supporting the alternative hypothesis.  Even if I tried my best I
  165. couldn't fiddle these tests.  These tests simply cannot be passed at any
  166. significance level.
  167.  
  168. It looks like _THIS_IS_ what Dr. Sidelnikov also did, and it means one
  169. of three things:  (ranked in order of likelihood as I see it)
  170.  
  171.    1)  Both Dr. Sidelnikov and I stuffed up.
  172.  
  173.    2)  This correlation test isn't appropriate for this situation.
  174.  
  175.    3)  Something funny is going on and either the RNG is badly
  176.        implemented or IDEA has a problem.
  177.  
  178. Number 1 sounds like the most likely and number 3 is just plain scary.
  179.  
  180. Incidentally, it's of no consequence whatsoever, but just in case
  181. anybody wants know, there were no cycles in the 20 samples files. At
  182. least this is something!  Of course it really means nothing because
  183. using a 1048576 byte sample isn't really a sensible way of testing for
  184. cycles.
  185.  
  186. Well, after all this, perhaps Dr. Sidelnikov isn't just a crock. If I
  187. didn't make any mistakes, there may be something to what he says after
  188. all.  Can somebody who really knows some real statistics shed a brighter
  189. light on the subject?
  190.  
  191. I hope this has been of some interest/help in any case.
  192.  
  193.  
  194.  
  195.     Sai  (e-mail sai@tornado.welly.gen.nz)
  196.          (s-mail PO Box 3598 Wellington, New Zealand)
  197.  
  198.  
  199. PS Can we have a little more sci in sci.crypt?
  200.