Random number generation strategies

From Randomness for cryptography
Jump to navigation Jump to search

Several random number generation strategies have been proposed for cryptographic use:

Use a hardware bit stream for all needs

  • AIS31 circuit: dual Zener diodes in avalanche mode, one connected to + input and one to - inputs of an op amp. Sampled sign of op amp output voltage becomes output bit.
  • difficult to tune a simple bit generator to be bias free
    • small bias may be harmless, can provide auditability
  • use whitening, but where?
    • inside sealed hardware box --idiot proof, but can conceal mischief; NIST 800-90B model
    • in software, requires careful programming, but allows some auditing, agr critique
  • commercial TRNGs
  • Linux /dev/random
  • Turbid ?

Seed once

  • Seed once with good entropy source and use strong PRNG thereafter
  • No recovery from internal state compromise
    • Some attacks have episodic success
    • Some systems run for years non-stop. Would one really use the same entropy forever when updating is cheap?

Seed periodically

  • Linux dev/urandom
  • Yarrow and Fortuna
  • Dodis algorithm -- theoretical basis for PRNG with input

Bernstein critique of mixed inputs

  • attacker with knowledge of PRNG state and control of last state can influence RNG output
  • DSA particularly vulnerable
  • responses
    • DSA is a bug
    • attacker with that level of knowledge has other attacks
      • but none as clean as a corrupted RNG -djb
    • use a key stretcher - agr
    • Dodis paper

Testing RNGs

  • NIST and AIS tests
    • can detect bad design and hardware failure, but can't distinguish TRNG from cooked PRNG
  • Entropy estimation, eg. Linux /dev/random. Bad idea according to Dodis
  • Audit tests

Are there upper bounds?

Do upper bounds exist for amount of data to be captured for various entropy sources to get a minimum seed (e.g. 256 bits)? (e.g. NIST SP-800-90C section 4.2)

Hard Truths about the Hard Business of finding Hard Random Numbers

In a 12 point strategy for building a random number generator, [serial skeptic Iang writes]:

  1. Use what your platform provides. Random numbers are hard, which is the first thing you have to remember, and always come back to. Random numbers are so hard, that you have to care a lot before you get involved. A hell of a lot. Which leads us to the following rules of thumb for RNG production.
    1. Use what your platform provides.
    2. Unless you really really care a lot, in which case, you have to write your own RNG.
    3. There isn't a lot of middle ground.
    4. So much so that for almost all purposes, and almost all users, Rule #1 is this: Use what your platform provides. E.g., for *nix, use urandom [Ptacek].
    5. When deciding to breach Rule #1, you need a compelling argument that your RNG delivers better results than the platform's [Gutmann1]. Without that compelling argument, your results are likely to be more random than the platform's system in every sense except the quality of the numbers.

That warning duly given, [proceed to points 2 thru 12].