Re: your mail

-----BEGIN PGP SIGNED MESSAGE-----

On Mon, 31 Jul 1995, Dr. Frederick B. Cohen wrote:
> I wrote:
>> On Fri, 28 Jul 1995, Dr. Frederick B. Cohen wrote:
>> 
>>> How (specifically) do you know that this is true?  Key generation is
>>> very tricky stuf, and very subtle changes can have very profound impacts.
>>> I doubt that Zimmerman's original was truly perfect at this either, but
>>> how do we really know?
>> 
>> Because I've succesfully run the primes that PGP generates through the
>> primality tests in other mathematical packages, most notably Arjen
>> Lenstra's FreeLIP package.  The remaining steps to generating an RSA
>> keypair are very easy to follow, and the result simple to check by
>> verifying that the components PGP comes up with satisfy
>> ed=1 mod(p-1)(q-1).  rsagen.c is pretty easy to follow if anyone wants to 
>> check for themselves.
> 
> But that doesn't guarantee there aren't weak keys at all.  For example,
> primes of the sort 2^N+1 would pass the primality tests and be very
> weak keys.

As I'm sure you know, PGP picks its primes by choosing a random starting 
point and testing each odd number upwards until it gets a probable 
prime.  The random number generator used to seed this search is mixed 
using MD5 which gives a uniform 1/0 distribution.  I'd hazard a guess 
that the chances of a start point having so many contiguous 1's as to be 
close to 2^N is so vanishingly small that it's more likely a 
non-prime would pass the probabalistic tests!

I suppose if I were really paranoid I'd feed in fixed starting points
for the search to MIT PGP and PGP 2.6.2 to make sure that they come out 
with the same keys.


- - Andy

+-------------------------------------------------------------------------+
| Andrew Brown  Internet <asb@nexor.co.uk>  Telephone +44 115 952 0585    |
| PGP (2048/9611055D): 69 AA EF 72 80 7A 63 3A  C0 1F 9F 66 64 02 4C 88   |
+-------------------------------------------------------------------------+


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2i

iQEVAwUBMBzOMCXfPV+WEQVdAQEs3Af/Qr1RSfgKw0lHSdo+3A59ZY/7cmw1voA3
6zrl1uAOxUfXVO36UPrSh5/lGHjGNW25FU4mckZ5qwhD9x8BEI3NemIddAtSrnbH
tNxTD5+dUpYyiab4j9CKE9FTBsuY+TriyafFOMRBvjELYVgh0zhnS6GBb2ZVN3R5
J1B+qItB/kK2rvrPN+9tqXaH6/lleOquZxA4quoVGOKOmdOg/uWA9xme90NqjjzS
ZbTKVSWEuqWvbaIvm3KexgH1/t9jIU7EcRbfoRWiFDQrW/ecvInW61J6kEGfVqPK
RmjsoyDsYZJ11AqPaZLgVDLY8lmAN9qzaiUH785tVRQY/A5qQzLrkA==
=sDbg
-----END PGP SIGNATURE-----

> As I'm sure you know, PGP picks its primes by choosing a random starting 
> point and testing each odd number upwards until it gets a probable 
> prime.  The random number generator used to seed this search is mixed 
> using MD5 which gives a uniform 1/0 distribution.  I'd hazard a guess 
> that the chances of a start point having so many contiguous 1's as to be 
> close to 2^N is so vanishingly small that it's more likely a 
> non-prime would pass the probabalistic tests!

Well, not exactly random starting points.  Starting points generated by
user keystrokes with characteristics that may be analyzed so as to
reduce the key space to a searchable size, starting points that are
determined by a transformation of those keystroke sequences using an
algorithm, starting points that are determined by an algorithm that uses
a deterministic (albeit complex) algorithm which performs input and
output based on timeslices and interrupt mechanisms and queues that may
tend to alter the statistics of arrival times.

> I suppose if I were really paranoid I'd feed in fixed starting points
> for the search to MIT PGP and PGP 2.6.2 to make sure that they come out 
> with the same keys.

