LWN: Comments on "The search for truly random numbers in the kernel"

Fortuna

joern — 2013-09-24T21:29:09+00:00

While in principle I like the fortuna design, I am wondering what problem you are trying to solve. Both fortuna and the current linux design are prng, both use (or can use) real entropy to seed their pools and to stir them up once in a while. Both should give random numbers that are impossible to predict, assuming the attacker can do almost anything except dump the entropy pool itself or control every bit of input to the pool.

One of the two might have a more pleasing design. But as long as both get the job done equally well, why would you want to do a replacement? You can easily introduce subtle bugs and, without a strong upside, I would like to avoid that possibility.

The search for truly random numbers in the kernel

broonie — 2013-09-21T13:19:00+00:00

Yes, just using it as an ADC.

The search for truly random numbers in the kernel

giraffedata — 2013-09-20T20:33:45+00:00

I thought broonie's point was that you can use a sound processor to sample eru's transistor's output.

The search for truly random numbers in the kernel

gmaxwell — 2013-09-20T20:00:40+00:00

SSH does, at least on some systems. If this is advisable or not is another question.

When long-term secrets are used for signing with DSA then whatever argument for /dev/random there was in the first place also really applies to the nonce generation— since weak nonces will leak the private key.

To some extent there is pressure on developers to use the "more secure" thing so long as it exists. No one wants to be wearing the dunce cap for some massive security compromise.

But it would be nice if there were enough space in the pool that it wasn't quite so much of a trap.

The search for truly random numbers in the kernel

ikm — 2013-09-20T19:32:31+00:00

Oh, I see what you meant now. But do SSH/SSL sessions really use /dev/random and not /dev/urandom? Sounds like an overkill to me. Once /dev/urandom is properly seeded, I would expect the numbers it provided to be sufficiently random for session keys.

The search for truly random numbers in the kernel

gmaxwell — 2013-09-20T19:10:47+00:00

::facepalm::

The entropy estimator is a counter. It is incremented by a scarce few entropy sources in the kernel. Decremented on read from /dev/random. When it reaches zero /dev/random blocks. I am talking about the housekeeping, not quality of the CSPRNG.

On a busy system (e.g. one with a lot of SSL activity) it is very easy to get mysteriously poor performance— things like SSH taking a long time to connect, as various random tasks block trying to read a few bytes from /dev/random.

Here is a monitoring on a system which has this problem (but normally has a daemon running that keeps the pool full, you can see what happens when the daemon is down): http://mf4.xiph.org/munin/xiph.org/mf4.xiph.org/entropy-y... (the graph claims 'bytes' but its really bits, and when its at zero, ssh connections and such start becoming visibly slow)

The search for truly random numbers in the kernel

ikm — 2013-09-20T19:01:01+00:00

> It's very easy to drain the cruddy 4kbit pool dry.

Do you have a proof of that? Even simply XORing new entropy into the current seed would never make the seed less random, given that the sources of entropy don't have access to its current value. I actually doubt that it is possible to decrease entropy at all, even if it is certainly possible to not increase it (in the case where you mixing in zeroes, for example).

The search for truly random numbers in the kernel

ikm — 2013-09-20T18:22:06+00:00

> on a number of architectures, the TSC does not exist and get_cycles() returns zero

In this case, one small source of entropy which could be used is the caller's instruction pointer (i.e. the address where get_cycles() should return to). Since the order in which get_cycles() is called due to hardware interrupts is unpredictable in most cases, this would certainly be better than always feeding zeroes.

Another option is mixing in the current top of stack pointer (be it the kernel or the userspace one), depending on the architecture implementation.

While giving this any entropy credit would be wrong, the randomness it provides can be useful.

The search for truly random numbers in the kernel

pizza — 2013-09-20T17:37:06+00:00

There's not enough entropy (ie noise) in my server environment for audio-based entropy sources to work. I found that surprising, but that's what audio-entropyd determined.

I simply don't have any meaningful source of entropy available, which is why I'm resorting to hacking together some sort of USB-based RNG.

The search for truly random numbers in the kernel

broonie — 2013-09-20T17:13:16+00:00

A sound card is usually pretty straightforward to get - a USB one can be added if required.

The search for truly random numbers in the kernel

