Entropy sources (was: /dev/random - a new approach)

Entropy sources (was: /dev/random - a new approach)

[Jeffrey Walton]

On Fri, Aug 19, 2016 at 1:20 PM, H. Peter Anvin <hpa@linux.intel.com> wrote:
> On 08/18/16 22:56, Herbert Xu wrote:
>> On Thu, Aug 18, 2016 at 10:49:47PM -0400, Theodore Ts'o wrote:
>>>
>>> That really depends on the system.  We can't assume that people are
>>> using systems with a 100Hz clock interrupt.  More often than not
>>> people are using tickless kernels these days.  That's actually the
>>> problem with changing /dev/urandom to block until things are
>>> initialized.
>>
>> Couldn't we disable tickless until urandom has been seeded? In fact
>> perhaps we should accelerate the timer interrupt rate until it has
>> been seeded?
>>
>
> The biggest problem there is that the timer interrupt adds *no* entropy
> unless there is a source of asynchronicity in the system.  On PCs,
> traditionally the timer has been run from a completely different crystal
> (14.31818 MHz) than the CPU, which is the ideal situation, but if they
> are run off the same crystal and run in lockstep, there is very little
> if anything there.  On some systems, the timer may even *be* the only
> source of time, and the entropy truly is zero.

It seems like a networked computer should have an abundance on entropy
available from the network stack. Every common case I can come up with
includes a networked computer. If a handheld is outside of coverage,
then it probably does not have the randomness demands because it can't
communicate (i.e., TCP sequence numbers, key agreement, etc).

In fact, there are at least two papers that use bits from the network stack:

* When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities
and Hedging Deployed Cryptography,
http://pages.cs.wisc.edu/~rist/papers/sslhedge.pdf
* When Virtual is Harder than Real: Security Challenges in Virtual
Machine Based Computing Environments,
http://www.usenix.org/legacy/event/hotos05/final_papers/full_papers/garfinkel/garfinkel.pdf

As IoT gains traction the entropy available locally should increase
because these devices are chatty. I also expect gossip protocols to
play more of a role in the future. A network based attacker cannot
possibly monitor every conversation, especially when devices pair and
form adhoc networks. The network attacker probably won't see the
traffic on a local LAN segment either for headless servers.

When using network bits, it seems like the remaining problem is
extracting the entropy. I think Krawczyk (et al) have done a lot of
work in this area:

* Leftover Hash Lemma, Revisited, http://eprint.iacr.org/2011/088.pdf
* Cryptographic Extraction and Key Derivation: The HKDF Scheme,
http://eprint.iacr.org/2010/264.pdf

Jeff

Re: Entropy sources (was: /dev/random - a new approach)

[H. Peter Anvin]

On 08/20/16 22:37, Jeffrey Walton wrote:
>>
>> The biggest problem there is that the timer interrupt adds *no* entropy
>> unless there is a source of asynchronicity in the system.  On PCs,
>> traditionally the timer has been run from a completely different crystal
>> (14.31818 MHz) than the CPU, which is the ideal situation, but if they
>> are run off the same crystal and run in lockstep, there is very little
>> if anything there.  On some systems, the timer may even *be* the only
>> source of time, and the entropy truly is zero.
> 
> It seems like a networked computer should have an abundance on entropy
> available from the network stack. Every common case I can come up with
> includes a networked computer. If a handheld is outside of coverage,
> then it probably does not have the randomness demands because it can't
> communicate (i.e., TCP sequence numbers, key agreement, etc).
> 
> In fact, there are at least two papers that use bits from the network stack:
> 

The network stack is a good source of entropy, *once it is online*.
However, the most serious case is while the machine is still booting,
when the network will not have enabled yet.

	-hpa

Re: Entropy sources (was: /dev/random - a new approach)

[Sandy Harris]

On Thu, Aug 25, 2016 at 5:30 PM, H. Peter Anvin <hpa@zytor.com> wrote:

> The network stack is a good source of entropy, *once it is online*.
> However, the most serious case is while the machine is still booting,
> when the network will not have enabled yet.
>
>         -hpa

One possible solution is at:
https://github.com/sandy-harris/maxwell

A small (< 700 lines) daemon that gets entropy from timer imprecision
and variations in time for arithmetic (cache misses, interrupts, etc.)
and pumps it into /dev/random. Make it the first userspace program
started and all should be covered. Directory above includes a PDF doc
with detailed rationale and some discussion of alternate solutions.

Of course if you are dealing with a system-on-a-chip or low-end
embedded CPU & the timer is really inadequate, this will not work
well. Conceivably well enough, but we could not know that without
detailed analysis for each chip in question.

Re: Entropy sources

[H. Peter Anvin]

On 08/25/16 16:35, Sandy Harris wrote:
> On Thu, Aug 25, 2016 at 5:30 PM, H. Peter Anvin <hpa@zytor.com> wrote:
> 
>> The network stack is a good source of entropy, *once it is online*.
>> However, the most serious case is while the machine is still booting,
>> when the network will not have enabled yet.
>>
>>         -hpa
> 
> One possible solution is at:
> https://github.com/sandy-harris/maxwell
> 
> A small (< 700 lines) daemon that gets entropy from timer imprecision
> and variations in time for arithmetic (cache misses, interrupts, etc.)
> and pumps it into /dev/random. Make it the first userspace program
> started and all should be covered. Directory above includes a PDF doc
> with detailed rationale and some discussion of alternate solutions.
> 
> Of course if you are dealing with a system-on-a-chip or low-end
> embedded CPU & the timer is really inadequate, this will not work
> well. Conceivably well enough, but we could not know that without
> detailed analysis for each chip in question.
> 

A lot of this is exactly the same thing /dev/random already does in
kernel space.  I have already in the past expressed skepticism toward
this approach, because a lot of the analysis done has simply been bogus.

	-hpa