Public Key Cryptography

We have been discussing secret key (also known as symmetric) cryptography along with related cryptosystems and possible attacks. Last time we discussed the problem of key distribution and looked at an example system (Kerberos) for key management. Today we will discuss another approach to cryptography known as public key or asymmetric cryptography. But first, lets try to establish an intuition for why we might want to consider an alternative to a secret key system using key distribution, and consequently what we're looking for in public key cryptography.

Problem of Key Distribution

As you may have noticed from the previous lecture on Key Distribution, there is one difficultly inherent in all KDC mechanisms. Specifically, it seems like you must already have agreed on a key in order to securely distribute the next key. This requirement causes problems because it won't work after your system has been compromised (when you have to start over again) and it won't work initially (when you have not yet agreed on a key). Basically, shared key distribution is a sham. You move the vulnerability away from "people trying to figure out a message" to the KDCs.

However, one can imagine a physical solution to the problem "Alice sends a secret to Bob, but they don't share a key", which is identical to the two problems mentioned above. Consider the following example:

1. Alice puts a secret in a box, which she locks with her own lock. Only Alice has the key to this lock.
2. Alice then ships the box to Bob.
3. Bob adds his own lock to this box in parallel, so that now the box has two locks.
4. Bob then ships the box back to Alice.
5. Alice, knowing that the box is secure with Bob's lock, then takes her own lock off the box (with her key).
6. Alice sends the box back to Bob.
7. Bob then removes his lock and receives the secret (which could have been a new shared key).

We have successfully shared a secret without exposing it, and without possessing a shared key initially. When we look at this mechanism as a whole, we can get an intuition of what exactly we need in a lock. As in the above system, we don't care who is able to actually lock our mechanism, but we want to make sure that only somebody with a key can unlock it. This is essentially the same as saying it should be cheap to unlock our mechanism with the key, but very expensive to try to unlock it without the key.

Let's try to look at this ideal lock in a mathematical sense. What we're looking for is called a 1-way trap-door function. To apply this idea to a cryptosystem, we would want an encryption mechanism that is a 1-way function, in other words, easy to compute but hard to invert. Our decryption of this resulting value should be easy if you know about the trap door. An example of a mathematical function that is very hard to do unless you know something about it is finding factors of numbers.

Diffie - Hellman Key Exchange

Now lets examine an implementation of a 1-way function. Diffie-Hellman Key Exchange allows two principals to agree on a shared key even though they exchange messages in public. In the protocol given below, there is no authentication, so either side could be be spoofed by an active wiretapper. The protocol can easily be extended into one that does also implement the necessary authentication.

The first step is to choose a large prime number p (around 512 bits). The second is to choose an integer g where g < p (with some other technical restrictions.) The protocol works as follows:

(T_B)^S_A
= (g^S_B mod p)^S_A
= (g^S_B)^S_A mod p
= ((g^S_BS_A) mod p).

(T_A)^S_B
= . . .
= ((g^S_AS_B) mod p).

A wiretapper can see all the messages that are sent, but can't do anything without having a fast way to compute logs in finite fields, which is assumed to be hard. One problem with Diffie-Hellman is that it does not generalize to send arbitrary messages.

Physical Analogy for Diffie-Hellman Key Exchange

We can borrow a physical analogy (from The Code Book) to better understand the principles underlining Diffie-Hellman key exchange. Consider the following:

1. We have two principals,A and B, each with a 3-liter paint pot that contains 1-liter of yellow paint. We will use E to denote a passive wiretapper. We can assume that mixed paint cannot be deconstructed into original colors.

2. A adds to her 1 liter of yellow paint a secret color S_A. B also adds to his 1 liter of yellow paint a secret color S_B.

3. A and B swap pots. E is able to observe the 2, 2-liter mixtures be exchanged, but E cannot deduce what color was added to either mixture, E can only deduce the relative color balance in the combined 4 liter mixture: 2 * yellow + S_A + S_B (Y:Y:S_A:S_B).

4. A adds S_A to B's pot. The result (Y:S_A:S_B) is the key. B adds S_B to A's pot. The result (Y:S_B:S_A) is the key.
   Notice: A and B have computed the same key, but E gets a different one.

Public Key Cryptography

In public key cryptography, some keys are known to everyone, so it would seem that the key distribution problem vanishes. The approach was first published in the open literature in 1975. (Recently declassified documents in Great Britain suggest that public key cryptography was known there before 1975.)

The basic idea of a public key cryptosystem is to have two keys: a private (secret) key and a public key. Anyone can know the public key. Plaintext to a principal B is encrypted using B's public key. B decrypts the enciphered text using its private key. As long as B is the only one who knows the private key, then only B can decrypt messages encrypted under B's public key.

