Editing Random number generator attack (section)

==Prominent examples==

===Predictable Netscape seed===
Early versions of [[Netscape Communications Corporation|Netscape]]'s [[Secure Sockets Layer]] (SSL) encryption protocol used pseudo-random quantities derived from a PRNG seeded with three variable values: the time of day, the process ID, and the parent process ID. These quantities are often relatively predictable, and so have little [[information entropy|entropy]] and are less than random, and so that version of SSL was found to be insecure as a result. The problem was reported to Netscape in 1994 by [[Phillip Hallam-Baker]], then a researcher in the CERN Web team, but was not fixed prior to release. The problem in the running code was discovered in 1995 by [[Ian Goldberg]] and [[David A. Wagner|David Wagner]],<ref>
{{cite web
| url=http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html
| title=Randomness and Netscape Browser
| work=Dr. Dobb's Journal
| date=January 1996
|author1=Goldberg, Ian |author2=Wagner, David }}
</ref> who had to [[Reverse engineering|reverse engineer]] the [[object code]] because Netscape refused to reveal the details of its random number generation ([[security through obscurity]]). That RNG was fixed in later releases (version 2 and higher) by more robust (i.e., more random and so higher entropy from an attacker's perspective) seeding.

===Microsoft Windows 2000/XP random number generator===
Microsoft used an unpublished algorithm to generate random values in older versions of its [[Microsoft Windows|Windows operating system]]. These random quantities are made available to users via the [[CryptGenRandom]] utility. In November 2007, Leo Dorrendorf et al. from the [[Hebrew University of Jerusalem]] and [[University of Haifa]] published a paper titled ''Cryptanalysis of the Random Number Generator of the Windows Operating System''.<ref>
{{cite journal
|last=Dorrendorf
|first=Leo
|author2=Gutterman, Zvi |author3=Pinkas, Benny
 |title=Cryptanalysis of the random number generator of the Windows operating system
|journal=ACM Transactions on Information and System Security
|date=1 October 2009
|volume=13
|issue=1
|pages=1–32
|doi=10.1145/1609956.1609966
|s2cid=14108026
|url=http://eprint.iacr.org/2007/419.pdf}}
</ref> The paper presented serious weaknesses in Microsoft's approach at the time. The paper's conclusions were based on [[disassembly]] of the code in Windows 2000, but according to Microsoft applied to Windows XP as well.<ref name=Keizer2007>
{{cite web
|last=Keizer
|first=Gregg
|title=Microsoft confirms that XP contains random number generator bug
|date=November 21, 2007
|url=http://www.computerworld.com/s/article/9048438/Microsoft_confirms_that_XP_contains_random_number_generator_bug
|work=[[Computerworld]]}}
</ref> Microsoft has stated that the problems described in the paper have been addressed in subsequent releases of Windows, which use a different RNG implementation.<ref name=Keizer2007/>

===Possible backdoor in Elliptic Curve DRBG===
The U.S. [[National Institute of Standards and Technology]] has published a collection of "deterministic random bit generators" it recommends as NIST Special Publication 800-90.<ref>
{{cite journal
| url=http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf
| title=Recommendation for Random Number Generation Using Deterministic Random Bit Generators
| journal=[[NIST]]
| date=January 2012
|author1=Barker, Elaine |author2=Kelsey, John | doi=10.6028/NIST.SP.800-90A
}}
</ref> One of the generators, [[Dual_EC_DRBG]], was favored by the [[National Security Agency]].<ref>
{{cite journal
|last=Schneier
|first=Bruce
|title=Did NSA Put a Secret Backdoor in New Encryption Standard?
|url=https://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
|journal=[[Wired (website)|Wired]]
|archiveurl=https://web.archive.org/web/20080511193207/http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115
|archivedate=May 11, 2008
|date=November 15, 2007}} [https://www.schneier.com/essay-198.html Alt URL]
</ref> Dual_EC_DRBG uses [[elliptic curve cryptography|elliptic curve technology]] and includes a set of recommended constants. In August 2007, Dan Shumow and Niels Ferguson of [[Microsoft]] showed that the constants could be constructed in such a way as to create a [[kleptographic]] [[Backdoor (computing)|backdoor]] in the algorithm.<ref>
{{cite web
|title=On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng
|url=http://rump2007.cr.yp.to/15-shumow.pdf
|work=cr.yp.to/
|author=Shumow, Dan
|author2=Ferguson, Niels
 |date=21 August 2007}}
</ref> 
In September 2013 ''The New York Times'' wrote that "the N.S.A. had inserted a back door into a 2006 standard adopted by N.I.S.T... called the Dual EC DRBG standard",<ref>{{cite news| url=http://bits.blogs.nytimes.com/2013/09/10/government-announces-steps-to-restore-confidence-on-encryption-standards/ | newspaper=The New York Times | first1=Nicole | last1=Perlroth | title=Government Announces Steps to Restore Confidence on Encryption Standards | date=10 September 2013}}</ref> thereby revealing that the NSA carried out a malware attack against the American people.
In December 2013, Reuters reported that documents released by [[Edward Snowden]] indicated that the [[NSA]] had paid [[RSA Security]] $10 million to make Dual_EC_DRBG the default in their encryption software, and raised further concerns that the algorithm might contain a backdoor for the NSA.<ref>{{cite news | url=https://www.reuters.com/article/us-usa-security-rsa-idUSBRE9BJ1C220131220 | title=Exclusive: Secret contract tied NSA and security industry pioneer | date=December 20, 2013 | work=Reuters | accessdate=December 20, 2013 | author=Menn, Joseph | location=San Francisco}}</ref> Due to these concerns, in 2014, NIST withdrew Dual EC DRBG from its draft guidance on random number generators, recommending "current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible."<ref>{{cite news| url=https://www.nist.gov/itl/csd/sp800-90-042114.cfm | work=National Institute of Standards and Technology | title=NIST Removes Cryptography Algorithm from Random Number Generator Recommendations | date=21 April 2014}}</ref>

===MIFARE Crypto-1===
[[Crypto-1]] is a cryptosystem developed by [[NXP]] for use on [[MIFARE]] chips. The system is proprietary and originally the algorithm has not been published. Upon reverse engineering of the chip, researchers from the University of Virginia and the [[Chaos Computer Club]] found an attack on Crypto-1 exploiting a poorly initialized random number generator.<ref>
{{cite journal
 | last = Nohl | first = Karsten |author2=David Evans |author3=Starbug Starbug |author4=Henryk Plötz
 | url = http://dl.acm.org/citation.cfm?id=1496724
 | title =  Reverse-engineering a cryptographic RFID tag
 | journal = SS'08 Proceedings of the 17th Conference on Security Symposium
 | publisher = [[USENIX]]
 | pages =  185–193
 | date = 2008-07-31 | series = SS'08 }}
</ref>

===Debian OpenSSL===
In May 2008, security researcher [[Luciano Bello]] revealed his discovery that changes made in 2006 to the random number generator in the version of the [[OpenSSL]] package distributed with [[Debian]] [[Linux]] and other Debian-based distributions, such as [[Ubuntu (operating system)|Ubuntu]], reduced the total entropy to the process id and made a variety of security keys vulnerable to attack.<ref>
{{cite web
|title=DSA-1571-1 openssl -- predictable random number generator
|url=http://www.debian.org/security/2008/dsa-1571
|work=[[Debian]] Security Advisory
|date=13 May 2008}}
</ref><ref>
{{cite web
|title=CVE-2008-0166
|url=https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166
|work=[[Common Vulnerabilities and Exposures|CVE]]
|date=January 9, 2008
|quote=OpenSSL 0.9.8c-1 up to versions before 0.9.8g-9 on Debian-based operating systems uses a random number generator that generates predictable numbers, which makes it easier for remote attackers to conduct brute force guessing attacks against cryptographic keys.}}
</ref> The security weakness was caused by changes made to the openssl code by a Debian developer in response to compiler warnings of accessing [[Uninitialized variable|uninitialized memory]].<ref>
{{cite web
|title=Random Number Bug in Debian Linux
|url=https://www.schneier.com/blog/archives/2008/05/random_number_b.html
|author=Schneier, Bruce
|date=May 19, 2008}}</ref> This caused a massive worldwide regeneration of keys, and despite all attention the issue got, it could be assumed many of these old keys are still in use. Key types affected include [[Secure Shell|SSH]] keys, [[OpenVPN]] keys, [[DNSSEC]] keys, key material for use in [[X.509 certificate]]s and [[session key]]s used in [[SSL/TLS]] connections. Keys generated with GnuPG or GNUTLS are not affected as these programs used different methods to generate random numbers. Keys generated by non-Debian-based Linux distributions are also unaffected. The weak-key-generation vulnerability was promptly patched after it was reported, but any services still using keys that were generated by the old code remain vulnerable. A number of software packages now contain checks against a weak key blacklist to attempt to prevent use of any of these remaining weak keys, but researchers continue to find weak key implementations.<ref>{{Cite web | url=http://theregister.co.uk/2015/06/03/compromised_ssh_keys_used_to_access_uk_govt_spotify_github_repos/ |title = Compromised SSH keys used to access Spotify, UK Govt GitHub repos|website = [[The Register]]}}</ref>

===PlayStation 3===
In December 2010, a group calling itself ''fail0verflow'' announced recovery of the [[elliptic curve digital signature algorithm]] (ECDSA) private key used by [[Sony]] to sign software for the [[PlayStation 3]] game console. The attack was made possible because Sony failed to generate a new random [[Cryptographic nonce|nonce]] for each signature.<ref>
{{cite news
|last=Bendel
|first=Mike
|title=Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access
|publisher=www.exophase.com
|date=2010-12-29
|url=http://exophase.com/20540/hackers-describe-ps3-security-as-epic-fail-gain-unrestricted-access/
|accessdate=2011-01-05}}</ref>

===RSA public key factoring===
An analysis comparing millions of [[RSA (algorithm)|RSA]] public keys gathered from the Internet was announced in 2012 by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter. They were able to factor 0.2% of the keys using only [[Euclid's algorithm]].<ref>
{{cite news
|last=Markoff
|first=John
|title=Flaw Found in an Online Encryption Method
|url=https://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html
|newspaper=[[The New York Times]]
|date=February 14, 2012
|authorlink=John Markoff}}</ref><ref>
{{cite journal
|last=Lenstra
|first=Arjen
|author2=Hughes, James P. |author3=Augier, Maxime |author4=Bos, Joppe Willem |author5=Kleinjung, Thorsten |author6= Wachter, Christophe 
|title=Ron was wrong, Whit is right
|year=2012
|page=17
|url=http://eprint.iacr.org/2012/064.pdf
|location=Santa Barbara: IACR}}</ref> They exploited a weakness unique to cryptosystems based on [[integer factorization]]. If {{nowrap|1=''n'' = ''pq''}} is one public key and {{nowrap|1=''n''′ = ''p''′''q''′}} is another, then if by chance {{nowrap|1=''p'' = ''p''′}}, then a simple computation of {{nowrap|1=gcd(''n'',''n''′) = ''p''}} factors both ''n'' and ''n''′, totally compromising both keys. [[Nadia Heninger]], part of a group that did a similar experiment, said that the bad keys occurred almost entirely in [[embedded system|embedded application]]s, and explains that the one-shared-prime problem uncovered by the two groups results from situations where the pseudorandom number generator is poorly seeded initially and then reseeded between the generation of the first and second primes.<ref>{{cite web |last1=Heninger |first1=Nadia |title=New research: There's no need to panic over factorable keys–just mind your Ps and Qs |url=https://freedom-to-tinker.com/2012/02/15/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs/ |website=Freedom to Tinker |date=15 February 2012 |access-date=27 November 2020 |archive-url=https://web.archive.org/web/20161224112657/https://freedom-to-tinker.com/2012/02/15/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs/ |archive-date=2016-12-24}}</ref>

===Java nonce collision===
In August 2013, it was revealed that bugs in the [[Java (programming language)|Java]] class [http://docs.oracle.com/javase/7/docs/api/java/security/SecureRandom.html SecureRandom] could generate collisions in the ''k'' nonce values used for ECDSA in implementations of [[Bitcoin]] on [[Android (operating system)|Android]].  When this occurred the private key could be recovered, in turn allowing stealing [[Bitcoin]]s from the containing [[Cryptocurrency wallet|wallet]].<ref>{{cite web
 |title=Android bug batters Bitcoin wallets
 |url=https://www.theregister.co.uk/2013/08/12/android_bug_batters_bitcoin_wallets/
 |last=Chirgwin
 |first=Richard
 |website=The Register
 |date=12 August 2013}}</ref>