Random number generator attack

Last updated

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

Contents

A high quality random number generation (RNG) process is almost always required for security, and lack of quality generally provides attack vulnerabilities and so leads to lack of security, even to complete compromise, in cryptographic systems. [1] The RNG process is particularly attractive to attackers because it is typically a single isolated hardware or software component easy to locate. If the attacker can substitute pseudo-random bits generated in a way they can predict, security is totally compromised, yet generally undetectable by any upstream test of the bits. Furthermore, such attacks require only a single access to the system that is being compromised. No data need be sent back in contrast to, say, a computer virus that steals keys and then e-mails them to some drop point.

Human generation of random quantities

Humans generally do poorly at generating random quantities. Magicians, professional gamblers and con artists depend on the predictability of human behavior. In World War II German code clerks were instructed to select three letters at random to be the initial rotor setting for each Enigma machine message. Instead some chose predictable values like their own or a girlfriend's initials, greatly aiding Allied breaking of these encryption systems. Another example is the often predictable ways computer users choose passwords (see password cracking).

Nevertheless, in the specific case of playing mixed strategy games, use of human gameplay entropy for randomness generation was studied by Ran Halprin and Moni Naor. [2]

Attacks

Software RNGs

Just as with other components of a cryptosystem, a software random number generator should be designed to resist certain attacks. Some attacks possible on a RNG include (from [3] ):

Direct cryptanalytic attack
when an attacker obtained part of the stream of random bits and can use this to distinguish the RNG output from a truly random stream.
Input-based attacks
modify the input to the RNG to attack it, for example by "flushing" existing entropy out of the system and put it into a known state.
State compromise extension attacks
when the internal secret state of the RNG is known at some time, use this to predict future output or to recover previous outputs. This can happen when a generator starts up and has little or no entropy (especially if the computer has just been booted and followed a very standard sequence of operations), so an attacker may be able to obtain an initial guess at the state.

Hardware RNGs

A number of attacks on hardware random number generators are possible, including trying to capture radio-frequency emissions from the computer (obtaining hard drive interrupt times from motor noise, for example), or trying to feed controlled signals into a supposedly random source (such as turning off the lights in a lava lamp or feeding a strong, known signal into a sound card).

RNG subversion

Subverted random numbers can be created using a cryptographically secure pseudorandom number generator with a seed value known to the attacker but concealed in the software. A relatively short, say 24 to 40 bit, portion of the seed can be truly random to prevent tell-tale repetitions, but not long enough to prevent the attacker from recovering, say, a "randomly" produced key.

Random numbers typically go through several layers of hardware and software before they are used. Bits may be generated in a peripheral device, sent over a serial cable, collected in an operating system utility and retrieved by a system call. The subverted bits can be substituted at any point in this process with little likelihood of detection.

A hardware circuit to produce subverted bits can be built on an integrated circuit a few millimeters square. The most sophisticated hardware random number generator can be subverted by placing such a chip anywhere upstream of where the source of randomness is digitized, say in an output driver chip or even in the cable connecting the RNG to the computer. The subversion chip can include a clock to limit the start of operation to some time after the unit is first turned on and run through acceptance tests, or it can contain a radio receiver for on/off control. It could be installed by the manufacturer at the behest of their national signals intelligence service, or added later by anyone with physical access. CPU chips with built-in hardware random number generators can be replaced by compatible chips with a subverted RNG in the chips' firmware.

Defenses

Designing a secure random number generator requires at least as high a level of care as designing other elements of a cryptographic system.

Prominent examples

Predictable Netscape seed

Early versions of 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 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 Wagner, [4] who had to 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 uses an unpublished algorithm to generate random values for its 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. [5] 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. [6] Microsoft has stated that the problems described in the paper have been addressed in subsequent releases of Windows, which use a different RNG implementation. [6]

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. [7] One of the generators, Dual_EC_DRBG, was favored by the National Security Agency. [8] Dual_EC_DRBG uses 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 in the algorithm. [9] 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", [10] 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. [11] 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." [12]

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. [13]

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, dramatically reduced the entropy of generated values and made a variety of security keys vulnerable to attack. [14] [15] The security weakness was caused by changes made to the openssl code by a Debian developer in response to compiler warnings of apparently redundant code. [16] 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 SSH keys, OpenVPN keys, DNSSEC keys, key material for use in X.509 certificates and session keys 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. [17]

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 nonce for each signature. [18]

RSA public key factoring

An analysis comparing millions of 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. [19] [20] They exploited a weakness unique to cryptosystems based on integer factorization. If n = pq is one public key and n′ = p′q′ is another, then if by chance p = p′, then a simple computation of 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 applications, 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. [21]

Java nonce collision

In August 2013, it was revealed that bugs in the Java class SecureRandom could generate collisions in the k nonce values used for ECDSA in implementations of Bitcoin on Android. When this occurred the private key could be recovered, in turn allowing stealing Bitcoins from the containing wallet. [22]