gmaxwell — 2013-09-20T01:28:45+00:00

Oh geesh, please don't reduce the estimates without increasing the size of the pool.

On many systems the only thing that adds to the pool estimate anymore is the TSC ... at about 50 bits per second. It's very easy to drain the cruddy 4kbit pool dry. There is no good way to increase the size of the pool— you have to modify the kernel and that means moving off a distribution kernel image to something you have to maintain for yourself.

Fortuna

cesarb — 2013-09-19T20:56:49+00:00

> Well, Fortuna is designed to be a secure pseudo-random number generator. If that's what you want then /dev/urandom is fine. What we are talking is true random output, which you can't simply generate large amounts of without external input.

Both /dev/random and /dev/urandom are secure pseudo-random number generators, and both are seeded with external entropy in the same way. The only difference between both is that /dev/random blocks if the entropy estimate is too low, while /dev/urandom does not.

You could use Fortuna for /dev/random too, you would just need to add some sort of entropy estimator, to keep compatibility with userspace which expects it to block arbitrarily. Since most users (even cryptographic libraries) seem to use /dev/urandom, any problems with this entropy estimator would not affect them.

And for users of /dev/random, you would gain the advantage that the quality of the random numbers would not be affected by bugs on the entropy estimator.

Yes, an overestimation would that mean more numbers would be generated from the same amount of entropy. But Fortuna (and Yarrow) is designed so that, as long as the generator has more than a minimum amount of good quality entropy to start with (256 bits IIRC), and the state is not compromised, the output is secure even without reseeding (if the state can be compromised from the output, AES is broken and you have bigger problems). After the initial seeding, the reseeding is there only to recover if the generator state is compromised; see the presentation for more details.

The SOURCE for truly random numbers in the kernel is external hardware

pizza — 2013-09-19T18:06:49+00:00

My servers are perpetually entropy-starved simply by random web crawlers hitting its TLS-exposed services. A full entropy pool is typically depleted within a few seconds, even under low-load situations.

Meanwhile, I won't be using the RNG output of the STM32 directly; it will be mixed and mangled before being passed to the host -- and since Linux will mix it with its other entropy sources, it's considerably less likely to be a problem.

Besides, let's be honest here, if you distrust commercial RNGs, wouldn't any random pre-packaged RNG design be equally suspect? Just because the design/code is open source doesn't mean there's not a weakness in it that only the NSAs in the world are capable of recognizing. And besides, even assuming noble intentions, designing a good RNG is *hard*; I'm actually more likely to introduce weaknesses (as opposed to improvements) with my meddling.

The SOURCE for truly random numbers in the kernel is external hardware

daney — 2013-09-19T17:52:16+00:00

You may not trust a commercial RNG, but if the USB interface to said class of devices were standardized, you might have the option of easily switching RNG vendor.

Fortuna

kleptog — 2013-09-19T17:26:05+00:00

Well, Fortuna is designed to be a secure pseudo-random number generator. If that's what you want then /dev/urandom is fine. What we are talking is true random output, which you can't simply generate large amounts of without external input.

We could just drop /dev/random altogether and symlink it to /dev/urandom. Which is what using Fortuna would amount to.

The SOURCE for truly random numbers in the kernel is external hardware

nix — 2013-09-19T16:36:22+00:00

I note that the entropy key's network entropy daemon actually relies on the kernel's entropy estimation: in particular, it relies on it so that it knows when not to bother sending in more entropy. This matters because extracting the entropy over USB is relatively CPU-expensive (it can eat a few percent of CPU time on slow machines), so it is best not to throw too much entropy into the pool unless people are using what you throw in. The key generates enough entropy to fill the pool in a couple of seconds, after all... and by the standards of modern entropy sources that is *slow*.

The SOURCE for truly random numbers in the kernel is external hardware

felixfix — 2013-09-19T15:46:41+00:00

But if commercial RNGs are not to be trusted, packaging it into a USB stick doesn't magically remove the stigma.

The SOURCE for truly random numbers in the kernel is external hardware

pizza — 2013-09-19T15:21:44+00:00

>it should be possible to build a USB attachable source of truly random numbers for a reasonable amount of money.

