Re: Why I have a 512 bit PGP key

eric@remailer.net (Eric Hughes)  writes:

>> Read Ken Thompson's Turing Award lecture for why that isn't
>> sufficient. Its quite amusing.
>
> I'm quite familiar with the work.  [For those who aren't, it's about
> compilers that compile in self-perpetuating bugs from their own source
> code.]
>
> Get the essay that Perry mentioned and start there.  Keep in mind that
> object code can be interpreted in many different ways, only one of
> them typically expected.

I strongly agree with both Perry that it is amusing and with Eric
that everyone should read it.

But I see it as more germane than Eric. It is not about
arbitrary self perpetuating bugs from source. It is
about serious security holes that are self perpetuatated
by the binaries of the complier. The compiler ignores
its own source and generates security hacked binaries,
even when the source looks like it is corrected.

One strongly held belief among lots on this list and in the PGP
advocacy world is that the availability of source
guarentees security. Thompson's lecture throroughly dispells
that hope, crushing the "guarentee" completely.

Drawing from Thompson, a simple MD5 is not sufficient.
Youd have to have multiple compilers, perferably on different
cpu architectures, build the tool from source, and compare the
results. Then, and only then, could you claim that you were
secure.

Of course, this is far too much work to be practical.

And this approach is impracticale without need to invent a conspiracy
between the compiler developers.

Pat

p.s. HappyNewYear!

Pat Farrell      Grad Student                 pfarrell@cs.gmu.edu
Department of Computer Science    George Mason University, Fairfax, VA
Public key availble via finger          #include <standard.disclaimer>

From: "Pat Farrell" <pfarrell@netcom.com>

   >> Read Ken Thompson's Turing Award lecture for why that isn't
   >> sufficient. Its quite amusing.

   But I see it as more germane than Eric. It is not about
   arbitrary self perpetuating bugs from source. It is
   about serious security holes that are self perpetuatated
   by the binaries of the complier. 

"Bugs" is shorthand for any arbitrary deviation from nominal source
code function.  Come on, do you expect a one sentence summary to be
accurate in all detail?

   Drawing from Thompson, a simple MD5 is not sufficient.

A single, unchanging, global MD5 source would be insufficient.  That's
not what I mentioned, but rather a constantly changing MD5 source.
One could also change the arbitrary constants in the MD5 source for a
"personal MD5".

Here's a summary of these self-perpetuating false compilers.  There is
an intermediate source code with the arbitrary deviant function
expressed.  A true compiler compiles this into the false compiler.
The arbitrary function includes a recognizer and a payload.  The false
compiler recognizes the source code of the true compiler.  At this
recognition, the corresponding payload is compiled in.  The payload
includes all the arbitrary deviant function of the intermediate
source, including the recognizer.  Thus the false compiler will
compile itself from the true source.  [This is a summary.  I believe
Thompson's original work has a full intermediate compiler; this makes
the attack easier to perform, but is not essential.]

Any such attack on the compiler requires a recognizer.  This is the
point of weakness, since recognizing arbitrary function is mighty
difficult.  The strongest form of the problem is unsolvable; it's a
quick corollary from the solution to the halting problem.  Practically
speaking, however, the problem is more tractable, because the ability
to change the source to some arbitrary form is not unconstrained.  

You can, however, make recognizing a source _extremely_ difficult.
Plus, if you're only interested in finding the first integrity
failure, the recognizer has to work on a source which the author of
the recognizer hasn't even seen yet!  Even with public source code of
a source scrambler available to the recognizer author, the scrambler
can use combinatorial explosions to eliminate hooks for recognition.
Reordering of parallelism, for example, or creative use of aliasing --
the number of techniques available is huge.

And that's only for a single algorithm.  Lots of functions exist that
will detect modification.  CRC's are a good example; there are _lots_
of primitive polynomials available for making your very own personal
CRC checker.  Remember, you only really need to detect the first
modification.

Eric

>   Pat Farrell writes:

> 
> But I see it as more germane than Eric. It is not about
> arbitrary self perpetuating bugs from source. It is
> about serious security holes that are self perpetuatated
> by the binaries of the complier. The compiler ignores
> its own source and generates security hacked binaries,
> even when the source looks like it is corrected.


	I hate to remind everyone, but it is possible to actually
inspect the compiled binary output by hand with a debugger and even
trace its execution step by step through the usually small security
sensitive sections of code.  While Thompson's famous hack was clever
indeed, it basically depended on security by obscurity - if someone had
looked at the generated machine code they easily could have spotted the
hook that inserted the magic password.  Granted of course this is a lot
of work, but so is modifying a compiler or perhaps several of them
to selectively insert security hooks. 

	On the other hand Eric's point about execs is more telling
however, if the evil sysadmin controls the kernal it is quite possible
for him to arrange to have the kernal recognize when the security
program code is running and fudge the state of the security code
variables by interupting its execution at a private to the kernal
breakpoint and invoking code that patches the state of the data or stack
areas and then returns to the user code.  Since the user process is
effectively running on a virtual machine it would be very difficult to
create code that would reliably detect such selective violations in the
consistancy of the virtual machine, especially as code to check for such
violations has to run on the same virtual machine and can also be
diddled with by the kernel. 

	In fact if the kernal one is running security code under is
not 100% trustworthy no amount of cleverness at the user level
can prevent it from obtaining any private information or modifying
any private data it wants.  And if the hacker is clever enough this
can be made nearly invisible to any application program and can be
used to do almost anything desired.

	And since the kernal (/vmunix or whatever) files are accessible
to anyone with root and are not integrity checked on bootup, such a hack
could be planted by some j. random hacker who had root momentarily and
activated much later (perhaps via an obscure user level control file
somewhere that specified the gory details of what to recognize and
patch). 


						Dave Emery 
						die@die.com