NIST Updates Random Number Generation Guidelines

An anonymous reader writes: Encryption weighs heavily on the public consciousness these days, as we've learned that government agencies are keeping an eye on us and a lot of our security tools aren't as foolproof as we've thought. In response to this, the National Institute of Standards and Technology has issued a formal update to its document on how to properly generate a random number — crucial in many types of encryption. The update (as expected) removes a recommendation for the Dual_EC_DRBG algorithm. It also adds extra options for CTR_DRBG and points out examples for implementing SP 800-90A generators. The full document (PDF) is available online.

Comments

Bad RNG will make your crypto predictable

[sinij]

One of they few poorly understood concepts in software development is that improperly initialized (called seeding) DRBG will break your crypto.

For Linux, and especially for headless systems, use /dev/random for seeding. You want it to block if not enough randomness available.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

Meh. It's all a crap shoot.

Re:Bad RNG will make your crypto predictable

[ArylAkamov]

Anywhere that somebody who knows jack shit about encryption could learn about this?

Re:Bad RNG will make your crypto predictable

[EmeraldBot]

One of they few poorly understood concepts in software development is that improperly initialized (called seeding) DRBG will break your crypto. For Linux, and especially for headless systems, use /dev/random for seeding. You want it to block if not enough randomness available.

Ehhhh, not always.

Re:Bad RNG will make your crypto predictable

[Copid]

The classic Schneier Applied Cryptography is a great read for anybody who wants a good starting point on the basic concepts and practical considerations. It's technical-ish but conceptual rather than mathematical and leans toward describing what the various crypto pieces do, why they exist, and what they're used for. To get a good intro to some math, try The Handbook of Applied Cryptography. If you have a little bit of number theory and are willing to do some exercises up front, the book is largely self-contained and very well written. It's free for personal use, but nobody I know regretted buying a hard copy.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

Many decades ago a weatherman told me that FM static is a pretty good random number generator.
Would that be a usable source to sample, and what would be potential downsides, i.e. if somebody in the same region were to record static and use that as a basis to break your randomness?

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

Get a survey meter and some potassium chloride from Whole Foods.

Re:Bad RNG will make your crypto predictable

[mlts]

What I liked was the original version of PGP when it would ask you to type some random numbers/letters and would use that as a seed.

It depends on the crypto I was doing: For a number of tasks, say if I were rolling dice for a game, /dev/urandom is good enough. For generating a nonpersistant key (like a session key that is used and tossed during a SSL transaction), /dev/random. For a key that is persistant, it might be even better to use /dev/random, but also ask the user to toss in some random keypresses/mouse movement [1], similar to how TrueCrypt and KeePass request it. This way, if there is something defective with the RNG, it is mitigated by a chunk of random bits from the user.

[1]: Take the time down to as precise as possible, plus the keystroke result itself, hash it (using the hash function as a "bit blender"), toss that in. For mouse movements, take measurements every random fraction of a second, hash those, toss those in as well.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

I doubt that keyboard input can be random because certain keys are more likely to be used

Re:Bad RNG will make your crypto predictable

[Bruce Perens]

The problem with FM static is that you could start receiving a station, and if you don't happen to realize you are now getting low-entropy data, that's a problem.

There are many well-characterized forms of electronic noise: thermal noise, shot noise, avalanche noise, flicker noise, all of these are easy to produce with parts that cost a few dollars.

Re:Bad RNG will make your crypto predictable

[Bruce Perens]

Most algorithms to do this use the time between keypresses, measured to very high precision so that the lower bits are chaotic. So it doesn't really matter what keys you hit, and it doesn't matter how rythmic your typing is.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

Ehhhh, not always [2uo.de].

Wow some guy (with his only other publication being a web caching tutorial) argues that secure random numbers are bad since blocking runs counter to availability and claims that since the random data from the entropy pool gets fed into a csrng it is no longer different from numbers generated by a predictable seed fed into the same csrng. The whole point of /u/random is being unpredictable, if a "random looking" number is all you want then the c rand function with a seed of 42 may be more then enough for you*, if you want a number the NSA/GCHQ/BND/KGB are unlikely to find you use the entropy pool version which gives you a number generated from an unpredictable seed.

I get his standpoint, he is a functional safety engineer, services that can block for an unknown time are against everything he stands for. There are however hardware sources for randomness and more than enough services and software that can wait for a bit to get a random number ( some only use it as a seed to an internal csrng ), I have even seen software that actively asks the user for entropy ( move mouse around ).

