PGP

Email securitySearch on YouTubeBookmarkSaved

The problemSearch on YouTubeBookmarkSaved

Email is one of the most widely used and regarded network services. At present, the contents of a message are not secure:

Four security enhancementsSearch on YouTubeBookmarkSaved

Four enhancements fix this problem. A secure email system must supply these services:

PGP overviewSearch on YouTubeBookmarkSaved

What PGP isSearch on YouTubeBookmarkSaved

PGP (Pretty Good Privacy) is widely used for secure email:

• Phil Zimmermann developed PGP.
• PGP selected the best available crypto algorithms and integrated them into a single program.
• PGP runs on Unix, PC, Macintosh and other systems.
• PGP was originally free. Commercial versions are also available.

Current applicationsSearch on YouTubeBookmarkSaved

Today, PGP means the OpenPGP standard for encryption and digital signatures. The slide shows four use cases:

The slide ends with one rule: the public-key identity must be verified. If you encrypt with the wrong public key, the wrong person can read the message. The section on key management returns to this problem.

PGP operationSearch on YouTubeBookmarkSaved

AuthenticationSearch on YouTubeBookmarkSaved

A digital signature gives authentication, integrity and non-repudiation of origin. The five steps are:

1. The sender creates the message.
2. The sender makes a SHA-1 160-bit hash of the message.
3. The sender attaches the RSA-signed hash to the message.
4. The receiver decrypts the signature and recovers the hash code.
5. The receiver verifies the hash of the received message.

$\text{signature} = E(PR_a,\ H(M)), \qquad H(M) \in \{0,1\}^{160}$

$PR_a$ is the private key of the sender. Only the holder of $PR_a$ can make a signature that the public key $PU_a$ accepts. Thus, the signature also identifies the sender.

ConfidentialitySearch on YouTubeBookmarkSaved

Encryption of the contents gives confidentiality. The five steps are:

1. The sender forms a 128-bit random session key for this message only.
2. The sender encrypts the message with the session key (symmetric cipher).
3. The sender attaches the session key, encrypted with RSA.
4. The receiver decrypts and recovers the session key.
5. The receiver uses the session key to decrypt the message.

$\text{output} = E(PU_b,\ K_s) \Vert E(K_s,\ X)$

$K_s$ is the session key and $PU_b$ is the public key of the recipient. RSA carries the small secret, and the fast symmetric cipher carries the long message. Each message gets a new $K_s$.

Both servicesSearch on YouTubeBookmarkSaved

PGP can use both services on the same message:

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

$\text{signed} = E(PR_a,\ H(M)) \Vert M \quad \rightarrow \quad E(PU_b,\ K_s) \Vert E(K_s,\ \text{signed})$

The signature is inside the encryption. Thus, an eavesdropper cannot see who signed the message.

CompressionSearch on YouTubeBookmarkSaved

By default, PGP compresses the message after signing but before encrypting. The slide gives the reason:

Email compatibilitySearch on YouTubeBookmarkSaved

PGP produces binary data (encrypted message, signature, encrypted session key). But email was designed only for text. Thus:

• PGP must encode the raw binary data into printable ASCII characters.
• PGP uses the radix-64 algorithm, also called "ASCII Armour".
  • Radix-64 maps 3 bytes to 4 printable characters (it is the Base64 of MIME).
  • Radix-64 also appends a 24-bit CRC.
• PGP also segments messages that are too big.

$\text{radix-64}: \ 3 \times 8 = 24 \text{ bits} \ \rightarrow \ 4 \times 6 = 24 \text{ bits} \ \rightarrow \ 4 \text{ printable chars}$

Armour makes the data about 33% larger (factor $4/3$). Compression recovers part of this increase.

Operation summarySearch on YouTubeBookmarkSaved

The summary slide shows two flowcharts. Transmission (from A):

$X \leftarrow \text{file}$

$\text{signature required? } \rightarrow X \leftarrow \text{signature} \Vert X$

$X \leftarrow Z(X) \qquad \text{(compress)}$

$\text{confidentiality required? } \rightarrow X \leftarrow E(PU_b,\ K_s) \Vert E(K_s,\ X)$

$X \leftarrow R64[X] \qquad \text{(convert to radix-64)}$

Reception (to B):

$X \leftarrow R64^{-1}[X]$

$\text{confidentiality required? } \rightarrow K_s \leftarrow D(PR_b,\ E(PU_b,\ K_s)), \quad X \leftarrow D(K_s,\ E(K_s,\ X))$

$X \leftarrow Z^{-1}(X) \qquad \text{(decompress)}$

$\text{signature required? } \rightarrow \text{strip signature from } X, \text{ verify signature}$

Reception does the steps in the reverse order. Compression and radix-64 conversion always occur.

Keys and message formatSearch on YouTubeBookmarkSaved

Session keysSearch on YouTubeBookmarkSaved

PGP needs a session key for each message:

• Session keys have varying sizes: 56-bit DES, 128-bit CAST or IDEA, 168-bit Triple-DES.
• PGP generates them with the ANSI X12.17 mode (the slide name; Stallings calls it ANSI X9.17).
• The generator uses random inputs from previous uses and from the keystroke timing of the user.

Key identifiersSearch on YouTubeBookmarkSaved

One user may have many public/private key pairs in use. Thus, each message must identify which key encrypted the session key:

• PGP could send the full public key with every message, but this is inefficient.
• Instead, PGP uses a key identifier (key ID) based on the key.
• The key ID is the least significant 64 bits of the key. It is very likely unique.
• PGP also uses the key ID in signatures.

$\text{Key ID} = PU \bmod 2^{64}$

