Fabulous Adventures In Coding
Eric Lippert is a principal developer on the C# compiler team. Learn more about Eric.
A lot of people really love the idea of cryptography. To computer geeks like us there is nothing cooler than the idea that computing relatively simple arithmetic on a message can enable you to communicate secretly with anyone in the world, even if there are eavesdroppers. Unfortunately, this means that there are a lot of computer people out there who are enamoured with the idea of creating their own cryptosystems, or their own implementations of the cryptosystems invented by others. It also means there are a lot of software product managers who are convinced that security equals cryptography, and that their products will magically become "secure" if only there is more crypto in them. I've gotten a fair number of questions over the years about how to add crypto to applications -- a subject that I am actually not an expert on -- and most of the time the answer is "don't". Many times the question comes from a developer who, though an expert developer of applications in their line of business doesn't "get" the basic idea of cryptography. As a public service, let me lay it out for you. The fundamental idea of modern cryptography is this:
The strength of the security of a large quantity of data -- known as the "plaintext" -- against discovery or modification by a motivated attacker depends upon the security of a small quantity of data -- known as the "key". (*)
That is, modern crypto is essentially a form of mechanical advantage. With a gearing system or a lever you can turn a small motion into a large motion. With a strong cryptosystem you can turn the security of a 1 KB key file into the security of a 10 MB data file. Cryptosystems do not manufacture new security, any more than a lever manufactures new motion. Cryptosystems turn the security of one thing (the key) into the security of another much larger thing (the plaintext).
It is the failure to understand that fundamental idea that underlies most of the questions I get from non-crypto experts about implementing crypto in their applications. Non-crypto experts get enamoured with the math of the cryptosystem but that is not the part that provides the security. The part that provides the security is the security of the key. The cryptosystem itself (or its implementation) might be weak or strong, but even the strongest modern cryptosystem depends fundamentally on the correct management of the keys for its security.
Before the 1970's, all modern cryptosystems were "shared key" systems. That is, if Alice wanted to send a message to Bob over an insecure channel that had attackers attempting to either read or modify the message, then first Alice and Bob would somehow communicate a secret shared key over a secure channel. Once Alice and Bob both had the shared key, Alice could encrypt the message with the shared key, send it over the insecure channel, and Bob could decrypt it with the shared key. Bob would then have the plaintext message, but the eavesdropper would only have the encrypted message. (There are also techniques in shared-key systems whereby Bob could verify that no one tampered with the encrypted message while it was in the insecure channel.)
Clearly the security of this system depends entirely on there being a secure channel over which Alice and Bob can negotiate what their small shared key is. If they try to exchange the secret key over an insecure channel then an eavesdropper can determine what the secret key is, and it's no longer a secret. (As we'll see later, a more aggressive "man in the middle" can cause even more havoc.)
You might immediately wonder why Alice and Bob need to use crypto at all if a basic assumption is that they have a secure method for key exchange. Why not just use the required-to-be-secure channel for sending the unencrypted text? The point is that the secure channel might be extremely expensive, or it might be available only at certain times. For example, the "secure channel" might be that Alice and Bob meet for coffee in Seattle in their hidden underground bunker, decide on a secret key, and then Alice moves to Switzerland and Bob moves to the Cayman Islands, and they can no longer cheaply meet for coffee. But they can still communicate securely after their key exchange, even if they are no longer in the same room together.
The security of the system also depends upon them both Alice and Bob being able to keep that key a secret. If Alice or Bob reveals the key to a third party -- say Eve, the eavesdropper -- then Eve can discover the plaintext of every message sent over the insecure channel. Worse, if the key is discovered by Mallory -- the "man in the middle" modifying the message -- then she can not only discover the plaintext but can modify the plaintext, encrypt the modified message with the secret key, and send the fake message to Alice or Bob, purporting to be the other.
What about public key cryptosystems? Don't they solve this problem? Turns out, no. Now you have four key management problems. Let me explain:
The idea of a public key cryptosystem is that there are two keys. One, the private key, is kept secret. The other, the public key, is -- you guessed it -- public. A message encrypted with the public key cannot be decrypted with the public key, but it can be decrypted with the private key, and vice versa. Alice and Bob both have a key pair; they do not know each other's private keys, but they do know each other's public keys. To send a message to Bob, Alice encrypts it with her private key(**), and then encrypts that with Bob's public key. She sends the twice-encrypted message over the insecure channel to Bob. Bob decrypts it with his private key, and then decrypts the result with Alice's public key. Now he knows that only he could read the message, because only he has his private key. And he knows that it was not tampered with, because only Alice's public key could decrypt the message. Therefore the message was neither read by Eve nor tampered with by Mallory.
Like I said, we now have four key management problems whereas before we had one. Before, Alice and Bob had to securely exchange their private key and then keep it secret. Now Alice and Bob both have to keep their private keys secret. If Bob's private key is compromised then Eve can read any message sent by Alice to Bob. And if Alice's private key is compromised then Mallory can send a fake message to Bob purporting to come from Alice.
That's two; what are the other two key management problems? I completely glossed over the most important part of the system! The detail that the security of the entire system rests on is that bit above where I said "but they do know each other's public keys". Somehow they had to securely exchange public keys. Why's that?
Suppose Alice and Bob are sending each other their public keys. How do they do that? If they do it over an insecure channel, it does not matter if Eve can read the public keys. They are public, after all. But it matters very much if Mallory can modify the keys in transit! If Alice sends her public key to Bob over an insecure channel then Mallory can intercept the message and replace Alice's public key with Mallory's public key. Mallory now knows Alice's public key, and Bob believes that Mallory is Alice! When Alice sends a message to Bob, Mallory can intercept it and replace it with a different message encrypted with Mallory's private key and Bob's public key. Bob decrypts the message with his private key and Mallory's public key, believing it to be Alice's public key, and Mallory has tricked Bob into thinking that she is Alice.
Similarly, when Bob sends his public key to Alice, Mallory can intercept it and replace it with Mallory's public key. When Alice sends a message to Bob she encrypts it with her private key and Mallory's public key, thinking that it is Bob's public key. Mallory can intercept it, decode it with her private key, read the message, and re-send it along to Bob, encrypted with Bob's real public key.
Somehow there has to be a secure channel by which public keys are exchanged. Remember, the entire point of crypto is to turn the security of a small amount of data into the security of a large amount of data. If the keys aren't secure -- either because the private keys are compromised or the public keys are not correctly associated with their real owners -- then the communication is not secure at all.
This is not of theoretical concern; we have to solve this problem in real life. When you go to a web site that is going to take your credit card number, you want some assurances that first, no eavesdropper is going to be able to see that credit card number when it goes over the wire, and second, that when you send your credit card to a web site, you really are communicating with the real web site, not a fake hacker web site that looks just like it. You might not know the public key of the web site! Without a secure mechanism to obtain that public key, you might be obtaining the man-in-the-middle's public key.
This problem is in practice solved by both the client (you) and the server (the web site) agreeing to trust a third party called the Certifying Authority, or CA. When the web site sends you the certificate containing their name and public key, the certificate is encrypted with the CA's private key. By decrypting it with the CA's public key, you can verify that the CA vouches for that web site actually being associated with that public key. Of course, if you do not trust the certifying authority, or the web site does not obtain certification from that certifying authority, then the key negotiation fails and the browser gives you some error message about the certificate not being verified.
But hold on a minute. Now we have yet another key management problem. The CA has to keep their private key a secret, and the CA has to somehow tell you what their public key is without being attacked by a man in the middle purporting to be the CA! We seem to have not solved the problem at all, but rather just pushed it off another level. How do we finally solve this problem once and for all? Can we use even more crypto?
Nope. This is the point where the crypto stops. (***) It has to stop somewhere; again, the point of crypto is to turn the security of a small thing into the security of a large thing; that security has to come from somewhere originally, just as the energetic motion of a lever has to come from somewhere outside the lever mechanism. The secure transmission of the CA's public key is the piece that has to be accomplished without using any crypto. How you accomplish that is up to you; typically the operating system comes pre-installed with a list of known public keys of certifying authorities that have been verified independently by the operating system vendor. New CA "root" certificates can also be installed by your machine or network administrator. The CA roots are the organizations you trust to make security-impacting decisions on your behalf.
I seem to have strayed somewhat from my original point, but I hope I've made myself clear: the hard part of a secure design that uses crypto is not the math. When adding crypto to an application, the fundamental question you should be asking yourself is not "what math am I going to do on the plaintext to encrypt it?" The fundamental question is "how are my users going to generate keys, securely exchange secret keys or public keys, and keep the secret keys private?" The security of the entire system rests upon being able to leverage the secure generation and distribution of the keys into the security of the message, so solve the key management problem first.
(*) A cryptosystem is strong or weak to the extent that it delivers on this fundamental goal. If the security of the message can be compromised without the user compromising the key then the cryptosystem is weak. The goal of modern crypto is to create cryptosystems that deliver on this promise.
(**) In a realistic scenario she encrypts a hash and appends that to the message, because that is higher performance. But let's gloss over that detail.
(***) Just to complete the sketch: the way HTTPS actually works is that a shared "session" key is securely exchanged between the client and the server. The shared key is then used to encrypt and decrypt all the messages sent between the client and the server. As we already discussed, to exchange that shared key we need a secure channel. To obtain a secure channel, the client and the server agree upon a mutually trusted CA. The server convinces the client that the agreed-upon CA vouches for the server's public key, and so the client now has the real public key of the server. The client can then suggest a shared session key to use for the rest of the communication, and send it to the server encrypted with the server's public key. So: the secure transmission of the shared session key relies upon (1) the secrecy of the server's private key, (2) the secrecy of the CA's private key, and (3) that the client and the server both have an accurate copy of the CA's public key, obtained through some non-crypto-based secure channel. The cryptosystem leverages the secrecy of two private keys and the successful transmitting of one public key into the security of the messages transmitted in the session. If any of those keys are compromised then the whole system falls apart. (To deal with that problem, CA's also provide the service of publishing a "revocation list" of servers that have lost control of their private keys, so that you know to not trust those guys.)
I wouldn't generalize into saying the public and private keys are equivalent. For example, in RSA, you have two keys:
The private key is two numbers: the product of two primes, and a second number cleverly derived from those primes
The public key is two numbers: the same product of two primes, and a second number that is probably 65537
If you have the private key, you can derive the public key rather quickly, because in general the public exponent is a very small prime to improve encryption speed.
@Dylan: Yeah, there was just a very similar discussion at StackOverflow a few weeks ago. In RSA the keys are not interchangeable, but in some other cryptosystems, it works differently.
See here: stackoverflow.com/.../naming-issue-of-public-and-private-key
There is a lot of confusion about cryptography around.
I meant, there is a lot of confusion, because some things look a bit complicated, the same terms are used in different contexts, and some cryptosystems work differently than the others.
Very good article about cryptography
This blogs make us learn a lot.
Just found your blogs, haven't been able to stop reading. Great articles, crypto systems is one my favorites especially as it pertains to the need to apply cryptography algorithms to the most inconsequential systems.