On improving entropy collection for VMs

[Joanna Rutkowska]

Hi List,

People with some background in cryptography are encouraged to read the
discussion under this ticket:

http://wiki.qubes-os.org/trac/ticket/673

... and to provide comments.

Thanks,
joanna.

[Abel Luck]

Joanna Rutkowska:

Ah good.

I've been worried about entropy in VMs recently as well, though I've
been using my EntropyKey where good entropy was crucial.


Going to read the ticket tomorrow (just shut down web browser VMs for
sleep).

[Joanna Rutkowska]

On 11/16/12 00:45, Abel Luck wrote:
> Joanna Rutkowska:
>> > Hi List,
>> >
>> > People with some background in cryptography are encouraged to read the
>> > discussion under this ticket:
>> >
>> > http://wiki.qubes-os.org/trac/ticket/673
>> >
>> > ... and to provide comments.
>> >
> Ah good.
>
> I've been worried about entropy in VMs recently as well, though I've
> been using my EntropyKey where good entropy was crucial.
>
>

And how do you use it in VMs? I suppose this hardware key is a USB
device, is it not? Do you use the new Alex's code for PVUSB? Or do you
assign the whole USB controller to the VM where you generate the key
(which, I think, would have quite the opposite effect in terms of
improving the security of the key generation process -- in fact I think
it would decrease it).

> Going to read the ticket tomorrow (just shut down web browser VMs for
> sleep).

Are you saying the S3 sleep/resume breaks if you don't shutdown certain
VMs? Or is it just part of a self-discipline?

joanna.

[abb]

On Friday, November 16, 2012 12:27:46 AM UTC+1, joanna wrote:

Hi List,

People with some background in cryptography are encouraged to read the
discussion under this ticket:

http://wiki.qubes-os.org/trac/ticket/6How come?73

... and to provide comments.

I don't know if it is feasible to spoil haveged, but it feeds on data which can be "modulated" by an attacker, so I suppose there is a small risk.

If there is a random byte stream available in dom0, the act of adding entropy into domU kernel can be done with rngd, something like 'qvm-run -p DOMU "rngd -f -r /dev/stdin"'.

Another interesting feature of rngd is its TPM support. Some people [1] supposedly seen it producing 6Kbps of random data. [3] says VTPM supports full TPM 1.2 spec. It VTPM gives access to RNG in the hardwared TPM, it would be the cleanest solution I think.

Also people say [2] increasing entropy poolsize helps, might be the most cost-efficient way to mitigate the problem if one occasionally needs a lot of entropy.

[1] http://www.outflux.net/blog/archives/2010/02/08/rng-tools-with-tpm/
[2] http://www.linuxfromscratch.org/hints/downloads/files/entropy.txt
[3] http://cybione.org/~cdidier/blog/200901221025.html
 

Thanks,
joanna.

[Joanna Rutkowska]

On 11/17/12 05:08, abb wrote:
> On Friday, November 16, 2012 12:27:46 AM UTC+1, joanna wrote:
>> >
>> > Hi List,
>> >
>> > People with some background in cryptography are encouraged to read the
>> > discussion under this ticket:
>> >

>> > http://wiki.qubes-os.org/trac/ticket/6How come?73<http://wiki.qubes-os.org/trac/ticket/673>

>> >
>> > ... and to provide comments.
>> >
> I don't know if it is feasible to spoil haveged, but it feeds on data which
> can be "modulated" by an attacker, so I suppose there is a small risk.

Can you elaborate?

joanna.

[Alexandre Bezroutchko]

A compromised domain running on the same host can affect measurements taken by haveged running in the secure domain, and take the same measurements by itself. Consider an extreme case when 39 out of 40 domUs are compromised. I wonder whether those 39 cooperating domains could cooperate to gather enough timing to make some guesses what measurements the secure domain takes. Wiki on /dev/random says "whilst entropy pool based methods are completely secure if implemented correctly, if they overestimate their entropy they may become less secure than well-seeded PRNGs." Can 39 cooperating domains trick the secure domain into believing it gets more entropy then it really does?