The session key component carries the key ID of the recipient. The signature carries the key ID of the sender. The receiver finds the correct key-ring entry with one lookup.

Message formatSearch on YouTubeBookmarkSaved

A PGP message has three components:

The operations on the whole message are:

• ZIP and $E(K_s, \cdot)$ cover the signature and the message. They do not cover the session key component.
• R64 covers all three components.

Key rings and processingSearch on YouTubeBookmarkSaved

Key ringsSearch on YouTubeBookmarkSaved

Each PGP user has a pair of keyrings:

The private-key ring stores each private key encrypted with a key from a hashed passphrase. Thus, the security of the private keys depends on the security of the passphrase.

The slide tables show these fields:

* = field used to index the table.

Message generationSearch on YouTubeBookmarkSaved

The generation slide connects the key rings to the operations (sign and encrypt):

1. The sender enters a passphrase. PGP hashes it (H).
2. The sender ID ($ID_A$) selects the entry in the private-key ring. The passphrase hash decrypts (DC) the encrypted private key and gives $PR_a$.
3. PGP hashes message $M$ (H) to get the message digest. $PR_a$ encrypts the digest (EP).
4. PGP joins the signature, the key ID of the sender and the message (concatenation).
5. The RNG makes the session key $K_s$. $K_s$ encrypts the signature and message (EC).
6. The recipient ID ($ID_B$) selects $PU_b$ in the public-key ring. $PU_b$ encrypts $K_s$ (EP).
7. The output is the key ID of $PU_b$, the encrypted session key, and the encrypted signature + message.

Message receptionSearch on YouTubeBookmarkSaved

The reception slide shows the reverse path:

1. The key ID of the receiver selects the entry in the private-key ring.
2. The hash (H) of the passphrase decrypts (DC) the encrypted private key. This gives $PR_b$.
3. $PR_b$ decrypts (DP) the encrypted session key. This gives $K_s$.
4. $K_s$ decrypts (DC) the encrypted message + signature.
5. The key ID of the sender selects $PU_a$ in the public-key ring.
6. $PU_a$ decrypts (DP) the encrypted digest.
7. PGP hashes the message again (H) and compares the two digests. Equal values verify the signature.

Key managementSearch on YouTubeBookmarkSaved

Web of trustSearch on YouTubeBookmarkSaved

PGP does not rely on certificate authorities (CAs). Instead:

• Each user is a CA. A user can sign keys for users that the user knows directly.
• This forms a "web of trust":
  • Trust the keys that you signed.
  • Trust keys that others signed if you have a chain of signatures to them.
• The key ring includes trust indicators (owner trust, key legitimacy, signature trust).
• Users can also revoke their keys.

Trust model exampleSearch on YouTubeBookmarkSaved

The web-of-trust diagram uses this legend:

In the PGP trust model, a key becomes legitimate in these ways:

• You signed the key yourself.
• One owner that you fully trust signed the key.
• Two owners that you partly trust signed the key.

A signature from an unknown ($?$) signatory gives no legitimacy. A signature from a legitimate key whose owner you do not trust also gives no legitimacy.

Quick self-testSearch on YouTubeBookmarkSaved

Why is plain email not secure?

The contents of the message are not secure. An eavesdropper can inspect them in transit. Privileged users on the destination system can also inspect them.

List the four email security enhancements.

Confidentiality: protection from disclosure. Authentication: of the sender of the message. Message integrity: protection from modification. Non-repudiation of origin: protection from denial by the sender.

Give the five steps of PGP authentication.

1. The sender creates the message. 2. The sender makes a SHA-1 160-bit hash. 3. The sender attaches the RSA-signed hash. 4. The receiver decrypts and recovers the hash code. 5. The receiver verifies the hash of the received message.

Give the five steps of PGP confidentiality.

1. The sender forms a 128-bit random session key. 2. The sender encrypts the message with it. 3. The sender attaches the session key, encrypted with RSA. 4. The receiver decrypts and recovers the session key. 5. The receiver decrypts the message with the session key.

When PGP uses both services, what is the order?

PGP creates the signature and attaches it to the message. Then PGP encrypts the message and the signature with the session key. Then PGP attaches the session key, encrypted with RSA/ElGamal.

Why does PGP compress after signing but before encrypting?

PGP can then store the uncompressed message and the signature for later verification. Compression is non-deterministic, because the result depends on user preferences. PGP uses the ZIP algorithm.

What does radix-64 armour do?

Radix-64 (ASCII Armour) maps 3 bytes to 4 printable characters, so binary data can go through text-only email. It also appends a 24-bit CRC. PGP also segments messages that are too big.

Give the sizes and the random sources of PGP session keys.

Sizes: 56-bit DES, 128-bit CAST or IDEA, 168-bit Triple-DES. PGP generates the keys with ANSI X12.17 mode. The random inputs come from previous uses and from the keystroke timing of the user.

What is a PGP key ID, and how big is it?

A key ID is the least significant 64 bits of the public key. It is very likely unique. The session key component carries the key ID of the recipient, and the signature carries the key ID of the sender.

Name the three components of the PGP message format.

Session key component: key ID of $PU_b$ and $K_s$, encrypted with $E(PU_b, \cdot)$. Signature: timestamp, key ID of $PU_a$, leading two octets of the digest, and the digest encrypted with $E(PR_a, \cdot)$. Message: filename, timestamp, data. ZIP and $E(K_s, \cdot)$ cover the signature and message, and R64 covers all.

How does a key become legitimate in the PGP web of trust?

PGP has no certificate authority, and each user signs the keys of people that the user knows. A key is legitimate if you signed it, or one fully trusted owner signed it, or two partly trusted owners signed it. Unknown signatories give no legitimacy.