Path: cactus.org!cs.utexas.edu!howland.reston.ans.net!agate!ucbvax!hplabs!
+     unix.sri.com!csl.sri.com!boucher
From: boucher@csl.sri.com (Peter K. Boucher)
Newsgroups: sci.crypt

Subject: Maurer Constant Too Low
Message-ID: <2e2mp4INNglq@roche.csl.sri.com>
Date: 7 Dec 93 19:49:56 GMT
Organization: Computer Science Lab, SRI International
Lines: 97
NNTP-Posting-Host: redwood.csl.sri.com

I modified the Maurer test poster earlier by Dimitri Vulis
to get rid of the Q input.  Q is the number of ``random''
values to skip so that, hopefully, at least one of each 
value has been seen before the actual testing begins.  
Maurer suggested 10 * 2**L, where L is the number of bits 
in each ``random'' value being examined.

Instead, my version skips inputs until one of each value has
been seen (takes the guesswork out) and reports the number of
values skipped (still calling it Q).  I found that Maurer's 
constant was frequently too low, even for streams that passed 
with flying colors, especially for larger values of L.

Also, I noticed that, even for DES, rho varied significantly
for different keys.  Do DES experts think that one could
deduce information about the DES key from the rho value?

Some test results from various ``random'' sources follow.  
PRNG's were seeded with time(NULL)*getpid().  Ciphers were
used to encrypt a stream of all 0x00's, and had their keys 
generated by rand(), after seeding srand with time(NULL)*getpid().  
Reported Qs that were too big are underlined.

MAURER TEST of stdlib rand() function
Q=  64,fTU= 5.9999531,y=287.354,sigma=0.002722,E= 5.2177052,rho=0.0000 :-(

BCRP (toy block cipher) MAURER TESTS
Q=   173,fTU= 5.2169981,y=0.260,sigma=0.002722,E= 5.2177052,rho=0.7951 :-)
Q=   299,fTU= 5.2191143,y=0.518,sigma=0.002722,E= 5.2177052,rho=0.6047 :-)
Q=  2473,fTU= 7.1849573,y=0.135,sigma=0.009556,E= 7.1836656,rho=0.8925 :-)
Q=  2114,fTU= 7.1808539,y=0.294,sigma=0.009556,E= 7.1836656,rho=0.7686 :-)
Q=  3101,fTU= 8.1742630,y=0.331,sigma=0.006533,E= 8.1764248,rho=0.7407 :-)
Q=  4020,fTU= 8.1780504,y=0.249,sigma=0.006533,E= 8.1764248,rho=0.8035 :-)
Q=  8471,fTU= 9.1718933,y=0.096,sigma=0.004480,E= 9.1723243,rho=0.9234 :-)
Q=  8025,fTU= 9.1729920,y=0.149,sigma=0.004480,E= 9.1723243,rho=0.8815 :-)
Q= 82674,fTU=12.1685804,y=0.347,sigma=0.001470,E=12.1680700,rho=0.7285 :-)
   ^^^^^
Q= 73420,fTU=12.1684352,y=0.248,sigma=0.001470,E=12.1680700,rho=0.8039 :-)
Q=681882,fTU=15.1672143,y=0.334,sigma=0.000493,E=15.1673790,rho=0.7381 :-)
  ^^^^^^
Q=677294,fTU=15.1670664,y=0.634,sigma=0.000493,E=15.1673790,rho=0.5258 :-)
  ^^^^^^

DES (CBC) MAURER TESTS
Q=   292,fTU= 5.2160100,y=0.623,sigma=0.002722,E= 5.2177052,rho=0.5335 :-)
Q=   332,fTU= 5.2168006,y=0.332,sigma=0.002722,E= 5.2177052,rho=0.7397 :-)
Q=  1751,fTU= 7.1829880,y=0.071,sigma=0.009556,E= 7.1836656,rho=0.9435 :-)
Q=  1241,fTU= 7.1827651,y=0.094,sigma=0.009556,E= 7.1836656,rho=0.9249 :-)
Q=  3578,fTU= 8.1760391,y=0.059,sigma=0.006533,E= 8.1764248,rho=0.9529 :-)
Q=  3871,fTU= 8.1778090,y=0.212,sigma=0.006533,E= 8.1764248,rho=0.8322 :-)
Q=  7401,fTU= 9.1723927,y=0.015,sigma=0.004480,E= 9.1723243,rho=0.9878 :-)
Q=  6633,fTU= 9.1715599,y=0.171,sigma=0.004480,E= 9.1723243,rho=0.8645 :-)
Q= 80193,fTU=12.1682074,y=0.093,sigma=0.001470,E=12.1680700,rho=0.9255 :-)
Q= 93893,fTU=12.1678558,y=0.146,sigma=0.001470,E=12.1680700,rho=0.8842 :-)
   ^^^^^
