Re: [Full-disclosure] Linux big bang theory....

On Sat, 26 May 2007 11:42:46 +0200, Pavel Kankovsky said:
On Mon, 21 May 2007, Vincent Archer wrote:

I don't have (and I doubt anybody around here can) the proof to make
this a theorem, but it is a good postulate:

- It is impossible to prove the integrity of a computing system from
within the same system.

From a theoretical POV, it might be possible do it with a program
requiring all memory of the tested system (*all* memory, including memory
occupied by existing data -- whether it is possible to reconstruct them
after the fact is a different question...) to compute a correct result.
Several difficult conditions would have to be satisfied:

I'm not sure that's sufficient - at first glance, it appears that "proving
the integrity" is a close relative of the Turing Halting problem. So you have
to deal with all sorts of Turing/Godel issues. I may be wrong, as I haven't
gotten much caffeine into me yet, but anytime you see the phrase "Prove
introspective result about X within system X", step 0 of the proof needs to
be something of the form "we can avoid Turing/Godel issues because...."

One important aspect that the system isn't just memory, it's the combination
of memory and architecture, which often means microcode. So you also need
to prove the microcode isn't tweaked (and such a tweak could conceivably
include code of the form "if any attempt is made to examine the actual
microcode contents, immediately hide the existence of any backdoors". (quite
plausible, we've seen similar things done to prevent reverse-engineering by
running code inside a debugger).

But hey, if your computational-theory-foo is stronger than mine, feel free
to point out where I'm wrong...

Attachment: pgpdFI74jLtEp.pgp
Description: PGP signature

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/