See also

Related Research Articles

A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG), is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed. Although sequences that are closer to truly random can be generated using hardware random number generators, pseudorandom number generators are important in practice for their speed in number generation and their reproducibility.

A key in cryptography is a piece of information, usually a string of numbers or letters that are stored in a file, which, when processed through a cryptographic algorithm, can encode or decode cryptographic data. Based on the used method, the key can be different sizes and varieties, but in all cases, the strength of the encryption relies on the security of the key being maintained. A key's security strength is dependent on its algorithm, the size of the key, the generation of the key, and the process of key exchange.

<span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

<span class="mw-page-title-main">Brute-force attack</span> Cryptanalytic method for unauthorized users to access data

In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key which is typically created from the password using a key derivation function. This is known as an exhaustive key search.

<span class="mw-page-title-main">Hardware random number generator</span> Cryptographic device

In computing, a hardware random number generator (HRNG), true random number generator (TRNG) or non-deterministic random bit generator (NRBG) is a device that generates random numbers from a physical process capable of producing entropy, rather than by means of an algorithm. Such devices are often based on microscopic phenomena that generate low-level, statistically random "noise" signals, such as thermal noise, the photoelectric effect, involving a beam splitter, and other quantum phenomena. These stochastic processes are, in theory, completely unpredictable for as long as an equation governing such phenomena is unknown or uncomputable. This is in contrast to the paradigm of pseudo-random number generation commonly implemented in computer programs and non-physical nondeterministic random bit generator that does not include hardware dedicated to generation of entropy.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also loosely known as a cryptographic random number generator (CRNG).

<span class="mw-page-title-main">RSA Security</span> American computer security company

RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest, Adi Shamir and Leonard Adleman, after whom the RSA public key cryptography algorithm was also named. Among its products is the SecurID authentication token. The BSAFE cryptography libraries were also initially owned by RSA. RSA is known for incorporating backdoors developed by the NSA in its products. It also organizes the annual RSA Conference, an information security conference.

<span class="mw-page-title-main">/dev/random</span> Pseudorandom number generator file in Unix-like operating systems

In Unix-like operating systems, /dev/random and /dev/urandom are special files that serve as cryptographically secure pseudorandom number generators. They allow access to environmental noise collected from device drivers and other sources. /dev/random typically blocked if there was less entropy available than requested; more recently it usually blocks at startup until sufficient entropy has been gathered, then unblocks permanently. The /dev/urandom device typically was never a blocking device, even if the pseudorandom number generator seed was not fully initialized with entropy since boot. Not all operating systems implement the same methods for /dev/random and /dev/urandom.

Key generation is the process of generating keys in cryptography. A key is used to encrypt and decrypt whatever data is being encrypted/decrypted.

Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology – Crypto '96. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth.

A random seed is a number used to initialize a pseudorandom number generator.

<span class="mw-page-title-main">Random number generation</span> Producing a sequence that cannot be predicted better than by random chance

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but unpredictable to foresight. True random number generators can be hardware random-number generators (HRNGs), wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs), which generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

The Microsoft Windows platform specific Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. It is a set of dynamically linked libraries that provides an abstraction layer which isolates programmers from the code used to encrypt the data. The Crypto API was first introduced in Windows NT 4.0 and enhanced in subsequent versions.

Cryptovirology refers to the use of cryptography to devise particularly powerful malware, such as ransomware and asymmetric backdoors. Traditionally, cryptography and its applications are defensive in nature, and provide privacy, authentication, and security to users. Cryptovirology employs a twist on cryptography, showing that it can also be used offensively. It can be used to mount extortion based attacks that cause loss of access to information, loss of confidentiality, and information leakage, tasks which cryptography typically prevents.

CryptGenRandom is a deprecated cryptographically secure pseudorandom number generator function that is included in Microsoft CryptoAPI. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed. A 2007 paper from Hebrew University suggested security problems in the Windows 2000 implementation of CryptGenRandom. Microsoft later acknowledged that the same problems exist in Windows XP, but not in Vista. Microsoft released a fix for the bug with Windows XP Service Pack 3 in mid-2008.

In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators. A lack of entropy can have a negative impact on performance and security.

Dual_EC_DRBG is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including the public identification of the possibility that the National Security Agency put a backdoor into a recommended implementation, it was for seven years one of four CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.

RDRAND is an instruction for returning random numbers from an Intel on-chip hardware random number generator which has been seeded by an on-chip entropy source. Intel introduced the feature around 2012, and AMD added support for the instruction in June 2015.

NIST SP 800-90A is a publication by the National Institute of Standards and Technology with the title Recommendation for Random Number Generation Using Deterministic Random Bit Generators. The publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash DRBG, HMAC DRBG, and CTR DRBG. Earlier versions included a fourth generator, Dual_EC_DRBG. Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the United States National Security Agency (NSA)

