[PGP-7340]: PGP Personal Privacy 6.0a, no key gen

[Dave Del Torto]

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

At 2:34 pm -0400 981003, Brian W Reichert wrote:
>All this discussion about different versions and different key types
>and sizes tends to get a bit confusing.  (At least to me.)  What is a
>DH/E1G key?  I see a reference to DH/DSS.  Is the E1G part included in
>there and just not noted?  Or is the E1G part new in Version 6.  I
>current am using 5.5.3.

Brian,

Quick acronym translations/answers:

[1] Key size indicates the strength of the encryption being done: the larger
the key size, the better (and sometimes slower) the encryption because
decryption becomes exponentially (another power of two) more difficult each
time you double the keysize. A well-designed cipher is also extremely
important: you can have bad ciphers with very big keys and vice versa, to
woeful effect. PGP uses well-designed ciphers, and so bigger keys are, in a
word, better.

[2] "DH/ElG" key means a "Diffie-Hellman/ElGamal" key, more commonly
referred to as "DH". See below. (Jack, note the spelling of "ElGamal": I
asked the man himself about his preferred spellings once upon a time.)

[3] DH/DSS is the same as "DH/ElG". Note that's a capital "i" not a 1. If
you choose to shorthand it this way, use "DH/EG".

FYI, "DH/ElG" is a shorthand fo more accurately describing the keytype as
using Taher ElGamal's variation on the original Diffie-Hellman algorithm, as
it introduces true encryption to what is otherwise mostly a secure
key-exchange protocol for study by cryptologist-mathematicians, not for mere
mortals like us who do not even have Erdos Numbers. ;)  This being said,
don't use this shorthand: if you and your correspondant are such
crypto-geeks that you can discuss aspects of the ElGamal variation on DH,
it's probably not even necessary to mention it (just use "ElGamal"). If
you're referring to PGP keytypes, "DH" will do just fine.

[4] "DH/DSS" more accurately describes the internal composition of the new
DH keytype, which actually has two subkeys, one subkeypair for encryption,
the other subkeypair for making digital signatures. The DH part refers to
the Diffie-Hellman (ElGamal) encryption subkey, and DSS refers to the
signature subkeypair, which uses DSS (the Digital Signature Standard) from
NIST.

[5] The ElGamal (DH) capability was introduced with v5.0 in Spring of 1997,
not in v6.0, but it's currently the more more ubiquitous keytype by far.

[6] If you have any friends who use PGP 2.6.2 on Linux, and you want to be
able to exchange messages with them, you should upgrade to v5.5.5 with RSA.
Note that most (if not all) NAI sales people do not understand this RSA
distinction, so be sure to specifically purchase the RSA capability and
check that they sent you the right version. If none of your friends pray to
the Penguin, I recommend that you upgrade to PGP 6.0 (DH-only for now) and
wait to buy a fully RSA-capable version of PGP 6.x later on. That should be
available before Christmas, but when won't matter to you if you have no
RSA-constrained recipients.

Someday, when there's a PGP 6.5(?) plugin for Mozilla (Netscape 5.0), then
Linux users will have a fully DH-capable version and we'll all be much
happier. Someone on UKCrypto suggested that one must run BillWare to use DH
keys, but I'll just remind him that v6 also runs on those nice new G3 Macs.
Small consolation, I know...



Now for the "long" answers: I've seen so much traffic on this topic, I hope
to answer a lot of questions here, so bear with me...

In order to foster interoperability and simplify encryption significantly
for lots of folks who didn't want to know all the technical details but who
wanted military-grade crypto (like me), Phil originally designed PGP as a
"hybrid cryptosystem." This is a Very Good Thing. It means that PGP uses a
specific set of algorithms to do the various jobs of symmetric encryption,
asymmetric encryption and hashing: the set is commonly known as a
"ciphersuite."

It helps to understand the guts of a PGP message here a little. If you're
interested in the technical details go read RFC 1991. If you already know
1991 or don't care to read it, I'll just explain (simply) that three major
cryptographic functions are involved in PGP encryption:

