So, I mentioned in an earlier post, that I'd lost my PGP private key and keyring; and that this was kind of a major irritation for me. Now it's time to explain, in excruciating detail, what that is, and why it's important.
First things first, what the heck is PGP?
PGP stands for "Pretty Good Privacy", an encryption and key management scheme (and associated utilities) written by Phil Zimmerman (A.K.A. PRZ); based on the earlier work of Whitfield Diffie, Martin Hellman, and Ralph Merkle, on something called "public key cryptography".
PGP was published over government objections in 1991. It's a great story really. The feds spent 5 years trying to put PRZ in jail for exporting controlled weapons (which is what they classified encryption as), failed miserably, and he eventually moved to Ireland (I think he's back in the U.S. now).
It's safe to say that PGP, in one implementation or another, is the most used interactive encryption software in the world. I say "interactive", because just about every web browser has SSL encryption software built in (which is a similar, but different encryption scheme), but most people never interact with it specifically; they just know that when they type in HTTPS instead of HTTP, and the little key or lock shows up in the browser, that they are "secure".
In my particular case I use GPG, the free and open source GNU implementation of PGP; both because it's free and open source, and because there are versions of it for every operating system I use (and pretty much every OS I don't use as well).
There is also a commercial implementation of the PGP standard, called simply enough, PGP (though the fact that they named the software after the standard confuses people as to whether they "really have PGP" if they don't use the "Official" commercial version); as well as numerous other implementations, both free and commercial, and plugins for other applications etc...
Theoretically, all of these different implementations should work together, because they all implement the same standard; though sometimes (frequently?) incompatibilities can pop up; especially between the open source and commercial implementations.
As I mentioned in passing above, PGP is what is called a "public key cryptography" scheme; and it works pretty simply in concept (though the math behind it is complicated).
The basic idea behind it, is that when two people want to talk to each other securely, they shouldn't have to know or trust each other first.
... Now there's a logical leap that many people seem to have a problem making; and in order to talk about it, we need to talk about what exactly cryptography is, and a bit about how it works.
At it's most basic, cryptography is (literally, from the greek), "secret writing". It's any means of writing a message in a way that is meaningful to those with the knowledge to understand it, but meaningless to all others.
Now, there are a heck of a lot of ways of doing that, but they almost all break down into two basic categories, ciphers and codes.
A code is a way of making writing secret by using symbols. A red Octagon is a way of writing "stop" in code for example, as is the sequence ... - --- .--.
The symbols of a code can be anything, pictures, shapes, sounds, even numbers or letters. The most well known code (at least that we explicitly think of as a code) in the world is probably Morse code (as above) where dots and dashes represent number and letters. Another one that is commonly known, is the admiralty radio code, also called the "Q code", where entire paragraphs can be expressed as groups of three letters, (that are convenient to tap out in morse code).
The important part is that each symbol has meaning, but that meaning isn't understood by someone who doesn't know the code. So in Q code, the letters "QRN" aren't spelling any meaningful word; but if you know the code, you know they mean "I'm having trouble understanding you because of radio interference".
Of course most people don't think of these as codes in the cryptographic sense (and in fact there is an entire academic field of study about symbology and the representation of meaning, that has very little to do with cryptography, called semiotics); I'm just using them as an example to illustrate the point.
Generally, when people think of cryptographic codes, they are thinking more along the lines of codebooks; which are kept secret, and which usually have groups of letters and numbers which are used to represent other words, letter, numbers etc...
Again, the important part here is that each symbol has a distinct meaning that it represents, which is not apparent to someone who doesn't know the code. So the code 999 doesn't mean nine hundred and ninety nine; it actually means "Oh god, Oh god, we're all gonna die".
Ciphers are a completely different way of making writing secret. Instead of using symbols to make things secret, they use math.
Putting the difference more simply, if a bit obscurely, code is representational, ciphers are transformational... or perhaps more clearly, codes translate, ciphers transform.
Huh?
Codes translate symbols; like from one language to another. In a code, the meaning is there in the symbols, you just can't understand it without the code book; much as you can't understand Urdu without a phrasebook. If I say salgirah mubarak, you don't know that it means "Happy Birthday" in Urdu.
Critical to understanding the difference between codes and ciphers though, is understanding that just because you don't know the meaning, doesn't mean the symbols have no meaning.
Ciphers TRANSFORM, not translate; so each individual symbol of the enciphered text (actually called ciphertext) has no actual meaning, without the cipher, and the ciphers key.
The ASCII octal code sequence 062060060070 always means "2008", even if you don't know the code and can't read it; whereas the ciphertext 062060060070 is completely meaningless without the math.
I realize that the distinction there is lost on some, but trust me, it's important.
From a strictly practical standpoint there is a huge difference: A code has to have symbols representing everything you want to say, or a way of making up new symbols built into it; a cipher doesn't, because there is no meaning to any particular symbol, it's all just math in and math out.
Ok, so that's what cryptography is, and what ciphers are specifically. Now, how does it work?
Well, there's a couple elements here:
First, you need a cipher; which is any algorithm (an algorithm is any process of applying structured transformation to any set of information) designed to make information secret.
Second, in what most people think of as "conventional" cryptography, there has to be what is known as a pre-shared secret, or pre-shared key, often referred to by the acronym PSK.
So, let's say two parties want to communicate securely. Those two people decide to communicate using a cipher, they decide on the cipher, and they decide on the key for the cipher.
Remember, the cipher is the math itself; the bit that actually makes the writing secret. The key, is that part that lets two people use the same cipher that other people are using, without anyone else who knows the cipher being able to read what you wrote. I can tell the whole world I'm using AES encryption, and not worry that they'll be able to read my messages; because the key is secret, the cipher doesn't have to be.
There are of course ciphers without keys, but they are far less secure; and far less convenient.
To illustrate the difference, think of the simplest cipher everyone learns as a kid, the alphabet transposition cipher (also called a simple substitution cipher). You know, that's the one where A is 1, B is 2 and so on (in fact, this is so simple that it's almost a code, but in reality it is a mathematical transform, therefore a cipher).
Now with a simple cipher, anyone can read the message as soon as they know the cipher. With a keyed cipher though, you add in a unique element, so that someone who knows the cipher can't read your message, unless they know the key as well.
For example, knowing that I'm using a simple alphabet transposition, you know that "3,1,20" is "cat".
Let's use the same simple alphabetic substitution, but we'll add what's called an "offset vector", and that will be our key.
An offset vector is just a fancy way of saying "add or subtract this number to your result to get the real number"; so your key, is the number you add to each digit, to get the real message. In this case we'll add it to encrypt, which means we subtract it to decrypt. This is the simplest type of keyed cipher, and has been in use for thousands of years (the romans and greeks both used similar keyed ciphers).
So, for this example I'm going to use 3 as our key. Given the transposition cipher, and the key "3", you can decrypt the digits 7,18,10, as "dog"; by taking each number, and subtracting 3 from it, then transposing back from numbers to letters.
Importantly, you can't know what I've written, unless you know both the cipher, and the key; and in order for you to decrypt the ciphertext, I had to share the key "3" with you beforehand.
This is called "symmetric cryptography", because both parties are using the same cipher, and the same key to encrypt and decrypt it.
The problem with internet communications (or really any communications over a distance) is how do two parties agree to a pre-shared key, if they can't talk to each other in person? A phone could be tapped, someone could be reading the mail etc... (that's called a "man in the middle" attack, which I'll explain deeper later)
What about if one person wants to send secure communications to someone they don't know yet?
Well, the way around it, is not to actually send the keys over the wire; or for that matter, to ever communicate the decryption keys to each other at all.
Okay, but how can I decrypt what you send to me, if I don't have the key you used to encrypt it?
This is where what is called "asymmetric cryptography" is applied.
In asymmetric cryptography, we both agree on an encryption scheme, and a cipher, but we don't share decryption keys in advance.
Again this is where people start to say "huh?".
What we do is, we both come up with a pair of keys; which are mathematically related, but which can't be derived from each other (so if I know one of your keys I can't figure out the other one), . Then we use a cipher that lets you encrypt with one key, and let's me decrypt with the other key.
Remember, the keys are mathematically related, but you can't figure out one from the other. That's why this works... it's also why I said the math is complicated.
Ok, next part is, because of that split key thing, you can encrypt messages to me by having half of my key pair, and I can decrypt with the other half; and vice versa, I can encrypt to you using half of your keypair, and you can decrypt using the other half.
Different keys are used to encrypt and decrypt, thus "asymmetric cryptography".
So, it takes four keys instead of one; but now, I never have to send the key I'm using to decrypt your messages to me over the wire, and you never need to send the key you're using to decrypt messages sent to you.
Pretty neat eh?
Just one more step though. What if we don't know each other beforehand?
This is where what is called "Public Key Cryptography" comes into play.
So I explained that in asymmetric cryptography, each person generated two keys, and that messages were encrypted and sent to you using one key, and that you decrypted those messages using the other one.
Well, since you never have to send the decryption key to anyone, you can keep that secret; but you can give ANYONE your encryption key, because they can't decrypt your messages with it.
The "public" part comes in when you don't want to have to pre-share your encryption key. Again, because you don't need to keep your ENCRYPTION key secret (just your decryption key), and anyone can use it without contacting you first, presuming they can get it. If you want unknown parties to be able to send you encrypted messages without your prior knowledge, you can just publish your encryption key out to the world. That way any time anyone wanted to send you secured info, they can just look up your encryption key.
Of course the system works, because you have a public key that you publish to the world, and a private key that you keep secret. If you ever lost the private key, you wouldn't be able to decrypt messages people sent you with the public key; and if the private key is exposed, ANYONE can decrypt messages sent to you.
Now, that covers my public and private key, but what the heck is a keyring?
... and we're back to PGP again.
Put simply, a keyring is a list of, and copy of, all the keys you know and trust; formatted in a way that PGP can use them.
It's important to understand that PGP isn't the encryption keys, or the algorithms themselves; it's the scheme for how you use them all together.
What PGP does, is provide an agreed upon framework (a language and format if you will) for people to generate and manage keypairs; store, retrieve, and manage public keys in trusted way; as well as a standard way of negotiating encryption algorithms, and presenting data and keys to those algorithms, for encryption or decryption.
The whole thing forms what is called a Public Key Infrastructure, or PKI; which you may have heard somethign (possibly quite a lot) about; and which I will explain in a later post.
Part of that key management framework... in fact, just about the most important part; is a concept called "the web of trust".
The problem with a public key infrastructure, is that in order for it to be useful, everyones encryption keys have to be made public; and when you do that, someone can impersonate you by publishing an encryption key in your name. Unless you know who to trust, and what keys are valid; you can't send anything securely without first verifying the key with the person you want to send information to. The whole point of having the PKI, was so that you wouldn't have to do that.
That's where the "web of trust" comes in.
This is basically the idea that you may not know and trust that a key you got off the internet is valid for the real person you want to talk to; but you do know that your friends keys are valid, and they know that THEIR friends keys are valid and so on.
Ok, how does that solve the problem?
In the web of trust, each person designates any keys he knows are good, by cryptographically "signing" them with their own key (sign as in signature, not as in "detour"). Then, when you download a key off the net, you know it's good because you've signed the key, of a guy who signed the key you downloaded; and you trust the guy who signed the key.
Basically I trust Bob and Bob trusts Steve, so I trust Steve. Trust becomes a transitive property of the keyweb.
Yes, it's like VD. You're not just trusting your friends, you're also trusting everyone they trust, and everyone they trust and so on and so forth; so be careful who you trust.
Remember, one poison key that you sign as trusted, can poison hundreds or thousands(or in the case of important signers that LOTS of people trust, like public certificate authorities, millions) of other trust relationships, and make an entire portion of the web untrustworthy.
It all sounds much more complicated than it really is; and for the most part the system works; but those key relationships can get complicated.
This is why the keyring files are important. It's essentially a record of who I trust, and who trusts me; in the form of a copy of all the keys I've signed, a copy of the keys of everyone who has signed mine, and a copy of all the keys of people I've communicated with; as well as a list of keys I know to be bad or invalid.
All pretty important stuff.
Of course, if you lose your keys, you can always generate new ones; but that means you won't be able to decrypt communications sent using the old ones. More importantly from a web of trust standpoint, you won't know whose keys to trust unless you got the key directly from them, and no-one will be able to trust your key, unless they got it directly from you; because you wont have signed any keys as being valid, and no-one will have signed your key as being valid.
Cascading further, keys signed using your OLD key can no longer use that signature as part of their trust metric; but because you can't revoke a key without first having that key, no other member of the web can be notified that your old signature is invalid, except by manually updating them all individually.
This by the way is why personal keys should always include an expiration date; and then should be renewed and refreshed periodically. My old keys have all expired now; which means they are still usable to encrypt and decrypt, but the web of trust knows that they are not to be trusted.
For a serious user of encryption, this loss of a keyring is devastating. Losing the private key is a major inconvenience; but if it's got an expiration, it doesn't corrupt the trust web too badly; and it's usually acceptable to be unable to decrypt a message, because you can usually tell the person who sent it that you have new keys. What is NOT acceptable, is not knowing what keys to trust.
You can't simply assume that keys are valid and trustworthy; so when you lose your keyring, you have to rebuild your portion of the web. This means you have to go back and manually fetch, and verify all the keys of everyone you communicate with, then sign them again; and get everyone to sign your key again etc... etc...
Ok, so that was a bit obscure, and probably mreo than most of you ever wanted to know about encryption... and yet it was barely a thumbnail sketch. For purposes of length and clairty, I've GROSSLY oversimplified this, left out... oooh about 90% of even the absolute basics; and deliberately used technically incorrect but logically correct illustrations.
In fact I based this post off a greatly condensed and simplified version of the introductory chapter of some training materials I wrote a few years ago, when I was teaching a basics of encryption class.
Just to let you know what a "basic" course is, the class covered a full five days, 6 hours a day, with a maximum of 12 students per instructor; and over 200 slides of material, with several hundred pages of supporting materials.
Yes, that's the basic introductory course. The advanced course was another 5 days, required the intro course as a pre-requisite; involved passing a certification test on the introductory course, as well as pre-reading a rather long and obscure text book before taking it.
I do this for a living; and let me tell you, the reality of encryption tends to be a lot more complicated and messy than what I've described above. If you thought this last bit was hard to understand, you should see how confused and messy things get out in the world.
Update: Because there seems to be interest (and a lot of confusion) about this topic, I think I'll make it into a series, and expand and clarify in later posts. Go ahead and leave comments about specific questiosn or issues you'd like to see me address.