Some public key cryptography schemes also allow plaintext to be run through the decryption algorithm (using the private key). What is produced is referred to as signed text and it can be "deciphered" using the public key. Only the possessor of a private key can create text that is decipherable using the public key. The functionality of signed text cannot be replicated using secret key/symmetric cryptography.

Public key cryptography is usually much slower than secret key cryptography, so it is rarely used to encrypt an entire message. Typically a message is encrypted using shared key cryptography (with a secret key). That secret key is then encrypted using public key cryptography, and the encrypted message and key are sent. This is known as hybrid encryption. This method can allow for complex structures in implementing our secrecy requirements (see Figure below) : e.g. "message is readable by A,B,C,D".

History of Public Key Cryptography

(United States)

• 1975: Diffie imagines asymmetric cryptography (Diffie + Hellman)
• 1976: Diffie-Hellman key exchange
• April 1977: RSA (Rivest, Shamir, Adelman)

(United Kingdom)

• 1969: Government Communications Headquarters (GCHQ) - succesor to Bletchly Park - asks James Ellis to look into the key distribution problem. Ellis recalls a Bell Labs report about adding noise to a signal, transmitting it, and then removing the noise.
• 1973: Clifford Cocks (recent Cambridge Math Ph.D) joins GCHQ. He hears about Ellis idea and searches for a suitable function, and he thinks of RSA. GCHQ now could do public key encryption.
• January 1974: Malcolm Williamson, in an effort to try to break Cock's work, discovers Diffie-Hellman.

Uses of Public-Key Cryptography

Secrecy is obtained when principal A encrypts a message m using B's public key. Thereafter, the only way to decrypt m is to know the private key of B. (see Figure below)

In secret key cryptography, doing authentication requires having a different key for each pair of principals; in public key cryptography, each principal needs to know just its own private key. An example of a public-key authentication protocol is:

A hash is a function that digests information. It takes a message as input and outputs a short bit string (say, 128 bits). An example of a 1-bit hash would be a function that returns the parity of the message. Think of a hash as a succint summary of a message that has four properties:

• It is computationally infeasible to determine the input message m based on the digest of that message hash(m), which means the digest must convey no information about the original message.
• It is infeasible to find any message with a given digest value, which means we can't attack by replacing a message m1 with another message m2 with the same hash value.
• It is infeasible to find 2 messages with a given hash. If we don't have this property, then it is possible a person could sign a message, then the signature could be cut and pasted on to another message with the same hash.
• And finally, changing even 1-bit of the input gets completely different output, so that syntactically similar messages generate very different outputs and it is not likely that two bit-strings with the same hash value could be mistaken for each other.

These properties make a message-text substitution attack difficult given a hash. Specifically, suppose that message m is sent along with a signed hash value for m. The properties of the hash function would make it difficult for an attacker to substitute another meaningful message that has the same hash value as the original.

We can easily have multiple signatures (see Figure 1 below), as well as build up a chain of signatures which establishes a valid history (see Figure 2 below). This chaining of signatures can be used to prove such a claim as "Alice had signed the message when I got it.".

Examples of Public-Key Cryptosystems

We will now examine a few examples of public key cryptography systems.

Merkle's Puzzles

A wiretapper C could steal the million puzzles. However, C would need to crack all million of the puzzles in order to discover the secret key. (If the wiretapper didn't know the pre-arranged string, then it can't even use a known-plaintext attack.) Since cracking each puzzle requires at least 2 minutes, the wiretapper would need on average 330 days to find the key.

RSA

• Choose two large primes (say, 256 bits each) p and q. These must be kept secret.
• Compute n = p*q. The number n is not secret. This systems works under the assumption that factoring n is computationally intractable.
• Chose e such that e is relatively prime to (has no common factors other than 1 with) (p-1)*(q-1). The number e is usually chosen to be small. 3 and 64437 are popular.
• The public key is the pair (e, n). Note that e doesn't have to be secret. The private key is (d, n) where d is the multiplicative inverse of e mod (p-1)(q-1).

A lot of number theory is needed to prove that this technique works. One necessary theorem is: m = (m^e mod n)^d mod n.

Certification Authorities (Public Key Infrastructure)

A certification authority (CA) is a trusted server that generates certificates of the form {name, public key}_CA where CA is the certification authority's signature (private) key. All hosts are preconfigured with the certification authority's public key, therefore any host can check the signature on these certificates. Note that a CA is more attractive than a KDC because a CA it doesn't need to be on-line. Certificates can be stored anyplace and forwarded anywhere as they are needed.

One problem is that if a principal's private key is compromised, then all those certificates (wherever they are) will cause the wrong public key to be used. Since there isn't a single authority that everyone trusts, updating all those certificates is not feasible. A solution is to require that certificates have expiration dates. This will limit damage but not rule it out entirely. Next lecture we will discuss the issues in somewhat more detail.