[1] generating a symmetric "session key", encrypting your data (the "literal
    data" packet, otherwise referred to as "the blob") with that sym key to
    produce an ESK (Encrypted Session Key),
[2] encrypting the ESK to your recipient(s)'s public keys using a asymmetric
    algorithm, and
[3] sometimes, for digital signatures/etc, calculating a unique message
    digest using a hash function. If you're interested in math, BTW, these
    algorithms belong to the "one-way function" family, with symmetric and
    asymmetric algorithms being "keyed" one-way functions, and hashes being
    "non-keyed".

Older versions of PGP, such as the still-viable-but-creaky 2.6.2 / 2.6.3
family (the occasional appended "i" indicates the build's international
origin, i.e. outside the US), all use the "RSA" ciphersuite, which are
semantically/technically to what you commonly see referred to as "RSA keys."
The RSA ciphersuite uses IDEA for the literal data encryption, the RSA
algorithm for asymmetrically encrypting the session key (which is used to
symmetrically encrypt the data, and results in what is often called as
"encrypting to your RSA public key") and MD5 (Message Digest 5) as the hash
function.

Here's which ciphers are part of which ciphersuite:

                  ..................... Ciphers (keysizes) .................
                  Symmetric        Asymmetric                Hash/Digest
Ciphersuites:
          RSA     IDEA (128)       RSA (512-2048)            MD5 (128)
       DH/DSS     CAST-5 (128)     DH/ElGamal (768-4096)     SHA-1 (160)


SHA (Secure Hash Algorithm) is part of DSA (the Digital Signature
Algorithm), which is part of the DSS (Digital Signature Standard) from NIST.
SHA-1 is a FIPS-compliant algorithm (Federal Information Processing
Standard, as the AES or Advanced Encryption Standard will someday be), which
makes it acceptable for all sorts of public/private/government sector work.
CAST is patented by Nortel, but they allow free use of it to anyone (yay,
Nortel!!). Since the DH patent expired recently (yay, Whit!), it's also now
in the public domain. In simple terms, this means we can all use these
algo's without paying any royalties. This is non-trivial, from a cypherpunk
point-of-view. The RSA algorithm, on the other hand, though technically
excellent, is not free, nor is IDEA (owned by Ascom Systec in Switzerland),
so it costs money to implement those, and those costs get passed along to
users like you and me and carry other restrictions that affect
exportability, etc. In a nutshell, this is why PGP Inc and now NAI choose to
favor the free algo's. This "unencumbered" status is also fundamental to
approval of any standard (such as OpenPGP) approved by the Internet
Engineering Task Force. If a company can restrict the use of a mathematical
algorithm, the IETF will not approve a standard that specifies it's use,
period.


All versions of PGP 2.x exclusively use the RSA ciphersuite: it's what they
were originally designed to do (we had few better algo's then), and those
old versions don't get any smarter. ;) BTW, "2.x" actually means any version
up to (and including) the somewhat confusingly-numbered "ViaCrypt PGP 4.0",
which is actually a "customized" version of PGP 2.6.2 in "business"
clothing. There's a long and terribly interesting story that I won't go into
here, but in 1996, PGP merged with ViaCrypt, re-acquired the VC source tree,
and in mid-1997 (after 5.0 was out wiht the new DH keytype) released two "DH
compatibility versions" (v4.0.1, v4.5.1) that did *ONE* basic job for those
users who had purchased VC/PGP but couldn't upgrade to PGP 5.0: these
versions didn't die a horrible writhing death when shown DH packets.

Some people still use these 2.6.x versions out of necessity (e.g. they have
an old PC running Win16, or they use an unsupported version of Unix). As PGP
proponents, it's our solemn obligation to do everything we can to maintain
that "legacy" as much as possible. Eventually, RSA keytype support will die
out for good, but it should be a gradual process. NAI is "helping" this
extinction along, and depending on what version you own/use, they're either
good guys or bad guys for doing that. Maybe, once RSADSI's RSA algorithm
patent runs out (if it doesn't get mysteriously extended by some govt
agency), NSA keys, er, excuse me _RSA_ keys could experience a minor
resurgence, but the DH key type is _so_ technically superior at this point,
I don't hold out much hope for that, and it would be very minor indeed.

And then there's OpenPGP, a working group of the IETF... that's where the
future lies for PGP, but it's also beyond the scope of this email. As that
strong, international standard develops, defining ciphersuites for
interoperability purposes will continue to be an important part (if not THE
most important part) of the OpenPGP standards process.

Are you confused yet? You are? Good. That means you're paying attention. ;)

OK, that was ancient history: now things get "interesting." When PGP Inc
started in early 1996, everything about PGP was rethought and lots of clever
ideas that came up over the volunteer years were incorporated, including the
API groundwork of the volunteer PGP 3.0 development team (some of whose
members are on this list). The (salaried) PGP engineering team rewrote
virtually all of the PGP source code to introduce a much more flexible
underlying architecture: the goal being a modern commercial software source
tree, designed for survivability in the marketplace. There were/are also
political, financial and technical reasons why the software had to change
inside, but the result was that the 2.x freeware source code base, which at
that point had had many cooks stirring it, gained a new architecture and a
vastly improved user interface -- and maintained compatibility with the old
versions. Again, this is non-trivial: kudos are due to Will and the others
who made this happen relatively seamlessly. Compatibility and
interoperability are VERY important goals in cryptography. Perhaps second
only to cipher strength, and even more important that ease of use, though
that's a close call.

Another new thing was added, a very important new ciphersuite with a new
type of keys, known commonly as "Diffie-Hellman" keys, in homage to Whit
Diffie and Martin Hellman who (unless those stories about the NSA and
British Intel in the 60's are true, and we'll never know) started this whole
Public Key Cryptography bent with their paper on it in 1976. Note that these
new keys have a different assumption about which set of ciphers
(sym/asym/hash) will be used when preparing a message for transport -- and,
of course, which ones should be used on the other end for one-pass
decryption. You can imagine what PGP would have been like if the idea of
ciphersuites was never widely adopted: everyone would use different
algorithms for all the different steps in the PGP process, based on their
personal preferences (which implies that they know enough about cryptology
to HAVE preferences ;). In other words, it would (have) be(en) a huge mess
and the intelligence agencies snooping on the wires would have been very
pleased because everyone would have been running around like a bunch of
idiot sheep bleating in different tongues, instead of developing standards
and describing our global Animal Farm for what it truly is.

Fortunately for everyone, it didn't happen that way, and we now have the
choice of a freely-available and royalty-free (DH) ciphersuite.

The downside is that there are now TWO types of keys: new PGP users get
(justifiably) confused and some versions of PGP die horribly if you hand
them the "Kryptonite" keytype instead of the "Dilithium" keytype they need.

Version numbering and keytypes-supported gets even more complicated at this
point, since legal reasons (an RSA lawsuit) forced PGP Inc to leave out RSA
capability in a few versions of PGP 5.5, notably the freeware. RSA may have
done us all a favor by forcing PGP Inc to drop RSA support for a few
versions here and there, but it sure caused a hell of a mess, and lamentably
we at PGP Inc got lots of blame for it. I'd like to point out that it was a
nightmare for us as far as support and customer confusion, and anyone who
actually thinks that we did that on a whim is a bogoid.

Generally, keytypes and versions looks something like this:
<http://www.freedomfighter.net/crypto/pgp-history.html>

Now, before anyone flames me, this is a "five-minute-jobby" and it
undoubtedly contains glaring errors, so it is NOT intended to be a
definitive matrix, but it's a start.
NOTE: there's a mailto URL on the webpage: any cypherpunks who want to send
me corrections or additions, please do so ASAP. I'll update the matrix and
then we can use it as a reference.


Also, in subsequent mail, you asked:

>I ... was wondering why I see so many people using
>RSA keys when DH/DSS is the newest, and supposedly better, encryption
>method?

FYI, "so many people" is probably well under 10,000 people at this point,
and I'm being very generous. It may be more like a few hundred die-hards.
The VAST majority of keys out there now are DH keys. The last keyserver
stats we had at PGP Inc put DH at over 90% -- but that figure's a year old
(Oct 97): it's probably asymptotically approaching 100% by now, and the
total population of PGP keys is probably closing in on several hundred
thousand, with more that haven't been posted publicly, such as internal
enterprise keys at corporate sites.

The remaining RSA key users have few choices: (1) upgrade their hardware or
software to be able to run a 32-bit OS (Win95,WinNT,etc), or (2) retire them
as soon as NAI provides a version of PGP 6 for their platform (mostly
applicable to users of some flavors of UNIX or Linux). I'm no happier than
this about them, and I do actually NEED to be able to have RSA capability,
since I exchange a lot of enc mail with 2.6.x users worldwide.

>I personally made one of each to make sure everyone could use at least one
>of these

That's very good PGP etiquette.  :)

>but now I hear about builds that support different key sizes.

As Phil Zimmermann (and others including me) have pointed out fairly
consistently, there's no huge value to generating RSA keys larger than 2048
bits, since it gains you only a tiny amount of security but breaks
introperability(!).

Basically, RSA keys >2048 bits are a violation of the "de facto" PGP
standard. Some of us had fun playing around with 8000-bit and even 32000-bit
keys in some wildly experimental builds years ago, but that was really just
for laughs. If anyone is putting out versions that exceed the de facto
standard, they are creating additional problems for users without delivering
significant benefits and should really stop.

Some may argue with me here that there should be 4096-bit RSA keys.
Actually, cryptographically-speaking, I agree. Practically speaking, though
I disagree. It's the old "in Theory vs in Practice" joke. I side with
"Practice" here: breaking interoperability is, IMHO, a big "no-no."

>My RSA key is 2048 bits

That's the "legal" maximum, to remain compatible with other RSA-capable
versions. Leave it that way.

>and my DH/DSS key is 4096 bits.

Well done: that's the maximum size for DH keys. Anything over ~3072 bits is
considered good, since asymmetric ElGamal encryption subkeys of
approximately 3072 bits are roughly equivalent to symmetric CAST keys of 128
bits (the actual bit size varies from ~2900 to ~3100, but 3072 is in the
pocket).

The important point here is that in your PGP messages, if the literal (sym)
packet is 128 bits, but you strap an ESK onto it encrypted with a <3072-bit
asymmetric key, the asym encryption becomes the "weak link", but if you use
an asym key >3072, the 128-bit sym enc is the "weak" part, which is pretty
good, since conservative estimates tell us that with current computing
technology, every CPU on the planet would have to work full-time for a few
billion times the lifetime of the known Universe to brute-force cryptanalyze
128-bit enc'd ciphertext. As Phil says, "That's Pretty Good."

>Will I now have to make keys that are smaller to make them more compatible?

No, you're all set. In fact, everyone should follow your example and build
RSA keys of (but no larger than) 2048 bits and DH keys of at least 3072 bits
(4096 preferred: there's no huge performance hit, since the only really
time-consuming activity is generating the key in the first place and you
only do that once).

Hopefully, this all helps you to understand these key issues "a bit better."

   dave

____________________________________________________________________________
 Dave Del Torto      <mailto:ddt@lsd.com>           Level Seven Digital Labs
 DH Key:   <http://pgp.ai.mit.edu:11371/pks/lookup?op=get&search=0x28C029AF>
 Fingerprint: 9b29 031d 70de f566 e076 b108 904d fea3 28c0 29af / Size: 4096
 RSA Key:  <http://pgp.ai.mit.edu:11371/pks/lookup?op=get&search=0x4AAF00E5>
 Fingerprint: 30d8 1f34 84e6 a83f  6ec8 d7f0 cab3 d265          / Size: 1024



-----BEGIN PGP SIGNATURE-----
Version: PGP 6.0
Comment: Get interested in computers -- they're interested in YOU!

iQA/AwUBNhv925BN/qMowCmvEQKlswCgxJ2WiDQQSdtIjSl0XF9hRvxXvl0AoN/X
E+DMycgRapWv5mTqLk2c5nBq
=8RA/
-----END PGP SIGNATURE-----