full-disclosure - Most common keystroke loggers?

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <51E88E13CDA16B43AAD6FDA7393C4A410126680F@na1fcm51.dearborn.ford.com>
Date: Mon Dec  5 20:32:40 2005
From: rrenshaw at ford.com (Renshaw, Rick (C.))
Subject: Most common keystroke loggers?

-----Original Message-----
From: full-disclosure-bounces@...ts.grok.org.uk
[mailto:full-disclosure-bounces@...ts.grok.org.uk] On Behalf Of
foofus@...fus.net
Sent: Friday, December 02, 2005 6:39 PM
To: full-disclosure@...ts.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.