Random, But Not Too Random: Best Practices for Cryptographic RNGs

I. Pendulum and random numbers.

Recently, I’ve been playing with different physical models and, in particular, with a double pendulum here:

https://www.myphysicslab.com/pendulum/double-pendulum-en.html

It looks nice and, most interesting, this kind of pendulum is almost chaotic and predicting its exact motion over long periods is nearly impossible.

After dealing with cryptography applications in the payment world for so long, I could not resist asking myself “Can this pendulum be used as a random number generator?” Unfortunately, it is very easy to answer NO to that question. I won’t bother you with formulas but if we can measure the angles of both pendulum’s parts with 1/1000 radian accuracy, we will have only 39 million states, which gives an entropy size of approx. 25 bits. This is way too few, having in mind that many standards (including NIST SP 800-57, FIPS 140-3, EMVco, PCI Secure Software, PCI 3DS SDK, and others) require 128 bits of entropy whenever you generate a random number to be used by your payment application(s).

II. Good and bad ways to generate a random number.

In your payment application(s), you might need a random number on many occasions. This can be a key generation seed, a hashing salt, an initial secret sequence number, etc. So, what are good and bad practices when generating random numbers? Good practices include:

• `Using OS-based RNGs:
  • /dev/urandom` (Linux/Unix): Provides high-quality entropy, including 128-bit values. It is a non-blocking RNG and generally suitable for cryptographic use.
  • `CryptGenRandom` (Windows): This is the cryptographic API for generating random data with sufficient entropy for security applications.
  • `/dev/random` (Linux/Unix): While it blocks until sufficient entropy is available, it can also be used to obtain 128 bits of entropy, although slower than `/dev/urandom`.
• Libraries:
  • OpenSSL’s `RAND_bytes()` function: A widely used function that provides cryptographically secure random bytes, including 128 bits of entropy.
  • Python’s `secrets` module: For example, `secrets.token_bytes(16)` generates 16 random bytes, equivalent to 128 bits.
  • Java `SecureRandom`: In Java, the `SecureRandom` class can generate random values with cryptographic security, and 128 bits of entropy can be obtained by calling `SecureRandom.nextBytes()` with 16 bytes.
  • C `getrandom()` or `/dev/urandom`: Provides high-quality entropy, including 128-bit values.
• Hardware RNGs:
  • Intel’s RDRAND instruction: Available in many modern processors, this hardware RNG can directly provide 128 bits of entropy.
  • TPM (Trusted Platform Module): Provides cryptographic functions, including a hardware-based RNG.
• Bad practices include but are not limited to: random (Python), java.util.Random (Java), rand() (C language), or any kind of unapproved in-house RNG implementations. In most cases, the behaviour of these functions is predictable or they have too low initial entropy (like 48 bits).

III. Is my random number random enough?

Here we come to the reality check. When the SSF Secure Assessor checks your payment application for conformity with PCI SSF Secure Software Standard, the Assessor needs to validate your random number generators, whenever you use them. Essentially, the Assessor will ask you to generate 128 MB of test data using the function you use as a part of your software and validate its entropy.

PCI Secure Software recommends using NIST Entropy Assessment Tool. However, this is not a silver bullet and it does not give a black/white answer to whether your data is random enough.

To check that out, I generated four 128 MB blocks of data – using “good” and “bad” methods in Java and Python. The source code is available here.

Compiling the NIST tool does not pose any difficulties, at least on Ubuntu. However, running it may cause problems. First of all, the NIST tool is too demanding for the RAM. While running a basic test (iid_main.cpp), working with 128 MB of data requires at least 2 GB of RAM, so don’t run it on a micro cloud instance:

I could not run the advanced test (non_iid_main.cpp) as 8 GB of RAM was not enough, the process got killed on an AWS large instance, and I did not want to build yet another bigger instance.
Finally, the test is time-consuming. A basic test may take from 15 minutes to 3 hours on a large AWS instance. The results of tests are confusing:

	Test completion time (128 MB of test data)	H_bitstring	Chi-square Independence Test P-value	Chi-square Goodness of Fit Test P-value
