PGP Notes

OverviewSearch on YouTubeBookmarkSaved

Why PGP existsSearch on YouTubeBookmarkSaved

Email is the most used network application. But usual email is like a postcard. Anyone can read it in transit or in the recipient's mailbox.

Pretty Good Privacy (PGP) gives confidentiality and authentication for email and file storage. Phil Zimmermann made most of it. He selected the best available cryptographic algorithms and put them into one program. PGP is independent of government organizations. It runs on many systems, in free and commercial versions.

Five servicesSearch on YouTubeBookmarkSaved

NotationsSearch on YouTubeBookmarkSaved

PGP operationSearch on YouTubeBookmarkSaved

AuthenticationSearch on YouTubeBookmarkSaved

1. The sender makes the message.
2. SHA-1 makes a 160-bit hash of the message.
3. RSA signs the hash with the private key of the sender. The signature is attached to the message.
4. The receiver uses RSA with the public key of the sender to recover the hash code.
5. The receiver calculates the hash of the received message. It compares this with the decrypted hash code.

ConfidentialitySearch on YouTubeBookmarkSaved

The sender:

1. Makes the message and a random session key for this message only.
2. Encrypts the message with the session key. It uses AES, 3DES, IDEA or CAST-128.
3. Encrypts the session key with the public key of the recipient, using RSA.
4. Attaches the encrypted session key to the message.

The receiver:

1. Decrypts the session key with its private key.
2. Decrypts the message with the session key.

Both servicesSearch on YouTubeBookmarkSaved

PGP can use both services on one message:

1. Make the signature and attach it to the message.
2. Encrypt the message and the signature.
3. Attach the session key, encrypted with RSA or ElGamal.

This is authenticated confidentiality.

CompressionSearch on YouTubeBookmarkSaved

By default, PGP compresses the message after the signature and before the encryption. This saves space for email transmission and for file storage. PGP uses ZIP.

PGP makes the signature before compression for two reasons:

1. The user can store the uncompressed message with its signature for later verification.
2. PGP compression is not deterministic. Hashing after compression would force all PGP implementations to use the same compression version.

PGP encrypts after compression. A compressed message has less redundancy than the plaintext. Thus cryptanalysis is more difficult.

Email compatibilitySearch on YouTubeBookmarkSaved

An encrypted block is a stream of arbitrary 8-bit octets. Many email systems accept only ASCII text. Thus PGP changes the binary stream to printable ASCII characters with radix-64 conversion:

• Each group of three octets becomes four ASCII characters.
• A CRC is appended to detect transmission errors.
• Radix-64 makes a message 33% larger. But with compression, the total size is still about one third smaller.

SegmentationSearch on YouTubeBookmarkSaved

Email systems often have a maximum message length. Many Internet systems accept at most 50,000 octets. PGP divides a longer message into segments that are small enough.

• Segmentation is done after all other processing, also after radix-64 conversion.
• The session key component and the signature component are only in the first segment.
• The receiver must reassemble the message before it verifies the signature or decrypts.

Keys and key IDsSearch on YouTubeBookmarkSaved

Key typesSearch on YouTubeBookmarkSaved

PGP uses four types of keys:

• one-time symmetric session keys,
• public keys,
• private keys,
• symmetric keys from a passphrase.

There are three requirements:

1. PGP must make unpredictable session keys.
2. A user can have many public/private key pairs.
3. Each PGP entity keeps a file of its own key pairs. It also keeps a file of the public keys of its correspondents.

Session keysSearch on YouTubeBookmarkSaved

Each session key is for one message only. It encrypts and decrypts that message. PGP makes random numbers with the ANSI X12.17 algorithm. The inputs come from the keystrokes of the user: the timing and the keys pressed.

Key identifiersSearch on YouTubeBookmarkSaved

A user can have many key pairs. Thus the receiver must know which key the sender used. To send the full public key each time is not efficient.

PGP sends a key ID in place of the full key. The key ID is the least significant 64 bits of the key. It is very probably unique:

$\text{key ID of } PU_a = PU_a \bmod 2^{64}$

The PGP digital signature also needs a key ID.

Message formatSearch on YouTubeBookmarkSaved

A message has three components:

