random(4) driver questions

random(4) driver questions

[Sandy Harris]

There was a paper some time back by a group of Israeli researchers
and looking at the Linux /dev/random driver, and claiming to find
it wanting in several ways. www.pinkas.net/PAPERS/gpr06.pdf

To what extent have their objections been dealt with. If some
were considered bogus, is there documentation somewhere
explaining why?

One problem they pointed out is that there may be little
entropy available on a Linux-based router; no keyboard or
mouse, solid state storage so no disk entropy, and an
enemy might observe network activity, so network
interrupts give little or no useful entropy.

The only in-kernel solution I can think of would be
to add something in the system call interface to
make very system call throw timing information
into the pool. I very much doubt, though, that that
is a good idea. What do others think, and does
anyone have a better idea?

What happens to /dev/random when it runs on
a virtual machine and all the things it relies on
for entropy get virtualised away?

The server that the VM is hosted on will usually
have plenty of entropy, often a hardware RNG.
Is there an interface that makes that visible
from the VM? Perhaps a virtual "hardware"
RNG driven by /dev/urandom on the host?

Re: random(4) driver questions

[Alexander Clouter]

Sandy Harris <sandyinchina@gmail.com> wrote:
> 
> One problem they pointed out is that there may be little entropy 
> available on a Linux-based router; no keyboard or mouse, solid state 
> storage so no disk entropy, and an enemy might observe network 
> activity, so network interrupts give little or no useful entropy.
> 
I vaguely recall network interrupts (anything that can be externally 
influenced) can be snooped upon so their use is discouraged.  Turns out 
IRQF_SAMPLE_RANDOM is scheduled for destruction, 
Documentation/feature-removal-schedule.txt.

> The only in-kernel solution I can think of would be to add something 
> in the system call interface to make very system call throw timing 
> information into the pool. I very much doubt, though, that that is a 
> good idea. What do others think, and does anyone have a better idea?
> 
An option I used, no idea if it safe though, for my headless colo box 
that seemed to always be running out of entropy was use a sleep() timing 
daemon:

http://www.vanheusden.com/te/

There was no chance of me using the ALSA/video4linux approach also on 
that site as I had a SPARC server so it was my only real choice.  Seems 
to work well, but had to apply a patch to stop it insanely spinning the 
CPU un-necessarily (the author unfortunately never responded):

http://stuff.digriz.org.uk/timer-select.diff

Another tool I found in my travels was HAVEGE:

http://www.irisa.fr/caps/projects/hipsor/index.php

Again, no idea if this is a good idea.

Of course in the VM world, the timer approach probably would work.

Cheers

-- 
Alexander Clouter
.sigmonster says: Some people only open up to tell you that they're closed.

Re: random(4) driver questions

[Ted Ts'o]

On Sat, Jun 25, 2011 at 01:51:07PM +0800, Sandy Harris wrote:
> There was a paper some time back by a group of Israeli researchers
> and looking at the Linux /dev/random driver, and claiming to find
> it wanting in several ways. www.pinkas.net/PAPERS/gpr06.pdf
> 
> To what extent have their objections been dealt with. If some
> were considered bogus, is there documentation somewhere
> explaining why?

Suffice it to say the random generator has changed significantly since
2006.  There is now a secondary pool, which uses catastrophic
reseeding, etc.

> One problem they pointed out is that there may be little
> entropy available on a Linux-based router; no keyboard or
> mouse, solid state storage so no disk entropy, and an
> enemy might observe network activity, so network
> interrupts give little or no useful entropy.

Sure, but a Linux-based router shouldn't be doing crypto work.  If it
*is* and it is important crypto work, then it needs a hardware random
number generator.  There's no magic here.

If you don't want to pay the cost of a random number generator, you
can do things such as at installation time, bootstrapping the random
number generator with some cryptographically secure randomness
available by the installation system.

> The only in-kernel solution I can think of would be
> to add something in the system call interface to
> make very system call throw timing information
> into the pool. I very much doubt, though, that that
> is a good idea. What do others think, and does
> anyone have a better idea?

It won't hurt (aside from wasting CPU time, assuming you don't add any
entropy credits), but won't necessarily help, either.

> What happens to /dev/random when it runs on
> a virtual machine and all the things it relies on
> for entropy get virtualised away?
> 
> The server that the VM is hosted on will usually
> have plenty of entropy, often a hardware RNG.
> Is there an interface that makes that visible
> from the VM? Perhaps a virtual "hardware"
> RNG driven by /dev/urandom on the host?

