Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 14:22:48 schrieb Austin S. Hemmelgarn:

Hi Austin,

> On 2016-06-21 12:28, Stephan Mueller wrote:
> > Am Dienstag, 21. Juni 2016, 12:03:56 schrieb Austin S. Hemmelgarn:
> > 
> > Hi Austin,
> > 
> >> On 2016-06-21 03:32, Stephan Mueller wrote:
> >>> Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
> >>> 
> >>> Hi Nikos,
> >>> 
>  On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller 
> >>> 
> >>> wrote:
> >> Personally, I don't really use /dev/random, nor would I recommend it
> >> for most application programmers.  At this point, getrandom(2) really
> >> is the preferred interface unless you have some very specialized
> >> needs.
> > 
> > I fully agree. But there are use cases for /dev/random, notably as a
> > seed
> > source for other DRNG.
>  
>  Is that really the case? I believe all DRNG's use /dev/urandom anyway
>  for seeding since they cannot afford indeterminate blocking. It would
>  be a gain for everyone if /dev/random was the same as /dev/urandom in
>  Linux.
> >>> 
> >>> For standard approaches, this is true. But there are regulations,
> >>> notably
> >>> in the German realm, /dev/random shall be used, at least partially (see
> >>> AIS 20/31).
> >> 
> >> Which just goes to show how utterly stupid some people who write laws
> >> and regulations are.  Saying specifically that '/dev/random shall be
> >> used' does not enforce any improvement of entrophic value in the data at
> >> all, it just coincidentally improves the theoretical quality of the data
> >> because of how Linux and some legacy UNIX systems are designed.  This
> >> 'regulation' already provides zero benefit other than a placebo effect
> >> on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
> >> derivatives, as /dev/random and /dev/urandom point to the same thing
> >> there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
> >> uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
> >> does likewise (although they use a design based on yarrow).
> > 
> > It is NOT utterly stupid, you should listen to the reasons.
> 
> I'm not commenting about them wanting cryptographically secure entropy.
> My statement about the intelligence of the people who wrote the standard
> was commenting on their saying '/dev/random shall be used' instead of 'a

It behooves if you read the documents before making statements! AIS 20/31 does 
not require /dev/random in the documentation, but specifies a number of 
requirements for a seed source (NTG.1, PTG.[1|2|3]). And /dev/random happens 
to be an NTG.1 whereas /dev/urandom is not.

> cryptographically secure entropy source shall be used'.  POSIX requires
> that the first statement imply the second, but the second does not
> require the first.  Their choice to use the first indicates that they
> assume this will be the only implementation that will ever matter, and
> that POSIX systems will be the only thing anyone using the standard
> cares about, both of which are inherently poor assumptions outside of a
> completely closed system.  Most standards proposed or mandated by
> bureaucracies have similar issues making bad assumptions about the
> context in which they will be used.
> 
> > The core reason is
> > explained with the following analogy:
> > 
> > /dev/urandom, for a short period of time, operates as a DRNG. For the sake
> > of discussion, let us assume that it is a DRNG which is, for the sake of
> > discussion, seeded with 256 bits of entropy.
> > 
> > Now, you pull 256 bits out of it, you have 256 bits of entropy.
> > 
> > You pull again 256 bit out of it -- what entropy do you have? You do NOT
> > have *again* 256 bits of entropy. All you can say is the entire generated
> > 512 bits have collectively 256 bits of entropy. And so on and so forth.
> > 
> > Now, if you want to say that your newly spawned DRNG is seeded with X
> > amount of entropy, the DRNG nature of /dev/urandom makes such a statement
> > a challenge. The easy way out of the challenge is to use /dev/random (I
> > am aware of the fact that the DRNG has a computational strength, but it
> > is not, well, entropy).
> > 
> > In addition, when using /dev/urandom, you have to show that at the time
> > you
> > seed the DRNG, it is fully seeded. That is a challenge at boot time - a
> > challenge this entire thread revolves around. Yes, getrandom(2) is the way
> > out, but not everybody uses it. Again, /dev/random does NOT have this
> > challenge.
> 
> The fact that that's how /dev/urandom works is a result of the
> implementation, I already listed at least 3 UNIX derivatives that do not
> work this way and provide cryptographically secure entropy from the same
> source stream for both /dev/random and /dev/urandom.  Changing this on
> Linux would not break backwards compatibility as long as we provide
> sufficient entropy via /dev/random, because nobody depends on it
> blocking 

Re: [PATCH v5 0/7] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 12:28, Stephan Mueller wrote:

Am Dienstag, 21. Juni 2016, 12:03:56 schrieb Austin S. Hemmelgarn:

Hi Austin,


On 2016-06-21 03:32, Stephan Mueller wrote:

Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:

Hi Nikos,


On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller 


wrote:

Personally, I don't really use /dev/random, nor would I recommend it
for most application programmers.  At this point, getrandom(2) really
is the preferred interface unless you have some very specialized
needs.


I fully agree. But there are use cases for /dev/random, notably as a
seed
source for other DRNG.


Is that really the case? I believe all DRNG's use /dev/urandom anyway
for seeding since they cannot afford indeterminate blocking. It would
be a gain for everyone if /dev/random was the same as /dev/urandom in
Linux.


For standard approaches, this is true. But there are regulations, notably
in the German realm, /dev/random shall be used, at least partially (see
AIS 20/31).


