1995-08-01 - Re: a hole in PGP

Header Data

From: “Perry E. Metzger” <perry@panix.com>
To: patl@lcs.mit.edu
Message Hash: 5898c6553a05675dd3ba5ca842c46089c4ba484d9b451591fff42d24784117ae
Message ID: <199508011542.LAA23817@panix4.panix.com>
Reply To: <199508011530.LAA00429@skyclad.lcs.mit.edu>
UTC Datetime: 1995-08-01 15:42:52 UTC
Raw Date: Tue, 1 Aug 95 08:42:52 PDT

Raw message

From: "Perry E. Metzger" <perry@panix.com>
Date: Tue, 1 Aug 95 08:42:52 PDT
To: patl@lcs.mit.edu
Subject: Re: a hole in PGP
In-Reply-To: <199508011530.LAA00429@skyclad.lcs.mit.edu>
Message-ID: <199508011542.LAA23817@panix4.panix.com>
MIME-Version: 1.0
Content-Type: text/plain

"Patrick J. LoPresti" writes:
> I find it surprising that people so familiar with public key
> cryptography would be reassured by the argument, "Here, this algorithm
> has been examined by thousands and nobody has found a trap door."
> Public key cryptography demonstrates that it is possible, in
> principle, to construct an algorithm with a trap door that nobody else
> is *ever* going to find.

This is not correct as you have phrased it.

Although it is not possible to find a decision proceedure for any
non-trivial property of programs in general (whether it halts, for
example) in practice well written code can be well understood and
cannot conceal very much at all.

In order to use public key cryptography to obfuscate a program as you
suggest, you'd have to include huge tables of large numbers in it. Any
idiot can observe the existance of such mysterious tables.

Trying to conceal anything in cleanly written code is an enormous
challenge, and one that has nothing to do with public key crypto per

Incidently, this doesn't mean that you can't conceal things by
producing subtle flaws in, for example, random number generation code.
However, such flaws are hardly of the form "nobody else is *ever*
going to find" -- anyone being extremely cautious in his analysis will
find such flaws.