Home / Blog / The importance of randomness

The importance of randomness

Posted on 11/25/2014, by Miguel Herrero (INCIBE)
Roulette

Random numbers are a key element in multiple processes of digital life. They’re used not only in applications with a vast component of randomness such as online gambling, but they also have multiple applications in the world of cybersecurity. In some cryptographic systems security depends on something known only by authorised personnel but unpredictable for attackers, as is the case in electronic token systems.

A second security factor is added in these systems, as it’s necessary not only to have “something I know”, a password, but also “something I have”, a number. To guarantee the robustness of the system, this number has a very short lifespan, on occasions shorter than 60 seconds, and it’s normally generated by the token’s built-in clock and a random “seed” loaded into the token.

RSA securID token

- RSA securID token -

Therefore, one of the pillars of the security of these systems is the randomness of the “seed” loaded into the token, as it also generates the necessary number to authenticate the system. If the seed was predictable it would be easy to generate the token’s number and therefore easier to jeopardise the system.

 Shannon entropy (or simply entropy) is used to measure the uncertainty of a source of information. A system with low entropy is more predictable than a system with high entropy. It is known that a bit can contain two values. If both values were equiprobable, a system with two bits would have entropy of 2. However, if a condition existed where by knowing one of the two bits you could access information from the other; the entropy of the system would be much lower.

Applying these concepts to the generation of random numbers used in cryptography, if knowing part of the numbers previously generated gave me information about the numbers that are going to be generated, the entropy of the system would be lower. Therefore, a generator of random numbers with a weak source of entropy will produce low quality and more predictable random numbers.

 

 Generation of random numbers

 

Currently two types of random number generators exist. On one hand, random number generators (RNG) are based on the measurement of a physical element such as thermal noise or quantum phenomena, which supposedly is random and then compensates for possible biases in the measurement process.

On the other hand, there are pseudorandom number generators (PRNG), which are deterministic algorithms that, from a small set of initial values (known as seed), can generate sequences of numbers with a good level of randomness. Inside PRNG’s there is a variety known as cryptographically secure PRNG (CPRNG) with properties that are adequate for use in cryptography.

The use of one type or another depends on the system and the necessary speed of random number generation. RNG’s tend to block their generation until enough entropy has been generated for the generated number to be random. PRNG’s also have a greater capacity of random number generation but they tend to reduce the entropy of the system, becoming more and more predictable.

To avoid PRNG’s from being predictable, the entropy of the system is regenerated periodically, changing the seed to a number generated by a RNG. 

A related incident: The theft of Bitcoins in 2013.

 As you were able to read in our guide, Bitcoin: A cryptographic currency, in mid August of 2013 the media covered a case of bitcoin theft that affected users who had virtual wallets generated via an application executed on a telephone with an Android operating system. Elliptic curve algorithms used to generate private passwords demand that random numbers used be used only once because if this wasn’t the case, private passwords would be accessible. These random numbers are known as nonce and are vastly used in cryptographic systems to, amongst other things, avoid traffic reinjection attacks. Therefore, Android’s poor capacity and implementation of random number generation provoked the reutilisation of nonces used in the generation of passwords, creating collisions in the passwords of users. This allowed a mass theft of bitcoin wallets through the illegal access to wallets belonging to some users that had created their wallet on their mobile phones, from which fraudulent bitcoin transactions were made. 

How to improve the entropy of a system 

Systems based on Linux regenerate their entropy with supposedly random events, such as keyboard entry or movement of the mouse. You can consult the amount of entropy available with the following command:

# cat /proc/sys/kernel/random/entropy_avail

Note that if you carry out a /dev/random (the random number generator in these systems) consultation, the entropy of the system reduces. If the entropy of the system runs out, the RNG freezes and doesn’t provide more data until enough entropy has been gathered to continue generating. This means that RNG’s aren’t very useful for real applications that require great amounts of random numbers (such as generators of codes used once to recover passwords or online casinos).

To avoid the freezing of /dev/random and therefore avoid the generation of more random numbers, what is normally done is to use the output of /dev/random as a seed for the pseudorandom number generator available on /dev/random, it doesn’t freeze as the numbers are pseudorandom.

If the entropy of the system runs out, random number generation will continue but they will be more susceptible to being predicted, affecting the security of the system that uses it. To avoid this from happening periodically, a new seed is generated and the /dev/random pseudorandom number generation process will be restarted.

In December of 2013 the Linux 3.13’s kernel underwent an update to improve the entropy generation speed. It also changed the seed regeneration process and it was decided that the seed would be regenerated when the equivalent of 128 bits of entropy had been accumulated, instead of regenerating the seed with less bits as had happened on previous versions.

The gathering of entropy can improve by installing certain software tools (such as rng-tools) or some hardware components such as Entropy key, which is an additional source of entropy that improves the quality of the randomly generated numbers, or the radio decoder (RTL-SDR) which can also be used to improve the entropy of the system via the use of rtl-entropy.

In Windows, the gathering of entropy can be done by asking the user to move the mouse for a certain amount of time or randomly typing letters on a similar screen to the one in the following image, which is used in password management systems such as keepass.

Keepas Enthropy gathering

- Keepass entropy gathering -

Mobile systems are slightly more limited in entropy gathering, at least in terms of using their hardware resources. In these kinds of systems you can resort to sound captured by microphones, information from accelerometers or asking users to take a photograph to then use a hash cryptographic function and use the result of that operation as a CPRNG seed. These kinds of operations are capable of generating random numbers with enough entropy to be used safely.