Which just goes to show how utterly stupid some people who write laws
and regulations are.  Saying specifically that '/dev/random shall be
used' does not enforce any improvement of entrophic value in the data at
all, it just coincidentally improves the theoretical quality of the data
because of how Linux and some legacy UNIX systems are designed.  This
'regulation' already provides zero benefit other than a placebo effect
on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
derivatives, as /dev/random and /dev/urandom point to the same thing
there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
does likewise (although they use a design based on yarrow).


It is NOT utterly stupid, you should listen to the reasons.
I'm not commenting about them wanting cryptographically secure entropy. 
My statement about the intelligence of the people who wrote the standard 
was commenting on their saying '/dev/random shall be used' instead of 'a 
cryptographically secure entropy source shall be used'.  POSIX requires 
that the first statement imply the second, but the second does not 
require the first.  Their choice to use the first indicates that they 
assume this will be the only implementation that will ever matter, and 
that POSIX systems will be the only thing anyone using the standard 
cares about, both of which are inherently poor assumptions outside of a 
completely closed system.  Most standards proposed or mandated by 
bureaucracies have similar issues making bad assumptions about the 
context in which they will be used.



The core reason is
explained with the following analogy:

/dev/urandom, for a short period of time, operates as a DRNG. For the sake of
discussion, let us assume that it is a DRNG which is, for the sake of
discussion, seeded with 256 bits of entropy.

Now, you pull 256 bits out of it, you have 256 bits of entropy.

You pull again 256 bit out of it -- what entropy do you have? You do NOT have
*again* 256 bits of entropy. All you can say is the entire generated 512 bits
have collectively 256 bits of entropy. And so on and so forth.

Now, if you want to say that your newly spawned DRNG is seeded with X amount
of entropy, the DRNG nature of /dev/urandom makes such a statement a
challenge. The easy way out of the challenge is to use /dev/random (I am aware
of the fact that the DRNG has a computational strength, but it is not, well,
entropy).

In addition, when using /dev/urandom, you have to show that at the time you
seed the DRNG, it is fully seeded. That is a challenge at boot time - a
challenge this entire thread revolves around. Yes, getrandom(2) is the way
out, but not everybody uses it. Again, /dev/random does NOT have this
challenge.
The fact that that's how /dev/urandom works is a result of the 
implementation, I already listed at least 3 UNIX derivatives that do not 
work this way and provide cryptographically secure entropy from the same 
source stream for both /dev/random and /dev/urandom.  Changing this on 
Linux would not break backwards compatibility as long as we provide 
sufficient entropy via /dev/random, because nobody depends on it 
blocking for anything other than ensuring they get good entropy, so if 
it always returns good cryptographically secure entropy, we never need 
to block unless the generator hasn't yet been seeded.  Now, on top of 
that, there's still no absolute guarantee that what you get from 
/dev/random is actually cryptographically secure, but that's a separate 
issue.

--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 12:03:56 schrieb Austin S. Hemmelgarn:

Hi Austin,

> On 2016-06-21 03:32, Stephan Mueller wrote:
> > Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:
> > 
> > Hi Nikos,
> > 
> >> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller 
> > 
> > wrote:
>  Personally, I don't really use /dev/random, nor would I recommend it
>  for most application programmers.  At this point, getrandom(2) really
>  is the preferred interface unless you have some very specialized
>  needs.
> >>> 
> >>> I fully agree. But there are use cases for /dev/random, notably as a
> >>> seed
> >>> source for other DRNG.
> >> 
> >> Is that really the case? I believe all DRNG's use /dev/urandom anyway
> >> for seeding since they cannot afford indeterminate blocking. It would
> >> be a gain for everyone if /dev/random was the same as /dev/urandom in
> >> Linux.
> > 
> > For standard approaches, this is true. But there are regulations, notably
> > in the German realm, /dev/random shall be used, at least partially (see
> > AIS 20/31).
> 
> Which just goes to show how utterly stupid some people who write laws
> and regulations are.  Saying specifically that '/dev/random shall be
> used' does not enforce any improvement of entrophic value in the data at
> all, it just coincidentally improves the theoretical quality of the data
> because of how Linux and some legacy UNIX systems are designed.  This
> 'regulation' already provides zero benefit other than a placebo effect
> on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD
> derivatives, as /dev/random and /dev/urandom point to the same thing
> there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but
> uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX
> does likewise (although they use a design based on yarrow).

It is NOT utterly stupid, you should listen to the reasons. The core reason is 
explained with the following analogy:

/dev/urandom, for a short period of time, operates as a DRNG. For the sake of 
discussion, let us assume that it is a DRNG which is, for the sake of 
discussion, seeded with 256 bits of entropy.

Now, you pull 256 bits out of it, you have 256 bits of entropy.

You pull again 256 bit out of it -- what entropy do you have? You do NOT have 
*again* 256 bits of entropy. All you can say is the entire generated 512 bits 
have collectively 256 bits of entropy. And so on and so forth.

Now, if you want to say that your newly spawned DRNG is seeded with X amount 
of entropy, the DRNG nature of /dev/urandom makes such a statement a 
challenge. The easy way out of the challenge is to use /dev/random (I am aware 
of the fact that the DRNG has a computational strength, but it is not, well, 
entropy).

In addition, when using /dev/urandom, you have to show that at the time you 
seed the DRNG, it is fully seeded. That is a challenge at boot time - a 
challenge this entire thread revolves around. Yes, getrandom(2) is the way 
out, but not everybody uses it. Again, /dev/random does NOT have this 
challenge.
> 
> On top of that though, just because some poorly thought out standard
> requires it's usage doesn't mean we have to work based on that.