The term paranoid is inappropriate in this context.  Paranoia refers to
an irrational fear, while I am expressing a rational concern over a
system that has been taken over by a (partially) government funded
university and which has not been properly verified.  The history of
cryptography (as they say) is (quite literally) littered with the dead
bodies of people killed because somebody else thought a cryptosystem was
good enough when it was not. 

-- 
-> See: Info-Sec Heaven at URL http://all.net
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236

Hey, Doc...

> The term paranoid is inappropriate in this context.  Paranoia refers to
> an irrational fear, while I am expressing a rational concern over a
> system that has been taken over by a (partially) government funded
> university and which has not been properly verified.  The history of
> cryptography (as they say) is (quite literally) littered with the dead
> bodies of people killed because somebody else thought a cryptosystem was
> good enough when it was not. 

If you are concerned that someone put a whole or backdoor in PGP, then
go grab the source and take a look for yourself.  Thats why the code
is available.  If you can't understand it, then you probably have no
real right to complain!  However if you are still paranoid (and yes, I
do believe this is an irrational fear, being the person who maintains
the MIT PGP development sources) then go find someone who can
understand it and ask them.

As a side note, PGP does not go out of its way to choose "good" primes
over other primes.  Take a look at genprime.c and read the comment
near the top of the file.  It explains why.

-derek

This might be a minor thing, but could people posting to the mailing list
please make sure that the Subject line doesn't say "re: your mail".
  it really slows me down to have to check manually what the actual
subject was or if it was directed to ME but put my addres in the cc 
instead of the To.


Thankyou.

Syed Yusuf
http://www.uidaho.edu/~yusuf921

> 
> Hey, Doc...
> 
> > The term paranoid is inappropriate in this context.  Paranoia refers to
> > an irrational fear, while I am expressing a rational concern over a
> > system that has been taken over by a (partially) government funded
> > university and which has not been properly verified.  The history of
> > cryptography (as they say) is (quite literally) littered with the dead
> > bodies of people killed because somebody else thought a cryptosystem was
> > good enough when it was not. 
> 
> If you are concerned that someone put a whole or backdoor in PGP, then
> go grab the source and take a look for yourself.  Thats why the code
> is available.  If you can't understand it, then you probably have no
> real right to complain!  However if you are still paranoid (and yes, I
> do believe this is an irrational fear, being the person who maintains
> the MIT PGP development sources) then go find someone who can
> understand it and ask them.
> 
> As a side note, PGP does not go out of its way to choose "good" primes
> over other primes.  Take a look at genprime.c and read the comment
> near the top of the file.  It explains why.

My assertion regarding weakness of the key generation algorithm was not
related to the response you gave.  As a result, it appears that you are
avoiding the issue.  This looks bad if you are, as you claim, maintaining
a legitimate algorithm.  Perhaps you would be better served by addressing
the specifics of my comments - to wit: What makes you think PGPs method
of getting seeds does not lead to a limited key space that is within the
realm of modern computers to search?

	Your assertion that I could find the backdoor by inspecting the
program is the wrong tactic for secure programs.  If you want people to
believe that a program is secure, you had better come up with good
reasons that it is secure, and not hide behind "if you can't find any
holes, it must be secure".

	Clever back doors are not accomplished by an obvious program
change, but rather by the subtle use of some technique that appears to
do one thing when it actually does something else.  As a good example, a
subtle interation with the rest of the environment could modify the key
generation algorithm after it is loaded.  Unfortunately, PGP is too
large to verify against such back doors, so I ask again:

	Why (specifically) do you think the MIT version of PGP has no
backdoors and is not subject to attacks such as the one outlined in my
previous posting?

-- 
-> See: Info-Sec Heaven at URL http://all.net
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236

> 	Your assertion that I could find the backdoor by inspecting the
> program is the wrong tactic for secure programs.  If you want people to
> believe that a program is secure, you had better come up with good
> reasons that it is secure, and not hide behind "if you can't find any
> holes, it must be secure".

This is where you are very wrong.  I am not saying that "if you can't
find any holes it must be secure".  What I am saying is that the
source is available, and thousands of people have looked at the
source, and none of them have found any holes in it.