* Correction: if you want a random looking number rand() is most likely not what you want, it is widely considered bad. Most people using it to generate random numbers mess up the distribution without even noticing. There are however many better alternatives available.

Re:Bad RNG will make your crypto predictable

[Alain Williams]

The trouble with FM static is that your ''enemy'' could also observe what you observe and thus have a good idea of what you are basing your random numbers on.

Re:Bad RNG will make your crypto predictable

[davester666]

yes, then drink the potassium chloride, and have someone time how long it takes you to die. that time will be sufficiently random for our purposes.

Re:Bad RNG will make your crypto predictable

[bytesex]

Sweeping statement - not necessarily. Pre-shared keys and all that. It is possible to make good crypto systems without using random. Sorry to be autistic about it.

Re:Bad RNG will make your crypto predictable

[bytesex]

It also means that you're allowing an outside source, which is extremely easy to manipulate (a van parked outside your house with a transmitter) to create your random.

Re: Bad RNG will make your crypto predictable

[AvitarX]

I would think non random pre shared keys are attackable.

At the extreme case, you end up with a Caesar shift.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

I think that you might die faster if it was potassium cyanide, potassium chloride is a salt substitute that is slightly less radioactive than bananas

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

The "time to die" will be more random if you take potassium chloride.

Re:Bad RNG will make your crypto predictable

[mlts]

If we pull numbers off a high precision clock function like Linux's clock_gettime (which has a nanosecond precision rate), it matters less what exact key the user pressed, because the part that rapidly changes (interval between keys, or even the absolute time (year/month/day/hour/minute/second/billionths of a second) can be used by running the output through a hashing algorithm and tossed into the RNG pool.

One you get into microsecond and nanosecond resolution, that is a quite usable random number source, since someone might be able to tap a key (even repeatedly) on a tenth to hundredth of a second scale, but definitely not be able to give repetitive keystrokes on a nanosecond level.

What key they press might give around six bits of random data, but you can get significantly more bits (20-30) per keystroke just from the high precision timer.

Re: Bad RNG will make your crypto predictable

[MadChicken]

Wouldn't they also have to know your sampling frequency for that to be of any use? And I'm guessing if you randomized that, they'd have to follow your entire tool chain to get the same random result. I'm just thinking out loud here...

Re:Bad RNG will make your crypto predictable

[davester666]

No, it will be sooner and less random.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

It's not a crapshoot. Using /dev/random is just plain idiotic. Both /dev/random and /dev/urandom use the same cryptographic primitives to hash the input seeds. Once you've fed a sufficient number of bits into the pool (e.g. 128), there's cryptographically no distinction to be had thereafter. Which means /dev/random is no better than /dev/urandom. If the cryptographic primitives are broken you can't trust either; if they're not broken both will emit streams which are indistinguishably random.

Relying on /dev/random being stronger is just believing in magic. And _real_ cryptographers will tell you this. Dan Bernstein goes even further and suggests that any system which continually reseeds it's PRNG is _worse_ than one that just seeds once, because the window for manipulating the PRNG is much wider, not to mention continually open.

The irony is that the OP think's he's being smart and intelligent. This kind of rubbish is why a little knowledge (heck, even alot of knowledge) can be a very dangerous thing.

Re: Bad RNG will make your crypto predictable

[Anonymous Coward]

It matters in as much that using keyboard input requires much more sampling than you would intuitively think. But, sure, there is entropy.

The problem with keyboard input is that we don't know how much entropy is there. With a diode or decay emitter, we can scientifically and mathematically know bounds on the entropy production. With keyboard input we're at the mercy of future experiments showing less entropy than we think. Which has been born output by history, especially since the advent of smart phones. Now fairly frequently researchers show new and novel techniques which lower the entropy estimates. And we can't know how low it will go, not anytime soon.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

Potassium chloride is only slightly less more than regular table, and it causes the same reaction if you take a lot of it at once: you throw up. In the long run, it is more difficult to have too much potassium compared to too much sodium.

Re:Bad RNG will make your crypto predictable

[sinij]

Using /dev/random, among many things, ensures that your long-term keys are not easily factorable. If all you are concerned is performance, then why even bother with cryptography?

Re:Bad RNG will make your crypto predictable

[sinij]

Also, when you are ready to take a leap from little knowledge, to a little bit more knowledge, read this paper: https://www.usenix.org/system/...

Re:Bad RNG will make your crypto predictable

[VTBlue]

Great resource! Thanks for this link.

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

