Prevent shared random seed across VMs

[marmarek]

Reported by @v6ak:

I've examined what is shared between AppVMs that use the same template with
focus on security and discussed that with the Qubes team. I've found that
/var/lib/systemd/random-seed is stored on /, which means:

1. Subsequent starts of a non-standalone VM use the same random-seed unless the underlying TemplateVM shutdown is performed between those two AppVM boots.
2. Two different AppVMs with the same TemplateVM may be seeded with the same initial random seed
3. This also applies between AppVM and TemplateVM. Such attacks are more attractive (as compromising entire TemplateVM is attractive), but they should be much less likely, as users are supposed to do limited set of tasks with a very limited network access.
4. When cloning a TemplateVM (either to another TemplateVM or to a StandaloneVM), the new VM gets initially the same random seed. It should, however, diverge after some time, so this issue is less serious.
5. Marek has confirmed that initial random seeds are predistributed with the ITL templates.

However, it is not as bad as it might look:

1. If haveged is used (i.e. on all ITL templates except fedora-minimal), it generates new entropy very quickly. Users of fedora-minimal should, however, be careful and consider installing haveged.
2. Quoting Marek: “the template is automatically started during its installation, so the new random seed will be saved. Not sure how predictable that new value is...”
3. According to Marek, systemd-random-seed only pushes the seed to the entropy pool, but does not increase the entropy_avail. As a result, this issue affects only /dev/urandom, while /dev/random seems to be unaffected.

Even better, this means that haveged reaches low water mark immediatelly
and starts gathering new entropy (if haveged is present), which minimizes
the issue.

Impact:

1. Long-term keys: They are usually recommended to be generated from /dev/random, so they should be usually unaffected. The cryptsetup uses /dev/urandom by default, but cryptsetup is typically not used in AppVMs.
2. Short-term keys can be affected in some cases, mostly on fedora-minimal, when you don't haveged installed.
3. Cryptographic nonces can be affected. If user is unlucky enough, he might get “ntwices” instead of nonces. Security implication of “ntwices” can vary, but it can be, for example, critical for ECDSA keys and thus for Bitcoin wallets. (Note that there were AFAIK some successful attacks on
   Bitcoin wallets where was a transaction signed by an Android client with flawed RNG, so such attacks might be practical.) Again, mostly users of fedora-minimal without haveged installed should be worried about this.

Note that users of non-systemd OSes (Debian 7?) may be affected more, because the random seed scripts may behave differently. If entropy_avail is increased by the random seed script, such issue would also affect /dev/random. Moreover, haveged would probably not reach low water mark so quickly, so the impact would be greater in such case. However, not using systemd does not imply this behavior. Not using systemd just means I don't know how it behaves.

How to fix?

Moving random seed to /rw does not fully solve this issue at the moment. The /rw is cloned from the TemplateVM, which is somehow suboptimal.

We've also discussed distributing some entropy from dom0 to AppVMs. Some related discussion: #673 . While it solves these issues, it makes dom0 potentially more vulnerable to its RNG flaws. I remember a keyboard timing side-channel vulnerability on /dev/random. Maybe dom0 should only provide an one-time random seed in order to lower impact of such vulnerabilities. If an AppVM asks for new random seed second time within one boot, the user should be at least notified.

How to prevent similar issues?

This and similar issues could have been found by:

1. deterministic builds of templates (random seed would cause) can uncover issues like pre-distributed random seed
2. no mutation after reboot (except some whitelist like logs) can uncover issues like random seed shared between AppVMs

Note that 1) does not uncover issues with packages that are not preinstalled. But such testing can be used on any package. It can uncover issues like shared SSH keys (I remember such issue at one VPS provider that provides VPS templates…) and so on.

Public discussion

We have decided to start a public discussion in order to find the best
solution.

The discussion:
https://groups.google.com/d/msgid/qubes-devel/8f3553f3-cf7e-41ce-959f-d81a6285a0f5%40googlegroups.com

[qubesuser]

Reading 256 bits from dom0 /dev/urandom at VM startup and passing the value to the VM by writing it to a part of the first sector of volatile.img that isn't the partition table seems the simplest solution, and should work with disposable VMs too (might need to blockdev --flushbufs the device before reading it).

[qubesuser]

Reading 256 bits from dom0 /dev/urandom at VM startup and passing the value to the VM by writing it to a part of the first sector of volatile.img that isn't the partition table seems the simplest solution, and should work with disposable VMs too (might need to blockdev --flushbufs the device before reading it).

[marmarek]

Linked thread already contains patches prepared by HW42, which
implements very similar approach, but use QubesDB for that. I'm going to
apply them.

Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?

[marmarek]

Linked thread already contains patches prepared by HW42, which
implements very similar approach, but use QubesDB for that. I'm going to
apply them.

Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?

[adrelanos]

Same issue reported against a different project:
grml/grml-debootstrap#91

The problem is, that no big mainstream distribution such as Debian or Fedora officially ships raw / VM images. They all ship installer dvd. Distributing images is relatively new.

Shipping public known random seeds by default is the worst situation. They should of course not be shipped. But not shipping the file at all and leaving it to the system may also be an issue. Perhaps that's off-topic here and deserves it's own ticket.

So when one installs using a mainstream installer dvd, how are the random seeds created on the disk? Can we re-use the same mechanism?

What happens if an image is started, that does not have the random seeds? Will the system safely create them at boot time then?

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only. Then this may also be not much more secure than shipping public known random seed files. I haven't fully wrapped my head around this yet. Might be upstream issues, but these need to be found and reported. Not sure it's a Tails specific or general issue.