There's an outfit out of the UK (www.entropykey.co.uk) that was selling such a widget for about $60, but they've hit some sort of unrelated financial problems and haven't been able to make/ship any for some time now.

In the mean time, I'm actually working on a USB-attached RNG now, utilizing an STM32F4 MCU, which has a high-quality hardware RNG onboard. You can buy the eval boards for $15 in single-unit quantity (STM32F4DISCOVERY), so I don't think there's much of a point in trying to design a custom board since we won't be able to meet that price target without a large enough initial order.

When I get it working (The USB stack is a bit of a PITA), I'll be releasing the firmware (and appropriate Linux code) under the GPL. If there's enough interest in dedicated hardware, perhaps Kickstarter may be an option, hmm.

The SOURCE for truly random numbers in the kernel is external hardware

mpr22 — 2013-09-19T15:11:45+00:00

It has already been done, and indeed has been mentioned in LWN comments in the past.

The SOURCE for truly random numbers in the kernel is external hardware

faramir — 2013-09-19T15:04:48+00:00

If I can buy a 4Gbyte USB flash drive for < $5, it should be possible to build a USB attachable source of truly random numbers for a reasonable amount of money. All that needs to happen in the kernel is to define exactly how such a device talks to the kernel and a way for a system administrator to enable use of a specific device. Then let the hardware guys do as many different implementations as the market will bear.

Personally, I would be happy to contribute $20 to a kickstarter project that wrote the appropriate software for Linux; designed and built the hardware; and made both the software and hardware "open source". For the paranoid, make it an option to just get an unpopulated circuit board so the recipient could source the rest of the off the shelf components from wherever they like. Many people may not be able to design the requisite hardware, but almost anyone who cares could learn to solder well enough to put such a device together.

Finally, given the existence of USB flash drives which

1. Pretend to have a higher capacity then they actually do (in order to commit fraud on the purchaser)

2. Pretend to be a USB keyboard/mouse for various nefarious purposes

this would seem to be a simple project for someone with hardware design skills. (Which is unfortunately not me.)

Fortuna

cesarb — 2013-09-19T14:04:00+00:00

Seconded. One interesting feature of Fortuna is that it does not need any entropy estimation.

Fortuna has two parts. The generator is simply AES (or another good block cipher) in counter mode, with the key being the state. When you request random bytes, it generates the requested bytes plus a new key (rotating the state).

The accumulator has 32 pools. Incoming entropy is uniformly distributed between the pools. Each pool is used for seeding half as often as the previous pool, so the first pool is used every reseed, the second pool is used every other reseed, the third pool is used every four reseeds, and so on. A reseed is done every time the generator is called (before calling the generator), if the first pool has received more than a fixed number of bytes, and at most once every 0.1 second.

With this design, at least one of the pools will have received enough entropy when it comes its turn to be used to reseed the generator. You do not have to know which one, so there is no need to estimate entropy. The state for the generator is the counter and the key, and the state for the accumulator is a rolling hash for each pool (which summarizes its contents) plus the size of the first pool and the last reseed time.

For more information, see http://th.informatik.uni-mannheim.de/people/lucks/papers/... and https://en.wikipedia.org/wiki/Fortuna_%28PRNG%29.

I believe the current Linux PRNG was originally derived from the one used by PGP, with modifications accumulating over time. Fortuna (and its predecessor Yarrow) is a more modern design.

The search for truly random numbers in the kernel

alankila — 2013-09-19T11:54:30+00:00

Linux's random source pool is IMHO distinguished by being miserably slow at accumulating random bits and ridiculously complex for what it does with difficult problems like entropy estimation. Why don't we just use some design such as Fortuna?

The search for truly random numbers in the kernel

eru — 2013-09-19T06:25:01+00:00

It seems the truly paranoid should solder their own hardware RNG. If I remember correctly, a basic RNG is not hard: wire a cheap transistor suitably and sample the resulting noisy signal. The last part is harder today. In the past, one could repurpose the printer port or an analogue joystick port for simple digitizing, but they have disappeared from current computers

The search for truly random numbers in the kernel

lsl — 2013-09-19T03:55:45+00:00

> There are probably home routers still stuck on 2.6

2.6? Optimistic. There are consumer routers sold today that ship with a 2.4 kernel.