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.