Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1388074 > unrolled thread

Re: random(4) changes

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: random(4) changes "George Spelvin" <linux@horizon.com> - 2016-04-26 22:50 +0200
    Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-26 23:10 +0200
      Re: random(4) changes "George Spelvin" <linux@horizon.com> - 2016-04-27 02:30 +0200
        Re: random(4) changes "George Spelvin" <linux@horizon.com> - 2016-04-27 20:10 +0200

#1388074 — Re: random(4) changes

Schrieb Stephan Mueller:
> Am Montag, 25. April 2016, 21:59:43 schrieb George Spelvin:
>> Indeed, this is an incredibly popular novice mistake and I don't
>> understand why people keep making it.

> Can you please elaborate on your statement to help me understanding the issue 
> and substantiate your claim here?

Basically, hashing down to 1 bit limits the entropy to 1 bit.

If there happened to be more than 1 bit of entropy in the
original input (and many timestamps *do* have more entropy than
that; the hard part is identifying which), you've thrown it away.

You need to hash eventually, to convert the large amount of weakly-random
input to the desired strongly-random output, but you should do that as
late in the processing as possible, and in as large blocks as possible.

The "novice mistake" is to try to concentrate the entropy (reduce the
number of bits used to store it) too soon.  You want to defer that as much
as possible.

> Please note the mathematical background I outlined in my documentation: What I
> try is to collapse the received data such as a time stamp into one bit by
> XORing each bit with each other. Note, the bits within a time stamp are IID
> (independent and identically distributed -- i.e. when you see one or more bits
> of a given time stamp, you cannot derive the yet unseen bit values). 
> Technically this is identical to a parity calculation.

And I'm still struggling to understand it.  You wrote it up formally, so
I want to stare at it for a few hours (which is a couple of days calendar
time) before passing judgement on it.

For example, my initial reaction is that the IID claim seems ridiculous.

Bit 63 of a rdtsc timestamp is always zero.  It's initialized to zero on
boot and no computer with a TSC has been up for the 50+ years it would
take to flip that bit.

But presumably that's obvious to you, too, so I'm misunderstanding.

I'm trying to catch up on your paper and all the other comments in this
thread at the same time, and my brain is a bit scattered.

I'm trying to resist the urge to respond until I understand everything
that's already been said, but as I mentioned previously, I'm not being
entirely successful.

> - the output of the entropy pool is meant to be fed into a DRBG. Such DRBG 
> (let us take the example of a Hash DRBG) will, well, hash the input data. So, 
> what help does a hash to raw entropy before feeding it to a DRBG which will 
> hash it (again)?

The two-stage hashing is a matter of practical implementation necessity.

Ideally, we'd take all of the raw sampled data and use a strong hash
on it directly.  But that requires an impractical amount of storage.

Just as good would be to losslessly compress the data.  If we could do
*perfect* compression, we'd get pure entropy directly.  But the latter
is impossible and even the former is impractical.

So we hash it to fit it into a fixed-size buffer.  This hash does
not have to be cryptographically strong, just minimize collisions.
(Since a collision is the one and only way to lose entropy.)  This is
explained in the comment at drivers/char/random.c:335.

A second design goal of this first stage hash is speed; we want to
minimize interrupt overhead.  Since it was first designed, cache effects
have gotten stronger and the scattered access to a large pool could be
improved upon, but it's still reasonably fast.


The second stage hash (DRBG or equivalent) then uses a strong cryptographic
algorithm to generate the final output.

> - the entropy pool maintenance does not need to have any backtracking 
> resistance as (1) it is always postprocessed by the cryptographic operation
> of the DRBG, and (2) constantly overwritten by new interrupts coming in

I don't see how (1) is relevant at all; if you can recover the DRBG
seed, you can recover the DRBG output, and (2) might not be fast enough.
For example, suppose someone suspends to disk immediately after generating
a key.

