12

Assume that I have a smart card that returns an 8 byte (for example) random value on reception of a command. The question is that:

How I can check if this value is really random? (I don't have any access to implementation and mechanism. I just see an 8 byte hex number.)

In the other world, Is there any way to check the randomness of output of the random generators based on the output? or the only way is analyzing the implementation and mechanism of generator?

  • You need to output many values in sequence, then test for randomness using standard test procedures for randomness – Richie Frame Mar 7 '15 at 9:12
  • @RichieFrame How many is typical? 1000 / 10000 / 100000? – TheGoodUser Mar 7 '15 at 9:30
  • @RichieFrame And how this test procedures detect randomness? – TheGoodUser Mar 7 '15 at 9:30
  • sample sizes vary per test csrc.nist.gov/groups/ST/toolkit/rng/documents/SP800-22rev1a.pdf – Richie Frame Mar 7 '15 at 9:38
  • The real problem with using samples in this case is likely to be the hardware - you need a lot of values, so have to spend time getting them. If the smart card is throttled (likely, for a couple of reasons), you may not be able to get enough samples to tell in a reasonable timeframe. – Clockwork-Muse Mar 7 '15 at 15:16
15

NIST has defined in NIST Special Publication 800-22 an extensive set of statistical tests for verifying a source of randomness.

However, while this is good enough to assert that a RNG is not obviously broken, it isn't sufficient to assert that a RNG is "good". It is the nature of RNGs that very subtle flaws can lead to breaking it. The only proper way of checking the robustness of an RNG is looking at the implementation.

  • 7
    In particular, a simple "counter+cryptographic hash function" looks random to anyone who doesn't know where the counter started, but is entirely predictable to someone who does. – Mark Mar 7 '15 at 11:00
2

Real "randomness" comes down to the amount of entropy in the samples. And entropy is more or less impossible to qualify in blackbox testing, as others pointed out. A good conditioning function and a simple input with very little information can pass statistical tests. So the tests can only point out that there is or isn't some inherent statistical weakness in the way the numbers were produced, they can't really confirm that they're unpredictable.

There are several elements that are important in evaluating an RNG's randomness, unpredictability, or its entropy:

  1. You need to determine whether you're talking about a true RNG with a live entropy source, or a DRNG with an initial seed (or a combination of the two).
  2. If there's a live noise source, you definitely need to check the implementation of the noise (entropy) source, and the underlying theory. Physical or stochastic models are used for this.
  3. When you're running statistical tests on output produced by the said RNG, it needs to be done on data collected prior to the application of a conditioning/compression function to get a clear idea on the real amount of entropy you're working with.
  4. If the RNG is not a true RNG, meaning that you're looking at a deterministic RNG, the DRNG algorithm implementation needs to be verified. This one can be done with test vectors.
  5. And finally, for a DRNG that doesn't have a live entropy source, the initial seed quality needs to be evaluated. If the seed is coming from a true RNG, then 1-3 above apply.

RNG evaluation has been getting a lot more attention recently, and the standards are becoming more stringent. You can look at the NIST SP800-90A/B/C series for a good overview of RNG design, and especially SP800-90B (still draft) for entropy source evaluation. BSI also has guidelines in AIS20/31 which explain how to evaluate RNGs.

And finally, NIST's STS 800-22a is a good test suite, as already pointed out. There's also the BSI's AIS20/31 test suite, and the Dieharder test suite as well.

2

You can't. It is impossible to verify that the output of a purported random generator is random enough for cryptography. (It is possible to verify that it's random enough for some applications such as Monte Carlo numerical methods, but not, say, to generate a cryptographic key.)

There exist cryptographically secure pseudorandom number generators, that is, random number generators which are deterministic but nonetheless indistinguishable from truly random sequences. We don't know how to distinguish the output of a CSPRNG from a truly random sequence: given part of the output of a CSPRNG, we don't know how to reconstruct the outputs we aren't given.

