Public Key Encryption

These days, most authentication procedures - including the way assemblies are signed - are done using public key encryption. You are probably familiar with the fact that public key encryption involves a public key and a private key, and that the public key is allowed to be made public while the private one must be kept confidential. In this part of the chapter we are going to have a deeper look at how public key encryption works under the hood. This will enable us to better understand how assemblies are signed and how ownership of assemblies is authenticated when they are downloaded.

The raison d'etre for using public key encryption is to solve two inherent weaknesses of symmetric encryption. These weaknesses both arise from the fact that the fact that both parties to a conversation need to know the key. This means that:

• Somehow the key needs to be transmitted. That's a real problem since if the key has to be transmitted over the network, there's a risk that the villainous Eve will discover it.

• Key management is a problem. If, for example, Alice wants to talk to someone else, without Bob listening-in, then she is going to need a different key for that channel. With a different key for every pair of people (or group of people) who might want to communicate, managing those keys is going to quickly become very difficult.

Public key encryption solves both of those problems. Let's go over how public keys work. Our earlier example using Alice and Bob demonstrated that encrypting a message required an algorithm and a key. Decrypting a message was different because it required a different key (encrypting with a key of 3 meant decrypting with a key of -3), although the algorithm was the same. In public key encryption, the algorithms associated with the two keys might be different too, but that fact is going to be irrelevant for our analysis.

Recall the situation for symmetric cryptography was this:

 S(P(M)) = P(S(M)) = M P(M) = encoded stuff that looks like garbage - you have to know what S is to decode it. S(M) = encoded stuff that looks like garbage - you have to know what P is to decode it. 

Now for public key cryptography we need to add one other requirement: we need to arrange things so that if you know P, then it's very easy to calculate S, but if you know S then it's next to impossible to work out P in a reasonable time. Mathematicians call working out S from P a trapdoor function, meaning it's very hard to reverse it.

In practice in real algorithms, the trapdoor function is achieved by using prime numbers. If you are given two large prime numbers, multiplying them together is easy. If you are given the product, however, trying to figure out what the two original primes were is a lot harder. So roughly speaking, in real public key encryption, P is the pair of original primes, S is their product.

So what happens with Alice and Bob? Well, they each have some software that can randomly generate a private-public key pair. Alice keeps her private key to herself (that's what we will call P), and tells Bob her public key (that key is the S - for "shared"). In fact, she doesn't just tell Bob. She tells everyone who's interested in knowing. She even tells Eve (it's not going to do Eve any good). Bob does the same thing - he doesn't use Alice's P and S, but instead generates his own P and S. And he keeps his private key to himself and tells everyone his public key.

Since S is publicly available you might wonder why I made an issue of it being easy to calculate S from P - why would anyone need to calculate it? The answer is that it's important when the key pair is initially created. P is usually generated at random and S immediately calculated from it. Alice will generate her P and S on her own computer so that P never needs to get passed around the network and so is kept secure, Similarly Bob generates his P and S on his own computer.

Now Alice sends Bob a message. Since she wants to keep it confidential, she encrypts it with Bob's public key and sends if off. Since the message was encrypted with Bob's public key, it needs Bob's private key to be decrypted. This means only Bob can decrypt it. Bob reads the message, then sends a reply back to Alice. He encrypts the reply with Alice's public key, which means only Alice can decrypt it. Eve has both public keys but she still can't read any messages. The situation so far looks like this:

There is a problem, however. We've gained confidentiality and data integrity. What we don't have is authenticity and non-repudiation. Eve might not be able to read any messages, but there's nothing to stop her from sending a message to Bob and signing it "Alice", and Bob has no way of telling that it is wasn't Alice who wrote the message (although Alice might be a bit surprised when she gets the reply back). And because we know that Eve can do this, it would be quite easy for Alice to send a message then deny having sent it. There's no way to prove that it really was her.

There is a very easy way to get the authenticity and non-repudiation, and keep data integrity, but we'll lose the confidentiality in the process. If Alice wants to prove her authorship of a message, all she has to do is encrypt it with her own private key. Now Bob can decrypt the message using Alice's public key. The fact that Alice's public key can be used to decrypt the message proves that it was Alice who sent the message. Alice can't deny sending it, because Bob can just hand over the encrypted message to a court and say "here - look. It decrypts with Alice's public key! This means it got encrypted with her private key, and no one else can do that". The only snag about this approach is that if the message has been encoded with Alice's private key, and her public key is freely available, that means that anyone can read the message. No confidentiality.