The signature component contains:

• Timestamp: the time of the signature.
• Message digest: the 160-bit SHA-1 digest, encrypted with the private signature key of the sender.
• Leading two octets of the digest: a plaintext copy. The recipient compares them with the first two octets of the decrypted digest. This shows that the correct public key was used. These octets are also a 16-bit frame check sequence.
• Key ID of the public key of the sender: it identifies the key that decrypts the digest. Thus it also identifies the private key that encrypted the digest.

The full block is usually radix-64 encoded.

Key ringsSearch on YouTubeBookmarkSaved

PGP keeps two data structures:

• a private-key ring for the key pairs of the user,
• a public-key ring for the public keys of other users.

Private-key ringSearch on YouTubeBookmarkSaved

Each row is one key pair of the user:

A user can give a different name to each pair. A user can also use the same user ID more than once.

Passphrase protectionSearch on YouTubeBookmarkSaved

The private-key ring stays only on the machine of its owner. PGP does not store the private key in plaintext. It encrypts the key with CAST-128 (or IDEA or 3DES):

1. The user selects a passphrase.
2. PGP makes a new RSA key pair and asks for the passphrase.
3. SHA-1 makes a 160-bit hash code from the passphrase. PGP discards the passphrase.
4. CAST-128 encrypts the private key with 128 bits of the hash code as the key.
5. PGP discards the hash code and stores the encrypted private key.

To use the private key, the user gives the passphrase again. PGP makes the hash code again and decrypts the private key with CAST-128.

Public-key ringSearch on YouTubeBookmarkSaved

Each row is the public key of another known user:

One public key can have many user IDs.

Transmission and receptionSearch on YouTubeBookmarkSaved

TransmissionSearch on YouTubeBookmarkSaved

The message from A to B is signed and encrypted.

1. Sign the message:

• PGP gets the private key of the sender from the private-key ring. It uses your_userid as the index. If there is no your_userid, it uses the first private key on the ring.
• PGP asks for the passphrase to recover the private key.
• PGP makes the signature component.

2. Encrypt the message:

• PGP makes a session key and encrypts the message.
• PGP gets the public key of the recipient from the public-key ring. It uses her_userid as the index.
• PGP makes the session key component.

ReceptionSearch on YouTubeBookmarkSaved

1. Decrypt the message:

• PGP gets the private key of the receiver from the private-key ring. The index is the key ID in the session key component.
• PGP asks for the passphrase to recover the private key.
• PGP recovers the session key and decrypts the message.

2. Authenticate the message:

• PGP gets the public key of the sender from the public-key ring. The index is the key ID in the signature component.
• PGP recovers the transmitted message digest.
• PGP calculates the digest of the received message. It compares the two digests.

Public-key managementSearch on YouTubeBookmarkSaved

Four approachesSearch on YouTubeBookmarkSaved

A wants a reliable public key of B. These approaches decrease the risk of false keys in the public-key ring:

1. Physical copy. B stores $PU_b$ on a floppy disk and gives it to A. This is very secure, but not practical.
2. Fingerprint check. B sends the key by email. PGP shows the 160-bit SHA-1 digest of the key in hex. This is the fingerprint. A telephones B and B reads the fingerprint. If the fingerprints match, the key is correct. A must recognize the voice of B.
3. Trusted introducer. A mutual trusted person D makes a signed certificate. It contains the public key of B, its time of creation and its validity period. D signs the SHA-1 digest of the certificate with the private key of D. Only D can make this signature.
4. Certifying authority. A trusted authority makes and signs a certificate. A gives a user name to the authority and gets the signed certificate.

Trust flag byteSearch on YouTubeBookmarkSaved

PGP links trust to public keys. It stores trust in a trust flag byte with three fields:

KEYLEGIT values:

1. unknown or undefined trust
2. key ownership not trusted
3. marginal trust in key ownership
4. complete trust in key ownership

A WARNONLY bit tells PGP to only warn the user when a key that is not fully valid is used for encryption.

SIGTRUST and OWNERTRUST values:

1. undefined trust
2. unknown user
3. usually not trusted to sign other keys
4. usually trusted to sign other keys
5. always trusted to sign other keys
6. this key is in the secret key ring (ultimate trust)