Yes, paravirtualizing the random number generator would be a big help.
Probably what I would do is to periodically add entropy from the host
OS to the guest OS, via some paravirt channel.  This would add a new
"catastrophic reseeding", and if the virtual guest can mix in some
other unknown material, again that can only help.

						- Ted

Re: random(4) driver questions

[Sasha Levin]

On Mon, 2011-06-27 at 10:54 -0400, Ted Ts'o wrote:
> > What happens to /dev/random when it runs on
> > a virtual machine and all the things it relies on
> > for entropy get virtualised away?
> > 
> > The server that the VM is hosted on will usually
> > have plenty of entropy, often a hardware RNG.
> > Is there an interface that makes that visible
> > from the VM? Perhaps a virtual "hardware"
> > RNG driven by /dev/urandom on the host?
> 
> Yes, paravirtualizing the random number generator would be a big help.
> Probably what I would do is to periodically add entropy from the host
> OS to the guest OS, via some paravirt channel.  This would add a new
> "catastrophic reseeding", and if the virtual guest can mix in some
> other unknown material, again that can only help.

virtio has a 'virtio-rng' device which does just that.

-- 

Sasha.

Re: random(4) driver questions

[Johann Meier]

On 06/27/11 16:54, Ted Ts'o wrote:
> On Sat, Jun 25, 2011 at 01:51:07PM +0800, Sandy Harris wrote:
>> There was a paper some time back by a group of Israeli researchers
>> and looking at the Linux /dev/random driver, and claiming to find
>> it wanting in several ways. www.pinkas.net/PAPERS/gpr06.pdf
>>
>> To what extent have their objections been dealt with. If some
>> were considered bogus, is there documentation somewhere
>> explaining why?
> 
> Suffice it to say the random generator has changed significantly since
> 2006.  There is now a secondary pool, which uses catastrophic
> reseeding, etc.
> 
>> One problem they pointed out is that there may be little
>> entropy available on a Linux-based router; no keyboard or
>> mouse, solid state storage so no disk entropy, and an
>> enemy might observe network activity, so network
>> interrupts give little or no useful entropy.
> 
> Sure, but a Linux-based router shouldn't be doing crypto work.  If it
> *is* and it is important crypto work, then it needs a hardware random
> number generator.  There's no magic here.
> 
> If you don't want to pay the cost of a random number generator, you
> can do things such as at installation time, bootstrapping the random
> number generator with some cryptographically secure randomness
> available by the installation system.
> 
>> The only in-kernel solution I can think of would be
>> to add something in the system call interface to
>> make very system call throw timing information
>> into the pool. I very much doubt, though, that that
>> is a good idea. What do others think, and does
>> anyone have a better idea?
> 
> It won't hurt (aside from wasting CPU time, assuming you don't add any
> entropy credits), but won't necessarily help, either.
> 
>> What happens to /dev/random when it runs on
>> a virtual machine and all the things it relies on
>> for entropy get virtualised away?
>>
>> The server that the VM is hosted on will usually
>> have plenty of entropy, often a hardware RNG.
>> Is there an interface that makes that visible
>> from the VM? Perhaps a virtual "hardware"
>> RNG driven by /dev/urandom on the host?
> 
> Yes, paravirtualizing the random number generator would be a big help.
> Probably what I would do is to periodically add entropy from the host
> OS to the guest OS, via some paravirt channel.  This would add a new
> "catastrophic reseeding", and if the virtual guest can mix in some
> other unknown material, again that can only help.
> 
> 						- Ted
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

