Question about the "Freeware Version"

3 views
Skip to first unread message

Preston Wilson

unread,
Jun 18, 1997, 3:00:00 AM6/18/97
to

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

On Tue, 17 Jun 1997 17:03:26 GMT, ja...@bellsouth.net (James) wrote:

> Does the freeware version of PGP 5.0 still give the option of
>"Faster
>Key Generation"? This option when turned off causes the program to
>generate an RSA key instead of a DSS/Diffie-Hellman key. The help
file
>says the DSS/Diffie-Hellman type key takes less time to generate than
>the RSA key.
>
>James

No! No! No! "Faster Key Generation" applies only to DH keys. If
the "Faster Key Generation" box (that is, indeed, present in 5.0
freeware) is *not* checked, it *still* creates a DH key. The only
difference is that it can take up to an hour, and you get a *gasp!*
_secure_ key out of the ordeal.

The "Faster Key Generation" option, for those who haven't scoured the
help file looking for information about it, is the default method of
key generation in the free and commercial versions of PGP 5.0. It
decreases the time required for key generation from somewhere near an
hour for a 4096-bit key on a P-166 with 64-MB memory down to a mere
second or two. How does it do this, you may ask. It uses
"precalculated prime numbers". Yeah, canned primes. If there were
ever a scheme to weaken PGP, it would be that; include with PGP a
fixed number of prime numbers from which users will be randomly
assigned two at the time of key generation. Customers will be happy
at their quickly generated keys, and the NSA will be happy with their
newfound ability of cryptanalysis.

In other words, I recommend turning this option *off* immediately
after installing PGP, and *before* generating a public/private key
pair. This "feature" is really just a Really Dirty Trick from a
company who's getting just a little too secure in their monopoly.

Preston

-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv

iQEVAwUBM6czk91+eVRobTc9AQFcWAf/YewofnD7SQ2AbtoYsF30akVyGPD6Hyah
F80Z9w2ogi8rpECb4Wu495enlxzNUtoPlttrqSYw0NKUKL8byn8j1JYLMJMyujYu
TY/eZFYU6RZnQAEppEgLVzS/WQW5gKZJdBf/zw+KC+PVhFehC0sjIB/5i5kamOKz
hUyi9CFMM8o2jEVIMswdmlDEG6SlBdO2AMwIzWXdw8dEv2sUxwWtQdq44I5isWSj
qe+avqKbeqpQyAv6uRQzqMjOGWQP/VmvcLdQG1vpw9uhIUOtWQk+ZJ283LzEWOI2
vVwy4K43sua3M2r3iWmfRi+i6m5euTw1H1rmD+4J3xxI/rlyDTogIQ==
=rpMZ
-----END PGP SIGNATURE-----


Wim Lewis

unread,
Jun 19, 1997, 3:00:00 AM6/19/97
to

In article <33a7321...@netnews.worldnet.att.net>,

Preston Wilson <pd...@usa.net> wrote:
>In other words, I recommend turning this option *off* immediately
>after installing PGP, and *before* generating a public/private key
>pair. This "feature" is really just a Really Dirty Trick from a
>company who's getting just a little too secure in their monopoly.

I notice you're using the new version anyway.

According to Schneier, the various primes can be shared among many
users without reducing the security of ElGamal or DSS. The primes
aren't secret, either, they're part of the *public* key (as opposed
to RSA where only the product of the two primes is public). See my
other post in this thread.

IMHO, screaming "wolf" without at least a little bit of actual
evidence is counterproductive. If there's a weakness in PGP5
(venal or otherwise) it's not going to be that obvious. As for
the Evils of Capitalism, it looks to me like PRZ and PGP Inc
have done a very reasonable job balancing any altruistic goals
of encryption-for-the-masses with the desire to make some money
off the considerable effort that has gone into PGP and the hassle
that has come out of it. Sure, it might just be for the PR value,
but we win anyway.

--
Wim Lewis * wi...@hhhh.org * Seattle, WA, USA
PGP 0x27F772C1: 0C 0D 10 D5 FC 73 D1 35 26 46 42 9E DC 6E 0A 88

Jeffrey I. Schiller