Dell BSAFE, formerly known as RSA BSAFE, is a FIPS 140-2 validated cryptography library, available in both C and Java. BSAFE was initially created by RSA Security, which was purchased by EMC and then, in turn, by Dell. When Dell sold the RSA business to Symphony Technology Group in 2020, Dell elected to retain the BSAFE product line. BSAFE was one of the most common encryption toolkits before the RSA patent expired in September 2000. It also contained implementations of the RCx ciphers, with the most common one being RC4. From 2004 to 2013 the default random number generator in the library was a NIST-approved RNG standard, widely known to be insecure from at least 2006, containing a kleptographic backdoor from the American National Security Agency (NSA), as part of its secret Bullrun program. In 2013 Reuters revealed that RSA had received a payment of $10 million to set the compromised algorithm as the default option. The RNG standard was subsequently withdrawn in 2014, and the RNG removed from BSAFE beginning in 2015.

References

  1. ↑ Michael Jenkins; Lydia Zieglar (September 28, 2018). "Commercial National Security Algorithm (CNSA) Suite Profile of Certificate Management over CMS". IETF draft draft-jenkins-cnsa-cmc-profile-00. U.S. National Security Agency. The use of inadequate pseudo-random number generators (PRNGs) can result in little or no security. The generation of quality random numbers is difficult.
  2. ↑ Halprin, Ran; Naor, Moni. "Games for Extracting Randomness" (PDF).
  3. ↑ Kelsey, J.; B. Schneier; D. Wagner; C. Hall (1998). "Cryptanalytic Attacks on Pseudorandom Number Generators". Fast Software Encryption, Fifth International Workshop Proceedings. Springer-Verlag. pp. 168–188. Retrieved 15 August 2013.
  4. ↑ Goldberg, Ian; Wagner, David (January 1996). "Randomness and Netscape Browser". Dr. Dobb's Journal.
  5. ↑ Dorrendorf, Leo; Gutterman, Zvi; Pinkas, Benny (1 October 2009). "Cryptanalysis of the random number generator of the Windows operating system" (PDF). ACM Transactions on Information and System Security. 13 (1): 1–32. doi:10.1145/1609956.1609966. S2CID   14108026.
  6. 1 2 Keizer, Gregg (November 21, 2007). "Microsoft confirms that XP contains random number generator bug". Computerworld .
  7. ↑ Barker, Elaine; Kelsey, John (January 2012). "Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). NIST . doi:10.6028/NIST.SP.800-90A.
  8. ↑ Schneier, Bruce (November 15, 2007). "Did NSA Put a Secret Backdoor in New Encryption Standard?". Wired . Archived from the original on May 11, 2008. Alt URL
  9. ↑ Shumow, Dan; Ferguson, Niels (21 August 2007). "On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng" (PDF). cr.yp.to/.
  10. ↑ Perlroth, Nicole (10 September 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times.
  11. ↑ Menn, Joseph (December 20, 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. San Francisco. Retrieved December 20, 2013.
  12. ↑ "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations". National Institute of Standards and Technology. 21 April 2014.
  13. ↑ Nohl, Karsten; David Evans; Starbug Starbug; Henryk Plötz (2008-07-31). "Reverse-engineering a cryptographic RFID tag". SS'08 Proceedings of the 17th Conference on Security Symposium. SS'08. USENIX: 185–193.
  14. ↑ "DSA-1571-1 openssl -- predictable random number generator". Debian Security Advisory. 13 May 2008.
  15. ↑ "CVE-2008-0166". CVE . January 9, 2008. 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.
  16. ↑ Schneier, Bruce (May 19, 2008). "Random Number Bug in Debian Linux".
  17. ↑ "Compromised SSH keys used to access Spotify, UK Govt GitHub repos". The Register .
  18. ↑ Bendel, Mike (2010-12-29). "Hackers Describe PS3 Security As Epic Fail, Gain Unrestricted Access". Exophase.com . Retrieved 2011-01-05.{{cite news}}: External link in |publisher= (help)
  19. ↑ Markoff, John (February 14, 2012). "Flaw Found in an Online Encryption Method". The New York Times .
  20. ↑ Lenstra, Arjen; Hughes, James P.; Augier, Maxime; Bos, Joppe Willem; Kleinjung, Thorsten; Wachter, Christophe (2012). "Ron was wrong, Whit is right" (PDF). Santa Barbara: IACR: 17.{{cite journal}}: Cite journal requires |journal= (help)
  21. ↑ Heninger, Nadia (15 February 2012). "New research: There's no need to panic over factorable keys–just mind your Ps and Qs". Freedom to Tinker. Archived from the original on 2016-12-24. Retrieved 27 November 2020.
  22. ↑ Chirgwin, Richard (12 August 2013). "Android bug batters Bitcoin wallets". The Register.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.