Another source of entropy they use -- timing of heavily branching computations -- I guess it also cannot be possibly really proven as reliable because it in fact depends on myriads of factors some of which can change without notice. My gut feeling tells me there can be no guarantee that that "heavily branching code" complied by a future version of gcc running on CPU with future version of microcode will still produce good random numbers and not falli into a loop or exhibit some other kind of behavior which will make it unsuitable as a source of random data. I believe Schneier in Applied Cryptography express strong opinion about home-made RNGs built by mindlessly throwing kinda-random pieces together -- that the result is typically of poor quality.

As a side note, I wonder how the rise of SSD impacts amount of entropy available from disk-related interrupts. Behavior of SSD (+noop disk scheduler they recommend using) is probably much more predictable than legacy mechanic drives.

Regards,
Alex

joanna.

[Juergen Schinker]

True i also use it for Tor

---

if you have Ivybridge (or later) and you trust your VMM, you have RDRAND.

--
 
 

[Joanna Rutkowska]

On 12/25/12 12:01, Juergen Schinker wrote:
> True i also use it for Tor
>

> ----- Original Message -----
>
>>> if you have Ivybridge (or later) and you trust your VMM, you have
>>> RDRAND.
>>
>
>> --
>

And how does one use RDRAND instruction for seeding the /dev/random?
(which is used by programs such as gpg, etc)?

joanna.

[Abel Luck]

Joanna Rutkowska:

I've had this exact question for awhile now, and I'm fairly certain it
is used by /dev/random in recent versions of Linux. Which versions, I'm
not 100% sure.

info: RDRAND is a high bandwidth and low latency instruction that
produces high-quality random numbers.

__Linux Status__

Here's all the evidence I have regarding the current status of RDRAND's
use in /dev/random

* 07-2011 - Patch contributed it to Linux kernel, and resulting
discussion (Linus involved):
http://thread.gmane.org/gmane.linux.kernel/1173350

* 12-2011 - 2.6.32 Changelog mentions commit
dd102079e9ad33c7f5377a22f6e381e36d566c61 from Linus that makes
/dev/random use RDRAND

https://www.kernel.org/pub/linux/kernel/v2.6/longterm/v2.6.32/ChangeLog-2.6.32.60

* 12-2011 - diff of aforementioned commit

https://git.kernel.org/?p=linux/kernel/git/stable/linux-stable.git;a=blobdiff;f=drivers/char/random.c;h=85da8740586b3dbe381373d6f7e52d6b348329ac;hp=6035ab8d5ef7e25e6eae89fbfdc53476f248de8b;hb=cf833d0b9937874b50ef2867c4e8badfd64948ce;hpb=5f0a6e2d503896062f641639dacfe5055c2f593b


* RDRAND will not be used as a primary source for /dev/random because

"This is
because RDRAND, although reseeded way more frequently than what is
practical to do in software, is technically a nonblocking source
that can behave as a PRNG." - H. Peter Anvin (first link), 07-2011

(Peter is an Intel kernel hacker)

"Another important Peter quote:

This basically means it is similar in behavior to our /dev/urandom in
that it may gracefully degrade to a PRNG for short stretches of time,
but will not degrade to a PRNG for an extended time, nor will it produce
guessable data, ever; instead it will "fail shut."

