From: lmccarth@cs.umass.edu (L. McCarthy)
Date: Tue, 1 Aug 95 01:21:38 PDT
To: cypherpunks@toad.com (Cypherpunks Mailing List)
Subject: Re: a hole in PGP
In-Reply-To: <9508010049.AA05263@all.net>
Message-ID: <9508010821.AA20913@cs.umass.edu>
MIME-Version: 1.0
Content-Type: text/plain


[NB: Due to some as-yet-undiagnosed bugs in my .procmailrc, I apparently
sent all my mail received between sometime Saturday and about 17:00 PT Monday
straight into the bit bucket. *sigh*  Archives are a Good Thing. If you
sent me mail during that approximate period, please contact me again. Thanks.]

Dr. Frederick B. Cohen writes:
> Request for Comments: 1750 - Randomness Recommendations for Security
> 
> "...Choosing random quantities to foil a resourceful and motivated
> adversary is surprisingly difficult. ...recommends the use of truly
> random hardware techniques and shows that the existing hardware on many
> systems can be used for this purpose."
> 
> PGP does not use "truly random hardware techniques"

Correct. However, the excerpt of RFC 1750 you quoted above does not claim
that all PRNG techniques are unreasonably insecure, nor does it suggest that
they should never be used.

> "...For the present, the lack of generally available facilities for
> generating such unpredictable numbers is an open wound in the design of
> cryptographic software. ... the only safe strategy so far has been to
> force the local installation to supply a suitable routine to generate
> random numbers. To say the least, this is an awkward, error-prone and
> unpalatable solution." - 1994 - after PGP was implemented.

I agree with the RFC's authors that mandating provision of platform-
dependent routines is an awkward and unappealing strategy. Note, however,
that they characterize it as "the only safe strategy". They say that the
_strategy_ is error-prone; they do not say that all locally-supplied
routines are unreasonably insecure, and should not be used.   

> and then: "This informational document suggests techniques for producing
> random quantities that will be resistant to such attack. It recommends
> that future systems include hardware random number generation or provide
> access to existing hardware that can be used for this purpose."

This is just a reiteration of the first section you quoted.