I cannot concur.


Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Austin S. Hemmelgarn]

On 2016-06-21 03:32, Stephan Mueller wrote:

Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:

Hi Nikos,


On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller 

wrote:

Personally, I don't really use /dev/random, nor would I recommend it
for most application programmers.  At this point, getrandom(2) really
is the preferred interface unless you have some very specialized
needs.


I fully agree. But there are use cases for /dev/random, notably as a seed
source for other DRNG.


Is that really the case? I believe all DRNG's use /dev/urandom anyway
for seeding since they cannot afford indeterminate blocking. It would
be a gain for everyone if /dev/random was the same as /dev/urandom in
Linux.


For standard approaches, this is true. But there are regulations, notably in
the German realm, /dev/random shall be used, at least partially (see AIS
20/31).
Which just goes to show how utterly stupid some people who write laws 
and regulations are.  Saying specifically that '/dev/random shall be 
used' does not enforce any improvement of entrophic value in the data at 
all, it just coincidentally improves the theoretical quality of the data 
because of how Linux and some legacy UNIX systems are designed.  This 
'regulation' already provides zero benefit other than a placebo effect 
on at least OpenBSD, FreeBSD, and I'm pretty certain most other BSD 
derivatives, as /dev/random and /dev/urandom point to the same thing 
there (on OpenBSD it's an arcfour based drbg, FreeBSD does similar but 
uses a CSPRNG called Fortuna), and while I'm not certain, I believe AIX 
does likewise (although they use a design based on yarrow).


On top of that though, just because some poorly thought out standard 
requires it's usage doesn't mean we have to work based on that.

--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 09:12:07 schrieb Nikos Mavrogiannopoulos:

Hi Nikos,

> On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller  
wrote:
> >> Personally, I don't really use /dev/random, nor would I recommend it
> >> for most application programmers.  At this point, getrandom(2) really
> >> is the preferred interface unless you have some very specialized
> >> needs.
> > 
> > I fully agree. But there are use cases for /dev/random, notably as a seed
> > source for other DRNG.
> 
> Is that really the case? I believe all DRNG's use /dev/urandom anyway
> for seeding since they cannot afford indeterminate blocking. It would
> be a gain for everyone if /dev/random was the same as /dev/urandom in
> Linux.

For standard approaches, this is true. But there are regulations, notably in 
the German realm, /dev/random shall be used, at least partially (see AIS 
20/31).

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Nikos Mavrogiannopoulos]

On Mon, Jun 20, 2016 at 5:43 PM, Stephan Mueller  wrote:
>> Personally, I don't really use /dev/random, nor would I recommend it
>> for most application programmers.  At this point, getrandom(2) really
>> is the preferred interface unless you have some very specialized
>> needs.
> I fully agree. But there are use cases for /dev/random, notably as a seed
> source for other DRNG.

Is that really the case? I believe all DRNG's use /dev/urandom anyway
for seeding since they cannot afford indeterminate blocking. It would
be a gain for everyone if /dev/random was the same as /dev/urandom in
Linux.

regards,
Nikos
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Dienstag, 21. Juni 2016, 01:12:55 schrieb Theodore Ts'o:

Hi Theodore,

> On Mon, Jun 20, 2016 at 09:00:49PM +0200, Stephan Mueller wrote:
> > The time stamp maintenance is the exact cause for the correlation: one HID
> > event triggers:
> > 
> > - add_interrupt_randomness which takes high-res time stamp, Jiffies and
> > some pointers
> > 
> > - add_input_randomness which takes high-res time stamp, Jiffies and HID
> > event value
> > 
> > The same applies to disk events. My suggestion is to get rid of the double
> > counting of time stamps for one event.
> > 
> > And I guess I do not need to stress that correlation of data that is
> > supposed to be entropic is not good :-)
> 
> What is your concern, specifically?  If it is in the entropy
> accounting, there is more entropy in HID event interrupts, so I don't
> think adding the extra 1/64th bit of entropy is going to be problematic.

My concern is that interrupts have *much* more entropy than 1/64th. With a 
revaluation of the assumed entropy in interrupts, we will serve *all* systems 
much better and not just systems with HID.

As said, I think we heavily penalize server type and VM environments against 
desktop systems by crediting entropy in large scale to HID and conversely to a 
much lesser degree to interrupts.
> 
> If it is that there are two timestamps that are closely correleated
> being added into the pool, the add_interrupt_randomness() path is
> going to mix that timestamp with the interrupt timings from 63 other
> interrupts before it is mixed into the input pool, while the
> add_input_randomness() mixes it directly into the pool.  So if you
> think there is a way this could be leveraged into attack, please give
> specifics --- but I think we're on pretty solid ground here.

I am not saying that there is an active attack vector. All I want is to 
revalue the entropy in one interrupt which can only be done if we drop the HID 
time stamp collection.

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Theodore Ts'o]

On Mon, Jun 20, 2016 at 09:00:49PM +0200, Stephan Mueller wrote:
> 
> The time stamp maintenance is the exact cause for the correlation: one HID 
> event triggers:
> 
> - add_interrupt_randomness which takes high-res time stamp, Jiffies and some 
> pointers
> 
> - add_input_randomness which takes high-res time stamp, Jiffies and HID event 
> value
> 
> The same applies to disk events. My suggestion is to get rid of the double 
> counting of time stamps for one event.
> 
> And I guess I do not need to stress that correlation of data that is supposed 
> to be entropic is not good :-)