that works only IFF the clock *really* gives nanosecond resolution and not just nanosecond values, but sampled at ten microsecond or so intervals, i.e. the nanosecond part predictable (e.g. always zero).
With all the caching and power saving (which means "waking up as seldom as possible") I wouldn't count on that. Hardware is tricky in that regard, as is modern optimized software.

Re: Bad RNG will make your crypto predictable

[Anonymous Coward]

With a diode or decay emitter, we can scientifically and mathematically know bounds on the entropy production

Until a weakness is found with a particular implementation or environment...

Re:Bad RNG will make your crypto predictable

[Anonymous Coward]

The thing is, mister /dev/urandom is going to be right 99.9% of the time but there will be that time that the weak pool was entirely predictable and the state can be guessed.

Hm....

[Anonymous Coward]

Well, as long as it doesn't effect ECDHE, eh?

Re:Hm....

[bytesex]

Lucky for us, Diffie-Helmann requires a random sources on each side. If your RNG is broken and your counter-party's isn't, you're still good.

Re: Hm....

[Anonymous Coward]

NSA used NIST to corrupt ECC.

Screw NIST

[Guy From V]

They're more like guidelines anyway.

Software should work

[maryjanety3]

There is no reason for creating dodgy software http://www.dailymotion.com/vid...

Randomness can't come from a computer program

[Bruce Perens]

True randomness comes from quantum mechanical phenomena. Linux /dev/random is chaotic, yes, enough to seed a software "R"NG. But we can do better and devices to do so are cheap these days.

I wouldn't trust anything but diode noise for randomness. If I had a need to transmit messages privately, I'd only trust a one-time pad.

Re:Randomness can't come from a computer program

[Anonymous Coward]

Most of us do have a need to transmit messages privately. Do you not make any online purchases?

Re:Randomness can't come from a computer program

[Anonymous Coward]

OneRNG - An Open and Verifiable hardware random number generator -- relevant talk from Linux.conf.au 2015. It uses diode and (optionally) RF noise to generate a stream of high-quality entropy which couples directly to the kernel.

They touch upon a concept that I believe many admins should be aware of: if you do mass-deployment of machines, this might very well include generation of e.g. SSH keys. The problem is if the keys are generated in such an early stage that the random pool has not been able to be readily distinguished from other machines within the deployment. This might open up the possibility for an attacker who has knowledge about a less privileged machine within such a deployment to attack machines which in a later state got more important roles.

I have even seen situations where companies have created images with pre-generated cryptographic signatures, making all machines within a deployment hold the exact same secret information...

Re:Randomness can't come from a computer program

[QuasiSteve]

To throw another one out there - lower bitrate, different approach, much cheaper (especially if built yourself - designs are completely open): https://github.com/waywardgeek...

Re:Randomness can't come from a computer program

[Anonymous Coward]

I have used one-time pads to generate password salts. Works well, and every time a salted password is sent over the net, it is unique. Did that in the mid-1990's for manufacturing systems.

Re:Randomness can't come from a computer program

[Bruce Perens]

Most of us do have a need to transmit messages privately. Do you not make any online purchases?

Yes, but those have to use public-key encryption. I am sure of my one-time-pad encryption because it's just exclusive-OR with the data, and I am sure that my diode noise is really random and there is no way for anyone else to predict or duplicate it. I can not extend the same degree of surety to public-key encryption. The software is complex, the math is hard to understand, and it all depends on the assumption that some algorithms are difficult to reverse - which might not be true.

Lottery machine?

[Anonymous Coward]