The one use case that it is cryptographically insufficient for is to
seed a new PRNG, which probably means it is unsuitable for being fed
as-is into /dev/random." - H. Peter Anvin
(http://www.spinics.net/lists/linux-crypto/msg05883.html), 06-2011

Based on the above links I'm fairly certain Linux >= 2.6.32 uses RDRAND
*partially* in /dev/random.


Other:

* LWN Article on RNG system changes to linux 3.6 (this is bad ass, a
must read for anyone interested in linux entropy). Includes discussion
of HAVEGD too.

https://lwn.net/Articles/525459/

> joanna.
>

[Abel Luck]

Joanna Rutkowska:

> On 11/16/12 00:45, Abel Luck wrote:
>> Joanna Rutkowska:
>>>> Hi List,
>>>>
>>>> People with some background in cryptography are encouraged to read the
>>>> discussion under this ticket:
>>>>
>>>> http://wiki.qubes-os.org/trac/ticket/673
>>>>
>>>> ... and to provide comments.
>>>>
>> Ah good.
>>
>> I've been worried about entropy in VMs recently as well, though I've
>> been using my EntropyKey where good entropy was crucial.
>>
>>
> And how do you use it in VMs? I suppose this hardware key is a USB
> device, is it not? Do you use the new Alex's code for PVUSB? Or do you
> assign the whole USB controller to the VM where you generate the key
> (which, I think, would have quite the opposite effect in terms of
> improving the security of the key generation process -- in fact I think
> it would decrease it).
>

You're correct it is a USB device. I've only been using it in dom0 with
gpg --genkey, no VMs involved. Of course this required installing the
ekey daemon in dom0 :|

Not ideal of course.

>> Going to read the ticket tomorrow (just shut down web browser VMs for
>> sleep).
>
> Are you saying the S3 sleep/resume breaks if you don't shutdown certain
> VMs? Or is it just part of a self-discipline?

Haha, I meant *I* was going to sleep and was writing that email after
shutting down my VMs as part of the process of turning my computer off
for the night.

Sleep+resume (on Qubes) works quite well actually.

[Abel Luck]

Joanna Rutkowska:

Woo! With the update of dom0 to kernel 3.7.x I now have loads of
entropy! I imagine this is due to the new support of the RDRAND instruction.

Also, by installing the rngd (package: rng-tools) I am also feeding
entropy to the kernel's from my TPM. My entropy buffer is constantly
hovering near 4000 bytes.

Now, we just need the service to distribute it to the VMs.

Joanna, Marek: Do you think a simple round robin approach would be
sufficient? That is a daemon that sends chunks of random bytes to each
VM in turn?

That seems somewhat wasteful and naive.

What if the VMs were able to request entropy from dom0 when they were
low? That would work nicer to satisfy those few VMs with a high entropy
demand, but opens us to a malicious program in one VM starving all the
other VMs of entropy by DoSing the service. We could rate limit it I
suppose?

What do you think?

~abel

[Joanna Rutkowska]

I think the simple round robin would be just good enough. The concept of
"wasting of randomness" doesn't really scare me that much. In addition
this has an advantage that Dom0 doesn't need to process any requests
from VMs.

So, this could be implemented as a trivial Qubes RPM service, say,
qubes.EntropyFeed. Abel, if you're planning to implement such service,
please do let us know.

joanna.

[Abel Luck]

Joanna Rutkowska:

So, we have a new development: I have a steady stream of entropy in all
of my VMs using the Fedora 18 template:

[user@appvm ~]$ cat /proc/sys/kernel/random/entropy_avail
3968
[user@appvm ~]$ cat /proc/sys/kernel/random/entropy_avail
3843

Quite startling to say the least. This is in every VM based on Fedora
18, the Fedora 17 vms do not exhibit this behavior.

After investigation I'm confident this is entropy generated using
Intel's new RDRAND instruction.

Justification:

Fedora 18 introduced 'rngd' a new system daemon that is turned on by
default [1]

[user@appvm ~]$ rngd --help
Usage: rngd [OPTION...]
Check and feed random data from hardware device to kernel
entropy pool.
....

[user@appvm ~]$ sudo rngd -v
Unable to open file: /dev/tpm0
Available entropy sources:
DRNG

This being a VM, there is no TPM. But what is this DRNG?

Digging into the sourcecode of rngd [2] we find:

/*
* Confirm RDRAND capabilities for drng entropy source
*/
int init_drng_entropy_source(struct rng *ent_src)
....

This function checks for the RDRAND instruction.

Apparently xen is passing through the RDRAND instruction to the VMs. I
can confirm this with the command:

[user@appvm ~]$ cat /proc/cpuinfo | grep rdrand
flags : fpu de tsc msr pae cx8 sep cmov pat clflush mmx fxsr sse
sse2 ss ht syscall nx lm constant_tsc rep_good nopl pni pclmulqdq ssse3
cx16 pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes f16c
***rdrand*** hypervisor lahf_lm ida arat epb pln pts dtherm fsgsbase erms
---------

To verify, can someone on a non-IvyBridge system check the output of
these commands in an AppVM?

sudo service rngd status
cat /proc/cpuinfo | grep rdrand
cat /proc/sys/kernel/random/entropy_avail

Repeat the last one several times to get an idea of how fast the entropy
pool is being replenished.

~abel

[1]: section 2.4.3
https://docs.fedoraproject.org/en-US/Fedora/18/html/Release_Notes/sect-Release_Notes-Changes_for_Sysadmin.html#idm36884800
[2]:
https://kernel.googlesource.com/pub/scm/utils/kernel/rng-tools/rng-tools/+/v4/rngd_rdrand.c

[coderman]

On Mon, Mar 11, 2013 at 6:02 AM, Abel Luck <ab...@guardianproject.info> wrote:

...

After investigation I'm confident this is entropy generated using
Intel's new RDRAND instruction.

Justification:
Fedora 18 introduced 'rngd' a new system daemon that is turned on by
default [1]

    ...

Apparently xen is passing through the RDRAND instruction to the VMs. I
can confirm this with the command:

RDRAND was explicitly designed to be "safe" to call from host or guest; this is as expected and an rngd in every domain is the proper solution to the entropy question. (as you've demonstrated with full entropy pools in every domain in your FC18 setup)

Note that if you don't have RDRAND you may need to use a real rngd to hw in dom0 and pass through to guests via virtio-rng.

[Joanna Rutkowska]

I have a Sandy Bridge CPU, and it doesn't have rdrand (cpuinfo in both
an AppVM, as well as in Dom0, doesn't report this capability). The
entropy in a VM is *very* slowly collected. In Dom0 I can see I get new
16 bytes of entropy every several seconds, when I do nothing with the
mouse (I just run xxd /dev/random to observe this).

joanna.

[Joanna Rutkowska]

And what is that?

[coderman]

On Mon, Mar 11, 2013 at 4:42 PM, Joanna Rutkowska <joa...@invisiblethingslab.com> wrote:

> Note that if you don't have RDRAND you may need to use a real rngd to hw in
> dom0 and pass through to guests via virtio-rng.
>

And what is that?

virtio-rng in Fedora summarized here:

  https://fedoraproject.org/wiki/Features/Virtio_RNG

it's relatively new, but i've used it with Qemu and Xen with great success.  if you're on FC18 like the thread above, the default enabled rngd will find a hardware random special character device, like you'd have with an actual TRNG/HWRNG, in /dev/. (typically /dev/hwrandom or /dev/hw_random) and feed the guest entropy pool accordingly.

the path of entropy would look like this:

dom0_TRNG (/dev/hwrandom, from XSTORE, RDRAND, scavenger, etc)

 -> dom0 rngd (/dev/hwrandom -> /dev/[u]random)

    -> dom0 virtio-rng device to guest (fed from /dev/random pool)

 === domain boundary ===

domU_virtio-rng device from host (/dev/hwrandom)

 -> domU rngd (/dev/hwrandom -> /dev/[u]random)

i'd love to get patches for Qubes with all of this integrated for the non RDRAND case, using virtio-rng, but have not had time available to do so.

best regards,

[Joanna Rutkowska]

I don't like the idea of using a 3rd party inter-vm protocol, especially
something that is emulated by qemu (qemu is probably the least secure
virtualization thing ever created).

If there is a simple way to feed an entropy from userland, then we can
have a *trivial* Qubes RPM service that would be feeding each VM with
entropy taken from Dom0, as I wrote in a previous message.

joanna.

[coderman]

On Tue, Mar 12, 2013 at 2:56 AM, Joanna Rutkowska
<joa...@invisiblethingslab.com> wrote:
> ...

> I don't like the idea of using a 3rd party inter-vm protocol, especially
> something that is emulated by qemu (qemu is probably the least secure
> virtualization thing ever created).

the virtio-rng device is commonly supported in guests; this makes it
convenient but by no means is it necessary for Qubes.
(i'd argue the kqemu module is the least secure virtualization thing
ever created ;)

> If there is a simple way to feed an entropy from userland, then we can
> have a *trivial* Qubes RPM service that would be feeding each VM with
> entropy taken from Dom0, as I wrote in a previous message.

aside from rolling your own, the only other solution along these lines
i've used is entropy broker:
http://www.vanheusden.com/entropybroker/

RDRAND with the default enabled rngd (FC18) really is the best
solution to this problem.

best regards,

[cprise]

On 3/11/13 9:02 AM, Abel Luck wrote:
> So, we have a new development: I have a steady stream of entropy in
> all of my VMs using the Fedora 18 template:

If I am following this correctly, then people with CPUs supporting
rdrand have relief from the low-entropy VM problem.

However, there is still the question of getting more entropy into VMs on
systems that lack rdrand. They may even have entropy-starved VMs while a
TPM or other hwrng is present.

It would probably be a good idea to pipe entropy from DOM0 to the VMs
regardless of whether rdrand is present. The discussion on the kernel
mailing list shows that the traditional entropy collection is still
considered pretty important, and the best source for that will be DOM0
(they put rdrand output in the same level as /dev/urandom). Without
that, in the VMs we would get mainly output from rdrand (if present)
XORed with the very slow/weak output from the VM-stifled entropy collector.

So the plentiful entropy you're seeing in your VMs Abel is not trusted
quite as much by the kernel developers as the kernel's normal CSPRNG
output. In their view, it is weaker than what is available in DOM0 (even
though both the VMs and DOM0 are getting input from rdrand).

Also, besides the simplicity/security issue that Joanna raises, there is
a question of whether the method of transfer into the VMs will be
efficient. Since a CSPRNG algorithm is operating -- both in DOM0 and in
each VM -- should this process be bypassed in the VMs so that the crypto
isn't unnecessarily run twice on the random stream?

[coderman]

On Tue, Mar 12, 2013 at 3:34 PM, cprise <cpr...@gmail.com> wrote:
> ...

> So the plentiful entropy you're seeing in your VMs Abel is not trusted
> quite as much by the kernel developers as the kernel's normal CSPRNG
> output. In their view, it is weaker than what is available in DOM0 (even
> though both the VMs and DOM0 are getting input from rdrand).

RDRAND is stronger that /dev/urandom, probably, but you can't be sure
given its design. internal state is intentionally obfuscated which
precludes independent validation of entropy density and bias. this is
fine for live use, but a debug / validation mode would be nice.

i would still prefer it over any other collection mechanism except
other HWRNG sources which do provide raw access.

> Also, besides the simplicity/security issue that Joanna raises, there is
> a question of whether the method of transfer into the VMs will be
> efficient. Since a CSPRNG algorithm is operating -- both in DOM0 and in
> each VM -- should this process be bypassed in the VMs so that the crypto
> isn't unnecessarily run twice on the random stream?

you want the kernel mixing behavior to remain in both host and guest
for two reasons:
1) it is good practice to keep the pool well mixed, so that entropy
extracted is robust from the first byte to the last.
2) demand for entropy is easily met even with this overhead in place;
you're not going to exhaust the entropy pool before rngd can fill it
unless you're initializing disks with /dev/random :)