>  - to wit: What makes you think PGPs method
> of getting seeds does not lead to a limited key space that is within the
> realm of modern computers to search?

How do you propose that a user's keystrokes can be analyzed?  If you
assume that the PC's internal clock speed >> typing speed (which is a
good assumption -- how many keystrokes/second can you type?) then you
have a large amount of randomness that can be gained from timing
keystrokes.  Even a good typist will not have an even typestroke!
Have you read RFC 1750?  If not, I would recommend you read it before
you consider continuing this thread!

> 	Why (specifically) do you think the MIT version of PGP has no
> backdoors and is not subject to attacks such as the one outlined in my
> previous posting?

I think it has no backdoors because Jeff Schiller and I (among others)
have looked closely at the random number generator code (he has taken
a much closer look than I) and believe it to be secure.  I also know
that I did not put any backdoors into the code (but why would you
believe me, I must be paid by the government to say this, right?)

As to why I believe it is not subject to attack, I ask you again to go
read RFC 1750.  PGP follows its recommendations fairly closely.  There
is only one place where PGP fails to follow, and that is that PGP does
expose the bucket of random bits, rather than mixing them before
exporting them.  However I do not believe that this would affect the
generation of PGP Public Keys.

-derek

PS: In what field is your Doctorate?

> > 	Your assertion that I could find the backdoor by inspecting the
> > program is the wrong tactic for secure programs.  If you want people to
> > believe that a program is secure, you had better come up with good
> > reasons that it is secure, and not hide behind "if you can't find any
> > holes, it must be secure".
> 
> This is where you are very wrong.  I am not saying that "if you can't
> find any holes it must be secure".  What I am saying is that the
> source is available, and thousands of people have looked at the
> source, and none of them have found any holes in it.

History shows that your approach fails. Here are some examples:

	Tens of thousands of people had source to the http daemon from
	CERN, and yet none of them noticed a hole that was detected as
	it was being exploited only a few months ago. 

	Tens of thousands of people have access to sendmail and yet
	new holes are found by attackers several times per year on
	average.

	Tens of thousands of people have access to the sources of
	various versions of hundreds of software packages, yet there
	are holes found every day.

> >  - to wit: What makes you think PGPs method
> > of getting seeds does not lead to a limited key space that is within the
> > realm of modern computers to search?
> 
> How do you propose that a user's keystrokes can be analyzed?  If you
> assume that the PC's internal clock speed >> typing speed (which is a
> good assumption -- how many keystrokes/second can you type?) then you
> have a large amount of randomness that can be gained from timing
> keystrokes.  Even a good typist will not have an even typestroke!
> Have you read RFC 1750?  If not, I would recommend you read it before
> you consider continuing this thread!

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"

"...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.

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."

"...Systems like Kerberos, PEM, PGP, etc.  are maturing and becoming a
part of the network landscape [PEM].  These systems provide substantial
protection against snooping and spoofing.  However, there is a potential
flaw.  At the heart of all cryptographic systems is the generation of
secret, unguessable (i.e., random) numbers. "

