full-disclosure - Re: Gödel and kernel backdoors

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 for Android: free password hash cracker in your pocket

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

Message-ID: <79454.1284986527@localhost>
Date: Mon, 20 Sep 2010 08:42:07 -0400
From: Valdis.Kletnieks@...edu
To: Hurgel Bumpf <l0rd_lunatic@...oo.com>
Cc: full-disclosure@...ts.grok.org.uk
Subject: Re: Gödel and kernel backdoors

On Mon, 20 Sep 2010 01:03:21 PDT, Hurgel Bumpf said:
> The solution could be a virtualized operating system, which has a control 
> layer between the operating system and the hardware abstraction layer. Changes
> to data could be non-persistent in the first step, and only written to
> the hdd after a heuristic check of the changes and a interaction with the user.

Actually, that's a very useful tool that you can even deploy today: Just use
the 'checkpoint' feature of a VMWare or similar tool, and keep around some
checkpoints that you're reasonably sure contain no malware.

Unfortunately, it suffers from the same exact Godel issue as any other system -
you simply *cannot* make that "heuristic check" 100% guaranteed correct and
accurate. (In fact, by definition a heuristic check *can't* be 100% accurate -
if a heuristic was perfect, it would be called an algorithm).

The point that everybody seems to be missing is this:

Godel, Turing, and all proved that you can't make that check 100% correct. They
said *nothing* about the possibility of building a checker that's 99.99998%
accurate (and in fact, that's totally within the realm of mathematical
possibility).  There are *real* problems that Godel says *nothing* about but
the real world does:

1) Making that mathematically possible 99.99998% accurate checker may require
so much simulation and state tracking that launch times for programs will be
measured in years or decades - as a practical matter, users may not want more
than 2 or 3 nines.  Heck, they whinge about the overhead of *current*
anti-malware.

2) With the plethora of complicated objects on the average computer system,
raising the "is javascript/vi modelines/whatever  data or executable code"
issues, we don't even have a clue how to do better than 95% or so.  So as an
industry, let's not bother worring about that Godel issue until we know how to
get to 99% and still have users happy with the overhead involved.

Content of type "application/pgp-signature" skipped

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