Most software and operating systems use random numbers for security processes. And because software is often built with cost and speed in mind, developers tend to use pseudo-random number generators (PRNGs) to create cryptographic keys and other system encryptions. PRNGs are algorithms that use mathematical formulas or precalculated tables to produce sequences of seemingly random numbers [1]. As the word “pseudo” suggests, the output is not truly random but can be “random enough” for many purposes.

If a PRNG is designed, implemented, and used properly, entities with significant computational resources should not be able to predict its output or distinguish it from true random data. Unfortunately, this is not always the case. PRNGs have become a single point of failure in many real-world systems because the generated numbers are not actually sufficiently random to resist attacks. As a result, the security of the software, its users, and sometimes an entire network can become compromised.

The most common definition of an “attack” in this context is “any method of distinguishing between PRNG outputs and random outputs” [2]. In practice, attackers work hard to learn about a PRNG’s input and output values so they can predict or control its future output. The following examples demonstrate how different software types can become vulnerable to attacks.

Hacker News PRNG Hack

Hacker News is a popular information security and hacking news website. Its login cookies were random eight-character strings that mapped to user names. This information was stored in a hash table on the server [3]. The website used a 32-bit PRNG called MRG32k3a to generate these strings. MRG32k3a, which was developed by Pierre L’Ecuyer, is not a cryptographically strong PRNG. It was designed to be fast and “random enough” for scientific applications.

Daniel Fox Franke, a security researcher, discovered that an attacker could predict the strings and steal accounts through a combination of exploits. He determined that the PRNG’s seed is the time (in milliseconds) when the Hacker News software was last started. Therefore, an attacker must determine the server’s start time to compromise the PRNG [3].

Franke decided to crash the server, wait for it to restart, and then note the start time. He succeeded in crashing the server and found that it was willing to provide the information that he needed. The successful attack yielded 60 seconds worth of possible seeds (60,000 values) [4].

Next, Franke logged into his account and noted the unique ID that the system assigned to him. He then ran the PRNG algorithm with each of the 60,000 possible seeds until he found a match with his own unique ID. That told him which seed had been used and enabled him to generate the same sequence of supposedly random numbers that Hacker News was using. From that he could predict the IDs assigned to users as they logged in and then steal their accounts [4].

Note: After the attack, Hacker News changed its code to use a more secure source of random numbers [4].

Debian OpenSSL PRNG Vulnerability

In 2008, a major vulnerability was discovered in the PRNG of the Debian version of OpenSSL [5]. OpenSSL is a general-purpose cryptography library and toolkit that enables secure network connections. It is widely used in web servers such as Apache and Nginx. Debian is a Unix-like operating system that is the basis for popular Linux distributions such as Ubuntu and Knoppix.

Luciano Bello, a former maintainer and now developer of Debian software, found that two lines of code had been removed from the original version of the OpenSSL library. Package maintainers removed these lines in 2006 because they triggered warnings from the tools used to detect and debug memory issues in the software. The tools warned about usage of uninitialized data in code that was linked to OpenSSL [6].

Like all PRNGs, OpenSSL’s PRNG is a deterministic function. An attacker who obtains key information such as input values can predict outputs. To make PRNGs secure, the entropy pool (source of randomness) must be seeded with many bytes from a source that the attacker cannot predict.

The lines of code that the Debian maintainers removed were responsible for this security measure. Without a mechanism for gathering entropy data, the PRNG could only use the software’s process IDs for seeding. This was problematic because on Linux the default maximum number of process IDs is 32,768, which is comparably a tiny figure in cryptography [6]. The small range of seed values caused the PRNG to generate predictable numbers for approximately two years.

The problem affected all Debian-based distributions that were used to create cryptographic keys. Furthermore, other systems were indirectly affected if these weak keys were imported into them. Private keys created with this version of OpenSSL are as a result very weak, so network connections created with those keys were considered compromised. Keys such as SSH keys, OpenVPN keys, DNSSEC keys, session keys used in SSL/TLS connections, and key material used in X.509 certificates were all affected [5].

Digital Signature Algorithm (DSA) Keys

The Debian security advisory for this vulnerability (DSA-1571-1) included the following statement: “All Digital Signature Algorithm (DSA) keys ever used on affected Debian systems for signing or authentication purposes should be considered compromised” [5].

DSA is a standard for creating digital signatures. Its algorithm includes steps for generating private and public keys, as well as generating and verifying signatures. DSA does not encrypt and decrypt message digests using private and public keys. Instead, it uses mathematical functions to generate digital signatures consisting of two 160-bit numbers. For each signature, the private key and message digests are used to generate the two numbers, while the public key is used for authentication [7].