(I'm assuming you instantiate a new DRBG for each open() of /dev/random.
I haven't read your code yet to verify that.)

If the amount of entropy added after the key generation is attackable (say
it's around 32 bits), then the image on disk can reveal the previously
generated key.

You're right that it's not a very critical feature in most use cases,
but it's not very expensive to implement and I think a lot of people
would question its dismissal.  Knowledgeable people, never mind the
howls from the peanut gallery if they hear we're weakening /dev/random.

(I mention that the NIST DRBGs implement anti-backtracking, so presumably
they think it's an important feature.)

> - to hash raw input data is usually performed to whiten it. When you have a 
>   need to whiten it, it contains skews and statistical weaknesses that
>   you try to disguise. My approach is to not disguise anything -- I try
>   to have "nothing up my sleeve".

Only the final hash, which produces the strongly-random output, is for the
explicit purpose of whitening.  That's because strongly-random bits are,
by definition, white.

Earlier steps should not try to whiten.

That's what I don't like about Intel's RDRAND and similar hardware RNGs:
they are whitening too early.

That's also what I don't like about XORing down to 1 bit before adding
to the pool.  Again, whitening too early!


Is that any clearer?

[toc] | [next] | [standalone]

#1388101

Am Dienstag, 26. April 2016, 16:43:30 schrieb George Spelvin:

Hi George,

(I am not covering the initial part as I leave you time to read through the 
paper which should cover those aspects)

> 
> That's what I don't like about Intel's RDRAND and similar hardware RNGs:
> they are whitening too early.
> 
> That's also what I don't like about XORing down to 1 bit before adding
> to the pool.  Again, whitening too early!
> 
> 
> Is that any clearer?

I see what you are saying. And I know that the best way (TM) would be to 
simply concatenate the time stamps. But that is not feasible.

And considering that I only want to have 0.9 bits of entropy, why should I not 
collapse it? The XOR operation does not destroy the existing entropy, it only 
caps it to at most one bit of information theoretical entropy. As I can show 
that the original value has many more bits of entropy, I use that as my safety 
margin.

Hence, I combine the safety margin provided by the XOR folding with a nice and 
easy maintenance of the harvested one bit by simply concatenating them. Again, 
the entire harvesting and collection shall be very easy to understand without 
hiding anything. In addition it is intended to solely use XOR and 
concatenation, i.e. the two only functions whose effect on entropy are known.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1388473

> And considering that I only want to have 0.9 bits of entropy, why
> should I not collapse it? The XOR operation does not destroy the existing
> entropy, it only caps it to at most one bit of information theoretical
> entropy.

No.  Absolutely, demonstrably false.

The XOR operation certainly *does* destroy entropy.
If you have 0.9 bits of entropy to start, you will have less
after the XOR.  It does NOT return min(input, 1) bits.

In rare cases, the XOR won't destroy entropy, but that's statistically
unlikely.


Here's a proof:

If there are only two possible inputs (timings), and those inputs have
opposite parities, then the XOR will cause no collisions and no entropy
is destroyed.

If you have at least three possibilities, hashing down to one bit (by
XOR or any other algorithm) must cause a collision, and that collision
will lose entropy.

Just as an example, let me use a 3-option distribution with roughly 0.5
bit of Shannon entropy: probabilities 90%, 9% and 1%.  Then list all
the possible collisions, and the Shannon and min-entropy in each case:

	%	Shannon		Min
	90/9/1	0.5159		0.1520
	90/10	0.4690	(91%)	0.1520	(100%)
	91/9	0.4365	(85%)	0.1361	(90%)
	99/1	0.0808	(16%)	0.0145	(10%)
	100	0		0

If you reduce the number of cases to 2, you lose Shannon entropy, always.

Min-entropy is preserved 1/4 of the time if you get lucky and none of the
less-likely options collide with the most-likely.

If the 4 possible collision cases are equally likely (which is the
case if the hashing to one bit is a random function), then you expect
to retain half of the input entropy.


If there are more than three possible inputs, the situation gets worse,
and the likelihood of no loss of min-entropy falls.


In a case of particular interest to an RNG, consider the min-entropy when
there are a large number of possible input measurements.  The min-entropy is
simply -log2(p(max)), where p(max) is the probability of the most likely
outcome.  If p(max) > 50%, then the input min-entropy is less than 1 bit.

In this case we can assume that, when collapsing to a single bit, the
less likely cases will be distributed uniformly between colliding and
not colliding with the most likely alternative.

Thus, the probability of the most likely increases from p to
p + (1-p)/2 = (1+p)/2, and the min-entropy correspondingly
decreases from -log2(p) to -log2((1+p)/2).

The ratio of output to input min-entropy varies from 50% near 0 bits to
45.7% at 0.5 bits to 41.5% at 1 bit input.

In this case, which I think is a plausible case for /dev/random
measurements, you're throwing away half the entropy.


Beyond 1 bit of input entropy, the ratio gets worse as the output
asymptotically approaches 1 bit of entropy.  Specifically, in order to
get 0.9 bits of min-entropy in the output (p(max) = 0.5358), you need
3.8 bits (p(max) = 0.07177 = 1/14) in the input!


I'm sorry, but collapsing individual samples to 1 bit is a Bad Design,
full stop.  It's not the algorithm used to do the reduction, it's the
reduction itself.

[toc] | [prev] | [next] | [standalone]

#1389422

Andi Kleen wrote:
> There is also the third problem of horrible scalability of /dev/random
> output on larger systems, for which patches are getting ignored.

I came up with some very pretty code to fix this, which
tried to copy_to_user with a lock held.

After all my attempts to fix that fatal flaw resulted in much uglier
code I set it aside for a while in the hopes that inspiration would
strike.

and it's still sitting unfinished.  :-(

But I want to finish it, honest!  This latest discussion has
made me acutely conscious of it.

The fact that the scope of changes just got bigger doesn't help of
course, but I *have* picked it up again.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web