Q=675247,fTU=15.1674124,y=0.068,sigma=0.000493,E=15.1673790,rho=0.9459 :-)
  ^^^^^^
Q=720779,fTU=15.1674871,y=0.219,sigma=0.000493,E=15.1673790,rho=0.8263 :-)
  ^^^^^^

PRNG (my own PRNG) MAURER TESTS
Q=   308,fTU= 5.2155251,y=0.801,sigma=0.002722,E= 5.2177052,rho=0.4232 :-)
Q=   395,fTU= 5.2173941,y=0.114,sigma=0.002722,E= 5.2177052,rho=0.9090 :-)
Q=  1488,fTU= 7.1840403,y=0.039,sigma=0.009556,E= 7.1836656,rho=0.9687 :-)
Q=  1271,fTU= 7.1820823,y=0.166,sigma=0.009556,E= 7.1836656,rho=0.8684 :-)
Q=  3178,fTU= 8.1736433,y=0.426,sigma=0.006533,E= 8.1764248,rho=0.6703 :-)
Q=  3412,fTU= 8.1734512,y=0.455,sigma=0.006533,E= 8.1764248,rho=0.6490 :-)
Q=  8980,fTU= 9.1697755,y=0.569,sigma=0.004480,E= 9.1723243,rho=0.5694 :-)
Q=  6938,fTU= 9.1686216,y=0.826,sigma=0.004480,E= 9.1723243,rho=0.4086 :-)
Q= 61101,fTU=12.1670289,y=0.708,sigma=0.001470,E=12.1680700,rho=0.4789 :-)
Q= 71414,fTU=12.1677327,y=0.229,sigma=0.001470,E=12.1680700,rho=0.8185 :-)
Q=716817,fTU=15.1673248,y=0.110,sigma=0.000493,E=15.1673790,rho=0.9125 :-)
  ^^^^^^
Q=790095,fTU=15.1671740,y=0.416,sigma=0.000493,E=15.1673790,rho=0.6773 :-)
  ^^^^^^

SCRP (toy stream cipher) MAURER TESTS
Q=   302,fTU= 5.2228173,y=1.878,sigma=0.002722,E= 5.2177052,rho=0.0604 :-)
Q=   403,fTU= 5.2178901,y=0.068,sigma=0.002722,E= 5.2177052,rho=0.9459 :-)
Q=  1965,fTU= 7.1821704,y=0.156,sigma=0.009556,E= 7.1836656,rho=0.8757 :-)
Q=  1687,fTU= 7.1831627,y=0.053,sigma=0.009556,E= 7.1836656,rho=0.9580 :-)
Q=  2831,fTU= 8.1769748,y=0.084,sigma=0.006533,E= 8.1764248,rho=0.9329 :-)
Q=  3174,fTU= 8.1756289,y=0.122,sigma=0.006533,E= 8.1764248,rho=0.9030 :-)
Q=  7090,fTU= 9.1717618,y=0.126,sigma=0.004480,E= 9.1723243,rho=0.9001 :-)
Q=  8716,fTU= 9.1726479,y=0.072,sigma=0.004480,E= 9.1723243,rho=0.9424 :-)
Q= 72757,fTU=12.1682649,y=0.133,sigma=0.001470,E=12.1680700,rho=0.8946 :-)
Q= 89762,fTU=12.1684022,y=0.226,sigma=0.001470,E=12.1680700,rho=0.8213 :-)
   ^^^^^
Q=713803,fTU=15.1674590,y=0.162,sigma=0.000493,E=15.1673790,rho=0.8710 :-)
  ^^^^^^
Q=752002,fTU=15.1674070,y=0.057,sigma=0.000493,E=15.1673790,rho=0.9547 :-)
  ^^^^^^

-- 
Peter K. Boucher
--
DISCLAIMER:  The above does not necessarily represent the opinions of my employe r.