If you don't have a hardware rnd, you can use an entropy daemon like
haveged (http://www.issihosts.com/haveged/)

Re: random(4) driver questions

[Sandy Harris]

Johann Meier <recv@containermaster-cmp.de> wrote:

> If you don't have a hardware rnd, you can use an entropy daemon like
> haveged (http://www.issihosts.com/haveged/)

Yes, and there are several other alternatives. Someone suggested a
timer-based daemon earlier in this thread. It looks reasonable at
first glance, but in security matters, I'm reluctant to trust version
0.1 of anything.

Peter Gutmann's cryptlib includes a well-analyzed daemon:
http://www.cs.auckland.ac.nz/~pgut001/cryptlib/

John Denker's turbid, using a sound card without microphone,
looks very good:
http://www.av8n.com/turbid/paper/turbid.htm

Re: random(4) driver questions

[Henrique de Moraes Holschuh]

On Tue, 28 Jun 2011, Sandy Harris wrote:
> Johann Meier <recv@containermaster-cmp.de> wrote:
> > If you don't have a hardware rnd, you can use an entropy daemon like
> > haveged (http://www.issihosts.com/haveged/)
> 
> Yes, and there are several other alternatives. Someone suggested a

The best of which is probably to _get_ a TRNG device.

I can recommend this excellent and inexpensive (< £40) one:
http://www.entropykey.co.uk/

It will do ~32kbit/s (well, at least that's what mine is doing right now).
It is designed for Linux and also for safe use and safe distribution of
entropy.  It is a small USB device, and uses the USB cdc_acm driver to talk
to a FLOSS userspace application (MIT license).

As any USB device, it is _not_ going to be capable of providing entropy to
the kernel boot process or to very early userspace.

PS: I am in no way affiliated with Simtec electronics, I am just one of
their happy customers.

-- 
  "One disk to rule them all, One disk to find them. One disk to bring
  them all and in the darkness grind them. In the Land of Redmond
  where the shadows lie." -- The Silicon Valley Tarot
  Henrique Holschuh

Re: random(4) driver questions

[Sandy Harris]

On Mon, Jun 27, 2011 at 10:54 PM, Ted Ts'o <tytso@mit.edu> wrote:

> Suffice it to say the random generator has changed significantly since
> 2006.  There is now a secondary pool, which uses catastrophic
> reseeding, etc.

Why does the secondary pool use another hash, rather than a
block cipher? I can see using a hash for the primary pool; at
the original design time, export laws were a concern, and in
any case a hash is the obvious mixing primitive there.

However, for the secondary pools, a block cipher seems to
me to be the obvious thing to use because there is plenty
of analysis, in the Yarrow paper and follow-ups, of that
technique. Also, I think it might be faster.

An AES-128 context, 11 128-bit round keys, is roughly the
same size as one of the current secondary pools, 32 32-bit
chunks. What would maintainers think of a patch along
those lines?

Another question is whether and when we might replace
SHA-1 with a more modern hash. Jeff Garzik has a patch
to add Skein to the crypto API. That would be faster
than SHA-1 and perhaps more easily analyzed since
the compression function is a block cipher. Of course
the SHA-3 Advanced Hash Standard process is not
scheduled to finish for another year and there's a
good argument that we should wait for that.

Also, though there are some attacks on SHA-1, none
of them appear to matter for this application, so
perhaps :If it ain't broke, don't fix it".

Re: random(4) driver questions

[Ted Ts'o]

On Tue, Jun 28, 2011 at 02:02:58PM +0800, Sandy Harris wrote:
> However, for the secondary pools, a block cipher seems to
> me to be the obvious thing to use because there is plenty
> of analysis, in the Yarrow paper and follow-ups, of that
> technique. Also, I think it might be faster.

Well, there hasn't actually been any analysis of the use of a block
cipher.  The Yarrow paper and all follow-ons that I'm aware simply
assume that the block cipher is secure.  Most of the Yarrow analysis
has been on what I consider to be largely pointless, academic
considerations about "what if you're able to get the internal state".
(Whereas I'm of the opinion, if you can get access to the internal
state of the kernel, you probably can do a lot of other things that
are much bigger deal --- such as, dropping in a root exploit and then
start tapping your keyboard, network, etc.)

> An AES-128 context, 11 128-bit round keys, is roughly the
> same size as one of the current secondary pools, 32 32-bit
> chunks. What would maintainers think of a patch along
> those lines?

But if you're ditching the AES key scheduling step, it's no longer
AES, which means all of the analysis for AES not necessarily
applicable....  So if you're going for a cryptographic conservative
design, it's not at all clear to me that a bastardized AES is an
improvement.

Also, note that faster is *not* a feature for a random number
generator...

> Another question is whether and when we might replace
> SHA-1 with a more modern hash. Jeff Garzik has a patch
> to add Skein to the crypto API. That would be faster
> than SHA-1 and perhaps more easily analyzed since
> the compression function is a block cipher. Of course
> the SHA-3 Advanced Hash Standard process is not
> scheduled to finish for another year and there's a
> good argument that we should wait for that.

Waiting for SHA-3 (and then giving a bit more time for the
cryptographers to spend more time trying to attack it) seems like a
better approach to me....

						- Ted