> So I guess the RFC supports my contention and not [Derek Atkins'].
[...]
[re: PGP's key generation methods]
> But the RFC acknowledges that these methods are highly suspect and should
> not be trusted.

Where ?  Give a citation, please. It doesn't say anything of the sort in
the part you quoted previously. Furthermore, you inexplicably omitted all
mentions of keystroke-timing PRNG techniques in RFC 1750. Here are some
excerpts that strike me as particularly germane to the quality of the
randomness in PGP:

------------------------------------------------------------------------
4.2 Timing and Content of External Events

   It is possible to measure the timing and content of mouse movement,
   key strokes, and similar user events.  This is a reasonable source of
   unguessable data with some qualifications. On some machines, inputs
   such as key strokes are buffered.  Even though the user's inter-
   keystroke timing may have sufficient variation and unpredictability,
   there might not be an easy way to access that variation.  Another
   problem is that no standard method exists to sample timing details.
   This makes it hard to build standard software intended for
   distribution to a large range of machines based on this technique.

   The amount of mouse movement or the keys actually hit are usually
   easier to access than timings but may yield less unpredictability as
   the user may provide highly repetitive input.
[...]
6.2 Non-Hardware Sources of Randomness

   The best source of input for mixing would be a hardware randomness
   such as disk drive timing affected by air turbulence, audio input
   with thermal noise, or radioactive decay.  However, if that is not
   available there are other possibilities.  These include system
   clocks, system or input/output buffers, user/system/hardware/network
   serial numbers and/or addresses and timing, and user input.
   Unfortunately, any of these sources can produce limited or
   predicatable values under some circumstances.
[...]
   The use of multiple random inputs with a strong mixing function is
   recommended and can overcome weakness in any particular input.  For
   example, the timing and content of requested "random" user keystrokes
   can yield hundreds of random bits but conservative assumptions need
   to be made.  For example, assuming a few bits of randomness if the
   inter-keystroke interval is unique in the sequence up to that point
   and a similar assumption if the key hit is unique but assuming that
   no bits of randomness are present in the initial key value or if the
   timing or key value duplicate previous values.  The results of mixing
   these timings and characters typed could be further combined with
   clock values and other inputs.

   This strategy may make practical portable code to produce good random
   numbers for security even if some of the inputs are very weak on some
   of the target systems.  However, it may still fail against a high
   grade attack on small single user systems, especially if the
   adversary has ever been able to observe the generation process in the
   past.  A hardware based random source is still preferable.
-------------------------------------------------------------------------

I find it difficult to reconcile your claim that "the RFC acknowledges
that these methods are highly suspect and should not be trusted" with the
RFC's assertions that:

	"the timing and content of [...] key strokes [...] is a reasonable
	 source of unguessable data"

	"the timing and content of requested `random' user keystrokes can
	 yield hundreds of random bits"

	"this strategy may make practical portable code to produce good
	 random numbers for security"

etc. 

Having said that, allow me to state my position on some of the other
issues you've raised. I do not _know_ nor can I _prove_ that PGP has
no cryptographic backdoors. I happen to _believe_ that it does not --
among other things, I have met Derek Atkins and Jeff Schiller, and I
trust them in this regard. I don't consider that any reason for you to
believe that it's backdoor-free. In fact, I'm not interested in trying to
persuade you or anyone else that it is backdoor-free. By the same token,
I don't see any reason for anyone here to heed your demands that they
justify _their beliefs_ to _your satisfaction_. 

I remain rather baffled as to your motives in this mini-campaign. You said
that no-one can prove PGP has no backdoors, and many here essentially said
"what else is new ?". In the white paper about your small "secure" HTTP daemon,
thttpd, (found at http://all.net/ManAl/white/whitepaper.html, to save you the
trouble of more self-promotion ;), it says:

> Proof of program correctness to verify even simple security
> properties, for example, grows almost exponentially with the number of 
> program statements. Verifying a 100 line limited-language program for the
> simple security properties associated with the Bell-LaPadula model of
> security takes about 24 hours of CPU time on a Cray supercomputer. The 
> source code for the NCSA W3 server in widespread use today is about 6600
> lines long, so there is no computer around today that is likely to be able
> to verify its security (or more likely demonstrate its insecurity).

If we adopt this standard, it seems hopeless to "verify" the PGP source, as
others have noted here. [BTW, I read your detailed code walkthrough for
thttp with interest, and commend your work on that. I'm planning some
sort of similar review for a larger piece of code, and it's encouraging
to see other people pulling it off.]

Nobody has suggested a serious, better-understood alternative to PGP as it
is used today (except maybe 2.6.2ui (?), the current int'l. version, for
merely MIT-allergic people :)

So, in summary, we effectively can't know for sure that PGP is secure, but as
a practical matter we have no choice but to accept it, albeit with varying
degrees of caution. This is hardly novel. Did you have a point I missed
somewhere ?  Your good stuff tends to get lost in your rhetoric,
recriminations, and advertising....

[On a largely unrelated note, why does http://all.net/admin/usepolicy.html
contain the following warning ?  Specifically, why the age limit ?

	"This service is ONLY for use by legally competent adults human [sic]
	 individuals of age 18 or older. If you do not meet these criteria, 
	 you should immediately cease and desist your use of this service."]

-Futplex <futplex@pseudonym.com>

"...because of Dr. Cohen's frequent, blatant, and intentional disregard for
 the guidelines that this list operates under, and because of his apparent
 disregard for the frequently expressed opinions of many of the members of
 this list that they don't appreciate his antics, I've configured Majordomo 
 to divert all messages he posts to Firewalls to the list owner for review 
 and approval before posting..." -Brent Chapman, July 24, 1995