Statistical Testing of Cryptographic Randomness

Öz

Security of a cryptographic application is highly related to the quality of randomness of the mechanism used

to encrypt a message. A ciphering process used to encrypt a message is mainly based on the cryptographic

random numbers. There are numerous methods proposed to generate random numbers for cryptographic

applications in the literature. To decide whether a cryptographic random number generator is suitable for

cryptographic applications or not, various statistical randomness tests are introduced. In practice, test

batteries that contain more than one randomness test are constructed and all the tests in a battery are applied

to evaluate the quality of random number generator. In this article, we present a review of test batteries and

recent statistical randomness tests used to evaluate output of a cryptographic random number generator. We

criticize test batteries in the sense of multiple testing problem, highlight some misuses of statistical notions in

hypothesis testing of cryptographic randomness, and discuss potential solutions to multiple testing problem

seen in the test batteries.

Anahtar Kelimeler

• multiple testing,random number generator,test of randomness,test battery

Kriptografik Rasgeleliğin İstatistiksel Olarak Test Edilmesi

Öz

uygulanmaktadır. Bu çalışmada, test kümeleri ve güncel olarak önerilmiş olan kriptografik rasgelelik testleri

derlenmiş, test kümeleri çoklu test problemi açısından değerlendirilmiş, bazı istatistiksel kavramların hatalı

kullanımları ve çoklu test problemine ilişkin olası çözümler üzerinde durulmuştur.

Anahtar Kelimeler

• Çoklu test problemi,rasgele sayı üreteci,rasgelelik testi,test kümesi.

Kaynakça

1. M.M. Alani, 2010, Testing randomness in ciphertext of block-ciphers using diehard tests, International Journal of Computer Science and Network Security, 10:53–57.
2. P.M. Alcover, A. Guillamon, M.C. Ruiz, 2013, A new randomness test for bit sequences, Informatica, 24:339–356.
3. B. Walsh, 2006, Multiple comparisons: Bonferroni corrections and false discovery rates. http://nitro.biosci.arizona.edu/workshops/Aarhus2006/pdfs/Multiple.pdf, Lecture notes for EEB 581, [Online; accessed 19-December-2014].
4. D. Bogdanov, L. Kamm, S. Laur, V. Sokk, 2014 Rmind: a tool for cryptographically secure statistical analysis. IACR Cryptology, ePrint Archive, 512.
5. R.G. Brown, D. Eddelbuettel, D. Bauer, 2014, Dieharder: A random number test suite (version 3.31.1). URL: http://www.phy.duke.edu/ rgb/General/dieharder.php, [Online; accessed 25-February-2014].
6. H. Demirhan, N.A. Dolgun, Y. Parlak Demirhan, M.O. Dolgun, 2010, Performance of some multiple comparison tests under heteroscedasticity and dependency, Journal of Statistical Computation and Simulation, 80:1083–1100.
7. A. Doganaksoy, C. Calik, F. Sulak, M.S. Turan, 2006, New randomness tests using random walk. In Proceedings of National Cryptology Symposium II, Turkey.
8. A. Doganaksoy, F. Sulak, M. Uguz, O. Seker, Z. Akcengiz, 2015, New statistical randomness tests based on length of runs, Mathematical Problems in Engineering, http://dx.doi.org/10.1155/2015/626408.

