drivers/char/random.c: variable type mismatch

drivers/char/random.c: variable type mismatch

[Stephan Mueller]

Hi,

the function add_timer_randomness currently defines:

        struct {
...
                unsigned cycles;
...
        } sample;

Cycles used to be of type cycles_t. The inline get_cycles that fills
cycles is still of type cycles_t.

Unsigned is 32 bit whereas get_cycles is 64 bit. This means that only
the lower 32 bits of get_cycles is used.

However, due to the fact that jiffies provides very few entropy, the
event value provides (almost) none, the majority of entropy comes from
the processor cycles. Assuming that the processor cycles increase once
per nanosecond, after 2**32 cycles (about 4 seconds), the counter wraps.

This now means that on a 32 bit system, the maximum theoretical entropy
that can be added by one event is always 32 bit. But it used to be
higher due to the 64 bit type.

Now granted, the entropy estimator only assigns 11 bits of heuristic
entropy per event as a maximum.

But why weaken the RNG? Unless there is a technical problem, I would
suggest changing the variable type of cycles into unsigned long, or
better back to cycles_t.

Ciao
Stephan

Re: drivers/char/random.c: variable type mismatch

[Theodore Ts'o]

On Thu, Nov 08, 2012 at 01:32:38AM +0100, Stephan Mueller wrote:
> 
> However, due to the fact that jiffies provides very few entropy, the
> event value provides (almost) none, the majority of entropy comes from
> the processor cycles. Assuming that the processor cycles increase once
> per nanosecond, after 2**32 cycles (about 4 seconds), the counter wraps.

Sure, we can make this change, but it doesn't make as much difference
as you think.  The high 32 bits gets incremented about ounce every 4
seconds, while jiffies gets incremented once every 1/HZ seconds.  But
the point is they are pretty well correlated (i.e., if you know the
jiffies values A' and A'', and I know the high 32 bits of the cycles
B', and you can determine the likely value of B'' to a very high
degree of accuracy.  Values which are correlated don't actually
entropy.

							- Ted

Re: drivers/char/random.c: variable type mismatch

[Stephan Mueller]

On 08.11.2012 12:47:08, +0100, Theodore Ts'o <tytso@mit.edu> wrote:

Hi Theodore,

> On Thu, Nov 08, 2012 at 01:32:38AM +0100, Stephan Mueller wrote:
>>
>> However, due to the fact that jiffies provides very few entropy, the
>> event value provides (almost) none, the majority of entropy comes from
>> the processor cycles. Assuming that the processor cycles increase once
>> per nanosecond, after 2**32 cycles (about 4 seconds), the counter wraps.
> 
> Sure, we can make this change, but it doesn't make as much difference
> as you think.  The high 32 bits gets incremented about ounce every 4
> seconds, while jiffies gets incremented once every 1/HZ seconds.  But
> the point is they are pretty well correlated (i.e., if you know the
> jiffies values A' and A'', and I know the high 32 bits of the cycles
> B', and you can determine the likely value of B'' to a very high
> degree of accuracy.  Values which are correlated don't actually
> entropy.
> 

I agree with the argument of correlation.

So, if the reduction of values with a known lack of entropy is of
interest, why not change the jiffies variable type too? There we know
that only the lower 32 bits are really relevant. Therefore, wouldn't be
a structure of

        struct {
                unsigned jiffies;
                unsigned cycles;
                unsigned num;
        } sample;

be more appropriate?

Thanks
Stephan

Re: drivers/char/random.c: variable type mismatch

[H. Peter Anvin]

On 11/14/2012 08:15 AM, Stephan Mueller wrote:
>
> I agree with the argument of correlation.
>
> So, if the reduction of values with a known lack of entropy is of
> interest, why not change the jiffies variable type too? There we know
> that only the lower 32 bits are really relevant. Therefore, wouldn't be
> a structure of
>
>          struct {
>                  unsigned jiffies;
>                  unsigned cycles;
>                  unsigned num;
>          } sample;
>
> be more appropriate?
>

Probably.  It doesn't make much difference, however.

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Re: drivers/char/random.c: variable type mismatch

[Stephan Mueller]

On 14.11.2012 18:52:53, +0100, H. Peter Anvin <hpa@zytor.com> wrote:

Hi Peter,

> On 11/14/2012 08:15 AM, Stephan Mueller wrote:
>>
>> I agree with the argument of correlation.
>>
>> So, if the reduction of values with a known lack of entropy is of
>> interest, why not change the jiffies variable type too? There we know
>> that only the lower 32 bits are really relevant. Therefore, wouldn't be
>> a structure of
>>
>>          struct {
>>                  unsigned jiffies;
>>                  unsigned cycles;
>>                  unsigned num;
>>          } sample;
>>
>> be more appropriate?
>>
> 
> Probably.  It doesn't make much difference, however.

Well, I guess it does. Because for every byte of the struct, the
input_pool is shuffled. Currently, it is shuffled with bytes known to
have no entropy. With the change, the number of bytes mixed into the
pool without entropy is reduced.
> 
>     -hpa
>