[adrelanos]

Same issue reported against a different project:
grml/grml-debootstrap#91

The problem is, that no big mainstream distribution such as Debian or Fedora officially ships raw / VM images. They all ship installer dvd. Distributing images is relatively new.

Shipping public known random seeds by default is the worst situation. They should of course not be shipped. But not shipping the file at all and leaving it to the system may also be an issue. Perhaps that's off-topic here and deserves it's own ticket.

So when one installs using a mainstream installer dvd, how are the random seeds created on the disk? Can we re-use the same mechanism?

What happens if an image is started, that does not have the random seeds? Will the system safely create them at boot time then?

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only. Then this may also be not much more secure than shipping public known random seed files. I haven't fully wrapped my head around this yet. Might be upstream issues, but these need to be found and reported. Not sure it's a Tails specific or general issue.

[marmarek]

So when one installs using a mainstream installer dvd, how are the random seeds created on the disk? Can we re-use the same mechanism?

In some cases, using post installation scripts, in other - on first startup. I don't think there is generic way to reuse any of those techniques. At least we need to ensure that distributed images are free from random-seeds. Building image twice and comparing the results should reveal that.

What happens if an image is started, that does not have the random seeds? Will the system safely create them at boot time then?

Most likely. And exceptions (hopefully rare) needs to be fixed some other way - for example creating them manually (copy&paste from post-installation script? re-running that script dpkg-reconfigure?)

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only.

This is already handled by patches for this very ticket.

[marmarek]

So when one installs using a mainstream installer dvd, how are the random seeds created on the disk? Can we re-use the same mechanism?

In some cases, using post installation scripts, in other - on first startup. I don't think there is generic way to reuse any of those techniques. At least we need to ensure that distributed images are free from random-seeds. Building image twice and comparing the results should reveal that.

What happens if an image is started, that does not have the random seeds? Will the system safely create them at boot time then?

Most likely. And exceptions (hopefully rare) needs to be fixed some other way - for example creating them manually (copy&paste from post-installation script? re-running that script dpkg-reconfigure?)

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only.

This is already handled by patches for this very ticket.

[adrelanos]

Marek Marczykowski-Górecki:

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only.
This is already handled by patches for this very ticket.

Isn't that something that should be upstreamed to Debian/Fedora? Or at
least reported upstream? Sounds like an upstream bug to me?

[adrelanos]

Marek Marczykowski-Górecki:

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only.
This is already handled by patches for this very ticket.

Isn't that something that should be upstreamed to Debian/Fedora? Or at
least reported upstream? Sounds like an upstream bug to me?

[marmarek]

On Sat, Oct 10, 2015 at 07:44:59AM -0700, Patrick Schleizer wrote:

Marek Marczykowski-Górecki:

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only.
This is already handled by patches for this very ticket.

Isn't that something that should be upstreamed to Debian/Fedora? Or at
least reported upstream? Sounds like an upstream bug to me?

I think there are two issues:

1. Having random seeds distributed in template packages
2. Having random seeds (and other unique identifiers) shared among VMs

The first one is a security issue, because it may affect quality of PRNG.
This also apply to other data like host keys etc (checked the obvious
locations and currently none are included). But it doesn't apply to just
"unique identifiers" (like machine-id). It's even better for anonymity
reasons. This apply only to software preinstalled in the templates.

The second one apply to all the files above - where it is also a
security issue. But in case of Whonix, it additionally apply to unique
identifiers, because it may be used to correlate different VMs on the
same physical system. Note that only unique identifiers not included in
the original template image are a threat here, because only those are
identifying the user (not just the fact that Whonix on Qubes is used).

The first issue probably worth reporting upstream. The second is quite
Qubes specific.

BTW Just checked that Debian Live image doesn't contain
/var/lib/urandom/random-seed. Is it removed somewhere during image
build (and we can reuse that code), or it isn't created at all - in
which case it's interesting why we had it created.

Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?

[marmarek]

On Sat, Oct 10, 2015 at 07:44:59AM -0700, Patrick Schleizer wrote:

Marek Marczykowski-Górecki:

Tails has a similar issue. See https://labs.riseup.net/code/issues/7642. It implies that the seed file may be seeded by date +%s.%N only.
This is already handled by patches for this very ticket.

Isn't that something that should be upstreamed to Debian/Fedora? Or at
least reported upstream? Sounds like an upstream bug to me?

I think there are two issues:

1. Having random seeds distributed in template packages
2. Having random seeds (and other unique identifiers) shared among VMs

The first one is a security issue, because it may affect quality of PRNG.
This also apply to other data like host keys etc (checked the obvious
locations and currently none are included). But it doesn't apply to just
"unique identifiers" (like machine-id). It's even better for anonymity
reasons. This apply only to software preinstalled in the templates.

The second one apply to all the files above - where it is also a
security issue. But in case of Whonix, it additionally apply to unique
identifiers, because it may be used to correlate different VMs on the
same physical system. Note that only unique identifiers not included in
the original template image are a threat here, because only those are
identifying the user (not just the fact that Whonix on Qubes is used).

The first issue probably worth reporting upstream. The second is quite
Qubes specific.

BTW Just checked that Debian Live image doesn't contain
/var/lib/urandom/random-seed. Is it removed somewhere during image
build (and we can reuse that code), or it isn't created at all - in
which case it's interesting why we had it created.

Best Regards,
Marek Marczykowski-Górecki
Invisible Things Lab
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?

[marmarek]

Update already in current-testing repository.

[marmarek]

Update already in current-testing repository.