Bad data (Python)	20 min	0.99984490850420782	0.31214656305242844	0.75563114566736833
Good data (Python)	22 min	0.99982920342511217	0.61164925080183941	0.95766589187690976
Bad data (Java)	3 hours	0.99983017608714864	0.79916871420328883	0.65182898948313528
Good data (Java)	23 min	0.99988509225229938	0.81589825130926297	0.55152294466919871

The bad surprise is that all tested data looks good from the NIST Tool perspective, moreover, the P-value for Java “good” data looks worse than the P-value for “bad” data. So, is there another way to answer our main question without a doubt?

IV. Using Dieharder tool

Another alternative to the NIST Tool is Dieharder.

It can be installed on Ubuntu very easily just by typing “sudo apt-get install dieharder”. The tool runs a wide variety of tests over the data provided and gives a very detailed report. It’s much faster and less RAM-consuming:

Let’s see what it shows us. Most tests are passed, I will omit them here and below, tests identified as “WEAK” are listed below. Bad data (Python):

• sts_serial|  15|    100000|     100|0.99863013|   WEAK
• rgb_bitdist|   4|    100000|     100|0.99823695|   WEAK

Good data (Python):

• rgb_lagged_sum|   7|   1000000|     100|0.00423489|   WEAK  

Bad data (Java):

• sts_serial|  14|    100000|     100|0.99848383|   WEAK
• sts_serial|  15|    100000|     100|0.99879386|   WEAK
• rgb_bitdist|  11|    100000|     100|0.99761733|   WEAK

Good data (Java):

• sts_serial|   3|    100000|     100|0.99770998|   WEAK
• sts_serial|   6|    100000|     100|0.99652944|   WEAK
• rgb_lagged_sum|  10|   1000000|     100|0.99879643|   WEAK
• rgb_lagged_sum|  30|   1000000|     100|0.99723789|   WEAK

V. Conclusion

Unfortunately, using the tools I showed you above, it is not possible to say with confidence that the random numbers you produce are “good” or “bad”. Statistical tests may react to extreme cases or algorithm non-conformities in a strange way. Therefore, all tested data is “good enough”, at least from the assessment tools’ point of view. I, as an assessor, am going to have a hard time explaining why you should not be using weak random number generation functions, but I will try.

To sum up, generating secure random numbers is essential for maintaining the integrity of cryptographic systems, especially in payment applications where compliance standards are strict. While tools like the NIST Entropy Assessment Tool and Dieharder provide valuable insights, my tests demonstrate that these tools may sometimes yield ambiguous results. This underscores the importance of selecting robust RNG methods and understanding the limitations of assessment tools.

Key Takeaways for Developers:

• Use Proven RNG Sources: Rely on cryptographically secure RNGs provided by the operating system (/dev/urandom on Unix/Linux, CryptGenRandom on Windows) or libraries such as SecureRandom in Java and Python’s secrets module.
• Avoid Predictable RNGs: Avoid non-secure RNGs like rand() in C or java.util.Random in Java, as they lack the entropy required for cryptographic security.
• Perform Rigorous Testing: For critical applications, consider running multiple types of tests (like both NIST and Dieharder) to validate your RNG output. Be cautious of “WEAK” results or P-values close to 1, as they can indicate potential issues.
• Monitor and Update RNG Practices: Cryptographic standards evolve, so keep up-to-date with recommended practices from organizations like NIST, PCI, and EMVCo to ensure your random number generation methods remain compliant.

Ultimately, secure random number generation is about balancing practicality with rigor. By using high-entropy sources and avoiding known pitfalls, developers can help ensure that their applications meet both security and compliance requirements.

Any word of wisdom from anyone having better experience with these analysis tools will be highly appreciated!