best regards,

[Alex Dubois]

Alex

On 12 Mar 2013, at 22:57, coderman <code...@gmail.com> wrote:

> On Tue, Mar 12, 2013 at 3:34 PM, cprise <cpr...@gmail.com> wrote:
>> ...
>> So the plentiful entropy you're seeing in your VMs Abel is not trusted
>> quite as much by the kernel developers as the kernel's normal CSPRNG
>> output. In their view, it is weaker than what is available in DOM0 (even
>> though both the VMs and DOM0 are getting input from rdrand).
>
> RDRAND is stronger that /dev/urandom, probably, but you can't be sure
> given its design. internal state is intentionally obfuscated which
> precludes independent validation of entropy density and bias. this is
> fine for live use, but a debug / validation mode would be nice.
>
> i would still prefer it over any other collection mechanism except
> other HWRNG sources which do provide raw access.
>
>
>> Also, besides the simplicity/security issue that Joanna raises, there is
>> a question of whether the method of transfer into the VMs will be
>> efficient. Since a CSPRNG algorithm is operating -- both in DOM0 and in
>> each VM -- should this process be bypassed in the VMs so that the crypto
>> isn't unnecessarily run twice on the random stream?
>
> you want the kernel mixing behavior to remain in both host and guest
> for two reasons:
> 1) it is good practice to keep the pool well mixed, so that entropy

