Re: TPMs and random numbers

Re: TPMs and random numbers

[David Safford]

>On 09/09/2013 02:11 PM, H. Peter Anvin wrote:
>> It recently came to my attention that there are no standards whatsoever
>> for random number generated by TPMs.  In fact, there *are* TPMs where
>> random numbers are generated by an encrypted nonvolatile counter (I do
>> not know which ones); this is apparently considered acceptable for the
>> uses of random numbers that TPMs produce.

The TPM specifications have extensive RNG requirements, and most 
major vendors do certify their RNG implementations to FIPS 140-2.
The current 1.2 spec has three pages of detailed RNG requirements. 
Even the earliest spec (1.1b from 2002) required FIPS 140-1 
compliant power-on self tests of the RNG, and since 2006 the specs 
have required full FIPS 140-2 RNG compliance for FIPS mode.

Back when TPMs were first added to Thinkpads, I did extensive 
testing of TPM RNG outputs, including start up entropy, and found
them to be an excellent source. There may well be bad TPMs out 
there (I've heard rumors too), but I haven't run into one.

>> There are two issues with this from a Linux point of view.  One, we
>> harvest supposed entropy from the TPM for /dev/*random use via
>> /dev/hwrng and rngd.  This was something I originally proposed because
>> on a lot of platforms it is the only available entropy source with any
>> significant bandwidth.  However, in light of the above it is
>> questionable at best, at least with entropy being credited.
>
>Presumably the "entropy" should be mixed in but not credited to the
>available entropy.
>
>> The other issue is that we use tpm_get_random() *directly* in
>> security/keys/trusted.c.
>
>I don't know whether this makes sense, but all but one call seem to be
>related to TPM transactions -- breaking the TPM's RNG won't have any
>effects beyond, say, breaking the TPM's SRK.
>
>The one that looks dangerous is the one just under case Opt_new: it's
>using tpm_get_random to create an encryption key *that's used by the
>kernel for software crypto*.  That's IMO bogus.
>
>--Andy

Conversely, other /dev/random sources can be slow to build entropy,
particularly in embedded systems (see
https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf)

As author of trusted.c, I think that there are advantages and
disadvantages to the different random sources. Trusted keys
already depend on the quality of TPM private keys generated
from the TPM RNG, so trusting the same RNG for symmetric key
generation seems reasonable. Several embedded systems I have 
looked at are _really_ bad at gathering entropy, so the TPM, 
seems a reasonably safe and convenient default. 

dave

Re: TPMs and random numbers

[Andy Lutomirski]

On Wed, Sep 11, 2013 at 10:22 AM, David Safford <safford@us.ibm.com> wrote:
>>On 09/09/2013 02:11 PM, H. Peter Anvin wrote:
>>> It recently came to my attention that there are no standards whatsoever
>>> for random number generated by TPMs.  In fact, there *are* TPMs where
>>> random numbers are generated by an encrypted nonvolatile counter (I do
>>> not know which ones); this is apparently considered acceptable for the
>>> uses of random numbers that TPMs produce.
>
> The TPM specifications have extensive RNG requirements, and most
> major vendors do certify their RNG implementations to FIPS 140-2.
> The current 1.2 spec has three pages of detailed RNG requirements.
> Even the earliest spec (1.1b from 2002) required FIPS 140-1
> compliant power-on self tests of the RNG, and since 2006 the specs
> have required full FIPS 140-2 RNG compliance for FIPS mode.
>
> Back when TPMs were first added to Thinkpads, I did extensive
> testing of TPM RNG outputs, including start up entropy, and found
> them to be an excellent source. There may well be bad TPMs out
> there (I've heard rumors too), but I haven't run into one.

A TPM that has an excellent internal entropy source and is FIPS 140-2
compliant with no bugs whatsoever may still use Dual_EC_DRBG, which
looks increasingly likely to be actively malicious.

>
>>> There are two issues with this from a Linux point of view.  One, we
>>> harvest supposed entropy from the TPM for /dev/*random use via
>>> /dev/hwrng and rngd.  This was something I originally proposed because
>>> on a lot of platforms it is the only available entropy source with any
>>> significant bandwidth.  However, in light of the above it is
>>> questionable at best, at least with entropy being credited.
>>
>>Presumably the "entropy" should be mixed in but not credited to the
>>available entropy.
>>
>>> The other issue is that we use tpm_get_random() *directly* in
>>> security/keys/trusted.c.
>>
>>I don't know whether this makes sense, but all but one call seem to be
>>related to TPM transactions -- breaking the TPM's RNG won't have any
>>effects beyond, say, breaking the TPM's SRK.
>>
>>The one that looks dangerous is the one just under case Opt_new: it's
>>using tpm_get_random to create an encryption key *that's used by the
>>kernel for software crypto*.  That's IMO bogus.
>>
>>--Andy
>
> Conversely, other /dev/random sources can be slow to build entropy,
> particularly in embedded systems (see
> https://www.usenix.org/system/files/conference/usenixsecurity12/sec12-final228.pdf)
>
> As author of trusted.c, I think that there are advantages and
> disadvantages to the different random sources. Trusted keys
> already depend on the quality of TPM private keys generated
> from the TPM RNG, so trusting the same RNG for symmetric key
> generation seems reasonable. Several embedded systems I have
> looked at are _really_ bad at gathering entropy, so the TPM,
> seems a reasonably safe and convenient default.

I'd be *much* happier if my system read a few hundred random bytes
from the TPM at startup and fed those bytes into the kernel's entropy
pool.  This should IMO happen at startup as early as possible.

Ideally the kernel would then ban any subsequent attempts to read the
TPM's RNG directly to make it much harder to exploit any backdoors in
the RNG that may exist.  Barring that, using the added protection that
the kernel's RNG provides but seeding it with the TPM's RNG is
probably at least as safe, if not much safer, than using the kernel's
RNG without entropy from the TPM or using the TPM's without extra
mixing.

In any case, just because they TPM's private keys may or may not be
backdoored, the keys the wrap should be as safe as can be arranged.

--Andy

>
> dave
>



-- 
Andy Lutomirski
AMA Capital Management, LLC

Re: TPMs and random numbers

[Theodore Ts'o]

On Wed, Sep 11, 2013 at 10:49:59AM -0700, Andy Lutomirski wrote:
> 
> A TPM that has an excellent internal entropy source and is FIPS 140-2
> compliant with no bugs whatsoever may still use Dual_EC_DRBG, which
> looks increasingly likely to be actively malicious.

To be fair, given the limited CPU found in most TPM's, using
Dual_EC_DRBG would be rather unlikely.  It's more likely that the TPM
would be using a real hardware RNG --- and if the TPM was compromised
by some evil spy agency, it would be doing using something like
AES_ENCRYPT(i++, NSA_KEY), not using Dual_EC_DRBG.

> I'd be *much* happier if my system read a few hundred random bytes
> from the TPM at startup and fed those bytes into the kernel's entropy
> pool.  This should IMO happen at startup as early as possible.

We should definitely do this.  If the TPM driver could fetch some
randomness and then call add_device_randomness() to feed this into the
random driver's entropy pool when it initializes itself, that would be
***really*** cool.

							- Ted

Re: TPMs and random numbers

[Jeff Garzik]

On Wed, Sep 11, 2013 at 2:45 PM, Theodore Ts'o <tytso@mit.edu> wrote:
> We should definitely do this.  If the TPM driver could fetch some
> randomness and then call add_device_randomness() to feed this into the
> random driver's entropy pool when it initializes itself, that would be
> ***really*** cool.


rngd already does this.

     Jeff

Re: TPMs and random numbers

[Andy Lutomirski]

On Wed, Sep 11, 2013 at 12:06 PM, Jeff Garzik <jgarzik@pobox.com> wrote:
> On Wed, Sep 11, 2013 at 2:45 PM, Theodore Ts'o <tytso@mit.edu> wrote:
>> We should definitely do this.  If the TPM driver could fetch some
>> randomness and then call add_device_randomness() to feed this into the
>> random driver's entropy pool when it initializes itself, that would be
>> ***really*** cool.
>
>
> rngd already does this.

And all those random numbers generated before rngd starts are quite
possibly crap.

I think that rngd makes sense as a tool to access strange sources of
entropy and to periodically reseed the pool, but I also think that the
kernel should really be pulling in easily available entropy on its own
at startup.

--Andy

Re: TPMs and random numbers

[H. Peter Anvin]

This of course has been a long-running debate.  Similarly, we could make much better use of RDRAND if instead of doing data reduction in rngd we could feed it to the pool and just credit fractional bits.  The FIPS tests that rngd runs are weak and obsoleted, but perhaps better than nothing (now when we don't shut down rngd due to false positives.)

Andy Lutomirski <luto@amacapital.net> wrote:
>On Wed, Sep 11, 2013 at 12:06 PM, Jeff Garzik <jgarzik@pobox.com>
>wrote:
>> On Wed, Sep 11, 2013 at 2:45 PM, Theodore Ts'o <tytso@mit.edu> wrote:
>>> We should definitely do this.  If the TPM driver could fetch some
>>> randomness and then call add_device_randomness() to feed this into
>the
>>> random driver's entropy pool when it initializes itself, that would
>be
>>> ***really*** cool.
>>
>>
>> rngd already does this.
>
>And all those random numbers generated before rngd starts are quite
>possibly crap.
>
>I think that rngd makes sense as a tool to access strange sources of
>entropy and to periodically reseed the pool, but I also think that the
>kernel should really be pulling in easily available entropy on its own
>at startup.
>
>--Andy

-- 
Sent from my mobile phone.  Please pardon brevity and lack of formatting.

Re: TPMs and random numbers

[Theodore Ts'o]

On Wed, Sep 11, 2013 at 12:25:48PM -0700, H. Peter Anvin wrote:
> This of course has been a long-running debate.  Similarly, we could
> make much better use of RDRAND if instead of doing data reduction in
> rngd we could feed it to the pool and just credit fractional bits.
> The FIPS tests that rngd runs are weak and obsoleted, but perhaps
> better than nothing (now when we don't shut down rngd due to false
> positives.)

/dev/urandom is using RDRAND already, and that's what most of the
applications which are generating ssh host keys, session keys, etc.,
are using.

/dev/random is using RDRAND as well, but we're not giving any entropy
credit, so it will take longer to get the necessary randomness to
generate a GPG key.

The rason why it would be good to use TPM to fetch randomness is for
those platforms is (a) for pre-RDRAND capable x86 systems, and (c)
non-x86 platforms that might be using a TPM which don't have a RDRAND
function.

Also, in general, it's better to use as many entropy sources as
possible.

Cheers,

					- Ted

Re: TPMs and random numbers

[H. Peter Anvin]

On 09/11/2013 01:28 PM, Theodore Ts'o wrote:
> On Wed, Sep 11, 2013 at 12:25:48PM -0700, H. Peter Anvin wrote:
>> This of course has been a long-running debate.  Similarly, we could
>> make much better use of RDRAND if instead of doing data reduction in
>> rngd we could feed it to the pool and just credit fractional bits.
>> The FIPS tests that rngd runs are weak and obsoleted, but perhaps
>> better than nothing (now when we don't shut down rngd due to false
>> positives.)
> 
> /dev/urandom is using RDRAND already, and that's what most of the
> applications which are generating ssh host keys, session keys, etc.,
> are using.
> 
> /dev/random is using RDRAND as well, but we're not giving any entropy
> credit, so it will take longer to get the necessary randomness to
> generate a GPG key.
> 

We're using RDRAND in two ways: in the kernel, we're "washing" the pool
output with it (with the notion that we'll always get the best of both
worlds) -- we don't give any entropy credit for that.

We are also using RDRAND with the architecturally required 512:1 data
reduction in rngd, to produce "creditable entropy".  This is in part
because rngd doesn't really have a way to deal with fractional entropy,
in the light of FIPS tests and all (which don't make sense anyway for
postconditioned output, from RDRAND, TPM or any other similar source.)

One could thus posit that it would make more sense for that type of
source to feed the kernel entropy pools directly from a kernel thread
rather than taking a trip to user space.  In the case of RDRAND
specifically, a kernel thread or similar could feed RDRAND to the pools
and credit 1/512 of the data volume as entropy.  Since the factor of 512
is an architectural lower bound (and *very* conservative) it would be
better to let the pool system do the data reduction than doing it in
userspace.

Now, I'm pretty sure that some cryptographers are very unhappy about the
fact that we use a linear operation to do the pool insertion mixing.  I
personally am not qualified to say to what extent that is an actual problem.

	-hpa

Re: TPMs and random numbers

[David Safford]

On Wed, 2013-09-11 at 10:49 -0700, Andy Lutomirski wrote:
> On Wed, Sep 11, 2013 at 10:22 AM, David Safford <safford@us.ibm.com> wrote:
> >>On 09/09/2013 02:11 PM, H. Peter Anvin wrote:
> 
> A TPM that has an excellent internal entropy source and is FIPS 140-2
> compliant with no bugs whatsoever may still use Dual_EC_DRBG, which
> looks increasingly likely to be actively malicious.

I don't know of any that do so (it's more complex and slower than
the alternatives). 

> I'd be *much* happier if my system read a few hundred random bytes
> from the TPM at startup and fed those bytes into the kernel's entropy
> pool.  This should IMO happen at startup as early as possible.

I agree completely that the ideal case is a system with good entropy
sources, including a TPM, and all these mixed as early as possible.
But I also think that the existing (certified) TPMs are good enough 
for direct use.

dave

Re: TPMs and random numbers

[Jörn Engel]

On Wed, 11 September 2013 14:47:04 -0400, David Safford wrote:
>
> But I also think that the existing (certified) TPMs are good enough 
> for direct use.

That is equivalent to trusting the TPM chip not to be malicious.  It
requires trusting the chip designer, trusting every single employee of
the chip designer, as some of them may be plants from a random
countries spook organization, trusting the fab where the chip was
manufactured, trusting your local dealer not to replace one chip with
another in a similar packaging, trusting third-party components the
designers may have incorporated, trusting intermediate steps between
designer and fab or fab and local dealer, trusting your own employees,
etc.

If you sum it all up, you quickly depend on hundreds of people in
multiple countries that have the ability to subvert your chips RNG
without you being able to notice any difference.

Or rather, you would only be able to notice the difference if you were
the person that subverted the chip.  So the NSA may be able to tell
whether the Chinese have subverted a specific chip.  Honi soit...

Jörn

--
"Security vulnerabilities are here to stay."
-- Scott Culp, Manager of the Microsoft Security Response Center, 2001

Re: TPMs and random numbers

[Andy Lutomirski]

On Thu, Sep 12, 2013 at 2:57 PM, Jörn Engel <joern@logfs.org> wrote:
> On Wed, 11 September 2013 14:47:04 -0400, David Safford wrote:
>>
>> But I also think that the existing (certified) TPMs are good enough
>> for direct use.
>
> That is equivalent to trusting the TPM chip not to be malicious.  It
> requires trusting the chip designer, trusting every single employee of
> the chip designer, as some of them may be plants from a random
> countries spook organization, trusting the fab where the chip was
> manufactured, trusting your local dealer not to replace one chip with
> another in a similar packaging, trusting third-party components the
> designers may have incorporated, trusting intermediate steps between
> designer and fab or fab and local dealer, trusting your own employees,
> etc.

I would argue that any TPM-using kernel code should go even further
than just not trusting its RNG.  We should be further wrapping the
TPM-generated keys so that even a complete leak of the SRK wouldn't
allow an adversary to unwrap the keys.

Of course, without blinded operations (which the TPM doesn't support),
we're always vulnerable to the TPM actively leaking private key bits,
but that seems less likely.

(I have a partial implementation of this called tpmkey -- some day I
hope to finish it.)

--Andy

Re: TPMs and random numbers

[Jeff Garzik]

On Thu, Sep 12, 2013 at 5:57 PM, Jörn Engel <joern@logfs.org> wrote:
> On Wed, 11 September 2013 14:47:04 -0400, David Safford wrote:
>> But I also think that the existing (certified) TPMs are good enough
>> for direct use.

> That is equivalent to trusting the TPM chip not to be malicious.  It

Indeed.  While it need not be rngd or userland at all, it seems
reasonable to require any hardware RNG to have its data pushed through
AES mix steps (as kernel random does now IIUC).

      Jeff

Re: TPMs and random numbers

[Jörn Engel]

On Thu, 12 September 2013 19:39:47 -0400, Jeff Garzik wrote:
> On Thu, Sep 12, 2013 at 5:57 PM, Jörn Engel <joern@logfs.org> wrote:
> > On Wed, 11 September 2013 14:47:04 -0400, David Safford wrote:
> >> But I also think that the existing (certified) TPMs are good enough
> >> for direct use.
> 
> > That is equivalent to trusting the TPM chip not to be malicious.  It
> 
> Indeed.  While it need not be rngd or userland at all, it seems
> reasonable to require any hardware RNG to have its data pushed through
> AES mix steps (as kernel random does now IIUC).

*shrug*

The hardware RNG is either providing good entropy or entirely
predictable data - without us being able to tell the difference.  So I
am torn between two extremes.  Either we admit it to the entropy pool
and mix it will all other sources - hoping that it actually is
unpredictable to The Bad Guys(tm).  Or we disregard all of it.

If we disregard all of it, that forces us to collect good entropy from
other sources.  Having what looks like good entropy but may not be
will a) make us complacent and b) make it hard to notice when our
random numbers are compromised.  It is the same strategy as burning
down the bridge, forcing your army to win or die.  It also shares the
same drawbacks.

Jörn

--
"Error protection by error detection and correction."
-- from a university class

Re: TPMs and random numbers

[Andy Lutomirski]

On Thu, Sep 12, 2013 at 3:13 PM, Jörn Engel <joern@logfs.org> wrote:
> On Thu, 12 September 2013 19:39:47 -0400, Jeff Garzik wrote:
>> On Thu, Sep 12, 2013 at 5:57 PM, Jörn Engel <joern@logfs.org> wrote:
>> > On Wed, 11 September 2013 14:47:04 -0400, David Safford wrote:
>> >> But I also think that the existing (certified) TPMs are good enough
>> >> for direct use.
>>
>> > That is equivalent to trusting the TPM chip not to be malicious.  It
>>
>> Indeed.  While it need not be rngd or userland at all, it seems
>> reasonable to require any hardware RNG to have its data pushed through
>> AES mix steps (as kernel random does now IIUC).
>
> *shrug*
>
> The hardware RNG is either providing good entropy or entirely
> predictable data - without us being able to tell the difference.  So I
> am torn between two extremes.  Either we admit it to the entropy pool
> and mix it will all other sources - hoping that it actually is
> unpredictable to The Bad Guys(tm).  Or we disregard all of it.

Supposedly, the Linux entropy pool has the property that mixing in
even actively malicious data is no worse than not mixing in anything
at all.

(This is probably not true if the so-called entropy can depend on the
current (secret) state of the pool, but the TPM has no way to see
that.)

--Andy

Re: TPMs and random numbers

[Jörn Engel]

On Thu, 12 September 2013 16:51:15 -0700, Andy Lutomirski wrote:
> 
> Supposedly, the Linux entropy pool has the property that mixing in
> even actively malicious data is no worse than not mixing in anything
> at all.

It is worse in three ways:
- it costs performance,
- it may create a false sense of safety and
- it actively does harm if we credit it as entropy.

How much weight you assign to each of those is up to you.  So long as
we don't credit any of it as entropy, I am not too adverse to mixing
it in.  But I can equally see benefit in burning the bridges.

Jörn

--
There are two ways of constructing a software design: one way is to make
it so simple that there are obviously no deficiencies, and the other is
to make it so complicated that there are no obvious deficiencies.
-- C. A. R. Hoare

Re: TPMs and random numbers

[Theodore Ts'o]

On Thu, Sep 12, 2013 at 06:23:09PM -0400, Jörn Engel wrote:
> It is worse in three ways:
> - it costs performance,
> - it may create a false sense of safety and
> - it actively does harm if we credit it as entropy.
> 
> How much weight you assign to each of those is up to you.  So long as
> we don't credit any of it as entropy, I am not too adverse to mixing
> it in.  But I can equally see benefit in burning the bridges.

Well, mixing it in and using /dev/[u]random is certainly better than
blindly using the output from the RNG from the TPM directly as a
key.

I'm not sure what you mean by "burning the bridges"; what is the
alternative that you are suggesting?

						- Ted

Re: TPMs and random numbers

[Jörn Engel]

On Thu, 12 September 2013 22:13:49 -0400, Theodore Ts'o wrote:
> On Thu, Sep 12, 2013 at 06:23:09PM -0400, Jörn Engel wrote:
> > It is worse in three ways:
> > - it costs performance,
> > - it may create a false sense of safety and
> > - it actively does harm if we credit it as entropy.
> > 
> > How much weight you assign to each of those is up to you.  So long as
> > we don't credit any of it as entropy, I am not too adverse to mixing
> > it in.  But I can equally see benefit in burning the bridges.
> 
> Well, mixing it in and using /dev/[u]random is certainly better than
> blindly using the output from the RNG from the TPM directly as a
> key.

Absolutely!

> I'm not sure what you mean by "burning the bridges"; what is the
> alternative that you are suggesting?

Not using hardware RNGs at all, see three messages back.  We know
those things can be compromised, we know a compromise cannot be
detected and we know of people/groups that have both a strong
motivation and likely the ability to pull it off.

I am not taking sides, but I can see good arguments for both
approaches.

Jörn

--
...one more straw can't possibly matter...
-- Kirby Bakken

RE: TPMs and random numbers

[Johnston, DJ]

	

>-----Original Message-----
>From: Andy Lutomirski [mailto:luto@amacapital.net] 

>A TPM that has an excellent internal entropy source and is FIPS 140-2 compliant with no bugs whatsoever may still use Dual_EC_DRBG, which looks increasingly likely to be actively malicious.

You can look up the FIPS certification to see which algorithms were approved. The Dual_EC_DRBG always looked suspect to me, which is one reason why it wasn't used in RdRand. The other is that the core crypto function doesn't do dual duty as an entropy extractor like AES hardware does with AES-CBC-MAC and AES-CTR-DRBG.
 
DJ

TPMs and random numbers

[H. Peter Anvin]

It recently came to my attention that there are no standards whatsoever
for random number generated by TPMs.  In fact, there *are* TPMs where
random numbers are generated by an encrypted nonvolatile counter (I do
not know which ones); this is apparently considered acceptable for the
uses of random numbers that TPMs produce.

There are two issues with this from a Linux point of view.  One, we
harvest supposed entropy from the TPM for /dev/*random use via
/dev/hwrng and rngd.  This was something I originally proposed because
on a lot of platforms it is the only available entropy source with any
significant bandwidth.  However, in light of the above it is
questionable at best, at least with entropy being credited.

The other issue is that we use tpm_get_random() *directly* in
security/keys/trusted.c.

I don't know what the policy ought to be, but I suspect we should ask
the question.

	-hpa

Re: TPMs and random numbers

[Andy Lutomirski]

On 09/09/2013 02:11 PM, H. Peter Anvin wrote:
> It recently came to my attention that there are no standards whatsoever
> for random number generated by TPMs.  In fact, there *are* TPMs where
> random numbers are generated by an encrypted nonvolatile counter (I do
> not know which ones); this is apparently considered acceptable for the
> uses of random numbers that TPMs produce.
> 
> There are two issues with this from a Linux point of view.  One, we
> harvest supposed entropy from the TPM for /dev/*random use via
> /dev/hwrng and rngd.  This was something I originally proposed because
> on a lot of platforms it is the only available entropy source with any
> significant bandwidth.  However, in light of the above it is
> questionable at best, at least with entropy being credited.

Presumably the "entropy" should be mixed in but not credited to the
available entropy.

> 
> The other issue is that we use tpm_get_random() *directly* in
> security/keys/trusted.c.

I don't know whether this makes sense, but all but one call seem to be
related to TPM transactions -- breaking the TPM's RNG won't have any
effects beyond, say, breaking the TPM's SRK.

The one that looks dangerous is the one just under case Opt_new: it's
using tpm_get_random to create an encryption key *that's used by the
kernel for software crypto*.  That's IMO bogus.

--Andy