Crypto Jargon
Hash Functions
A hash function is a completely public algorithm (no key in that) which mashes bit together in a way which is truly infeasible to untangle: anybody can run the hash function on any data, but finding the data back from the hash output appears to be much beyond our wit. The hash output has a fixed size, typically 256 bits (with SHA-256) or 512 bits (with SHA-512). The SHA-* function which outputs 160 bits is called SHA-1, not SHA-160, because cryptographers left to their own devices can remain reasonable for only that long, and certainly not beyond the fifth pint.
Signature Algorithms
A signature algorithm uses a pair of keys, which are mathematically linked together, the private key and the public key (recomputing the private key from the public key is theoretically feasible but too hard to do in practice, even with Really Big Computers, which is why the public key can be made public while the private key remains private). Using the mathematical structure of the keys, the signature algorithm allows one:
- to generate a signature on some input data, using the private key (the signature is a mathematical object which is reasonably compact, e.g. a few hundred bytes for a typical RSA signature);
- to verify a signature on some input data, using the public key. Verification takes as parameters the signature, the input data, and the public key, and returns either “perfect, man !” or “dude, these don’t match”.
For a secure signature algorithm, it is supposedly unfeasible to produce a signature value and input data such that the verification algorithm with a given public key says “good”, unless you know the corresponding private key, in which case it is easy and efficient. Note the fine print: without the private key, you cannot conjure some data and a signature value which work with the public key, even if you can choose the data and the signature as you wish.
“Supposedly unfeasible” means that all the smart cryptographers in the world worked on it for several years and yet did not find a way to do it, even after the fifth pint.
Most (actually, all) signature algorithms begin by processing the input data with a hash function, and then work on the hash value alone. This is because the signature algorithm needs mathematical objects in some given sets which are limited in size, so they need to work on values which are “not too big”, such as the output of a hash function. Due to the nature of the hash function, things work out just well (signing the hash output is as good as signing the hash input).
Key Exchange and Asymmetric Encryption
A key exchange protocol is a protocol in which both parties throw mathematical objects at each other, each object being possibly linked with some secret values that they keep for them, in a way much similar to public/private key pairs. At the end of the key exchange, both parties can compute a common “value” (yet another mathematical object) which totally evades the grasp of whoever observed the bits which were exchanged on the wire. One common type of key exchange algorithm is asymmetric encryption. Asymmetric encryption uses a public/private key pair (not necessarily the same kind than for a signature algorithm):
With the public key you can encrypt a piece of data. That data is usually constrained in size (e.g. no more than 117 bytes for RSA with a 1024-bit public key). Encryption result is, guess what, a mathematical object which can be encoded into a sequence of bytes.
With the private key, you can decrypt, i.e. do the reverse operation and recover the initial input data. It is assumed that without the private key, tough luck.
Then the key exchange protocol runs thus: one party chooses a random value (a sequence of random bytes), encrypts that with the peer’s public key, and sends him that. The peer uses his private key to decrypt, and recovers the random value, which is the shared secret.
A historical explanation of signatures is: “encryption with the private key, decryption with the public key”. Forget that explanation. It is wrong. It may be true only for a specific algorithm (RSA), and, then again, only for a bastardized-down version of RSA which actually fails to have any decent security. So no, digital signatures are not asymmetric encryption “in reverse”.
Symmetric Cryptography
Once two parties have a shared secret value, they can use symmetric cryptography to exchange further data in a confidential way. It is called symmetric because both parties have the same key, i.e. the same knowledge, i.e. the same power. No more private/public dichotomy. Two primitives are used:
Symmetric encryption: how to mangle data and unmangle it later on.
Message Authentication Codes: a “keyed checksum”: only people knowing the secret key can compute the MAC on some data (it is like a signature algorithm in which the private and the public key are identical — so the “public” key had better be not public !).
HMAC is a kind of MAC which is built over hash functions in a smart way, because there are many non-smart ways to do it, and which fail due to subtle details on what a hash function provides and does NOT provide.
Certificates
A certificate is a container for a public key. With the tools explained above, one can begin to envision that the server will have a public key, which the client will use to make a key exchange with the server. But how does the client make sure that he is using the right server’s public key, and not that of a devious attacker, a villain who cunningly impersonates the server ? That’s where certificates come into play. A certificate is signed by someone who is specialized in verifying physical identities; it is called a Certificate Authority. The CA meets the server “in real life” (e.g. in a bar), verifies the server identity, gets the server public key from the server himself, and signs the whole lot (server identity and public key). This results in a nifty bundle which is called a certificate. The certificate represents the guarantee by the CA that the name and public key match each other (hopefully, the CA is not too gullible, so the guarantee is reliable — preferably, the CA does not sign certificates after its fifth pint).
The client, upon seeing the certificate, can verify the signature on the certificate relatively to the CA public key, and thus gain confidence in that the server public key really belongs to the intended server.
But, you would tell me, what have we gained ? We must still know a public key, namely the CA public key. How do we verify that one ? Well, we can use another CA. This just moves the issue around, but it can end up with the problem of knowing a priori a unique or a handful of public keys from über-CAs which are not signed by anybody else. Thoughtfully, Microsoft embedded about a hundred of such “root public keys” (also called “trust anchors”) deep within Internet Explorer itself. This is where trust originates (precisely, you forfeited the basis of your trust to the Redmond firm — now you understand how Bill Gates became the richest guy in the world ?).
SSL
Now let’s put it all together, in the SSL protocol, which is now known as TLS (“SSL” was the protocol name when it was a property of Netscape Corporation).
The client wishes to talk to the server. It sends a message (“ClientHello”) which contains a bunch of administrative data, such as the list of encryption algorithms that the client supports.
The server responds (“ServerHello”) by telling which algorithms will be used; then the server sends his certificate (“Certificate”), possibly with a few CA certificates in case the client may need them (not root certificates, but intermediate, underling-CA certificates).
The client verifies the server certificate and extracts the server public key from it. The client generates a random value (“pre-master secret”), encrypts it with the server public key, and sends that to the server (“ClientKeyExchange”).
The server decrypts the message, obtains the pre-master, and derive from it secret keys for symmetric encryption and MAC. The client performs the same computation.
Client sends a verification message (“Finished”) which is encrypted and MACed with the derived keys. The server verifies that the Finished message is proper, and sends its own “Finished” message in response. At that point, both client and server have all the symmetric keys they need, and know that the “handshake” has succeeded. Application data (e.g. an HTTP request) is then exchanged, using the symmetric encryption and MAC.
There is no public key or certificate involved in the process beyond the handshake. Just symmetric encryption (e.g. 3DES, AES or RC4) and MAC (normally HMAC with SHA-1 or SHA-256).
Thanks to Tom Leek for this.