(We actually can't prove mathematically that a CSPRNG exists, but there are CSPRNG built on cryptographic primitives such as AES and SHA-2, which are CSPRNG under the same hypothesis that make AES suitable to derive encryption algorithms from, and SHA-2 a cryptographic hash function.)

Since a CSPRNG is deterministic, you know its output if you know its initial state; more generally, if you know its internal state at some point, you know all subsequent outputs. Thus a CSPRNG is a suitable way to generate cryptographic keys and other random values for cryptography only if the adversary doesn't know the internal state.

A CSPRNG whose internal state is known to an adversary (not suitable for cryptography) is not distinguishable from a CSPRNG whose internal state is not known outside the smartcard (suitable for cryptography). Thus it is impossible to test the quality of an RNG from its output alone. All you can see from the output is to detect some grave flaws, but not all grave flaws.

In order to verify that an RNG does its job, it is necessary to look inside. This is done in two parts:

  • Verify that the CSPRNG uses an appropriate algorithm and is implemented correctly.
  • Verify that the CSPRNG is seeded from material that is not known to an adversary.

(An RNG based on physical processes alone pretty much always has detectable biases, so physical RNG are not used directly, but fed as entropy input (i.e. seed) to a CSPRNG.)

The CSPRNG implementation is validated by examining the source code, checking that the algorithm is a good one (algorithms from standards such as NIST SP 800-90A are typically prefered or even mandated), and conducting a few tests to detect implementation errors such as storing the result at the wrong address.

The seeding of the RNG is more delicate to validate. Some systems include a “true random number generator”, i.e. a piece of hardware that returns unpredicatable bits based on unpredictable physical processes such as radioactive decay or chaotic oscillators. Validating these is conducted with statistical tests that demonstrate that the output of the TRNG has sufficient entropy.

Note that the TRNG may actually not be “truly random”: it can have biases. What is important is that it is sufficiently random so that the probability of correctly predicting its next output is so low that the adversary will not be able to make an informed guess. These biases are why a CSPRNG is applied to the output of the TRNG: the use of a cryptographic “mixing” function turns observable correlations (e.g. if a bit is 0 then the next bit has a 52% chance of also being 0) into correlations that are impossible to calculate.

It is also possible to make an RNG by seeding the CSPRNG once and for all with a secret value. This is viable only you are sure that the internal state of the PRNG will not leak out. The seed value itself must be generated randomly, ultimately from some form of TRNG; but this way, the TRNG can be in the factory, rather than in the device where the RNG runs.

As a purchaser of smartcards, you cannot look inside to see what the card is doing. (Not being able to look inside is an important property of smartcards.) However, the card you're using may have been evaluated by a security laboratory. There are standards to evaluate the security of smartcards, such as Common Criteria protection profiles. You can check if your card has been certified. CC aren't the only such certification; credit card companies such as Visa and Mastercard have their own certification process. If the card has been evaluated, your vendor should point you to the certificate — it's a marketing argument. There are many smartcard certifications and they test different things, so check exactly what the certificate guarantees. You won't find out exactly how the RNG works (that's usually a trade circuit), but you'll know that a security laboratory looked into it and found no flaw.

-1

Use it to generate an image: random x, y, r,g,b... spot any pattern..?

Update: While I agree that 1) this is not a very scientific method, and 2) it doesn't prove that the RNG is cryptographically secure, it is a quick and easy way to check if a RNG is not random... E.g. here's a visualisation of .net's System.Random:

random scatter with x/y/argb generated from System.Random

  • Good idea. But how I can do it? – TheGoodUser Mar 7 '15 at 8:48
  • He has an 8 byte, so 64 bit number. Suppose the bitstream repeats itself every 63 bits. You won't notice the 63 image pattern. Instead, you should look at the bitstream itself and see when it starts repeating itself. – user21287 Mar 7 '15 at 9:13
  • @CamilStaps Yes, a very clear pattern will be visible (in a trapezoid form). Try this out. – peterh says reinstate Monica Mar 7 '15 at 11:23
  • @peterh you can easily miss this. Also, try what happens when it repeats itself every 1023 bits, and you have a repetition after lcm(1023, 64) = 65472 images. The problem is that with a small number of bits in the repetition pattern, the number of images in the repetition pattern is already very large. – user21287 Mar 7 '15 at 11:25
  • 1
    While this may be a very rough indicator of statistical randomness, it tells you nothing about the unpredictability of the output, which is critical for cryptographic randomness as the question is tagged. – Xander Mar 7 '15 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.