In the constantly evolving world of cybersecurity, certain aspects are quite vital to ensure the integrity and confidentiality of our systems and ultimately to ensure our cryptographic systems are strong enough to provide such properties. Among these aspects are cryptographic random number generators (
CRNG). Cryptographic Random Number Generators are vital to the robustness of our existing cryptographic systems and even security protocols. They are mainly about producing unpredictable and non-repeating sequences of numbers which ensures that encrypted data remains hidden to unauthorized parties. Furthermore, CRNG’s are one of the main aspects that are used in cryptographic key generation which are essential for lots of security protocols.
Categories of Random Number Generators
1) True Random Number Generators (TRNGs):
First type of random number generators are True Random Number Generators (TRNG) which are used to produce random numbers by using certain unpredictable physical properties. The reason why it uses physical processes is because they are hard to predict and thus their outcome can’t be reproduced. Accurately measuring physical properties like atmospheric noise, thermal noise in electronic circuits and even things like radioactive decay can be used to obtain some organic naturally-generated random numbers.
2) Pseudorandom Number Generators (PRNGs):
Pseudorandom Number Generators (PRNG) utilize some deterministic mathematical algorithms to produce random sequences of numbers. However, they utilize a “seed” value into those algorithmic calculations which will always produce the exact same sequence of numbers for a particular seed value. Thus the seed needs to be changed in order to achieve true randomness every time and it must be protected to avoid predicting the certain sequence of numbers generated. Another property of PRNG’s is that they are periodic and will always repeat after reaching a certain number in the sequence. However, they only repeat after extremely long periods making repetition quite unlikely in a practical scenario.
3) Cryptographically Secure Pseudorandom Number Generators (CSPRNGs or CRNGs):
Cryptographically Secure Pseudorandom Number Generators (CSPRNG’s) which are also referred to as Cryptographic Random Number Generators (CRNG’s) are a specific type of PRNG’s (Pseudorandom Random Number Generators) which are widely used for cryptographic algorithms. Their output is computationally un-distinguishable from truly random numbers which means that even if an attacker knows a certain portion of the generated sequence they won’t be able to predict any of the future generated random numbers using CRNG’s.
Features of a well-designed CRNG
1) Unpredictability
A good cryptographic number generator must produce numbers that are unpredictable. As we mentioned previously, the output of a Cryptographically Secure Random Number Generator (CSPRNG’s or CRNG’s) must be computationally indistinguishable from truly random numbers which means that even with investing a large sum of computing power, the attacker still wouldn’t be able to distinguish the CRNG generated numbers result from a truly random stream. We can test this phenomenon using the “next bit test” where given a sequence of generator produced bits, no algorithm will be able to predict the next bit with a probability of success better than 50%.
2) Statistical Randomness
Beyond cryptographic unpredictability, it’s also important that CRNG’s have a strong statistical properties of randomness which eliminates obvious patterns and ultimately avoids predicting the random numbers patterns. Statistical testing can be done to test out whether a random number generator does actually produce numbers that are random enough to avoid statistical correlations. This is where the NIST (National Institute of Standards and Technology) stepped in and created a comprehensive testing suite published in their NIST SP 800-22. These tests examine aspects like the frequency of bits, the lengths of identical bits runs and other sophisticated statistical patterns which if passed shows how much the generated random numbers output is uniformly distributed and ultimately how much free it is from detectable correlations and biases.
3) Resistance to Cryptanalytic Attacks
A well-defined CRNG must also be able to withstand cryptanalytic attacks like the “state compromise extension attack” in which an attacker who somehow managed to reveal part of the CRNG’s internal state at a given moment wouldn’t be able to computationally reconstruct the stream of random numbers generated right before the moment of revealing this internal state part of the CRNG. This is called forward secrecy. Likewise they also shouldn’t be able to predict future outputs of the disclosed internal state of the CRNG which in turn is called backward secrecy.
CRNGs must also be resistant to side-channel attacks which exploit subtle information leakage from the implementation of a system like timing variations and/or power consumption.
Key Properties of a Good CRNG
| Property | Description |
|---|---|
| Unpredictability | Computationally infeasible to predict future outputs; passes the "next-bit test" |
| Statistical Randomness | Output exhibits uniform distribution and passes rigorous statistical tests (e.g., NIST SP 800-22). |
| Backward Secrecy (Prediction Resistance) | Compromise of a long-term secret key does not compromise the secrecy of future encrypted communication. |
| Resistance to Cryptanalytic Attacks | Withstands mathematical and algorithmic attacks (e.g., brute-force, differential cryptanalysis) against its design. |
| Resistance to Side-Channel Attacks | Mitigates information leakage from physical or software implementation characteristics (e.g., timing, power consumption, cache access patterns). |
The Foundation of Randomness - Entropy
What’s Entropy
Entropy is essentially the measure of uncertainty or disorder within a system which ultimately shows the degree of unpredictability of a random-event. A well-defined entropy is usually defined from unpredictable environment events in which the higher the entropy, the greater the randomness and unpredictability which is typically measured in bits. All encryption keys must be generated using a highly strong level of entropy which is also used in creating unpredictable sessions tokens and protecting against replay attacks.
Entropy Sources
Entropy can be harvested from various sources:
- Hardware Based Entropy Sources (
HRNGs): These are considered the gold standard as they leverage the inherent unpredictability of physical processes. Examples include:- Natural activities like thermal noise in electronic circuits, atmospheric noise, radioactive decay, and even electronic noise.
- Dedicated Hardware like CPU on-chip random number generators, and specialized entropy-gathering cards.
- Software-Based Entropy Sources: Operating systems collect "random" events from various system activities and environmental noise like:
- User Interactions like the timings between keyboard inputs and subtle variations in mouse movements.
- System Activity like Disk operations (for example seek times, or access patterns), and network packet arrivals.
NIST Special Publication 800-90A of DRBGs (Deterministic Random Bit Generators)
NIST SP 800-90A publication provides some detailed recommendations to be employed for random number generation within cryptographic systems. NIST SP 800-90A outlines techniques for generating random bits by utilizing Deterministic Random Bit Generators (DRBG's) which are a type of CSPRNG’s. DRBG’s designed under this standard are considered to be “backtracking resistant” which means that they have both forward secrecy (past outputs can’t be recovered) and backward secrecy (future outputs are also unpredictable after reseeding).
Exploring Hash_DRBG, HMAC_DRBG, and CTR_DRBG
NIST SP 800-90A recommends three primary DRBG (Deterministic Random Bit Generators) mechanisms for cryptographic use :
Hash_DRBGwhich is constructed using a cryptographic hash function like SHA-256 and thus it relies on the strong properties of hash functions, such as collision resistance and preimage resistance.Hash_DRBGis generally considered to be a robust Deterministic Random Number Generation methodology which aligns with NIST's security expectations and claims.HMAC_DRBGwhich is based onHMAC(Keyed-Hash Message Authentication Code) construction which combines a cryptographic hash function with a secret key and this leads to a high security margin. However, it’s not considered to be forward-secure when utilized without any additional input.CTR_DRBG: It utilizes a block cipher such asAESthat’s operating in counter mode in which its security depends on the strength of the underlying utilized block cipher. However, despite its wide usage, it’s been found thatCTR_DRBGhas major imperfections related to the interactions between the block cipher's block size and the requested key size, which ultimately limits its effective security level.
Common Vulnerabilities and Implementation Weaknesses
Predictable Seeds
Sometimes initial seeds are predictable or could be derived easily using some guessable data. If seeds have been predicted then an attacker can potentially predict all subsequent generated random numbers by the CRNG. This type of vulnerability usually arises where the seed value is obtained from easily accessible system information like timestamps or Process ID’s for instance.
Side-Channel Attacks
Side-Channel attacks are a major threat to CRNG’s. The way they work is by exploiting subtle information leakage from the CRNG system instead of exploiting existing flaws in the cryptographic algorithm itself. Some examples of information to be used in Side-Channel attacks involve physical properties leakage like power consumption and software-based properties like timing variations in operations and cache access patterns. However, it’s possible to greatly limit the successful attack possibility of Side-Channel attacks by employing constant-time algorithms where execution time is dependent on secret unpredictable data and even by injecting unexpected delays to the physical or software properties so their leakage won’t be meaningful by attackers.
Conclusion
Overall, creating a good cryptographic random number generator requires much more than just unpredictability in generating random numbers. It requires the ability to withstand most sophisticated adversary attacks. Computational unpredictability is a must for all CRNG’s to prevent predicting future or past random number outputs even with a significant amount of computational resources employed by attackers. Additionally, robust entropy management plays a big role in protecting the integrity of CRNG’s. The existence of vulnerabilities like predictable seeds and side-channel attacks suggests that algorithmic flaws could arise and thus ensuring the quality of cryptographic randomness requires careful consideration to standards like NIST SP 800-22 with the goal of creating and designing well tested Cryptographic Random Number Generators that will be key to strong cryptographic systems and ultimately, the key to a safer digital world.