(Internet RFCs are searchable at http://all.net)

So I guess the RFC supports my contention and not yours.

> > 	Why (specifically) do you think the MIT version of PGP has no
> > backdoors and is not subject to attacks such as the one outlined in my
> > previous posting?
> 
> I think it has no backdoors because Jeff Schiller and I (among others)
> have looked closely at the random number generator code (he has taken
> a much closer look than I) and believe it to be secure.  I also know
> that I did not put any backdoors into the code (but why would you
> believe me, I must be paid by the government to say this, right?)

You might be, but even if you are not, that doesn't mean there are no
back doors.  Your inability to detect a backdoor gives me little
confidence, since this is at least an NP-complete problem and, with all
due respect, today, nobody can prove that PGP is free of backdoors

> As to why I believe it is not subject to attack, I ask you again to go
> read RFC 1750.  PGP follows its recommendations fairly closely.  There
> is only one place where PGP fails to follow, and that is that PGP does
> expose the bucket of random bits, rather than mixing them before
> exporting them.  However I do not believe that this would affect the
> generation of PGP Public Keys.

But the RFC acknowledges that these methods are highly suspect and should
not be trusted.

> PS: In what field is your Doctorate?

Ph.D. Electrical and Computer Engineering, U. of Southern California, 1986,
subject "Computer Viruses".  My complete resume is available through the W3
server (below) under Management Analytics.

-- 
-> See: Info-Sec Heaven at URL http://all.net
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236

[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

> > 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.

Nor do I.

> > "...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.

But in practice, PGP is not used this way by the masses.  They use standard
distributions withou alteration.

...
> > 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:

That is my interpretation, however, reasonable people may differ...

> ------------------------------------------------------------------------
> 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.
> [...]

Sounds like this is not very random - I agree that "the user may provide
highly repetitive input".  Just because one type of input is more
repetitive, doesn't make the other truely random.

...
> 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"

You left out "with some qualifications".  This is the part where I have concern.

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

You missed the "but conservative assumptions need to be made" part.  Hundreds
of random bits are possible, but how many actual bits of content are contained in
PGP input.

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

You missed the "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." part and your reliance on the term
"may" as "does" is overly optimistic.

> 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_. 

Not demands - questions.  Why is it that you are unwilling to take
questions as questions and instead translate them into demands? You
could have answered my questions without all the other side comments. 
Why didn't you? I interpret this as being defensive, which means to me
that you are not as sure as you outwardly indicate and that there may be
some lingering issues.  So I ask more questions.  You respond with more
posturing and fewer answers, so I become even more concerned.

It's probably my fault for not asking them in the way you are used to
hearing them, or maybe we are all over-sensitive about our work.

> 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).

Which is why we need very small programs (which PGP is not) that do the
security-critical functions.  We can then analyze these programs and
determine many important properties with regard to their security, which
we cannot do with PGP.

> 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.]

Thank you, but I think it may be too hard to do for a much larger piece
of code.  There is another gentleman who is now working on formally (and
automatically) verifying these properties.  Perhaps his results will be of
value in your problem and similar problems for other programs.

...

> [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."]

I think that some of the popular literature sections may be considered
pornography (Fanny Hill, the Kama Sutra, etc.) and in order to comply
with the applicable laws, I thought it would be prudent to warn off our
fragile youth.

> "...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

And if enough of those on this list feel that this discussion and my postings
are too commercial or too abusive to take, I am certain that Brent will send
you a free copy of his Fred filter.

-- 
-> See: Info-Sec Heaven at URL http://all.net
Management Analytics - 216-686-0090 - PO Box 1480, Hudson, OH 44236

Dr. Frederick B. Cohen writes:
> It's probably my fault for not asking them in the way you are used to
> hearing them, or maybe we are all over-sensitive about our work.

Since I've had no involvement in the writing of PGP and RFC 1750, I don't 
think I'm being sensitive about my work :]

[...]
> And if enough of those on this list feel that this discussion and my postings
> are too commercial or too abusive to take, I am certain that Brent will send
> you a free copy of his Fred filter.

Nah, we're not into third-party censorship here. As for myself, I intend to
keep reading what you write here. Your manner is not a legitimate reason to 
ignore the value of (some of) your words. 

-Futplex <futplex@pseudonym.com>

Agreed.  If PGP has a hole it in it's not in the sources, nor in the 
executables.  Any hole would be a breaking of the RSA or IDEA cyphers by 
the TLA's who wouldn't talk about it, or the availablity of enough super 
fast hardware to brute force it.

It wouldn't be that PGP, it's sources, or algorithms have holes.  It 
would be that there is a way to factor RSA that as of yet we don't know 
about.  And hell, that's as likely as meeting Elvis at your local 7-11. ;-)


=================================================================93=======
 + ^ + |  Ray Arachelian | Amerika: The land of the Freeh. | \-_    _-/  |
  \|/  |sunder@escape.com| Where day by day, yet another   |  \  --  /   |
<--+-->|                 | Constitutional right vanishes.  |6 _\-  -/_  6|
  /|\  |    Just Say     |                                 |----\  /---- | 
 + v + | "No" to the NSA!| Jail the censor, not the author!|     \/      |
=======/---------------------------------------------------------VI------/
      /  I watched and weeped as the Exon bill passed, knowing that yet /
     / another freedom vanished before my eyes.  How soon before we see/
    /a full scale dictatorship in the name of decency? While the rest /
   /of_the_world_fights_FOR_freedom,_our_gov'ment_fights_our_freedom_/

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "warlord" == Derek Atkins <warlord@mit.edu> writes:

 warlord> This is where you are very wrong.  I am not saying that "if
 warlord> you can't find any holes it must be secure".  What I am
 warlord> saying is that the source is available, and thousands of
 warlord> people have looked at the source, and none of them have
 warlord> found any holes in it.

While I largely disagree with Dr. Cohen's conclusions, I do think we
should extinguish the "Examine the source!" mantra.

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.  I wonder whether Rivest could construct a
hash function which only he could invert...  :-)