How about turning some kind of analogy of the function of a lottery machine into some code/device for creating random numbers? (Assuming there isn't any cheating implemented ofc.)

Re:Lottery machine?

[black3d]

From a code approach it's pointless, because the physical simulation would run exactly the same each time. Unless your randomize various factors such as for example, the release time of the balls, the speed the wheel which "mixes" them up. However, for this approach to work, you still need your underlying random number generator to already be working to generate the randomization required by the physics engine. And at the end of it all, you're putting a whole lot of effort into a limited entropy randomization system when you could just use a couple of dedicated algorithms to achieve a much greater result.

From a device point of view, yes - this is basically what hardware random number generators are. There are lots of different ones out there that use different factors such as background radiation, RF noise, plasmas, etc, to create a non-reproducible value. Most of them are pretty good at what they do, and while some may be "better" than others, the differences in the degrees of entropy they produce are largely academic - almost any of them will do the job.

Re:Lottery machine?

[Psychotria]

I agree. The outcome from lottery machines is way too predictable and that's why I'm a billionaire having never worked a day in my life.

Re:Lottery machine?

[Anonymous Coward]

From a code approach it's pointless, because the physical simulation would run exactly the same each time

Chaotic systems are determinant, so that if you start with the same starting conditions you get the same results. A simulation with no changing inputs would get the same result every time. Real life doesn't allow you to measure starting conditions with enough precision to maintain an accurate prediction over long enough time periods (solutions in chaotic systems diverge exponentially with time, so you would need to exponentially improve your accuracy of your measurement to get a constant gain in useful time).

hardware random number generators are. There are lots of different ones out there...

And yes, as said, ones not based on physical simulations exist, and you can find even ones rolling physical dice. But the purely electronic ones are much faster, smaller, cheaper, and quieter.

Re:Lottery machine?

[black3d]

Your reading comprehension needs some work.

A lot of effort to make sure bits aren't leaked

[thogard]

Why do so many systems still use the hashed root or admin password to seed tcp sequence numbers? Cisco, Sun, IBM and DEC all started doing it about the same time. So who suggested it to them and just how many groups know how what it takes to pull bits out of that hash?

Re:A lot of effort to make sure bits aren't leaked

[Anonymous Coward]

Fascinating! Where did you read about this? Got a link?

Is this what has been holding up SHA-3?

[Anonymous Coward]

Is this document what has been holding up the finalizing of SHA-3? What's the reason for the curiously long hold-up on SHA-3?

Why should we trust NIST encryption?

[Slayer]

NIST recklessly broke our trust in them by allowing known to be broken encryption into their standard. Their new document may come with all the best intentions, but it will take years to rebuild that trust. Let's wait for what the crypto community has to say about these documents, before we blindly follow their latest standards.

Re:Why should we trust NIST encryption?

[TechyImmigrant]

NIST recklessly broke our trust in them by allowing known to be broken encryption into their standard. Their new document may come with all the best intentions, but it will take years to rebuild that trust. Let's wait for what the crypto community has to say about these documents, before we blindly follow their latest standards.

Well you could go with the ANSI or ISO RNG specs.

Oh wait, they're written by the same people.

Re:Why should we trust NIST encryption?

[sinij]

All you say is true, but you only need to look at what NSA uses to protect their own stuff to know what is secure. Sure, given a chance they will backdoor your stuff, but they will never do this to their own security, since they know even their own backdoor could be used against them.

Thanks for the link

[xarragon]

Thank you a thousand times to the link to the handbook! Now I can ditch the boring William Stallings crypto book which I never finished AND I don't need a physical copy!

So the work begins again

[bytesex]

To find out where the NSA put the twist.

Re:So the work begins again

[TechyImmigrant]

To find out where the NSA put the twist.

Well P-224 isn't twist secure, if that's what you're hinting at.

In reality the backdoor isn't in SP800-90A, B or C. It's in FIPS 140-2 section 4.9.2. In a FIPS certified module, that procedure applies to all RNG outputs 16 bits and above. A test that changes the data to create a stream of known algebraic inequalities. Genius.

Re:So the work begins again

[Anonymous Coward]

No tinhat, they're just doing their jobs. They were also just doing their jobs saying "just trust us" on parts of DES back in 1974 - came out they were already aware of an attack method discovered by others in the mid 1990s... etc, etc
Yes, they've overstepped reasonableness the past decade or more, but we never hear of the otyher side -- Russia, China, Ira[nq], etc -- who are up to absolutely no good but zero scrutiny. At least the US still has some shattered remains of a system of scrutiny.

Re:So the work begins again

[Anonymous Coward]

Bollocks!

If anything, recent events have demonstrated a LACK of scrutiny. Information has only been revealed due to leaks.

All these replies and no XKCD?

[dwillmore]

https://xkcd.com/221/

Re:All these replies and no XKCD?

[Anonymous Coward]

Oh well, it was good while it lasted...

Re:All these replies and no XKCD?

[Anonymous Coward]

See also Dilbert's Tour of Accounting.

Fuck NIST

[Anonymous Coward]

Traitors. You should be hanging from lamp posts in the streets of your neighborhoods.

Nice try NSA...

[Anonymous Coward]

'nuff said

Yarrow isn't a thing?

[kriston]

The Yarrow algorithm, or its progeny Fortuna, are not yet a thing?
Shame.

https://en.wikipedia.org/wiki/...