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

From: Ingo Molnar
Date: Tue May 24 2011 - 00:06:45 EST



* Valdis.Kletnieks@xxxxxx <Valdis.Kletnieks@xxxxxx> wrote:

> On Mon, 23 May 2011 12:49:02 +0200, Ingo Molnar said:
> > 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();
>
> I'm having trouble convincing myself that RTC and cycles are truly independent
> variables.... ;)

Generally the RTC stores absolute time in seconds (it stores the date), while
cycles start new when the CPU is reset.

So they are independent.

The question i think you are asking is whether the fact that we can observe
current values of them after bootup can be used to figure out their value:

> Consider the case of a fixed-frequency CPU - if you know the time since boot,
> and the current RTC, and the current cycle count, you can work backwards to
> find the RTC and cycle count at boot. [...]

Yes, you are correct, if you are local then the guessing the RTC to the second
is probably possible.

Guessing the cycle counter's value will be hard: see the natural noise it has
at a fixed instruction after bootup in the same-bzImage test i performed - with
no IRQs having executed at all yet ...

The RTC is still reasonably noisy to external attackers though.

> [...] I'm not sure that a variable clockspeed helps all that much - an
> attacker can perhaps find a way to force the highest/ lowest CPU speed - or
> the system may even helpfully do it for the attacker - I've seen plenty of
> misconfigured laptops that force lowest supported CPU clockspeed on battery
> rather than race-to-idle.

The tests i performed were on a fixed frequency system - the cycle counter was
still largely random during early bootup.

Others should try it too - i've attached a simple patch. Maybe my system has
more bootup noise than others.

> Having said that, the 13 bootup rdtsc values you list *seem* to have on the
> order of 24-28 bits of entropy, and only the lowest-order bit seems to be
> non-random (the low-order byte of the 13 values are 28, b6, 44, 54, dc, 78,
> 2c, 38, 02, 58, 76, 16, and be). So rdtsc appears to be good enough for what
> we want here...

Yeah. And for cases that the rdtsc might be predictable for some weird reason
(say it would be 0 on an old system with no RDTSC), the RTC would give some
minimal fallback seed to make the canary at least not remotely guessable.

Thanks,

Ingo

---
init/main.c | 6 ++++++
1 file changed, 6 insertions(+)

Index: linux/init/main.c
===================================================================
--- linux.orig/init/main.c
+++ linux/init/main.c
@@ -472,6 +472,12 @@ asmlinkage void __init start_kernel(void
*/
boot_init_stack_canary();

+ {
+ u64 cycles = get_cycles();
+
+ printk("RDTSC: %Ld / %08Lx\n", cycles, cycles);
+ }
+
cgroup_init_early();

local_irq_disable();
--
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/