When an algorithm is essentially defined by a tangle of C code, like
the PGP random number generator, the "Examine the source!" mantra
becomes even more hollow.  Ironically, the fact that it was designed
by competent cryptographers potentially makes it even more dangerous.

Of course, there is no practical alternative at this time.  Maybe
someday your entire operating environment will be formally proven
correct, and the cryptographic algorithms will be provably as hard as
factoring, and factoring will be proven hard, and the system will ask
you to flip a coin and type "0" or "1" every time it needs a random
bit.  But until that day, you will have to decide whom to trust.

Personally, I trust the authors of PGP.  So do most of the people on
this list, I suspect.  Maybe Dr. Cohen can convince me that my trust
is misplaced; but to do so, he will need something better than NSA
conspiracy theories.

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.3beta, an Emacs/PGP interface

iQCVAwUBMB5IU3r7ES8bepftAQGRvQP+Masb3fWdJg9UA6YYufuVZ5EZU8wfhuar
IXpjID+iSyVV1UnMN5CiWj8912H3buUslygVnbCwv/vnuKdtz5h9k2+lpCUX4r11
2QVAWg4ij1LiA1DU7N2l2K4oqb5mszVZrQcW6aJJzqiuPcvij5Vl7cN3hDTfdttJ
x9emd0xEjPA=
=nxBy
-----END PGP SIGNATURE-----

"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
se.

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.

.pm

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "perry" == "Perry E Metzger" <perry@panix.com> writes:

 perry> "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.

 perry> This is not correct as you have phrased it.

On the contrary, it is *precisely* correct as I have phrased it.

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

Check my phrasing again.  Note the use of "in principle".

Whether the principle applies in practice is certainly a matter for
debate.  I would point out that 1) PGP is hardly well written code,
and 2) many current cryptographic algorithms make ideal places for
concealing all sorts of things.

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

Sorry, I can't resist.  From "md5.c" in the PGP distribution:

/*
 * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
 * initialization constants.
 */
void MD5Init(struct MD5Context *ctx)
{
...


(Note: Of course I don't think that MD5 has a back door, but that has
more to do with my trust of Rivest than the fact the algorithm is
public.)

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

By "cleanly written code", I presume you mean code which is either
formally proven to be a correct implementation, or code which is so
transparent that it is "obviously" a correct implementation.  PGP's
random number generator is neither.

Moreover, as I precisely mentioned, the algorithms themselves can
conceal back doors.  This has plenty to do with public key
cryptography.  A reduction proof from a known hard problem would make
this virtually impossible, but there is no such proof for PGP's random
number generator.  (Nor for any other algorithm used by PGP, although
I admit RSA comes close.)


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.3beta, an Emacs/PGP interface

iQCVAwUBMB5XVXr7ES8bepftAQGkJgP9Gopf96k2vu5ORjqQCOk0hPNrdwtmcR71
THm+nPgWk2m1CHGXHF3FhgZ7FNZS8zubv1fzunKA+QDFcqKghHCFfhD+pof4bUF6
fYVq89Oc3P7/pIvS3pCR8BBN/8BTLwxlP+OsPbF4YNANXqsbiqyjvezruojKaOI8
QiVInZxdeoI=
=BfP6
-----END PGP SIGNATURE-----

> 
> -----BEGIN PGP SIGNED MESSAGE-----
> 
> >>>>> "warlord" == Derek Atkins <warlord@mit.edu> writes:
> 
>  warlord> This is where you are very wrong.  I am not saying that "if
>  warlord> you can't find any holes it must be secure".  What I am
>  warlord> saying is that the source is available, and thousands of
>  warlord> people have looked at the source, and none of them have
>  warlord> found any holes in it.
> 
> While I largely disagree with Dr. Cohen's conclusions, I do think we
> should extinguish the "Examine the source!" mantra.
> 
> 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.  I wonder whether Rivest could construct a
> hash function which only he could invert...  :-)

  That's a neat metaphor, but it doesn't always apply. It shouldn't
