Abstract
NIST SP800-22 (2010) proposed the state of the art statistical testing techniques for testing the quality of (pseudo) random generators. However, it is easy to construct natural functions that are considered as GOOD pseudorandom generators by the NIST SP800-22 test suite though the output of these functions is easily distinguishable from the uniform distribution. This paper proposes solutions to address this challenge by using statistical distance based testing techniques. We carried out both NIST tests and LIL based tests on the following pseudorandom generators by generating more than 200TB of data in total: (1) the standard C linear congruential generator, (2) Mersenne Twister pseudorandom generator, (3) PHP random generators (including Mersenne Twister and Linear Congruential based), and (4) Debian Linux (CVE-2008-0166) pseudorandom generator with OpenSSL 0.9.8c-1. As a first important result, our experiments show that, PHP pseudorandom generator implementation (both linear congruential generators and Mersenne Twister generators) outputs completely insecure bits if the output is not further processed. As a second result, we illustrate the advantages of our LIL based testing over NIST testing. It is known that Debian Linux (CVE-2008-0166) pseudorandom generator based on OpenSSL 0.9.8c-1 is flawed and the output sequences are predictable. Our LIL tests on these sequences discovered the flaws in Debian Linux implementation. However, NIST SP800-22 test suite is not able to detect this flaw using the NIST recommended parameters. It is concluded that NIST SP800-22 test suite is not sufficient and distance based LIL test techniques be included in statistical testing practice. It is also recommended that all pseudorandom generator implementations be comprehensively tested using state-of-the-art statistically robust testing tools.
Chapter PDF
Similar content being viewed by others
References
Ahmad, D.: Two years of broken crypto: debian’s dress rehearsal for a global pki compromise. IEEE Security & Privacy 6(5), 70–73 (2008)
Clarkson, J.A., Adams, C.R.: On definitions of bounded variation for functions of two variables. Tran. AMS 35(4), 824–854 (1933)
Debian. Debian security advisory dsa-1571-1, http://www.debian.org/security/2008/dsa-1571
Feller, W.: Introduction to probability theory and its applications, vol. I. John Wiley & Sons, Inc., New York (1968)
Hellinger, E.: Neue begründung der theorie quadratischer formen von unendlichvielen veränderlichen. J. für die reine und angewandte Mathematik 136, 210–271 (1909)
Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your ps and qs: Detection of widespread weak keys in network devices. In: Proc. 21st USENIX Security Symposium, vol. 2 (2012)
Khinchin, A.: Über einen satz der wahrscheinlichkeitsrechnung. Fund. Math. 6, 9–20 (1924)
Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM TOMACS 8(1), 3–30 (1998)
NIST. Test suite (2010), http://csrc.nist.gov/groups/ST/toolkit/rng/
OpenSSL. Openssl implementation from http://www.openssl.com/
RANDOM.ORG. Random.org, http://www.random.org/
Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Vangel, M., Banks, D., Heckert, A., Dray, J., Vo, S.: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST SP 800-22 (2010)
Wang, Y.: Resource bounded randomness and computational complexity. Theoret. Comput. Sci. 237, 33–55 (2000)
Wang, Y.: A comparison of two approaches to pseudorandomness. Theoretical computer science 276(1), 449–459 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Wang, Y., Nicol, T. (2014). Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL. In: Kutyłowski, M., Vaidya, J. (eds) Computer Security - ESORICS 2014. ESORICS 2014. Lecture Notes in Computer Science, vol 8712. Springer, Cham. https://doi.org/10.1007/978-3-319-11203-9_26
Download citation
DOI: https://doi.org/10.1007/978-3-319-11203-9_26
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11202-2
Online ISBN: 978-3-319-11203-9
eBook Packages: Computer ScienceComputer Science (R0)