What is your concern, specifically?  If it is in the entropy
accounting, there is more entropy in HID event interrupts, so I don't
think adding the extra 1/64th bit of entropy is going to be problematic.

If it is that there are two timestamps that are closely correleated
being added into the pool, the add_interrupt_randomness() path is
going to mix that timestamp with the interrupt timings from 63 other
interrupts before it is mixed into the input pool, while the
add_input_randomness() mixes it directly into the pool.  So if you
think there is a way this could be leveraged into attack, please give
specifics --- but I think we're on pretty solid ground here.

Cheers,

- Ted

--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[George Spelvin]

> With that being said, wouldn't it make sense to:
> 
> - Get rid of the entropy heuristic entirely and just assume a fixed value of 
> entropy for a given event?

What does that gain you?  You can always impose an upper bound, but *some*
evidence that it's not a metronome is nice to have.

> - remove the high-res time stamp and the jiffies collection in 
> add_disk_randomness and add_input_randomness to not run into the correlation 
> issue?

Again, you can argue for setting the estimate to zero, but why *remove*
the timestamp?  Maybe you lose nothing,maybe you lose something, but it's 
definitely
a monotonic decrease.

> - In addition, let us credit the remaining information zero bits of entropy 
> and just use it to stir the input_pool.

Unfortunately, that is of limited use.  We mustn't remove more bits (of data,
as well as entropy) from the input pool that there are bits of entropy coming 
in.

So the extra uncounted entropy never goes anywhere and does very little good.
So any time the input pool is "full" (by counted entropy), then the uncounted
entropy has been squeezed out and thrown away.

> - Conversely, as we now would not have the correlation issue any more, let us 
> change the add_interrupt_randomness to credit each received interrupt one bit 
> of entropy or something in this vicinity?  Only if random_get_entropy returns 
> 0, let us drop the credited entropy rate to something like 1/10th or 1/20th 
> bit per event.

Baically, do you have a convincing argument that *eery* interrupt has
this?  Even those coming from strongly periodic signals like audio DMA
buffer fills?

> Hence, we cannot estimate the entropy level at runtime. All we can do is 
> having a good conservative estimate. And for such estimate, I feel that 
> throwing lots of code against that problem is not helpful.

I agree that the efficiency constraints preclude having a really
good solution.  But is it worth giving up?

For example, suppose wecome up with a decent estimator, but only use it
when we're low on entropy.  When things are comfortable, underestimate.

For example, a low-overhead entropy estimator can be derived from
Maurer's universal test.  There are all sort of conditions required to
get an accurate measurement of entropy, but violating them produces
a conservative *underestimate*, which is just fine for an on-line
entropy estimator.  You can hash non-binary inputs to save table space;
collisions cause an entropy underestimate.  You can use a limited-range
age counter (e.g. 1 byte); wraps cause entropy underestimate.  You need
to initialize the history table before measurements are accurate, but
initializing everything to zero causes an initial entropy underestimate.
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Montag, 20. Juni 2016, 14:44:03 schrieb George Spelvin:

Hi George,

> > With that being said, wouldn't it make sense to:
> > 
> > - Get rid of the entropy heuristic entirely and just assume a fixed value
> > of entropy for a given event?
> 
> What does that gain you?  You can always impose an upper bound, but *some*
> evidence that it's not a metronome is nice to have.

You are right, but that is an online test -- and I suggest we have one. 
However, the heuristic with its fraction of bits maintenance and the 
asymptotic calculation in credit_entropy_bits is a bit over the top, 
considering that we know that the input data is far from accurate.
> 
> > - remove the high-res time stamp and the jiffies collection in
> > add_disk_randomness and add_input_randomness to not run into the
> > correlation issue?
> 
> Again, you can argue for setting the estimate to zero, but why *remove*
> the timestamp?  Maybe you lose nothing,maybe you lose something, but it's
> definitely a monotonic decrease.

The time stamp maintenance is the exact cause for the correlation: one HID 
event triggers:

- add_interrupt_randomness which takes high-res time stamp, Jiffies and some 
pointers

- add_input_randomness which takes high-res time stamp, Jiffies and HID event 
value

The same applies to disk events. My suggestion is to get rid of the double 
counting of time stamps for one event.

And I guess I do not need to stress that correlation of data that is supposed 
to be entropic is not good :-)

> 
> > - In addition, let us credit the remaining information zero bits of
> > entropy
> > and just use it to stir the input_pool.
> 
> Unfortunately, that is of limited use.  We mustn't remove more bits (of
> data, as well as entropy) from the input pool that there are bits of
> entropy coming in.

I am not saying that we take more bits out of the input pool. All I am 
suggesting is to take out the correlation and in the end credit the entropy 
source which definitely is available on all systems with higher entropy rates.
> 
> So the extra uncounted entropy never goes anywhere and does very little
> good. So any time the input pool is "full" (by counted entropy), then the
> uncounted entropy has been squeezed out and thrown away.
> 
> > - Conversely, as we now would not have the correlation issue any more, let
> > us change the add_interrupt_randomness to credit each received interrupt
> > one bit of entropy or something in this vicinity?  Only if
> > random_get_entropy returns 0, let us drop the credited entropy rate to
> > something like 1/10th or 1/20th bit per event.
> 
> Baically, do you have a convincing argument that *eery* interrupt has
> this?  Even those coming from strongly periodic signals like audio DMA
> buffer fills?

I am sure I cannot be convincing as you like it because in the end, entropy is 
relative.

