Random number generator attack
The security of
A high quality
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
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
- Mix (with, for example, xor) hardware generated random numbers with the output of a good quality stream cipher, as close to the point of use as possible. The stream cipher key or seed should be changeable in a way that can be audited and derived from a trustworthy source, e.g. dice throws. The Fortunarandom number generator is an example of an algorithm which uses this mechanism.
- Generate passwords and passphrases using a true random source. Some[clarification needed] systems select random passwords for the user rather than let users propose their own.
- Use encryption systems that document how they generate random numbers and provide a method to audit the generation process.
- Build security systems with off the shelf hardware, preferably purchased in ways that do not reveal its intended use, e.g. off the floor at a large retail establishment. From this perspective, sound cards and webcams may be a better source of randomness than hardware made for that purpose.
- Maintain complete physical control over the hardware after it has been purchased. The hardware should at one place or location and need no other transmission to a peer-to-peer hardware. Attacks are on the line in the network not the hardware itself.
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
Microsoft Windows 2000/XP random number generator
Microsoft uses an unpublished algorithm to generate random values for its
Possible backdoor in Elliptic Curve DRBG
The U.S.
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 byMIFARE Crypto-1
Debian OpenSSL
In May 2008, security researcher
PlayStation 3
In December 2010, a group calling itself fail0verflow announced recovery of the
RSA public key factoring
An analysis comparing millions of
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
- Pseudorandom number generator
- Cryptographically secure pseudorandom number generator
- Key generation
- One-time pad
- Salt
- Nonce
References
- ^ 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.
- ^ Halprin, Ran; Naor, Moni. "Games for Extracting Randomness" (PDF).
- ^ 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.
- ^ Goldberg, Ian; Wagner, David (January 1996). "Randomness and Netscape Browser". Dr. Dobb's Journal.
- ^
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. S2CID 14108026.
- ^ a b Keizer, Gregg (November 21, 2007). "Microsoft confirms that XP contains random number generator bug". Computerworld.
- ^ Barker, Elaine; Kelsey, John (January 2012). "Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (PDF). .
- ^
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
- ^ 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/.
- ^ Perlroth, Nicole (10 September 2013). "Government Announces Steps to Restore Confidence on Encryption Standards". The New York Times.
- ^ Menn, Joseph (December 20, 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. San Francisco. Retrieved December 20, 2013.
- ^ "NIST Removes Cryptography Algorithm from Random Number Generator Recommendations". National Institute of Standards and Technology. 21 April 2014.
- ^ 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.
- ^ "DSA-1571-1 openssl -- predictable random number generator". Debian Security Advisory. 13 May 2008.
- ^
"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.
- ^ Schneier, Bruce (May 19, 2008). "Random Number Bug in Debian Linux".
- ^ "Compromised SSH keys used to access Spotify, UK Govt GitHub repos". The Register.
- ^
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
(help)|publisher=
- ^ Markoff, John (February 14, 2012). "Flaw Found in an Online Encryption Method". The New York Times.
- ^
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) - ^ 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.
- ^ Chirgwin, Richard (12 August 2013). "Android bug batters Bitcoin wallets". The Register.
Further reading
- Gutterman, Zvi; Benny Pinkas; Tzachy Reinman (2006). "Analysis of the Linux Random Number Generator" (PDF). 2006 IEEE Symposium on Security and Privacy (S&P'06). p. 385. S2CID 6385808.
- Eastlake, D.; J. Schiller; S. Crocker (June 2005). "Randomness Requirements for Security". RFC. IETF.