1995-08-01 - Re: a hole in PGP? NOT!

Header Data

From: fc@all.net (Dr. Frederick B. Cohen)
To: warlord@ATHENA.MIT.EDU (Derek Atkins)
Message Hash: fd034b146792e900e4e40cb54cd1c9022a5601ffe3ed21a5ca5965c7eb3997ce
Message ID: <9508011148.AA15766@all.net>
Reply To: <199508010658.CAA18603@charon.MIT.EDU>
UTC Datetime: 1995-08-01 11:54:41 UTC
Raw Date: Tue, 1 Aug 95 04:54:41 PDT

Raw message

From: fc@all.net (Dr. Frederick B. Cohen)
Date: Tue, 1 Aug 95 04:54:41 PDT
To: warlord@ATHENA.MIT.EDU (Derek Atkins)
Subject: Re: a hole in PGP?  NOT!
In-Reply-To: <199508010658.CAA18603@charon.MIT.EDU>
Message-ID: <9508011148.AA15766@all.net>
MIME-Version: 1.0
Content-Type: text

Sorry for the long reply.  I hpe this will be taken off-line soon.

> Here are some snipets of things you've said.  First, you say that it
> is a rational concern since PGP was taken over by us:
> > 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. 

This is a true statement.  Tens of thousands of people have dies because
cryptosystems were trusted when they should not have been (hind sight
being 20/20 of course). 

> Then you talk about the MIT version as if it were the original thing:
> > 	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?
> PGP 2.0 was released in September, 1992, from Europe, and many many
> people have been examining it ever since.  I truly belive that there
> are no backdoors.

So you believe that there are no backdoors because it was released from
Europe and people have looked at it since.

> Anyways, to get back to my claims of your hurtful statements:
> > Why (specifically) do you think so? Because you claim it? Because the
> > MIT maintainer claims it? You say MIT is not associated with the NSA,
> > but they have historically been funded by the NSA and other federal
> > agencies for work on information security.  Do you really think that the
> > only information protected by PGP is dirty pictures? Do you somehow
> > think that MIT and the NSA are above that sort of thing? All you have to
> > do is look at history, and it should be clear that this appeal to
> > authority is often used by those trying to cover things up.  If you know
> that, I cannot BELIEVE you would have the Balls to say that the NSA
> has bought me.  Go re-read what you've said.  You have just said that
> the MIT PGP team, through MIT, is bound to be covering something up
> because of historical fact.  

I think that you miss the point.  If you worked for the NSA, you would
probably say this as well.  The point is that, for the purposes of
looking at the security of PGP, we should assume that you have evil
intent, whether you do or not.

I didn't say that the NSA bought you.  I asked " Why (specifically)..."
The question mark at the end is a dead give-away.  It is factually
accurate that government agencies have gotten the cooperation of
academics in the past to carry out subversions in order to further their
goals.  I asked "Do you somehow think that MIT and the NSA are above
that sort of thing?"  You apparently do, but history tell us that it is
imprudent to do this.

So if there has been a failure in communications in this respect, I
appologize for not making it as clear as I might have.  If you feel
personally slighted, I am sorry that you feel this way.  Nevertheless, I
believe that it is prudent to believe that the NSA has "bought you" for
the purpose of assessing the security of PGP and to ask the question
"Why (specifically) do you think so?"

> I have never said "Believe me when I said PGP is secure".  I have
> continually asked for you to check on the security yourself.  But you
> have continually refused to do that, and asked why it is secure!  So,
> you refuse to look for yourself, and you refuse to believe it when you
> are told.

I have not refused to do any such thing.  I have had a copy of PGP for
quite some time, but it is too large and complex for me to verify by
hand, and I know of no automated technique that can do the job in any
reasonable amount of time.  I was probably wrong to assume that this was

>  So, what the hell do you want?  Do you want a line-by-line
> examination of the code????  Sheesh!

I think it would be prudent to do and publish a line-by-line walkthrough
of the source of PGP (although not to the whole list please).  You
should be trying to prove properties such as the non-interference of any
of the rest of the code with the key generation (or other) algorithms. 
This may be done by an information flow analysis similar to what was
done on our secure W3 server.  It would also be prudent to perform
adequate tests of the properties of inputs from people to determine the
true information content of the seeds and to publish these results so
they can be critiqued.  Perhaps it would also be valuable to have the
members of this list contribute ideas about properties they think would
be worth verifying.

> > It cannot be safely assumed that any program is clean or that any one
> > person or group is not involved with intentionally subverting security.
> > That violates the fundamental principles of information protection.
> You're right, which is why the source code is publically available.  I
> would wholeheartedly agree with you if only binaries are shipped, but
> the source is available.  Anyone can look through and verify the code.
> Anyone can try to find weaknesses.  In fact, everyone is encouraged to
> do so.  I don't see how _this_ "violates the fundamental principles of
> information protection".

The problem is that merely shipping however many lines of source code
does little to demonstrate its propriety.  A publicly posted version of
the source for IRC, for example, had an obvious Trojan horse that wasn't
detected for more than 6 months and was actively being used to attack
systems over the entire period.  In order to assess the source code, it
is necessary to also publish appropriate demonstrations of WHY it is
> > 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
> I think I've finally figured out where you are completely confused!!!
> You are confusing "back door" with "bug".  FYI: A back door is usually
> a means to make it easy for someone to get into a system.  For
> example, if I put in code so that I could read every PGP message by
> typing the passphrase "Setec Astronomy", that would be a backdoor.
> The fact that httpd was exploitable, or sendmail holes, or etc. are
> BUGS, not Back doors.

But don't you see? If I introduce a subtle backdoor and make it look
like a bug, I have plausible deniability.  Since I, as an independent
observer, cannot tell whether the hole is intentional or accidental, I
should, for the purposes of considering security, assume that it is

> Your problem is that you are using these terms interchangably.  THEY
> ARE NOT THE SAME.  Putting in a backdoor has the connotation of
> intent.  A bug is an accidental occurrance that was a side effect of
> poor coding, a typo, carelessness, confusion, inconsistency, etc.  A
> back door, on the other hand, is a DELIBERATE ATTEMPT TO REDUCE OR

But how can I, as an independent observer, tell if it is an accident or
a cleaverly intentional subversion? I cannot look into your brain and
tell the difference, and no statement you make can reasonably convince
me.  They may not be the same, but they are not differentiable by an
independent observer.  From a scientific point of view, they are the
same.  From a humanistic point of view they may be different.

> > "...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"
> Oh?  It doesnt?  How can you say that?  In what way does it not do
> this?  The RFC states, in your quote, that "existing hardware on many
> systems can be used" for truly random hardware techniques.  Please,
> substantiate your claim that PGP does not do this.  Show me code
> segments which show it does not.  Show me an analysis that goes
> contrary to the RFC.

You have it backwards.  You show me that the techniques you claim to be
truely random are indeed that.  Supposedly random number generators have
been created for many years, and plenty of them have been broken after
many years of being held to be secure with the algorithm and the full
details available for all to see.

> > But the RFC acknowledges that these methods are highly suspect and should
> > not be trusted.
> You're right, it should not be blindly trusted.  Go read the code and
> examine the algorithms to prove to yourself that it is secure.  I've
> done that to the extent that I wish, and I believe it is secure.  But
> you wont take my word for it, so go ahead and check!  Oh, wait, you
> wont do that either.  Sorry.  I forgot.

But I cannot prove that it is secure.  In fact, I believe that it is not!

> > How is it "unscholarly, unprofessional, needlessly personal, and just
> > plain insulting" to question the idea that hundreds of thousands of
> > people are trusting their freedom to software that is probably not
> > secure? I think it is highly unprofessional to try to claim that PGP is
> > secure and to try to bolster that position by claiming that some
> > "Request for Comments" supports it when that same said RFC refutes it.
> Show me some proof that PGP is "probably not secure"?  Come on, there
> is a finite probability that I can walk through a wall!  The laws of
> quantum probablility give me this finite probability!  But I'd be hard
> pressed to show you that I can walk through the wall.  It looks good
> on paper, but it just ain't gonna happen.

That's exactly what the Germans said about the Enigma and others have
been saying about cryptosystems for the past 4,000+ years.  They have
been shown wrong again and again, and as a result, people like me want
more than just an "I believe it's secure".

> As for the RFC, it does not refute that PGP is secure.  In fact, PGP
> pretty much follows the RFCs guidelines.  You clearly have selective
> reading.  A useful skill -- I should learn it.

It takes years of practice.

> > It has been my general impression that "scholarly" means, among other
> > things, questioning the status quo and finding out where the generally
> > accepted ideas break down.  I am a professional in the field of
> > information protection, and I consider it highly unprofessional in this
> > field to assume that systems are secure without ample evidence to
> > support it.
> Dont forget that you have to run PGP in some OS.  Please show me a
> secure OS!  Given that the OS cannot be secure (using your logic it is
> intuitively obvious that this is true) then how can you ask to see a
> program any more secure than the enviornment in which it runs?  PGP
> tries to be as secure as possible given the environment in which it is
> being run.

I agree that it is often easier to break into the computer to get the
keys than it is to break the cryptosystem.  That was my next bone to
pick with PGP - the way it stores the keys.  But I'll save that for
another day. 

> > So far, I see no ample evidence to support the security of PGP's key
> > generation algorithm relative to the concerns I have expressed.  Those
> > concerns are fairly specific as far as I am concerned, but if you feel I
> > have to demonstrate a specific attack that works in order to question
> > the adequacy of protection, I think you have it backwards.
> No, your concerns have been utterly vague.  The closest you've come to
> being at all specific is some vague notion of analyzing keystrokes.
> In every message I've responded to, I've asked you to expand upon what
> you mean.  What kind of analysis do you mean?  How do you propose to
> analyze keystroke timings?  Even if you have a probabalistic model of
> keystroke timings, all you can possibly do is compare two different
> probabilities to see if they are the same.  But that doesn't help you
> limit the search on keys.

For example, you can generate the most probable 10^40 or so input
sequences, do key generation, and test against them to find out if the
user's key is one of them.  The question I am posing could be considered
as a question of the information content of the original input to PGP's
key generation process.

How could this be subtly altered by a person responsible for maintaining
PGP or detected and not repaired by same? For example, a loop index
could be calculated incorrectly by having a different part of PGP
overwrite the loop index using an incorrect ponter conversion.  Then the
loop that uses all of the input bits would be subtly altered so as to
use fewer of them.  The results would still look random but the total
search space would be reduced to the point where a good supercomputer
could run through it in only a few hours.

> > If the people at MIT feel personally insulted because I have questioned
> > their previously accepted ideas, it's just too bad.  I didn't say they
> I'm not insulted that you are questioning PGP.  I am insulted because
> in every message you have sent, you have postulated some conspiracy
> with the government or postulated some intentional weakening of PGP.

And history tells us that the U.S.  government does this quite often. 
They are actively trying to harass PGP's author using a variety of what
could be reasonably called dirty tricks, they are actively trying to
prevent the use of good cryptography in the US, and they are actively
trying to make certain uses of cryptography illegal.  Why should I
believe that they would not also try to subvert PGP?

> Your statements could almost be construed as libelous, which is why I
> feel insulted.  I feel extremely comfortable with people questioning
> the security of PGP.  What I dont like is someone stating that it is
> not secure, slaiming some sort of back door (which connotes some
> intent to reduce the security) and does not back up the claim with any
> proof.

What I don't like is people that state it is secure but can't back it up
with real facts.  Why (specifically) do you believe PGP is secure?
Forget your ego and the posturing about how you are not working for the
NSA and come up with a really good demonstration of the reason PGP is
secure, and I will be very quick to commend you.

> Ok.  Please explain what kind of keystroke timing analysis you
> propose, and I will attempt to answer that, or concede your point.

Fair enough.  A useful first step would be to demonstrate the real
information content of the keystrokes and timings entered by the user
across a reasonable number of different platforms, users, and trials.
That would start to address the potential that there is a fundamental
mistake in (or intentional corruption of) the input process.

The demonstrations described earler would also be worthwhile in
demonstrating the lack of subtle interaction among the parts of PGP (I
refer to the information flow analysis).

After that, you should solicit other ideas from as wide an audience as
possible to see what sorts of properties should be considered for this
sort of program, and go about picking the most important ones first, and
so on.  I would be happy to discuss further details off-line.

> > 	OR come up with another alternative that doesn't ignore my question,
> > 	doesn't avoid the issue, doesn't appeal to authority that fails to
> > 	adequately support your contentions, and doesn't claim that I an
> > 	somehow unprofessional or scholarly for questioning an unproven
> > 	contention.
> Have you heard the thought experiment of putting a back-door in login
> by modifying the C compiler to modilgy the C compiler to modify login?
> Think about that in terms of the security of PGP -- you are always
> going to be limited in security to the security of the system on which
> you are running.

Not a thought experiment, the Turing award paper in 1984 - came out just
a little bit after the IFIP conference in which computer viruses were
first publicly described and analyzed. 

> I only believe you are being unscholarly because you are making claims
> without any supporting evidence.  _THAT_ is unscholarly!

I think there is good supporting historical evidence for my questions.
But I don't believe I have made any "claims".


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