unread,
Jun 19, 1997, 3:00:00 AM6/19/97
to

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> The "Faster Key Generation" option, for those who haven't scoured the
> help file looking for information about it, is the default method of
> key generation in the free and commercial versions of PGP 5.0. It
> decreases the time required for key generation from somewhere near an
> hour for a 4096-bit key on a P-166 with 64-MB memory down to a mere
> second or two. How does it do this, you may ask. It uses
> "precalculated prime numbers". Yeah, canned primes. If there were
> ever a scheme to weaken PGP, it would be that; include with PGP a
> fixed number of prime numbers from which users will be randomly
> assigned two at the time of key generation. Customers will be happy
> at their quickly generated keys, and the NSA will be happy with their
> newfound ability of cryptanalysis.

This isn't how it works. A DSS key has four components:

g -- Called the generator. This is the base that other work is done with.
p -- *The* prime field that is used in calculations. Can be 512-1024 bits.
(more then 1024 bits doesn't really yield additional security).
q -- A 160 bit number which is used to reduce the computation (q is
chosen to be the same length as the SHA-1 hash).
x -- Your private key, "x" is the only secret value.
y -- Your public key. It is g^x mod p.

So your public key is the combination of g,p,q and y.
You private key is the combination of g,p,q and x.

PGP 5.0 uses the Elgamal variation on Diffie-Hellman. It has a similar
set of parameters as DSS except there is no "q" value. A PGP 5.0 key
is actually two completely separate keys. A DSS key for signing and an
Elgamal key for encrypting.

PGP supports Elgamal primes of up to 4096 bits.

The time consuming part of key generation is selecting the large prime
"p" (for both DSS and Elgamal). However these are "public" values and
it doesn't really matter if a lot of people use the same p,g (and q
for DSS).

However. The Diffie-Hellman algorithm is "brittle." When you attack a
Diffie-Hellman (or DSS) key, you attack the prime. Specifically you
compute a table of logs that permits you to take a "y" value and lookup
the "x" value (x being the private key). It is also possible to specially
compute a weak "p" value, so it is important that people believe that
the "p" value they are using is secure.

Computing log tables for prime values of 1024 and larger are currently
computationally intractable.

So what does PGP 5.0 to provide for secure prime fields:

Well for starters all of the builtin primes for PGP 5.0 are at least
1536 bits long. In other words if you choose a value of 1024 bits for
your DSS key (recommended) it will be generated at random just for you.
So even if someone, with a *lot* of computer time, can solve the log
table for a 1024 bit prime, they only get one key's worth (this is
similar to a factoring attack on RSA).

However generating a random 2048 bit prime takes a while (not *that*
long), so PGP has a built in value. To ensure that the built in values
are not "trapped", the way they are created will be documented.

I won't go into all the details here, but the gist of it is that a
quote from Ghandi is run through a hash function to create a random
starting point for the search for the primes. One of the Ghandi quotes
used is "Whatever you do will be insignificant, but it is very
important that you do it!"

What this all means is that you can generate a DSS/DH key with a
1024 bit DSS prime and a shared (built in) 2048 bit DH prime in a
very reasonable amount of time.

The downside is that *if* someone can compute a table of logs for the
built in 2048 bit DH prime, they will be able to break everyone's
encryption key that is using that prime. However a 2048 bit prime is
a *very* *very* *very* hard prime to compute the log table of. It is
not likely to happen in my lifetime (or that of my grand kids, at
least not without a mathematical breakthrough that would make this all
moot anyway).

However, if you are concerned, you are welcome to generate your own
DH prime. All you have to do is uncheck the fastkeygen option.

Heck, if you wanted to build a backdoor into PGP there are much better
ways to do it then to use a bad prime (you can test if a prime is
trapped, so any such back door would be findable).

-Jeff

-----BEGIN PGP SIGNATURE-----
Version: PGP for Personal Privacy 5.0
Charset: noconv

iQA/AwUBM6mKcPAgc1f0FJUrEQLoCACgqObiYpKf486H6dQWDdNWSsIjPuEAoLKk
wlsGQZf0DT6Vk/ud21vTfY+8
=fPo/
-----END PGP SIGNATURE-----

Reply all
Reply to author
Forward
0 new messages