The Sad History of Random Bits

Authors

  • George Markowsky School of Computing & Information Science, University of Maine

DOI:

https://doi.org/10.13052/jcsm2245-1439.311

Keywords:

Debian, system accident, SSL, SSH, Bitcoin, cryptography, security breach, software engineering, PRNG, pseudo-random numbers, booby trap, BSAFE, Dual_EC_DRNG

Abstract

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

Download data is not yet available.

Author Biography

George Markowsky, School of Computing & Information Science, University of Maine

George Markowsky spent ten years at the IBM Thomas J. Watson Research Center where he served as Research Staff Member, Technical Assistant to the Director of the Computer Science Department, and Manager of Special Projects. He came to the University of Maine as the first Chair of the Computer Science Department. During 2004–2005 he was Dean of the American-Ukrainian Faculty at Ternopil National Economic University in Ukraine. In 2006–2007 he was Visiting Professor at Rensselaer Polytechnic Institute Lally School of Management and Technology. He became Chair of the Computer Science Department again in 2008 and served in that capacity until the Department became part of the new School of Computing and Information Science at which time he became the Associate Director of the School. In 2013–2014 he has been a Visiting Scholar in the Department of Computing Security at the Rochester Institute of Technology. He is currently Professor of Computer Science at the University of Maine. George Markowsky has published 113 journal papers, book chapter, book reviews and conference papers on various aspects of Computer Science and Mathematics. He has written or edited 15 books and reports on various aspects of computing. He also holds a patent in the area of Universal Hashing. His interests range from pure mathematics to the application of mathematics and computer science to biological problems. He has also built voice controlled and enhanced keyboard terminals for use by paralyzed individuals. He is very active in homeland security and is the director of the University of Maine Homeland Security Lab.

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.

Downloads

Published

2014-06-05

How to Cite

1.
Markowsky G. The Sad History of Random Bits. JCSANDM [Internet]. 2014 Jun. 5 [cited 2024 Mar. 28];3(1):1-26. Available from: https://journals.riverpublishers.com/index.php/JCSANDM/article/view/6165

Issue

Section

Articles