What is a pseudo-random number generator (PRNG) and why do they matter?

Recently, a problem was discovered in the pseudo-random number generator which Google Chrome and Node.js's V8 JavaScript engine uses and depends on. The problem was that a pattern was discovered in the series of numbers which the RNG algorithm produced, meaning you could guess the "random" outcome at a probability higher than chance, giving you an advantage - whether the application is breaking encryption or passwords or beating games of chance.

Edward Snowden, who had worked for the CIA, warned of problems or backdoors in hardware random number generators which many computers which the public use rely on for security (if you have a good chance of knowing or guessing the RNG seed produced by such a compromised device then you have a chance of predicting the values some piece of software will use for it's "secret" numbers, enough of an edge to make an uncrackable code crackable by fast computers).

So even though Intel chips come with hardware random number generation capabilities which are easily accessed from code via an added instruction, certain systems software developers, whether due to Snowden or from other sources of skepticism, do not consider Intel's RNG to be secure.

Instead, we use PRNGs (pseudo-random number generators, algorithsm which are deterministic given any given seed, but whose distribution is seemingly unordered and not clustered around any values). This is what the popular Mersenne Twister algorithm provides. It's based on a large prime (Mersenne prime) number, and its implementations run fast.

This isn't just an academic or theoretical problem, but a class of vulnerabilities which have been exploited before resulting in financial losses: Users lost bitcoins from their hot wallets due to a problem in the randomness of /dev/random (source of randomness provided by Unix and Linux and in this case Android).

Any RNG depends on a seed which is used to start generating numbers. It cannot be the same static number for each start, otherwise the results will be predictable. So even a Random Number Generator needs another source providing a random number to start with, and this is what shows up in the /dev/random Linux pseudo-device mentioned earlier. Linux will already consider the timing of various hardware interrupts (like keyboards or network activity) as sources of entropy. Some portion of the current time (e.g. time modulo microseconds) can also be used as a seed. Besides what an Intel CPU implements, there are also external (USB) pluggable devices which serve as sources of entropy, using digitized values from random natural phenomena. Such external sources of entropy might be necessary if you need to generate many random numbers, so many that you will quickly loop into a repeating pattern.

Most developers don't need to worry about how to generate random numbers. They will just use whichever rand() function is provided by their programming language or a system library. It's great that the majority of developers don't need to be crypto experts but it means the common work we all rely on is all the more crucial.

What is a pseudo-random number generator (PRNG) and why do they matter? | TECH.SAIGONIST.COM

Error

×

Error message

  • Warning: mkdir(): Permission denied in boost_mkdir() (line 1347 of /home/tomo/web/tech.saigonist.com/drupal7/php/sites/all/modules/boost/boost.module).
  • Warning: Cannot modify header information - headers already sent by (output started at /home/tomo/web/tech.saigonist.com/drupal7/php/includes/common.inc:2776) in drupal_send_headers() (line 1486 of /home/tomo/web/tech.saigonist.com/drupal7/php/includes/bootstrap.inc).
  • Error: Class 'CToolsCssCache' not found in _cache_get_object() (line 32 of /home/tomo/web/tech.saigonist.com/drupal7/php/includes/cache.inc).
The website encountered an unexpected error. Please try again later.