Computer Security lecture notes

Copyright © 2004 Mark Dermot Ryan
The University of Birmingham
Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License,

Key certificates and PGP

Recap on issues about how cryptography is used

Symmetric-key encryption allows agents to communicate securely, but leaves them with a hard problem: how to agree securely on a key? The main solutions available to them are:

Face-to-face key exchange
Key exchange via a trusted third party (TTP), with whom the agents already share a secret symmetric key.

These solutions are inconvenient and expensive, especially as they have to be done frequently, or you have a key-management headache. (With n parties, you have O(n²) keys, or O(2ⁿ) keys if you want to allow messages private to a group.)

Public-key encryption solves the problem of key exchange, but gives us another problem: how to ensure the authenticity of other people's public keys? The same solutions exist:

Face-to-face key exchange
Key exchange via a TTP

but now they have to be done only once, since are only O(n) keys to manage. Public-key encryption also gives us another solution:

Key certificates.

The concept of key certficate

A key certificate is an assertion that a certain key belongs to a certain entity, which is digitally signed by an entity (usually a different one).

If Alice trusts Bob and knows his public key, and Bob has signed asserting that Carol's key is K, then Alice may be willing to believe that Carol's key is K.

There can be trust chains. Suppose

A1 has signed asserting that A2's key is K2
A2 has signed asserting that A3's key is K3
. . .
A18 has signed asserting that A19's key is K19
A19 has signed asserting that A20's key is K20
A20 has signed asserting that B's key is K

If I know A1's key, and I trust A1, A2,..., A20, then I am willing to believe that B's key is K.

A1 states that A2's key is K2. So, if A2 signs an assertion X, then A1 states that A2 states X. Thus, in the situation above, A1 states that A2 states that A3 states ... that A19 states that A20 states that B's key is K.

X.509 certificates

X.509 certificates are used by SSL/TLS, SET, S/MIME, IPSec and other protocols. They have these components:

Version
Serial number
Signature algorithm identifier
Issuer name
Period of validity
Subject name
Subject public-key and algorithm
Issuer unique identifier
Subject unique identifier
Extensions
Signature

The unique identifier fields were added in version 2 to handle the possible re-use of subject and/or issuer names; rarely used.

X.509 certificates are typically issued by a certificate authority (CA). Anyone can be a CA, but not all CA's are trusted by everyone. Verisign is a top-level CA, trusted by most people. Its key (valid 9/11/94--7/1/10) is built into browsers. If you go to Amazon's secure server and you view the certificate information held by your browser, you will see that Verisign certifies its public key (valid 14/5/03--13/5/04). So the chain is:

The browser knows Verisign's key
Verisign signs Amazon's key

We trust Verisign, so we are assured of Amazon's key. Therefore we can be sure that we are dealing with Amazon, and not someone who is pretending to be Amazon (e.g, by launching a man-in-the-middle attack).

If you go to sis.cs.bham.ac.uk, Mozilla will say:

Unable to verify the identity of School Information System. Possible reasons for this error: (a) Your browser does not recognise the CA; (b) The site's certificate is incomplete due to a server misconfiguration; (c) You are connected to a site pretending to be School of Information System, possibly to obtain your confidential information.

(You can continue anyway, at your own risk.) The reason is that SIS has not obtained a certificate from a CA recognised by the browser, such as Verisign (because it is expensive and inconvenient to do so).

PGP ("Pretty Good Privacy")

PGP is a complete working system for cryptographic protection of files and email. It offers confidentiality, integrity, and non-repudiation, by using public-key cryptography algorithms. The original version by Phil Zimmermann was released on the Internet in 1991.

PGP is now commercial, though freeware versions for Windows and other non-Linux platforms exist for individual, non-commercial use. OpenPGP is a set of standards which describes the formats for encrypted messages, keys, and digital signatures. GnuPG (or gpg) is an open-source GPL implementation of the standards, and is the usual implementation found on GNU/Linux systems. Most of what you read about PGP applies also to GnuPG, and vice versa.

A "PGP key" has several parts:

the name of its owner
the numerical value(s) comprising the key
what the key is to be used for (e.g., for signing; for encryption)
the algorithm the key is to be used with, e.g. El Gamal; RSA; DSA
(possibly) an expiration date

These fields are similar to those of an X.509 certificate. But a PGP key is not yet a certificate (no-one has signed it yet).

The PGP software will generate keys for you, and help you manage them. Usually you will have a different key for signing as for encryption. You may even have two keys for signing; one for signing keys and one for signing email and everything else. This is for extra security; your key-signing key is the most important one, and if other keys were compromised you would like that one not to be automatically compromised too.

When using PGP, you will need to store lots of keys.

your own secret key (this will be stored encrypted with a passphrase)
your own public key and the public keys of your friends and associates (stored in the clear)

The PGP software puts them in a file, called your keyring. Your private keys are in a file only you can read; for extra security, they are stored encrypted with a pass phrase. The public keys don't have to be protected. The keyring also stores certificates, i.e. copies of other people's public keys which are signed by you. These ones are known with certainty by you to belong to the people they claim to belong to.

When you send someone a "signed message", PGP actually signs a hash of the message. This is because

it is more efficient; it only has to sign 160 bits instead of your whole message, for remember that PK crypto is expensive;
it means that the signature is a manageable length (160 bits, ASCII-armoured, so perhaps 50 or 60 bytes)

When you send someone a message "encrypted with their public key", PGP actually encrypts it with a newly-generated symmetric key, and then you send that encrypted version appended to the symmetric key encrypted with the public key. It's more efficient. It also means you can prepare a message for reading by several people: just append the symmetric key several times, each time encrypted with one of the public keys of the intended recipient.