But look at my measurements for my LRNG, tested with and without tickless 
kernel. I see timing variations which ten times the entropy rate I suggest 
here. Besides, the analysis I did for my Jitter RNG cannot be discarded 
either.
> 
> > Hence, we cannot estimate the entropy level at runtime. All we can do is
> > having a good conservative estimate. And for such estimate, I feel that
> > throwing lots of code against that problem is not helpful.
> 
> I agree that the efficiency constraints preclude having a really
> good solution.  But is it worth giving up?
> 
> For example, suppose wecome up with a decent estimator, but only use it
> when we're low on entropy.  When things are comfortable, underestimate.
> 
> For example, a low-overhead entropy estimator can be derived from
> Maurer's universal test.  There are all sort of conditions required to

I am not suggesting any test. Entropy cannot be measured. All we can measure 
are statistics. And I cannot see why one statistical test is better than the 
other. Thus, let us have the easiest statistical test there is: use a fixed, 
but appropriate entropy value for one event and be done with it.

All that statistical tests could be used for are health tests of the noise 
source.

> get an accurate measurement of entropy, but violating them produces
> a conservative *underestimate*, which is just fine for an on-line
> entropy estimator.  You can hash non-binary inputs to save table space;
> collisions cause an entropy underestimate.  You can use a limited-range
> age counter (e.g. 1 byte); wraps cause entropy underestimate.  You need
> to initialize the history table before measurements are accurate, but
> initializing everything to zero causes an initial entropy underestimate.


Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Montag, 20. Juni 2016, 11:28:38 schrieb Theodore Ts'o:

Hi Theodore,

> On Mon, Jun 20, 2016 at 07:51:59AM +0200, Stephan Mueller wrote:
> > - Correlation of noise sources: as outlined in [1] chapter 1, the three
> > noise sources of the legacy /dev/random implementation have a high
> > correlation. Such correlation is due to the fact that a HID/disk event at
> > the same time produces an IRQ event. The time stamp (which deliver the
> > majority of entropy) of both events are correlated. I would think that
> > the maintenance of the fast_pools partially breaks that correlation to
> > some degree though, yet how much the correlation is broken is unknown.
> 
> We add more entropy for disk events only if they are rotational (i.e.,
> not flash devices), and the justification for this is Don Davis's
> "Cryptographic randomness from air turbulence in disk drives" paper.
> There has also been work showing that by measuring disk completion
> times, you can actually notice when someone walks by the server
> (because the vibrations from footsteps affect disk head settling
> times).  In fact how you mount HDD's to isolate them from vibration
> can make a huge difference to the overall performance of your system.
> 
> As far as HID's are concerned, I will note that in 99.99% of the
> systems, if you have direct physical access to the system, you
> probably are screwed from a security perspective anyway.  Yes, one
> could imagine systems where the user might have access to keyboard and
> the mouse, and not be able to do other interesting things (such as
> inserting a BadUSB device into one of the ports, rebooting the system
> into single user mode, etc.).  But now you have to assume the user can
> actually manipulate the input devices down to jiffies 1ms or cycle
> counter (nanonsecond) level of granularity...
> 
> All of this being said, I will freely admit that the hueristics of
> entropy collection is by far one of the weaker aspects of the system.

With that being said, wouldn't it make sense to:

- Get rid of the entropy heuristic entirely and just assume a fixed value of 
entropy for a given event?

- remove the high-res time stamp and the jiffies collection in 
add_disk_randomness and add_input_randomness to not run into the correlation 
issue?

- In addition, let us credit the remaining information zero bits of entropy 
and just use it to stir the input_pool.

- Conversely, as we now would not have the correlation issue any more, let us 
change the add_interrupt_randomness to credit each received interrupt one bit 
of entropy or something in this vicinity? Only if random_get_entropy returns 
0, let us drop the credited entropy rate to something like 1/10th or 1/20th 
bit per event.

> Ultimately there is no way to be 100% accurate with **any** entropy
> system, since ENCRYPT(NSA_KEY, COUNTER++) has zero entropy, but good
> luck finding a entropy estimation system that can detect that.

+1 here

To me, all the entropy heuristic today is only a more elaborate test against 
the failure of a noise source. And this is how I use the 1st/2nd/3rd 
derivation in my code: it is just a failure test.

Hence, we cannot estimate the entropy level at runtime. All we can do is 
having a good conservative estimate. And for such estimate, I feel that 
throwing lots of code against that problem is not helpful.
> 
> > - The delivery of entropic data from the input_pool to the
> > (non)blocking_pools is not atomic (for the lack of better word), i.e. one
> > block of data with a given entropy content is injected into the
> > (non)blocking_pool where the output pool is still locked (the user cannot
> > obtain data during that injection time). With Ted's new patch set, two 64
> > bit blocks from the fast_pools are injected into the ChaCha20 DRNG. So,
> > it is clearly better than previously. But still, with the blocking_pool,
> > we face that issue. The reason for that issue is outlined in [1] 2.1. In
> > the pathological case with an active attack, /dev/random could have a
> > security strength of 2 * 128 bits of and not 2^128 bits when reading 128
> > bits out of it (the numbers are for illustration only, it is a bit better
> > as /dev/random is woken up at random_read_wakeup_bits intervals -- but
> > that number can be set to dangerous low levels down to 8 bits).
> 
> I believe what you are referring to is addressed by the avalanche
> reseeding feature.  Yes, that can be turned down by
> random_read_wakeup_bits, but (a) this requires root (at which point
> the game is up), and (b) in practice no one touches that knob.  You're
> right that it would probably be better to reject attempts to set that
> number to too-small a number, or perhaps remove the knob entirely.
> 
> Personally, I don't really use /dev/random, nor would I recommend it
> for most application programmers.  At this point, getrandom(2) really
> is the preferred interface unless you have some very specialized
> needs.