There is a way around that problem, however. All Alice needs to do is to encrypt the message with her private key, and then further encrypt the cipher text with Bob's public key. That meets all our requirements: no one except Bob can decrypt it, and Bob will have the proof that the message really came from Alice. The big win is that the private keys never have to be transmitted over a network. They can be kept strictly confidential, within an organization. We finally have a secure encryption system!

Although this solution looks ideal, for performance reasons public-key encryption is rarely used to encrypt entire messages. Instead, there are various techniques for confining the public-key encryption to a small part of the message while keeping security, some of which we'll see later in this chapter. One of these techniques is the SSL security that you'll be used to seeing when connecting to secure web sites. Kerberos security is also based on very similar principles.

Key Size

Since the way that messages are cracked is by trying keys at random until you find the right one, the main factor that affects the safety of your encoding is how big the key is. In our earlier example of transposing letters, there were only 26 possible values for the key. So a computer could try every possibility in a tiny fraction of a second. Modern cryptography algorithms, however, have large keys, which would require a cracker to try out huge numbers of possible values. For symmetric encryption, there have traditionally been three key sizes in common use: 40-bit, 56-bit, and 128 bit, though other sizes are used too, and keys used in public key encryption tend to be larger. Bear in mind that the number of possible key values grows exponentially with key size - a 40-bit number can have up to 2 to the power of 40 (that's one million million) values, although not necessarily all those values are legitimate keys. For every bit you add, you double the number of values.

The following story should give you some idea of the relative risk: in 1997, to test how secure cryptography was, RSA Data Security, Inc. offered a reward for the first person to crack a message encoded with a 40-bit key. It took a college student, Ian Goldberg, three and a half hours to win the prize. Later in the year, a similar challenge was issued by DES using a 56-bit key. It took a large team of people working together to pool their computing resources three months to win the prize. To my knowledge, there's no public record of anyone having ever cracked a 128-bit key. In general, 40-bit keys will survive a casual attack but not a determined attack. 56-bit keys are reasonably secure in the short term. 128-bit keys are for all practical purposes impregnable in the short to medium term. However, in the long run, no key size is going to be secure against time and improvements in computer speed. The longer the key you choose, the longer your data will stay impregnable for.

Many countries impose legal restrictions on the use or export of cryptography software, based on the key size, although in general these restrictions have eased considerably in the last couple of years. For example, it used to be illegal to export more than 40-bit software from the USA to any other country, which lead to the odd situation that people in much of Europe and Canada could use 128-bit encryption software only if it was written outside the USA! These days, the regulations are more liberal and are mostly aimed at preventing export of encryption software to countries regarded as representing a high security risk. If you do write encryption software, though, you will still need to carefully check any legal restrictions your own government imposes on the use or distribution of that software. (Microsoft does, of course, make every effort to comply with those restrictions in the software it places on Windows, so if you have a legal copy of Windows and .NET, you almost certainly don't need to worry about being allowed to do things like sign assemblies!)

Session Keys

We've seen how, in principle, public-key cryptography can be used to allow completely secure communication of messages, without the need for a key to be transmitted across the network. Although this sounds fine in principle, in practice it's almost never done that way. The reason? Performance. The algorithms in use for public-key cryptography generally involve treating blobs in the message as numbers and raising them to certain powers. That involves lots of multiplication, and it's very slow. In fact Microsoft claims that encoding a message using one of the public key algorithms takes about 1000 (yes, one thousand) times as long as encrypting the same message using a symmetric key algorithm such as DES. Because of this, what almost invariably actually happens is that public key cryptography is used to encrypt only the most sensitive information, with symmetric encryption being used most of the time. Session keys provide one example of this technique.

If a conversation is to be based on a session key, what happens is that most of the conversation will be encrypted symmetrically. However, prior to the conversation one of the parties will create a symmetric key and send it to the other using public-key cryptography. That key will then be the agreed key to be used for the duration of that conversation (or session), and will be thrown away afterwards - hence the name, session key. The result is huge encryption performance gains, but the conversation is for all practical purposes almost as secure as if public key cryptography had been used throughout. The session key is never transmitted in a form that Eve is able to read, so Eve still has to resort to the brute-force technique to figure out the key. The only benefit Eve has is she gets the same performance gains as Alice and Bob when she's trying to decode the messages. The trouble is, that's offset by the fact that the session key is only temporary anyway. Even if Eve does have some serious computer power available and somehow does manage to find the key, by then it's too late. Alice and Bob will have ended the session, the messages are probably out of date, and that key won't get used any more.

If you connect to a web site and see from the URL that the HTTPS protocol is being used, that means communications are being encrypted using a protocol based on the Windows Secure Sockets Layer (SSL) - and session keys play an important role here.