apply to algorithms which are primitive recursive. Elementary
algorithms like multiprecision add, sub, multiply, divide, modmult,
and modexp (the basis of public key encryption) are all provably
correct and all terminate. (the basis is polynomial operators over a
ring) It is possible to verify the implementation (assuming the
correctness of the compiler). Now there could be a "factoring"
trapdoor in RSA, but that's a trapdoor not in the implementation of
PGP, but in the algorithm itself. RSA-in-4-lines-perl is probably
provably correct.  To guard against trapdoors in PGP, you should
verify the correctness of the PRNG, Key Generator, and that no private
key bits or session key bits are leaked. I would suspect this could be
difficult, but approximations could be determined to within a high
degree of confidence.

-Ray

-----BEGIN PGP SIGNED MESSAGE-----

>>>>> "rjc" == Ray Cromwell <rjc@clark.net> writes:

 rjc>   That's a neat metaphor, but it doesn't always apply. It
 rjc> shouldn't apply to algorithms which are primitive
 rjc> recursive. Elementary algorithms like multiprecision add, sub,
 rjc> multiply, divide, modmult, and modexp (the basis of public key
 rjc> encryption) are all provably correct and all terminate. (the
 rjc> basis is polynomial operators over a ring) It is possible to
 rjc> verify the implementation (assuming the correctness of the
 rjc> compiler). Now there could be a "factoring" trapdoor in RSA, but
 rjc> that's a trapdoor not in the implementation of PGP, but in the
 rjc> algorithm itself. RSA-in-4-lines-perl is probably provably
 rjc> correct.  To guard against trapdoors in PGP, you should verify
 rjc> the correctness of the PRNG, Key Generator, and that no private
 rjc> key bits or session key bits are leaked. I would suspect this
 rjc> could be difficult, but approximations could be determined to
 rjc> within a high degree of confidence.

As I suggested, you could 1) only use algorithms which are provably as
hard to break as known hard problems, and 2) only use implementations
which are proven correct.  PGP does neither.  In addition, the
complexity of the source makes #2 difficult even to approximate.

Now, we could certainly take care of #1 fairly easily by using a
different set of algorithms.  And as you suggest, #2 can be
approximated if the code is written cleanly.  But this would be a big
project, and it would not be PGP.

I personally would find such a project pointless, since I trust PGP
enough for my needs.  The availability of the source is a necessary
prerequisite for that trust, but it is by no means convincing.

-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
Comment: Processed by Mailcrypt 3.3beta, an Emacs/PGP interface

iQCVAwUBMB5cZHr7ES8bepftAQFtBwQA2qDiS0BpvkFBj9HRRd/83OxjSczna/jn
wj5eb+2KMSbj87SuD3ByUFcXQmWIqO6bNq5CkzoxmGvrk/y1futjAF/BeGcVlM1+
T4ClfmrIFbqwd/j7i1Qaw7ExN6rNjgQUdRYmo8Nlr1JVaAymCtx2f4GqKRuwP3oy
Tc/W8GXThM0=
=qdFB
-----END PGP SIGNATURE-----