Thus, PGP puts together the ideas of symmetric-key encryption, public-key encryption, and hash functions, and also text compression, in a practical and usable way to enable you to sign and/or encrypt email. The algorithms PGP uses are:

RSA, DSS, Diffie-Hellman for public-key encryption
3DES, IDEA, CAST-128 for symmetric-key encryption
SHA-1 for hashing
ZIP for compression

Key management

I need to have Bob's public key on my keyring if

I want to send Bob an encrypted message
I want to verify the authenticity of a message which appears to have come from Bob

So, how do I get Bob's key onto my keyring? Here are some ways in which Bob can give me his key in a secure way:

He can give it to me physically, e.g. on his business card, on a floppy disk/CDROM/. . .
He can read it to me on the phone (assuming I can recognise him)
He can register with Verisign, but this is expensive and inconvenient and rather against the universal spirit of PGP.

More often, I will get Bob's key in an insecure way. . .

I get it from his web page
He sends it to me by email
I get it from an untrusted PGP key server

. . . and then I will verify it, e.g.

By reading a hash of it on the phone (assuming I can recognise him)
By checking a hash of it obtained in a secure way
By establishing a key-signing chain like the one with A1, A2, . . ., A20 above. This is the basis for. . .

The web of trust

A key in your public keyring has the following attributes associated with it:

The owner
The owner trust, assigned by the user. It is a measure of how much the user trusts the owner to sign keys. Values are

ultimate trust: the owner is the user
complete trust: the owner is always trusted
marginal trust: the owner is usually trusted
untrusted: the owner is not trusted
unknown

Zero or more signatures, each one associated with a signatory trust. It takes the same range of values as the owner trust. If the signatory's key is in the keyring, then its owner trust is used; else, unknown is used.
The key legitimacy, computed by PGP from the collection of signatory trust fields. If a signatory has owner-trust ultimate, then the key legitimacy is set to complete. Otherwise, PGP computes a weighted sum of the trust values. A weight of 1/X is given to always-trusted signatures, and 1/Y to usually-trusted signatures, where X,Y are set by the user (defaults: X=1, Y=2). When the sum reaches 1, the legitimacy is set to complete. Thus, X always-trusted signatures or Y usually-trusted signatures, or some combination, is needed for you to consider a key legitimate.

The diagram below is reproduced from William Stallings' excellent book, Cryptography and Network Security [2]. These diagrams are copyright 2003 by Pearson Education Inc., and are not covered by the Gnu Free Documentation License which covers the other parts of this document.
Example web of trust

The diagram illustrates how signature trust and key-signing combine to produce key legitimacy. The user (marked "you") always trusts agents D, E, F, and L to sign other keys and partially trusts users A and B to sign other keys. The arrows show who has signed whose key.

X may sign Y's key, and also trust Y. Example: you and D. You're best friends, or frequent associates.
X may sign Y's key, without trusting Y. Example: you and C. In this case, you assert you know it's C's key, but you don't necessarily have reason to believe in C's judgment.
X may not have signed Y's key, but still trust Y. Example: you and L. You're friends, but you haven't had much electronic communication yet.
X may not have signed Y's key, and not trust Y. Example: you and P, or you and R, or you and S. They don't know each other.

Getting started with PGP/GnuPG

Look to see what support your mail client has. If none, change to Mutt if you like an ascii text-only client, or Mozilla Thunderbird if you want a GUI. They're both free.

Why does no-one use it?

Sadly, nearly no-one uses PGP. Among the 80 staff at SoCS, none of them use it regularly. Among the 73 PhD students, two use PGP regularly. Yet these people are among the most computer-literate people you can find, and they also have the right sort of political profile to be interested in PGP. I think there are several reasons why PGP is not much used.

It's not considered necessary. There's not that much call for encrypted email, and not that much email forgery. (However, phishing is on the increase, and spam could easily be solved if everyone used PGP. So this reason will disappear soon.)
It's commonly felt that, since there is no such thing as 100% security, you might go to a lot of effort and still be compromised. The cryptography is almost certainly secure, but all the bits around the edges are not. You can be tricked into accepting illigitimate keys. And implementations can have bugs.
It's quite complicated. You need to spend a day to understand it properly. And even then, understanding is not guaranteed!
It's a hassle. You need to maintain your keys, your web of trust, you need to configure your mail client.

Why Johnny can't encrypt is an interesting article attempting to explain why people can't/don't want to use PGP. The problems here are among the most difficult ones in computer security. I think they can be overcome, and I think they will have to be in the long term, as attacks on privacy (including identity theft, spam, phishing) continue to increase.

Sources

S. Garfinkel and G. Spafford, Web Security, Privacy & Commerce, O'Reilly, Second edition, 2002. There is very readable and good information about PGP/OpenPGP in Chapters 4, 6, 7.
William Stallings, Cryptography and Network Security, Principles and Practice, Prentice Hall, 1999.
The Gnu Privacy handboook is a good intro to getting started with GPG (at least under Linux; not sure about the situation for other operating systems)
Mutt is an easy-to-use text-based email client which can easily be set up to use PGP or GPG, for email signing, signature verification, and encryption/decryption.

Trivia:

VeriSign dead certificate: After the cert VeriSign used to sign other certs expired, the chain of trust was broken, leaving some aps unable to set up a secure connection. These apps then defaulted to trying to access Verisign's certificate revocation list server (crl.verisign.com) which, faced with a huge extra load, buckled under the pressure.

End