RE: Most common keystroke loggers?

["Renshaw, Rick (C.)" <rrenshaw () ford com>]

-----Original Message-----
From: full-disclosure-bounces () lists grok org uk
[mailto:full-disclosure-bounces () lists grok org uk] On Behalf Of
foofus () foofus net
Sent: Friday, December 02, 2005 6:39 PM
To: full-disclosure () lists grok org uk
Subject: Re: [Full-disclosure] Most common keystroke loggers?


On Sat, Dec 03, 2005 at 12:22:17PM +1300, Nick FitzGerald wrote:
> > Ahh, no...
> >
> >    http://en.wikipedia.org/wiki/Halting_problem
> >
> > Basically (and simplifying a lot), the Halting Problem means that you
> > cannot write a computer program to determine if some other program 
> > exhibits "function X", _in finite time_.  

> I don't think this is what the Halting Problem means.  My understanding
is that it means you can't write a program to determine if *any* other
program exhibits "function X", >in finite time.  For a particular
program, however, this may be quite feasible.

You're right, the particular problem of finding if a program exhibits
"function X" is Rice's Theorem, which is related to the Halting problem,
but is properly a subset of the problem.

http://en.wikipedia.org/wiki/Rice%27s_theorem

> > Thus, you cannot write a
> > program to detect all viruses, you cannot write a program to detect
key 
> > loggers, you cannot write a prorgram to detect all spyware, etc, etc.

> How do you know that the problem of detecting all keystroke loggers is 
> equivalent to the Halting Program?  Is there a proof somewhere that
> keystroke loggers do not share some characteristic that makes them
detectable?
>  <-- I am not being sarcastic; this is an earnest question.

Quoted (with minor changes of what the function does) from the Rice's
theorem page referenced above:

Suppose we have an algorithm for examining a program p and determining
infallibly whether p is an implementation of a keystroke logger.  

The claim is that we can convert our algorithm for identifying key
loggers into one which identifies functions that halt.  We will describe
an algorithm with takes inputs a and I and determines whether program a
halts when given input i.

The algorithm is simple, we construct a new program t which (1)
temporarily ignores its input while it tries to execute program a on
input i, and then, if that halts, (2) returns whether a keylogger was
detected.  Clearly, t is a function for finding keyloggers if and only
if step 1 halts.  Since we've assumed that we can infallibly identify
programs for finding keyloggers, we can determine whether t is such a
program, and therefore whether program a halts on input i.  Note that we
needn't actually execute t, we need only decide whether it is a squaring
program, and, by hypothesis, we know how to do this.

> My formal CS background is weak, but I don't think the problem of
programmatically detecting compromised machines of a given OS (not the
general case of "compromised machines >of any sort) has been proven 
> to be undecidable in the strong way that the Halting Problem has.  I
may 
> be wrong, though, which is why I ask.
_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/