Re: [BUG] perf: bogus correlation of kernel symbols

[Ingo Molnar]

* Dan Rosenberg <drosenberg@xxxxxxxxxxxxx> wrote:

> On Sun, 2011-05-22 at 16:49 -0700, Tony Luck wrote:
> > 
> > 
> > On Sun, May 22, 2011 at 11:45 AM, Dan Rosenberg
> > <drosenberg@xxxxxxxxxxxxx> wrote:
> >         1. Is it ok to assume the existence of rdtsc?  If not, what
> >         are other
> >         ways of gathering entropy early in the boot process?  If this
> >         is the
> >         approach that's going to be taken, system uptime potentially
> >         becomes
> >         useful for attackers.  Any thoughts on how to address this?
> >         
> > There is a cpuid bit to tell you whether the processor supports rdtsc.
> > 
> 
> This might be worth checking, but it also might just be easier to clearly 
> document in the Kconfig that the feature requires rdtsc.  I'll play with it a 
> bit.

All modern x86 boxes have an RDTSC so this not really a practical concern - 
other than not crashing old boxes that do not have an RDTSC.

In theory there's other sources of entropy: we could read out the RTC CMOS as 
well. We could also read the current CPU frequency and fan speeds - those have 
components of thermal noise as well. Obviously it's hard to read this out early 
during bootup, when system devices are not enumerated yet.

What would be very useful is to print out the bootup RDTSC value for several 
bootups. I've done this on a testbox here, with real full reboots inbetween, 
putting the RDTSC printout very close to where you'd sample it for kernel image 
randomization:

[    0.000000] RDTSC: 26615467048
[    0.000000] RDTSC: 26527108278
[    0.000000] RDTSC: 26464738628
[    0.000000] RDTSC: 26554778708
[    0.000000] RDTSC: 26441165788
[    0.000000] RDTSC: 26555252088
[    0.000000] RDTSC: 26431986988
[    0.000000] RDTSC: 26521303608
[    0.000000] RDTSC: 26497878018
[    0.000000] RDTSC: 26455546968
[    0.000000] RDTSC: 26467673718
[    0.000000] RDTSC: 26460404758
[    0.000000] RDTSC: 26496175038

Even visually there's *plenty* of real randomness in the bootup value of the 
cycle counter (look at the above pattern of numbers and squint), even during 
early bootup, on real hardware.

While the last few bits are non-random there's at least 10-20 bits of 
randomness on this (very simple) testbox - possibly more.

I've done a few tests on virtual hardware as well, KVM based:

[    0.000000] RDTSC: 208122033
[    0.000000] RDTSC: 200455104
[    0.000000] RDTSC: 207258945

As expected there's even more randmness on virtual hardware than on real 
hardware: virtual hardware will boot in a complex host CPU state and is so 
exposed to the non-determinisic CPU cache state.

So the cycle counter is plenty good for this.

[ I'd only worry about the cycle counter if a hardware platform is so 
  minimalistic that it boots up very quickly without exposing itself to natural 
  sources of entropy. Eventually we'll get such systems, but right now the 
  cycle counter is good enough. ]

Btw, we already rely on the cycle counter for early bootup randomness: 
boot_init_stack_canary() relies on it.

> > Sometime soon you'll have "rdrand" available (check a different cpuid bit).
> 
> This of course is highly preferable, but I'd rather implement a solution 
> that's widely supported in hardware today.  Perhaps further down the road it 
> could be switched.

Well, since entropy does not get reduced on addition of independent variables 
the right sequence is (pseudocode):

	rnd  = entropy_cycles();
	rnd += entropy_rdrand();
	rnd += entropy_RTC();
	rnd += entropy_system();

That way systems that do not have RDRAND will still have the other ones as 
fallback.

Of course in your prototype you can use RDTSC as a first step, just make it 
easy to add other sources.

Thanks,

	Ingo
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/