I fully agree. But there are use cases for 

Re: [PATCH v5 0/7] /dev/random - a new approach

[Theodore Ts'o]

On Mon, Jun 20, 2016 at 07:51:59AM +0200, Stephan Mueller wrote:
> 
> - Correlation of noise sources: as outlined in [1] chapter 1, the three noise 
> sources of the legacy /dev/random implementation have a high correlation. 
> Such 
> correlation is due to the fact that a HID/disk event at the same time 
> produces 
> an IRQ event. The time stamp (which deliver the majority of entropy) of both 
> events are correlated. I would think that the maintenance of the fast_pools 
> partially breaks that correlation to some degree though, yet how much the 
> correlation is broken is unknown.

We add more entropy for disk events only if they are rotational (i.e.,
not flash devices), and the justification for this is Don Davis's
"Cryptographic randomness from air turbulence in disk drives" paper.
There has also been work showing that by measuring disk completion
times, you can actually notice when someone walks by the server
(because the vibrations from footsteps affect disk head settling
times).  In fact how you mount HDD's to isolate them from vibration
can make a huge difference to the overall performance of your system.

As far as HID's are concerned, I will note that in 99.99% of the
systems, if you have direct physical access to the system, you
probably are screwed from a security perspective anyway.  Yes, one
could imagine systems where the user might have access to keyboard and
the mouse, and not be able to do other interesting things (such as
inserting a BadUSB device into one of the ports, rebooting the system
into single user mode, etc.).  But now you have to assume the user can
actually manipulate the input devices down to jiffies 1ms or cycle
counter (nanonsecond) level of granularity...

All of this being said, I will freely admit that the hueristics of
entropy collection is by far one of the weaker aspects of the system.
Ultimately there is no way to be 100% accurate with **any** entropy
system, since ENCRYPT(NSA_KEY, COUNTER++) has zero entropy, but good
luck finding a entropy estimation system that can detect that.

> - The delivery of entropic data from the input_pool to the 
> (non)blocking_pools 
> is not atomic (for the lack of better word), i.e. one block of data with a 
> given entropy content is injected into the (non)blocking_pool where the 
> output 
> pool is still locked (the user cannot obtain data during that injection 
> time). 
> With Ted's new patch set, two 64 bit blocks from the fast_pools are injected 
> into the ChaCha20 DRNG. So, it is clearly better than previously. But still, 
> with the blocking_pool, we face that issue. The reason for that issue is 
> outlined in [1] 2.1. In the pathological case with an active attack, 
> /dev/random could have a security strength of 2 * 128 bits of and not 2^128 
> bits when reading 128 bits out of it (the numbers are for illustration only, 
> it is a bit better as /dev/random is woken up at random_read_wakeup_bits 
> intervals -- but that number can be set to dangerous low levels down to 8 
> bits).

I believe what you are referring to is addressed by the avalanche
reseeding feature.  Yes, that can be turned down by
random_read_wakeup_bits, but (a) this requires root (at which point
the game is up), and (b) in practice no one touches that knob.  You're
right that it would probably be better to reject attempts to set that
number to too-small a number, or perhaps remove the knob entirely.

Personally, I don't really use /dev/random, nor would I recommend it
for most application programmers.  At this point, getrandom(2) really
is the preferred interface unless you have some very specialized
needs.  


Cheers,

- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Pavel Machek]

Hi!

> > On Sun 2016-06-19 17:58:41, Stephan Mueller wrote:
> > > Hi Herbert, Ted,
> > > 
> > > The following patch set provides a different approach to /dev/random which
> > > I call Linux Random Number Generator (LRNG) to collect entropy within the
> > > Linux kernel. The main improvements compared to the legacy /dev/random is
> > > to provide sufficient entropy during boot time as well as in virtual
> > > environments and when using SSDs. A secondary design goal is to limit the
> > > impact of the entropy collection on massive parallel systems and also
> > > allow the use accelerated cryptographic primitives. Also, all steps of
> > > the entropic data processing are testable. Finally massive performance
> > > improvements are visible at /dev/urandom and get_random_bytes.
> > 
> > Dunno. It is very similar to existing rng, AFAICT. And at the very
> > least, constants in existing RNG could be tuned to provide "entropy at
> > the boot time".
> 
> The key differences and thus my main concerns I have with the current design 
> are the following items. If we would change them, it is an intrusive change. 
> As of now, I have not seen that intrusive changes were accepted. This led me 
> to develop a competing algorithm.

Well, intrusive changes are hard to do, but replacing whole subsystems
is even harder -- and rightly so.

> - There was a debate around my approach assuming one bit of entropy per 
> received IRQ. I am really wondering about that discussion when there is a 
> much 
> bigger "forcast" problem with the legacy /dev/random: how can we credit HIDs 
> up to 11 bits of entropy when the user (a potential adversary) triggers these 
> events? I am sure I would be shot down with such an approach if I would 
> deliver that with a new implementation.

Well, if you can demonstrate 11 bits is too much, go ahead... I'm sure
that is rather easy to adjust.

But I believe that 1) user is not normally an adversary and 2) the
best thing for him to do would still be "pressing nothing". It will be
hard to press keys (etc) with great enough precision...

