From: eric@remailer.net (Eric Hughes)
Date: Wed, 28 Dec 94 08:20:02 PST
To: cypherpunks@toad.com
Subject: Re: Why I have a 512 bit PGP key
In-Reply-To: <35603.pfarrell@netcom.com>
Message-ID: <199412281619.IAA02917@largo.remailer.net>
MIME-Version: 1.0
Content-Type: text/plain


   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