Generating signatures requires a single-use, random number called a “nonce.” The privacy and entropy of that nonce are critical. An attacker who knows its value and obtains a signature generated from that nonce can recover the signer’s private key with a simple calculation [8]. In the case of Debian’s vulnerable PRNG, a skilled attacker can repeat the calculation for all 32,767 possible values with considerable ease.

Knowledge of only a few bits of the nonce, along with multiple signatures, can also reveal a signer’s private key. Phong Nguyen and Igor Shparlinski demonstrated this attack in their paper “The Insecurity of the Digital Signature Algorithm with Partially Known Nonces” [9]. Their approach involves reducing the DSA problem to a variant of the hidden number problem (HNP) introduced by Dan Boneh and Ramarathnam Venkatesan [10]. The impact of this attack is that signatures generated on vulnerable systems reveal private keys. An attacker can retroactively seek out DSA signatures by crawling websites, inspecting signed email messages, analyzing saved packet captures of SSL exchanges, and other methods [8].

US Lottery PRNG Hack

A former director of information security for Iowa’s Multi-State Lottery Association (MSLA) installed malicious code on computers that generated the random numbers used in choosing the winning lottery tickets. Eddie Raymond Tipton was one of the developers who designed and programmed a PRNG for the MSLA, which administers games such as Powerball and Lotto America. The code that he installed enabled him to predict the winning numbers in several states and win roughly $16.5 million in six years.

The MSLA performed multiple security audits of their internal systems but did not find any suspicious modifications. This is because Tipton programmed the malicious component to delete itself after a specific period of time. Investigators eventually found a suspicious dynamic link library (DLL) on one of the computers responsible for producing random numbers [11].

DLLs contain specific functions (for example, sending documents to a printer) and instructions that allow other programs to run those functions. The files often run unnoticed on the operating system because the functions are loaded in memory only when necessary. DLLs also allow developers to share and upgrade functions without relinking applications. Updating a DLL does not affect most of the other operating system components [12].

The malicious DLL attracted attention because it was not completely identical to the one that had been verified as legitimate in a previous security audit. Tipton added two blocks of code that caused the suspicious DLL to take over the PRNG on three days of the year, on two particular days of the week, and after a certain time of day. If lottery drawings were scheduled when those conditions were met, a different random generator algorithm would draw the numbers [13]. This is why the winning tickets linked to Tipton were all drawn on either November 23 or December 29.

Anyone familiar with the MSLA’s PRNG and security procedures could predict the numbers generated by this other algorithm. Tipton’s knowledge enabled him to calculate the numbers that would be drawn and therefore buy a winning ticket beforehand. Investigators used a working sample of the DLL to recreate one of the draws. By correctly setting the time (to fulfill the conditions for execution), they produced the same winning numbers [14].

From Pseudo to True Randomness

True randomness is generated outside of closed-loop computer systems.

As the examples demonstrate, randomization-related weaknesses and vulnerabilities in cryptographic systems can have extensive consequences. The PRNGs that currently exist are weakened by the patterns that emerge in their “period,” which is the quantity of random numbers generated before the sequence begins to repeat itself. Unless these PRNGs are seeded with values that are derived from high-entropy sources, their output cannot be considered authentic random numbers (aRNs).

In our next article, we will explore how true random number generators (TRNGs) operate and how hybrid approaches that leverage certain entropy sources may be the key to creating extreme unpredictability. We will also discuss Unitychain’s novel approach in generating aRNs while maintaining decentralization and transparency.

References

[1] Haahr, M. Introduction to Randomness and Random Numbers.
[2] Kelsey, J., Schneier, B., Wagner, D., Hall, C. (1998). Cryptanalytic Attacks on Pseudorandom Number Generators.
[3] Franke, D. (2009). How I Hacked Hacker News (with arc security advisory).
[4] Graham-Cumming, J. (2013). Why secure systems require random numbers.
[5] Debian Project. (2008). DSA-1571-1 openssl — predictable random number generator.
[6] Wikinews. (2008). Predictable random number generator discovered in the Debian version of OpenSSL.
[7] Techopedia. Digital Signature Algorithm (DSA).
[8] Lawson, N. (2009). The Debian PGP disaster that almost was.
[9] Nguyen, P., Shparlinski, I. (2002). The Insecurity of the Digital Signature Algorithm with Partially Known Nonces.
[10] Boneh, D., Venkatesan, R. (1996). Hardness of Computing the Most Significant Bits of Secret Keys in Diffie-Hellman and Related Schemes.
[11] Paganini, P. (2016). Lottery security director hacked random-number generator to rig lotteries.
[12] Microsoft Support. What is a DLL?
[13] Kuksov, I. (2016). Lottery scams for the digital age.
[14] Vaas, L. (2016). Forensics uncover how brothers rigged the lottery.

entropy exploits hacks PRNG random number generator randomness security vulnerabilities