• SIGTRUST has a CONTIG bit. It is set if the signature leads on a contiguous trusted certification path to the owner of the key ring.
• OWNERTRUST has a BUCKSTOP bit. PGP sets it automatically if the key is in the secret key ring.

Trust processingSearch on YouTubeBookmarkSaved

This is the trust processing on the public-key ring of user A:

1. A new key is added. PGP assigns a trust value to the owner of the key. If the owner is A, the key is also in the private-key ring. Then PGP assigns ultimate trust automatically. If not, A selects the level: unknown, untrusted, marginally trusted or completely trusted.
2. A signature is added. PGP searches the ring for the author of the signature. If the author is a known owner, PGP copies the OWNERTRUST value of the author to the SIGTRUST of the signature. If not, it assigns "unknown user".
3. KEYLEGIT is calculated. If one signature has ultimate trust, KEYLEGIT is "complete". If not, PGP calculates a weighted sum. An always-trusted signature has weight $1/X$. A usually-trusted signature has weight $1/Y$. The user sets X and Y. When the sum is 1, KEYLEGIT is "complete".

Without ultimate trust, PGP needs at least X always-trusted signatures, Y usually-trusted signatures, or a mixture.

PGP scans the public-key ring from top to bottom to keep it consistent. For each owner, it sets the SIGTRUST of that owner's signatures equal to the OWNERTRUST. It starts with the keys that have ultimate trust. Then it calculates all KEYLEGIT fields from the attached signatures.

Revoking keysSearch on YouTubeBookmarkSaved

A user revokes a public key in two cases:

• An opponent possibly has the unencrypted private key.
• The user does not want to use the same key for a long period.

The owner issues a signed key revocation certificate. The owner signs it with the matching private key. It is similar to a usual signature certificate, but it revokes the public key. The owner broadcasts it as soon as possible. Then other users can update their public-key rings.

Web of trustSearch on YouTubeBookmarkSaved

The trust fields make a web of trust in a community of users.

• Alice trusts only Abe to sign certificates. Then she does not accept the certificates of Martha or Emily.
• If she also trusts Bob to sign certificates, she can trust the certificate of Emily.
• If she also trusts Carl, she can trust the certificates of all users.

Quick self-testSearch on YouTubeBookmarkSaved

Give the five PGP services. Which three are transparent to the user?

Authentication, confidentiality, compression, email compatibility, and segmentation and reassembly. The last three are transparent.

Give the PGP authentication steps.

The sender hashes the message with SHA-1 and signs the hash with RSA and its private key. The receiver recovers the hash with the public key of the sender. It compares this with the hash of the received message.

How does PGP give confidentiality, and what does it not give?

A new session key encrypts the message. RSA encrypts the session key with the public key of the recipient. Confidentiality alone does not authenticate the sender.

Why does PGP sign before compression and encrypt after compression?

Signature first: the user can store the uncompressed message with the signature. Also, compression is not deterministic. Encryption after compression: less redundancy makes cryptanalysis more difficult.

What is a key ID, and why does PGP use it?

The key ID is the least significant 64 bits of the key, $PU_a \bmod 2^{64}$. It identifies the key and is much shorter than the full key.

How does PGP protect the private key in the private-key ring?

SHA-1 hashes the passphrase. CAST-128 encrypts the private key with 128 bits of the hash code. PGP discards the passphrase and the hash code.

Give the reception steps for a signed and encrypted message.

Use the key ID in the session key component to get the private key. Ask for the passphrase, recover the session key and decrypt. Then use the key ID in the signature component to get the public key of the sender. Compare the digests.

Give four approaches to get a reliable public key of B.

A floppy disk from B. An email key with a fingerprint check by telephone. A certificate signed by a trusted introducer. A certificate from a trusted certifying authority.

Give the three trust fields and their special bits.

KEYLEGIT (WARNONLY bit), SIGTRUST (CONTIG bit) and OWNERTRUST (BUCKSTOP bit).

How does PGP calculate KEYLEGIT without ultimate trust?

Each always-trusted signature has weight $1/X$. Each usually-trusted signature has weight $1/Y$. When the sum is 1, KEYLEGIT is "complete".