Pretty Good Privacy (PGP) was first released in 1991 to offer data encryption and authentication. It rapidly became very popular and was later adopted as the OpenPGP standard in RFC 2440, published in 1997. That RFC defines the OpenPGP Message Format followed by PGP.
The open source software GNU Privacy Guard (GPG or GnuPG) implements OpenPGP and was released in 1999. It was ported to Windows in 2000.
PGP is proprietary software while GPG is a free open source tool. They both run on Linux, BSD, Mac OS X, Windows, and most Unix operating systems. The latest software versions are mostly compatible. This section mainly focuses on the free GPG; for more information on PGP, please see PGP Versus GPG Compatibility.
GPG uses both symmetric and asymmetric keys (see The SSH-2 Protocol). It supports the RSA, DSA, and ElGamal algorithms for public key encryption, and CAST5, 3DES, Blowfish, and AES algorithms for symmetric encryption. Use the following commands to check the list of algorithms supported by your local binary:
[julien@asus ˜]$ gpg --version
gpg (GnuPG) 1.4.2.2
Copyright (C) 2005 Free Software Foundation, Inc.
[...]
Supported algorithms:
Pubkey: RSA, RSA-E, RSA-S, ELG-E, DSA
Cipher: 3DES, CAST5, BLOWFISH, AES, AES192, AES256, TWOFISH
Hash: MD5, SHA1, RIPEMD160, SHA256, SHA384, SHA512
Compression: Uncompressed, ZIP, ZLIB, BZIP2Tip
Some advisories published in 2003 described that GPG's ElGamal signing keys were compromised. This implementation bug is fixed. The ElGamal algorithm is safe to use and is the default for signing.
The data encrypted with a public key can only be decrypted by the associated private key. If you want to send encrypted data to someone, GPG works the following way:
Retrieve the recipient's public key.
Generate the session key (a random symmetric key used only once).
Encrypt the session key with the recipient's public key.
Encrypt the data with the session key.
You can now send your encrypted data chunk, which contains both the encrypted session key and the encrypted message.
The recipient will reverse these steps to decrypt your message:
The recipient decrypts the session key with his private key.
The recipient decrypts the message with the session key.
Optionally, the data can be compressed with one of the compression algorithms supported by GPG (e.g., BZIP2, ZIP). The data compression is done before the encryption with the session key, and the decompression is executed after the decryption with the same session key.
Most of these steps are transparently completed by GPG (see File and Email Signing and Encryption).
The process to digitally sign data is slightly different. GPG will:
Create a hash (MD5, SHA512) of your message.
Generate a signature by encrypting the hash with your private key.
Send the data to the recipient along with the signature.
The recipient, or anybody who wants to verify the email's origin, can check the signature:
The recipient creates a hash from the message using the same algorithm you used.
The recipient decrypts the signature with your public key. The hash obtained should be identical to the hash calculated previously by the recipient.
The data can both be signed and encrypted. When that is the case, the digital signature, by convention, is created first, then the signed data is encrypted.
For PGP to be trusted, you have to exchange public keys with the recipient of your message. The best way to do so is a physical exchange where you and the recipient verify each other's identity; unfortunately, this is not always practical. Another method in absence of physical proximity is to exchange keys by email. However, because you cannot yet exchange encrypted emails, you must ensure that keys were not tampered with and that they indeed originate from each other.
Fortunately, the OpenPGP standard defines the MD5 hash of a key as its fingerprints. The public key and its fingerprints form a unique couple (the collision's probability can be considered negligible). You and the recipient can simply verify each other's key fingerprints by meeting in person or over the phone. When you do it over the phone, make sure you are talking to the intended person. Again, email cannot be used until keys are trusted for encryption or digital signing.
This method is not particularly scalable when people do not know each other directly or when there are too many people to exchange keys with. For example, if you send a signed message to a public mailing list, millions of people may want to verify its origin.
Public keyservers act as key repositories (e.g., pgp.mit.edu). Most public keyservers synchronize with each other, therefore, adding your public key to one server should propagate it to others. Thanks to the keyservers, you will not receive millions of requests to send your public key. Readers will automatically download keys from the keyserver. However, this does not solve the issue of the fingerprint verification. Downloading the public key is not enough to associate it with you. And you are not going to meet each reader individually to verify their identity and public key fingerprints.
In order to surely authenticate a message, its signing key needs to be valid. A key is valid if either of the following is true:
It is signed by the owner of the local keyring.
It is signed by enough other key holders who are trusted by the keyring's owner.
As explained earlier, a public key should be signed only after its fingerprints have been verified out-of-band. Because this is not always possible, we need to rely on a web of trust. The idea is that a recipient might not trust you directly, but they might trust another person who trusts your key and has verified your fingerprint. In addition to their public key, GPG/PGP users are invited to upload public keys they signed by pushing them to a keyserver. This forms the backbone of the Web of Trust.
Each key has a locally configurable trust level. In addition to signing and publishing verified keys, users can change the level of trust for each public key in their local keyrings. There are four levels of trust:
- Unknown or untrusted
Keys signed by such unknown or untrusted owner are not trusted, thus ignored by the Web of Trust scheme.
- Marginal
The owner is known to properly verify key fingerprints before signing them. When multiple marginally trusted keys have been used to sign a locally untrusted key, that untrusted key automatically becomes trusted. OpenPGP implementations don't always require the same minimal number of marginally trusted keys to trust a third key.
- Full or complete
The owner always verifies keys carefully and can be trusted at the highest level.
- Ultimate
If you have the corresponding secret key, that key is ultimately trusted.
Levels of trust assigned to each key are stored locally and cannot be exported to keyservers. It is up to the user to decide how the Web of Trust should be configured:
On PGP 5.x and 9.x for Windows, one fully or marginally trusted key signature is enough to trust an unknown key.
On PGP 2.x for Unix, the Web of Trust is configurable but the default is that two fully trusted keys or four marginally trusted signatures are necessary for an unknown key to be trusted.
On GPG 1.4.x, one fully trusted or three marginally trusted key signatures are required to trust an unknown key.
As you can see, this does not always make sense, especially in Windows implementations. In addition to that, there can be many links on the chain. Usually, short paths of five or less intermediate keys are considered trustable, while paths with six or more keys should be ignored. Figure 15-15 illustrates some valid paths between two people.
In my experience, PGP/GPG works well to exchange encrypted emails with people I know directly, or with one fully trusted intermediate. However, if you want to verify the signature of software to download on the Internet, it is very unlikely that you will have even one path that leads to the owner's key.
The Web of Trust is certainly the weakest component of GPG. It is possible to quantify the trust in the keys signed directly, but the trust on the keys signed by other people is unknown. Someone can sign a lot of keys without proper verification with full trust and thus be part of many shortest trustable paths.
We talked about the Web of Trust, but in reality it is a multitude of separate Webs of Trust. The analogy with the Internet web, where virtually all web sites are linked to each other, cannot be applied to GPG. Webs of Trust are created by corporations, communities, or organizations with few links to the outside. S/MIME has a very different approach from PGP to trust keys (see the previous section).
Signing parties are organized to meet different people from different communities. In a few minutes, you may be able to verify someone's identity before signing his key; however, it is certainly not enough to determine how much trust you can put in him. In the end, adding a few local people to your direct contact does not make a big difference in the building of your Web of Trust.