Some basic cryptography stuff

I've been asked about cryptography a couple of times. Some folks don't want to go and buy their own copy of Applied Cryptography (Bruce Schneier) so this is a basic introduction for people who don't want to get too into it.

I'm assuming a basic level of knowledge here... you wouldn't be reading this if you didn't have a basic level of knowledge -right?

Put simply, there are two main forms of encryption. Symmetric, and asymmetric. In symmetric cryptography the key is either the same at both ends, or one key is easily calculable using the other. This means that both parties in a conversation can decrypt any of the messages. Keys used in symmetric cryptography tend to be large, and the algorithms are fast. There's also the problem of how I should get a key to you in order to communicate, because if anyone else has the key, its useless.

In asymmetric cryptography, there exists a pair of keys. We name these keys a public key and a private key. Messages encrypted by the public key can only be decrypted using the private key. Hence, if you have my public key, you can encrypt a message with it, and you can be sure that only someone with my private key can read the message. So long as I've been careful with my private key, that should be only me.

There's another very useful side to it. If you can decrypt a message using my public key, then you can be sure that it has been encrypted using my private key. Again, so long as no-one else has obtained my private key, that message must have come from me. But note that anyone else in the world might have my public key, so the message I sent you has not been hidden from them, this is just a way to prove the source of a message. If I want to send you a secret, I do so by encrypting the message using *your* public key.

Asymmetric cryptography is slow, but the properties of public and private keys are very useful.

By combining the two techniques, we can arrive at something more useful. Consider this:

You send me a message that says "I'd like to communicate in secret".
I generate a nice big pseudo-random symmetric key. I encrypt the key with my private key, and then again using your public key, and then send it to you.
You decrypt the message using your private key, and that makes you happy that nobody else can have seen the info in transit.
You decrypt the message using my public key, and that makes you happy that the message actually came from me, and not an impostor.
You now have a copy of the nice big symmetric key which we can use to communicate quickly.

That sounds great, doesn't it?

Consider this:

You and I have never spoken before, I don't have your public key, and you don't have mine. (Note: we give the public key to anyone who asks for it, its public, we don't care who has it.)
You send me a message asking to communicate, as above.
I need your public key, so I send a message asking you for it.
A malicious guy called Mallory is in full control of part of the network connection between you and I.
Mallory intercepts my request, impersonates you, and sends me his public key. I think this key is yours.
I generate a symmetric key, encrypt it using my private key, and (unwittingly) Mallory's public key.
I think only you will be able to read the message, and you can verify it is from me. I send the message.
Mallory intercepts the message. he decrypts it using his private key, and my public key.
Mallory now has a copy of the symmetric key.
Mallory now impersonates me, and asks you for a copy of your public key.
He encrypts the symmetric key with his own private key, and your public key.
You decrypt it with your private key. You're happy that no-one observed it in transit.
You send a message asking for my public key.
Mallory intercepts the message, impersonates me, and sends you his public key.
You decrypt the message with what you think is my public key. Having done so, you're happy that the message is from me.
We now both have the symmetric key (and so does Mallory)
We begin to communicate using it.
Mallory intercepts everything, and decides which messages to forward, which to alter, and which to delete.
Mallory has defeated the scheme completely. We think we're communicating in secrecy, and that we've verified each other.

Passwords things.

Passwords are kind of encrypted. They are operated on by a trapdoor function (aka one-way function). The idea is that this function can be used to generate a 'hash' from a password, but it is practically impossible to take a hash, and recreate the password from it, even with full knowledge of the algorithm that has been used.

What one can do, however is to guess the password, calculate the hash of the guess, and compare it with the desired hash.

A plain brute-force attack systematically goes through every possible password doing this until a matching hash is found. A more intelligent password cracker makes assumptions about what the password is likely to be, and tries those guesses first. This is still a brute-force approach, but uses assumptions about the password, hopefully to decrease the expectation of time taken till a password is guessed.

Approaching a brute force by trying to log into a telnet server / whatever with every possible password is probably going to draw attention. For this reason (and for speed advantages), an attacker generally tries obtain a copy of the password hashes.

Back in the old days, linux used to have the password hashes readable by anyone in the filesystem (you'd still need access to an account on the system, or to find a broken ftp config or something to get to them). Nowadays, the password hashes are better understood to be a secret thing which you shouldn't let people get their grubby little mitts on.

For reference, a password cracker which I have used, on a AthlonXP 1600, running win2k can perform over 4000 MD5 crypts/second, and over 600,000 NT LM crypts/second. With today's computing power, brute-forcing passwords doesn't really take very long.

If I know your password is MD5, 6 characters long, I know the salt, and I know you're used only lowercase alphabet characters, and the ten numerals, on this pc here, I can brute force the password in 6-days, worst case. These assumptions are not bad for 80% of computer users.

"What's this Salt? You didn't mention that before!"
It's a fair cop.
Salt is a string that is concatenated with your password before being hashed. It is generated when your password is changed. The salt is stored in the file with the password hashes. MD5 can use between 12 and 48 bits of salt. From a quick look on my Slackware 8.1 box, all of my passwords have been given the full 48 bits of salt.

If not for salt, I could take a couple of weeks or so to calculate the MD5 hash of every probable password, until I ran out of space to store the hashes. Then when I steal a file full of hashes, it only takes me a few seconds to compare a hash to a table of known hashes.

Without knowing the salt in advance, this table would have to be 2^48 (approx 10^14) times larger in order to store the same number of passwords.