Best regards,
Pavel

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) 
http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Am Sonntag, 19. Juni 2016, 21:36:14 schrieb Pavel Machek:

Hi Pavel,

> On Sun 2016-06-19 17:58:41, Stephan Mueller wrote:
> > Hi Herbert, Ted,
> > 
> > The following patch set provides a different approach to /dev/random which
> > I call Linux Random Number Generator (LRNG) to collect entropy within the
> > Linux kernel. The main improvements compared to the legacy /dev/random is
> > to provide sufficient entropy during boot time as well as in virtual
> > environments and when using SSDs. A secondary design goal is to limit the
> > impact of the entropy collection on massive parallel systems and also
> > allow the use accelerated cryptographic primitives. Also, all steps of
> > the entropic data processing are testable. Finally massive performance
> > improvements are visible at /dev/urandom and get_random_bytes.
> 
> Dunno. It is very similar to existing rng, AFAICT. And at the very
> least, constants in existing RNG could be tuned to provide "entropy at
> the boot time".

The key differences and thus my main concerns I have with the current design 
are the following items. If we would change them, it is an intrusive change. 
As of now, I have not seen that intrusive changes were accepted. This led me 
to develop a competing algorithm.

- Correlation of noise sources: as outlined in [1] chapter 1, the three noise 
sources of the legacy /dev/random implementation have a high correlation. Such 
correlation is due to the fact that a HID/disk event at the same time produces 
an IRQ event. The time stamp (which deliver the majority of entropy) of both 
events are correlated. I would think that the maintenance of the fast_pools 
partially breaks that correlation to some degree though, yet how much the 
correlation is broken is unknown.

- Awarding IRQs only 1/64th bit of entropy compared to HID and disk noise 
sources is warranted due to the correlation. As I try to show, IRQs have a 
much higher entropy rate than what they are credited currently. But we cannot 
set that value higher due to the correlation issue. That means, currently we 
prefer desktop machines over server type systems since servers usually have no 
HID. In addition, with SSDs or virtio-disks the disk noise source is 
deactivated (again, common use cases for servers). Hence, server environments 
are heavily penalized. (Note, awarding IRQ events one bit of entropy is the 
root cause why my approach claims to be seeded very fast during boot time. 
Furthermore, as outlined in [1] chapter 1 and 2, IRQ events are entropic even 
in virtual machines which implies that even in VMs, my approach works well.)

- I am not sure the current way of crediting entropy has anything to do with 
its entropy. It just happen to underestimate our entropy so it does not hurt. 
I see no sensible reason why the calculation of an entropy estimate rests on 
the first/second and third derivation of the Jiffies -- the Jiffies hardly 
deliver any entropy and therefore why should they be a basis for entropy 
calculation?

- There was a debate around my approach assuming one bit of entropy per 
received IRQ. I am really wondering about that discussion when there is a much 
bigger "forcast" problem with the legacy /dev/random: how can we credit HIDs 
up to 11 bits of entropy when the user (a potential adversary) triggers these 
events? I am sure I would be shot down with such an approach if I would 
deliver that with a new implementation.

- The delivery of entropic data from the input_pool to the (non)blocking_pools 
is not atomic (for the lack of better word), i.e. one block of data with a 
given entropy content is injected into the (non)blocking_pool where the output 
pool is still locked (the user cannot obtain data during that injection time). 
With Ted's new patch set, two 64 bit blocks from the fast_pools are injected 
into the ChaCha20 DRNG. So, it is clearly better than previously. But still, 
with the blocking_pool, we face that issue. The reason for that issue is 
outlined in [1] 2.1. In the pathological case with an active attack, 
/dev/random could have a security strength of 2 * 128 bits of and not 2^128 
bits when reading 128 bits out of it (the numbers are for illustration only, 
it is a bit better as /dev/random is woken up at random_read_wakeup_bits 
intervals -- but that number can be set to dangerous low levels down to 8 
bits).


[1] http://www.chronox.de/lrng/doc/lrng.pdf

Ciao
Stephan
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Sandy Harris]

On Sun, Jun 19, 2016 at 3:36 PM, Pavel Machek  wrote:

>> The following patch set provides a different approach to /dev/random ...
>
> Dunno. It is very similar to existing rng, AFAICT.

I do not think so. A lot of the basic principles are the same of course,
but Stephan is suggesting some real changes. On the other hand, I'm
not sure all of them are good ideas & Ted has already incorporated
some into the driver, so it is debatable how much here is really useful.

> And at the very least, constants in existing RNG could be tuned
> to provide "entropy at the boot time".

No, this is a rather hard problem & just tweaking definitely will
not solve it. Ted's patches, Stephan's, mine, the grsecurity
stuff and the kernel hardening project all have things that
might help, but as far as I can see there is no complete
in-kernel solution yet.

Closest thing I have seen to a solution are Denker's suggestions at:
http://www.av8n.com/computer/htm/secure-random.htm#sec-boot-image

Those, though, require changes to build & installation methods
& it might be hard to get distros & device vendors to do it.

> So IMO this should be re-done as tweaks to existing design, not as
> completely new RNG.

I agree, & I think Stephan has already done some of that.
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v5 0/7] /dev/random - a new approach

[Pavel Machek]