9. O.J. Dunn, 1961, Multiple comparisons among means, Journal of the American Statistical Association, 56:52–64.
10. J.E. Freund, B.M. Perles, 2003, Statistics A First Course, Prentice Hall, New Jersey, 8 edition.
11. S. Geza, 2007, Introduction to Probability with Statistical Applications, Birkhauser, Boston.
12. J.C. Hernandez, J.M. Sierra, A. Seznec, 2004, The sac test: a new randomness test, with some applications to PRNG analysis. Proceedings of the International Conference Computational Science and Its Applications, 960–967.
13. Y. Hochberg, A.C. Tamhane, 1987, Multiple Comparison Procedures, Wiley, New York.
14. I. Jang, H.S. Yoo, 2006, Pseudorandom number generators using optimal normal basis. In Kumar V. Tan C.J.K. Taniar D. Lagan A. Mun Y. Choo H. Gervasi, O. (eds.), Computational Science and Its Applications - ICCSA 2006, Part II, 206–212. Springer-Verlag.
15. C. Kenny, 2005, Random number generators: An evaluation and comparison of random.org and some commonly used generators, Trinity College Dublin, management science and information systems studies project report. https://www.random.org/analysis/Analysis2005.pdf, 2005. [Online; accessed 24-February- 2014].
16. D.E. Knuth, 1969, The Art of Computer Programming, Volume 2 / Seminumerical Algorithms, Addison- Wesley, Reading, Massachusetts, 1 edition.
17. D.E. Knuth, 1981, The Art of Computer Programming, Volume 2 / Seminumerical Algorithms, Addison- Wesley, Reading, Massachusetts, 2 edition.
18. D.E. Knuth, 1998, The Art of Computer Programming, Volume 2 / Seminumerical Algorithms, Addison- Wesley, Reading, Massachusetts, 3 edition.
19. P. L’Ecuyer, P. Hellekalek, 1998, Random number generators: Selection criteria and testing, Random and Quasi-Random Point Sets Lecture Notes in Statistics, 138:223–265.
20. P. L’Ecuyer, R. Simard, 2007, Testu01: A c library for empirical testing of random number generators. ACM Transactions on Mathematical Software, 33: Article 22.
21. P. LEcuyer, R. Simard, 2014, Testu01: A C library for empirical testing of random number generators - user’s guide, compact version. Testu01. http://www.iro.umontreal.ca/ simardr/testu01/guideshorttestu01.pdf, [Online; accessed 24-February-2014].
22. H. Maaranen, K. Miettinen, M.M. Mkel, 2003, Using Quasi Random Sequences in Genetic Algorithms, Optimization and Inverse Problems in Electromagnetism, 33–44. Springer, New York.
23. G. Marsaglia, 2014, Diehard: A battery of tests of randomness. http://stat.fsu.edu/ geo/diehard.html, 1996. [Online; accessed 25-February-2014].
24. G. Marsaglia, W.W. Tsang, 2002, Some difficult-to-pass tests of randomness, Journal of Statistical Software, 7:3.
25. K. Marton, A. Suciu, C. Sacarea, O. Cret, 2012, Generation and testing of random numbers for cryptographic applications, The Publishing House of the Romanian Academy, 4:368–377.
26. M. Mascagni, A. Srinivasan, 2000, Algorithm 806: SPRNG: A scalable library for pseudorandom number generation, ACM Transactions on Mathematical Software, 26:436–461.
27. U.M. Maurer, 1992, A universal statistical test for random bit generators, Journal of Cryptology, 5:89–105.
28. U.M. Maurer, J.L. Massey, 1991, Local randomness in pseudorandom sequences, Journal of Cryptology, 4:135–149.
29. B.D. McCullough, 2006, A review of Testu01, Journal of Applied Econometrics, 21:677–682.
30. R. Nuzzo, 2014, Scientific method: Statistical errors, Nature, 506(7487):150.
31. A. Rukhin, J. Soto, J. Nechvatal, M. Smid, E. Barker, S. Leigh, M. Levenson, M. Vangel, D. Banks, A. Heckert, J. Dray, S. Vo., 2001, http://csrc.nist.gov/rng/. [Online; accessed 25-February-2014].
32. A.L. Rukhin, 2001, Testing randomness: A suite of statistical procedures, Theory of Probability and Its Applications, 45:111–132.
33. M. Rutti, 2004, A Random Number Generator Test Suite for the C++ Standard. Diploma Thesis. Institute for Theoretical Physics, ETH Zurich.
34. B.Y. Ryabko, V.A. Monarev, 2005, Using information theory approach to randomness testing, Journal of Statistical Planning and Inference, 133:95–110.
35. B.Y. Ryabko, V.S. Stognienko, Yu.I. Shokin, 2004 A new test for randomness and its application to some cryptographic problems, Journal of Statistical Planning and Inference, 123:365–376.
36. J.K.M. Sadique, U. Zaman, R. Ghosh, 2012 Review on fifteen statistical tests proposed by NIST, Journal of Theoretical Physics and Cryptography, 1:18–31.
37. Z.K. Sidak, 1967, Rectangular confidence regions for the means of multivariate normal distributions, Journal of the American Statistical Association, 62:626–633.
38. J. Soto, 1999, Statistical testing of random number generators. Proceedings of the 22nd National Information Systems Security Conference, USA, National Institute of Standards and Technology.
39. M. Sys, Z. Ryha, 2014, Faster randomness testing with the NIST statistical test suite. In Chakraborty R.S. et al. (eds.), Security, Privacy, and Applied Cryptography Engineering Lecture Notes in Computer Science, 272–284, Portugal, Springer.
40. M. Sys, P. Svenda, M. Ukrop, V. Matyas, 2014, Constructing empirical tests of randomness. In Andreas Holzinger Mohammad S. Obaidat and Pierangela Samarati (eds.), SECRYPT 2014 Proceedings of the 11th International Conference on Security and Cryptography, 229–237, Portugal, SCITEPRESS Science and Technology Publications.
41. I. Vattulainen, T. Ala-Nissila, K. Kankaala, 1995 Physical models as tests of randomness, Physical Review Engineering, 52:3205–3213.
42. J. Walker, 2014, Ent - a pseudorandom number sequence test program. https://www.fourmilab.ch/random/, [Online; accessed 25-February-2014].