The Sad History of Random Bits
DOI:
https://doi.org/10.13052/jcsm2245-1439.311Keywords:
Debian, system accident, SSL, SSH, Bitcoin, cryptography, security breach, software engineering, PRNG, pseudo-random numbers, booby trap, BSAFE, Dual_EC_DRNGAbstract
In this paper we examine the history of using random numbers in computer programs. Unfortunately, this history is sad because it is replete with disasters ranging from one of the first pseudo-random number generators, RANDU, being very bad to the most recent efforts by the NSA to undermine the pseudo-random number generator in RSA's BSAFE cryptographic library. Failures in this area have been both intentional and unintentional, but unfortunately the same sorts of mistakes are repeated. The repeated failures in getting our “random numbers” correct suggests that there might be some systemic reasons for these failures. In this paper we review some of these failures in more detail, and the 2006 Debian OpenSSL Debacle in great detail. This last event left users of Debian and its derivatives with seriously compromised cryptographic capabilities for two years. We also illustrate how this failure can be exploited in an attack. We also modify the concept of a system accident developed in the work of Charles Perrow [1]. We identify some system failures in building pseudo-random number generators and offer some suggestions to help develop PRNGs and other code more securely.
Downloads
References
Charles Perrow, Normal Accidents, Princeton University Press, 1999.
George Markowsky, “Was the 2006 Debian SSL Debacle a System Accient?,”
Donal Knuth, The Art of Computer Programming, 3rd ed., 1998, Vol. 2, Seminumerical Algorithms.
Geiger counter-based random number generator. http://www.fourmilab.ch/hotbits/.
An atmospherically based random number generator. http://www.random.org/.
Quantum Mechanics Random Number Generator Project, ‘http://qrng. physik.hu- berlin.de/.
PQRNG 150 (Quantum Mechanics Random Number Generator) PicoQuant GmBH, http://www.picoquant.com/products/category/ quantum-random-number-generator/pqrng-150-quantum-random-number-generator.
Rodrigo Gallego, Lluis Masanes, Gonzalo De La Torre, Chirag Dhara, Leandro Aolita and Antonio Acfin, “Full Randomness from Arbitrarily Deterministic Events,” Nature Communications 4, Article number: 2654, http://conference.iiis.tsinghua.edu.cn/QIP2013/wp-content/uploads/2012/12/qip2013_submission_7.pdf
Robert Coveyou, “Random Number Generation Is Too Important to Be Left to Chance,” Studies in Applied Mathematics, III, 1970, pp. 70–111.
George Markowsky, “Bounds on the Index and Period of a Binary Relation on a Finite Set,“Semigroup Forum, v. 13, 1877, pp. 253–259.
“Mersenne Twister,” Wikipedia, February 1, 2014, http://en.wikipedia.org/wiki/Mersenne_twister.
Makoto Matsumoto and Takuji Nishimura, “Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator,” ACM Trans. on Modeling and Computer Simulation, v. 8, n, 1, January, 1998, pp. 3–30.
Jerry Dwyer, 'Quick and Portable Random Number Generators,” Dr. Dobb's Journal, June 1, 1995, http://www.drdobbs.com/quick-and-portable-random-number- generat/184403024
“RANDU,” Wikipedia, February 2, 2014, http://en.wikipedia.org/wiki/RANDU
David Ahmad, “Two Years of Broken Crypto,” IEEE Security & Privacy, 2008, pp. 70–73.
Russ Cox, “Lessons from the Debian/OpenSSL Fiasco,”, blog, http://research. swtch.com/openssl.
Bruce Schneier, “Random Number Bug in Debian Linux,” blog Schneier on Security, http://www.schneier.com/blog/archives/2008/05/random_number_b.html
Luciano Bello and Maximiliano Bertacchini, “Predicatable PRNG In the Vulnerable Debian OpenSSL Package: The What and the How,” DEFCON 16, August 8–10, 2008, Las Vegas, NV, http://www.youtube.com/watch?v=yXr7KBC3G3I. The slides are available at http://www.citedef.gob.ar/si6/descargas/openssl-debian-defcon16.pdf.
Jacob Applebaum, Dino Dai Zovi, and Karsten Nohl, “Crippling Crypto: The Debian OpenSSL Debacle,”, http://www.youtube.com/watch?v=QdknzkoN_aI. The slides are available at http://trailofbits.files.wordpress.com/2008/07/hope-08- openssl.pdf.
Valgrind Website, http://valgrind.org/.
“Some SecureRandom Thoughts,” Android Developers Blog, August 14, 2013, http://android-developers.blogspot.com/2013/08/some-securerand om- thoughts.html.
Dan Goodin, “Google Confirms Critical Android Crypto Flaw Used in $5,700 Bitcoin heist,”, em Ars Technia, August 14, 2013, http://arstechnica.com/security/2013/08/google-confirms-critical-andro id-crypto-flaw-used-in-5700- bitcoin-heist/.
Jim Edwards, “A Thief Is Attempting To Hide $100 Million In Stolen Bitcoins And You Can Watch It Live Right Now,” Business Insider, December 3, 2013, http://www.businessinsider.com/a-thief-is-attempting-to-hide-100-million-in-stolen-bitcoins-and-you-can-watch-it-live-right-now-2013–12.
“RSA BSAFE,” Wikipedia, February 2, 2014, http://en.wikipedia.org/ wiki/ RSA_BSAFE.
Matthew Green, “RSA Warns Developers Not to Use RSA Products,” blog, http://blog.cryptographyengineering.com/2013/09/rsa-warns- developers-against-its-own.html.
Dan Shumow and Niels Feguson, “On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng,” http://rump2007.cr.yp.to/15-shumow.pdf.
Glenn Greenwald, “Edward Snowden: the whistleblower behind the NSA surveillance revelations,” The Guardian, June 9, 2013, http://www.theguardian.com/world/2013/jun/09/edward-snowden-nsa-whistleblower-surveillance.
“Edwward Snowden,” Wikipedia, February 2, 2014, http://en.wikipedia.org/wiki/Edward_Snowden#cite_note-cnn-hotel-104.
Joseph Menn, “Exclusive: Secret Contract Tied NSA and Security Industry Pioneer,” Reuters, December 20, 2013, http://www.reuters.com/article/2013/12/20/ us-usa-security-rsa-idUSBRE9BJ1C220131220.
Dan Goodin, “Stop using NSA-influenced code in our products, RSA tells customers,” Ars Technica, September 19, 2013, http://arstechnica.com/security/2013/09/ stop-using-nsa-influence-code-in-our-product-rsa-tells-customers/
Dan Goodin, “More Researchers Join RSA Conference Boycott to Protest $10 million NSA Deal,” Ars Technia, January 7, 2014, http://arstechnica.com/security/2014/01/more-researchers-join-rsa-conference-boycott-to-protest-10-million-nsa-deal/
Charles Perrow, “Software Failures, Security, and Cyberattacks,” Online article at http://www.cl.cam.ac.uk/rja14/shb08/perrow.pdf, http://www.tatup-journal.de/english/tatup113_perr11a.php.
“Booby-Trapped Onion Patch Kills Owner, Son,”, Los Angeles Times, June 12, 1994, http://articles.latimes.com/1994–06-12/news/mn-3270_1_onion-patch.
“NASA's metric confusion caused Mars orbiter loss,” CNN, September 30, 1999, http://www.cnn.com/TECH/space/ 9909/30/mars.metric/.
“Metric Moon,”, NASA Science News, online article, http://science1.nasa.gov/science-news/science-at-nasa/2007/08jan_metricmoon/.
Richard Kettlewell, “valgrind-clean the RNG,” Debian Bug report logs -#36516, http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=363516.
Kurt Roeckx, “Random number generator, uninitialized data and valgrind,”, OpenSSL Mail Archive, http://www.mail-archive.com/openssl-dev@openssl. org/msg21156.html.
Ulf Möller, “Random number generator, uninitialized data and valgrind,”, OpenSSL Mail Archive, http://www.mail-archive.com/openssl-dev@openssl.org/ msg21157.html.
Debian Security Advisory 1571, http://www.debian.org/security/2008/dsa-1571.
Luciano Bello, “Exploiting DSA-1571: How to break PFS in SSL with EDH,” http://www.lucianobello.com.ar/exploiting_DSA-1571/
Ben Feinstein, “Loaded Dice: SSH Key Exchange & the Debian OpenSSL PRNG Vul- nerability,” ToorCon X, September 27, 2008. Slides are available at http://www.cs.unh.edu/it666/reading_list/Keys/ssh_key_exchange.pdf.
Scott Yilek, Eric Rescorla, Hovav Shacham, Brandon Enright, and Stefan Savage, “When Private Keys are Public: Results for the 2008 Debian OpenSSL Vulnerability”, ICM'09, November 4–6, 2009, Chicago Illinois, USA.
“The SSL Keys and Various Applications,” http://wiki.debian.org/SSLkeys
OpenSSL Source Code for md rand.c, https://github.com/luvit/openssl/blob/master/openssl/crypto/rand/md_rand.c
TJ. O'Connor, Violent Python: A Cookbook for Hackers, Forensic Analysts, Penetration Testers and Security Engineers, Syngress, Waltham, MA, 2013.
Daniel J. Barrett, Richard E. Silverman, and Robert G. Byrnes, SSH, The Secure Shell, The Definitive Guide, 2nd ed., O'Reilly, Sebastopal, CA, 2005.
“A Detector for Known Weak Key Material,”, Debian.org, http://security.debian.org/project/extra/dowkd/dowkd.pl.gz.
Donald E. Knuth, Literate Programming, Center for the Study of Language and Information, 1992.
Donald E. Knuth and Silvio Levy, The CWEB System of Structured Documentation, Version 3.6, Addison-Wesley, 1994, http://sunburn.stanford.edu/knuth/cweb. html.
Kent Beck, Test-Driven Development by Example, Addison-Wesley, 2002.
“Test-Driven Development,” Wikipedia, February 4, 2014, http://en.wikipedia.org/wiki/Test-driven_development.
Gerard j. Holzmann, Design and Validation of Computer Protocols, Prentice Hall, 1991.
H. K. Berg, W. E. Boebert, W. R. Franta and T. G. Moher, Formal Methods of Program Verification and Specification, Prentice Hall 1982.
“Home Page for Spin,” http://spinroot.com/spin/whatispin.html.
Gerard J. Holzmann, The SPIN Model Checker: Primer and Reference Manual, Addison- Wesley, 2003.