As long as an element of entropy from dom0 given to a VM can never be given to another VM, if you trust you source entropy this is sufficient afaik.

> extracted is robust from the first byte to the last.
> 2) demand for entropy is easily met even with this overhead in place;
> you're not going to exhaust the entropy pool before rngd can fill it
> unless you're initializing disks with /dev/random :)
>
> best regards,
>

> --
> You received this message because you are subscribed to the Google Groups "qubes-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to qubes-devel...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Abel Luck]

cprise:

>
>
> On 3/11/13 9:02 AM, Abel Luck wrote:
>> So, we have a new development: I have a steady stream of entropy in
>> all of my VMs using the Fedora 18 template:
>
> If I am following this correctly, then people with CPUs supporting
> rdrand have relief from the low-entropy VM problem.
>
> However, there is still the question of getting more entropy into VMs on
> systems that lack rdrand. They may even have entropy-starved VMs while a
> TPM or other hwrng is present.
>
> It would probably be a good idea to pipe entropy from DOM0 to the VMs
> regardless of whether rdrand is present. The discussion on the kernel
> mailing list shows that the traditional entropy collection is still
> considered pretty important, and the best source for that will be DOM0
> (they put rdrand output in the same level as /dev/urandom). Without
> that, in the VMs we would get mainly output from rdrand (if present)
> XORed with the very slow/weak output from the VM-stifled entropy collector.
>
> So the plentiful entropy you're seeing in your VMs Abel is not trusted
> quite as much by the kernel developers as the kernel's normal CSPRNG
> output. In their view, it is weaker than what is available in DOM0 (even
> though both the VMs and DOM0 are getting input from rdrand).
>

Yes, this is what I was alluding at with my post. If you look at the
RDRAND discussions, it guarantees too be non-blocking, which, observers
have noted, indicates there is likely an internal fallback to a PRNG in
cases where it cannot produce "hard" entropy fast enough.

> Also, besides the simplicity/security issue that Joanna raises, there is
> a question of whether the method of transfer into the VMs will be
> efficient. Since a CSPRNG algorithm is operating -- both in DOM0 and in
> each VM -- should this process be bypassed in the VMs so that the crypto
> isn't unnecessarily run twice on the random stream?

I think writing chunks of bytes from dom0 into the VMs will be fine
enough. We must take care *not* to repeat the written bytes among VMs,
i.e., each VM gets unique data from dom0.

~abel

[Alex Dubois]

Alex

Ok makes sense, and would also feed the seed for the PRNG? I think we also need to ensure this is the case.

>
> ~abel