On Sun 2016-06-19 17:58:41, Stephan Mueller wrote:
> Hi Herbert, Ted,
> 
> The following patch set provides a different approach to /dev/random which
> I call Linux Random Number Generator (LRNG) to collect entropy within the 
> Linux
> kernel. The main improvements compared to the legacy /dev/random is to provide
> sufficient entropy during boot time as well as in virtual environments and 
> when
> using SSDs. A secondary design goal is to limit the impact of the entropy
> collection on massive parallel systems and also allow the use accelerated
> cryptographic primitives. Also, all steps of the entropic data processing are
> testable. Finally massive performance improvements are visible at /dev/urandom
> and get_random_bytes.

Dunno. It is very similar to existing rng, AFAICT. And at the very
least, constants in existing RNG could be tuned to provide "entropy at
the boot time".

So IMO this should be re-done as tweaks to existing design, not as
completely new RNG.
Pavel

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) 
http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--
To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH v5 0/7] /dev/random - a new approach

[Stephan Mueller]

Hi Herbert, Ted,

The following patch set provides a different approach to /dev/random which
I call Linux Random Number Generator (LRNG) to collect entropy within the Linux
kernel. The main improvements compared to the legacy /dev/random is to provide
sufficient entropy during boot time as well as in virtual environments and when
using SSDs. A secondary design goal is to limit the impact of the entropy
collection on massive parallel systems and also allow the use accelerated
cryptographic primitives. Also, all steps of the entropic data processing are
testable. Finally massive performance improvements are visible at /dev/urandom
and get_random_bytes.

The design and implementation is driven by a set of goals described in [1]
that the LRNG completely implements. Furthermore, [1] includes a
comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
AIS20/31.

Changes v5:
* fix treating LRNG_POOL_SIZE_BITS as entropy value in lrng_get_pool
* use CTR DRBG with AES256 as default due to its superior speed -- on X86_64
  executing within a KVM I get read speeds of up to 850 MB/s now. When using a
  fake NUMA system with 4 nodes on 4 CPUs, I still get up to 430 MB/s read speed
  with four parallel reads. Note, this patch applies to the current
  cryptodev-2.6 tree.
* simplify lrng_get_arch
* use DRBG security strengths as defined in SP800-57 section 5.6.1
* add security strength to /proc/sys/kernel/random/lrng_type
* add ChaCha20 DRNG: in case the kernel crypto API is not compiled, the ChaCha20
  DRNG with the SHA-1 C implementations are used to drive the cryptographic part
  of the LRNG.The ChaCha20 RNG is described in [1]. I analyzed it with a user
  space version of it.
* Editorial changes requested by checkpatch.pl

Changes v4:
* port to 4.7-rc1
* Use classical twisted LFSR approach to collect entropic data as requested by
  George Spelvin. The LFSR is based on a primitive and irreducible polynomial
  whose taps are not too close to the location the current byte is mixed in.
  Primitive polynomials for other entropy pool sizes are offered in the code.
* The reading of the entropy pool is performed with a hash. The hash can be
  specified at compile time. The pre-defined hashes are the same as used for
  the DRBG type (e.g. a SHA256 Hash DRBG implies the use of SHA-256, an AES256
  CTR DRBG implies the use of CMAC-AES).
* Addition of the example defines for a CTR DRBG with AES128 which can be
  enabled during compile time.
* Entropy estimate: one bit of entropy per interrupt. In case a system does
  not have a high-resolution timer, apply 1/10th bit of entropy per interrupt.
  The interrupt estimates can be changed arbitrarily at compile time.
* Use kmalloc_node for the per-NUMA node secondary DRBGs.
* Add boot time entropy tests discussed in section 3.4.3 [1].
* Align all buffers that are processed by the kernel crypto API to an 8 byte
  boundary. This boundary covers all currently existing cipher implementations.

Changes v3:
* Convert debug printk to pr_debug as suggested by Joe Perches
* Add missing \n as suggested by Joe Perches
* Do not mix in struck IRQ measurements as requested by Pavel Machek
* Add handling logic for systems without high-res timer as suggested by Pavel
  Machek -- it uses ideas from the add_interrupt_randomness of the legacy
  /dev/random implementation
* add per NUMA node secondary DRBGs as suggested by Andi Kleen -- the
  explanation of how the logic works is given in section 2.1.1 of my
  documentation [1], especially how the initial seeding is performed.

Changes v2:
* Removal of the Jitter RNG fast noise source as requested by Ted
* Addition of processing of add_input_randomness as suggested by Ted
* Update documentation and testing in [1] to cover the updates
* Addition of a SystemTap script to test add_input_randomness
* To clarify the question whether sufficient entropy is present during boot
  I added one more test in 3.3.1 [1] which demonstrates the providing of
  sufficient entropy during initialization. In the worst case of no fast noise
  sources, in the worst case of a virtual machine with only very few hardware
  devices, the testing shows that the secondary DRBG is fully seeded with 256
  bits of entropy before user space injects the random data obtained
  during shutdown of the previous boot (i.e. the requirement phrased by the
  legacy /dev/random implementation). As the writing of the random data into
  /dev/random by user space will happen before any cryptographic service
  is initialized in user space, this test demonstrates that sufficient
  entropy is already present in the LRNG at the time user space requires it
  for seeding cryptographic daemons. Note, this test result was obtained
  for different architectures, such as x86 64 bit, x86 32 bit, ARM 32 bit and
  MIPS 32 bit.

[1] http://www.chronox.de/lrng/doc/lrng.pdf

[2] http://www.chronox.de/lrng.html

Stephan Mueller (7):
  crypto: DRBG - externalize DRBG functions for LRNG
  random: