From: Mike Ingle <MIKEINGLE@delphi.com>
Date: Thu, 26 Aug 93 23:05:52 PDT
To: cypherpunks@toad.com
Subject: Commercial PGP; trapdoor rumors
Message-ID: <01H2813M8J6090MZGB@delphi.com>
MIME-Version: 1.0
Content-Type: text/plain


It would be very easy to put a trapdoor into a version of PGP, and the
only way to detect it would be to reverse-engineer the object code. For
example: take the date, recipient's key id, and a 16 bit random number,
MD5 it, and that's your session key. They all look random, but to crack
it you only have to try 65536 combinations (trivial - IDEA is fast).
You could also set a trapdoor value which would always be accepted as
a valid signature.

However, it would be very unlikely that a company which deals in
cryptography would actually do this. There are quite a few hackers
around who can reverse-engineer code. If one of them found the
tampering, ViaCrypt would be commercially ruined (magazine headlines,
nobody buys crypto from them again) and likely open to lawsuits from 
anyone who ever used their product. If they really want to reassure
us: let Phil Zimmerman and a couple of others examine *all* of the
source code, let Zimmerman run the compiler himself, then Zimmerman
and the others sign the object code and a statement that they certify
the program has no trapdoors. Include this as a detached signature
certificate with the program, much like PGPSIG.ASC. Also, offer a 
sizable reward ($1000 or better) for anyone who breaks either commercial 
or freeware PGP and tells how it's done.

PGP uses randseed.bin and the time to generate random session keys.
If you used the same randseed and wrote a tsr which freezes the
clock (i.e. always gives the same value) wouldn't you get the same
session key? You'd have to recopy randseed from a backup after each
run, because it's re-scrambled. If you get free PGP to give the
same key twice, commercial PGP should give the same key under
the same conditions.

There should be no way to tell, by looking at keys or ciphertext,
whether they were created by commercial or free PGP. This would
head off any persecution of free PGP users, provided of course
that anyone who makes a cent from PGP had better *own* the commercial
version. He could, of course, *use* the free version!

Will PKP agree to condone the use of the free version for personal
non-profit communication? They will if they know what's good for their
bottom line. PGP could become a standard, and they stand to make
a lot of money off its success. 

I hope that future U.S. PGP's are not hobbled with slow PKP-approved
RSA code. If they are, I and many people will ftp the foreign versions
from sites outside the U.S.

> From:   IN%"an31144@anon.penet.fi" 26-AUG-1993 19:17:39.96
> I would be pleased to see some truly exhaustive efforts made to test
> PGP's actual security.

> I have been seeing yet more criticisms of PGP, this time from some
> character calling himself "Raymond Paquin."  He claims to be a
> professor of mathematics who has been working at an unnamed university
> exclusively on cryptographics for the past twelve years.  He implies
> that he is working for some government in a classified capacity and is
> thus unable to either publish or discuss the matter openly.

> He claims that PGP is fatally flawed, though the flaw is in niether
> RSA or IDEA, but rather somewhere within the PGP part of the program.

> Copping the "I can say no more!  I have said too much already!"
> melodrama, no more detailed information is forthcoming.

> Now, this tease seems to reek of a hoax, but Zimmermann himself claimed
> no high degree of security for the program.  To my knowledge, no serious
> or well-funded unclassified attempts have been made to crack PGP.  I
> fear that we are putting our faith in snake oil, as Zimmermann puts it.

> I am not a mathematician, but merely a former spear-carrier in the Cold
> War with some fairly well-developed residual instincts about this sort
> of thing, including a conviction that all security measures - physical,
> electronic or cryptographic - can be compromised by a determined
> opponent with extensive resources.  Once compromised, attacks thereafter
> may often be trivially accomplished.

> From:   IN%"an31185@anon.penet.fi" 26-AUG-1993 20:40:09.66
> an31144@anon.penet.fi writes:

> ["Raymond Paquin"]
> >.. claims that PGP is fatally flawed, though the flaw is in niether
> >RSA or IDEA, but rather somewhere within the PGP part of the program.
> >
> >Copping the "I can say no more!  I have said too much already!"
> >melodrama, no more detailed information is forthcoming.

> Yes, this seems to be a persistent rumour, though I've no idea how true
> it might be. I uploaded PGP to a bulletin board a few months back and
> received a message from another user claiming the same thing. (And taking
> the same copout...)

> I've been meaning to take a good look at the source for a while, I think
> it's about time to investigate the key generation code.....

Where did these rumors come from?

1: PKP
2: NSA
3: David Sternlight

I remember a thread on alt.security.pgp about version 2.3 having a
trapdoor in it. And I think they said the same about 2.2 before that.
Whoever "Raymond Paquin" is, he's no spook. Spooks just don't do
things like that - tell a little bit, then clam up. They are 
trained by instinct never to leak. Most rumors wilt under bright 
lights; where were these originally posted? Ask this person to
post anonymously: where is the trapdoor?

If there is any flaw in PGP, there are only a few places where it
could be. The basic mechanics of the program (RSA, IDEA, etc) obviously
work. The file format can easily be checked to make sure it is correct.
A subtle flaw would have to be somewhere like: prime number generation,
random RSA key generation, or random session key generation. If the primes
weren't actually prime, that would make the RSA keys breakable. But
you could take the primes (pgp -kg -l and you will see them in hex)
and feed them into a primality tester to verify that.

The most likely place for a bug would be in the randomness. I suppose
it is possible that a one-line bug somewhere could leave out most of 
the randomness, making the keys still look random but actually be
predictable. Random number generation is hard to verify. How has
that in PGP been checked? The PGP source is so big and spread out,
it's hard to check. I don't think there is a bug, but it would
be nice if PGP were carefully examined and attacked. Where are these
rumors coming from? They are bad for the cause. 

                                     < mikeingle@delphi.com >
                                     PGP key on servers.
                                     Clipper - Big Brother Inside!