full-disclosure-uk May 2007 archive
Main Archive Page > Month Archives  > full-disclosure-uk archives
full-disclosure-uk: Re: [Full-disclosure] Linux big bang theory.

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

From: Pavel Kankovsky <peak_at_nospam>
Date: Sun May 27 2007 - 12:22:25 GMT
To: Valdis.Kletnieks@vt.edu

On Sat, 26 May 2007 Valdis.Kletnieks@vt.edu wrote:

> On Sat, 26 May 2007 11:42:46 +0200, Pavel Kankovsky said:
> > From a theoretical POV, it might be possible do it with a program
> > requiring all memory of the tested system [...] to compute a correct
> > result. Several difficult conditions would have to be satisfied:
> I'm not sure that's sufficient - [...]

If we are going to get a correct result (and those extra conditions are satisfied) then we know that, at some point during the execution of our program, the tested system has to pass through a certain well-defined state and that state determines all its future states like a Cauchy surface in physics (as long as the system stays isolated).

Well, we cannot really tell whether there was anything wrong with the system before it reached the "Cauchy surface-like state" but we know nothing undesired can survive when the system passes through it.

Any malware trying to cheat and hide itself will make the test fail because there will not be enough memory to complete the computation--the C. s.-like state is uncompressible and needs every bit of memory installed on the tested system. The only way to avoid detection is to self-destruct. I admit this kind of proof of integrity bears some similarity to proving the window is broken by throwing a rock through it. :)

> So you have to deal with all sorts of Turing/Godel issues.

Indeed. Kolmogorov complexity is this kind of issue.

(To be absolutely precise, it is not the true K. c. based on a universal Turing machine but a computational K.-like c. based on the system being investigated. This complexity is decidable (in theory) as long as the system is deterministic and its memory finite.)

> 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 [...]

"All memory" involves any aspect of the system mutable by the software. If the microcode is mutable than the memory used to store it is a part of "all memory".

I don't think you'll get any well-defined state other than "an extremely expensive piece of dead silicon" from any real CPU when you fill its microcode PROM with a string of uncompressible data but I said it was a theoretical approach... :)

--Pavel Kankovsky aka Peak [ Boycott Microsoft--http://www.vcnet.com/bms ] "Resistance is futile. Open your source code and prepare for assimilation."

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