I recently had just an excellent conversation with my friend Rich Blewett, also a DevelopMentor instructor. He asked me to explain the basics of cryptography, and the conversation went from there. I've put it here in its entirety with his permission.
Rich : I've been watching the conversations about ws-sec and a few others. Whats the best way to get to understand alll this stuff about keys, encryption, etc. Does secrets and lies cover it all? or do I need to read other stuff too?
* Auto-response sent to Rich : I am currently idle.
Rich : lol
Rich : I like the auto response
Craig : Secrets and Lies does an ok job.
Craig : Applied Cryptography is better if you want the nitty-gritty.
Craig : I haven't looked at Keith's course: there may be some slides in there.
Craig : There are really only a few things you need to understand.
Rich : ok, its not that I want to become a world expert, I just feel there is a bit of a hole in my knowledge here
Craig : Secrets and Lies rocks, BTW.
Craig : I'll see if I can give you the two-minute rundown.
Rich : cool
Craig : Hash: a one-way function that takes a message of an arbitrary length and computes a checksum of a fixed length.
Craig : Hashes cannot be reversed: given a hash, it's essentially impossible to come up with a document that hashes to that value without just trying all possible documents until you get a match.
Craig : Got that one?
Rich : yep
Craig : OK.
Craig : Symmetric key ciphers. Also known as private key ciphers. Transforms a message into another message based on a key. You need that same key to transform it back. So there's only one key.
Craig : Got it?
Rich : ok and both oparties need access to the key
Craig : That's right.
Craig : So key exchange is a big deal. But we'll get to that.
Rich : so its reversable as long as you have the correct key - unlike a hash
Craig : Yep!
Craig : Ready for the next one?
Rich : yep
Craig : Asymmetric key ciphers. Also called public key algorithms. You start with two numbers: the public key and the private key. It is mathematically intractable to get one given the other. Anything encrypted with one can only be decrypted with the other.
Craig : So far so good?
Rich : ok - let me reword ...
Rich : so I have 2 keys that are related, but cannot by discovered from eachother ...
Craig : Right!
Rich : I encrypt with one, I can decrypt with the other#
Craig : Correct.
Rich : so I let others encypt with on I make public and I can decrypt what they send me
Rich : my private keyt
Craig : And no one else can read it, yes.
Craig : So it gives you privacy.
Rich : cool - next
Craig : Those are the basic primitives. And you've already talked about one way they can get used: you can encrypt something with someone's public key to get privacy.
Craig : Here's another.
Craig : If I were to encrypt something with my private key, anyone could decrypt it, but they'd know I wrote it. So that would give me authenticity.
Craig : With me?
Rich : ahhh - of course, as long as they could verify what they decrpted it to was accurate
Craig : Sure, but that's an easy problem to solve, right? Just put some sort of well-known header on it.
Rich : yep
Craig : OK. So here's the problem: asymmetric algorithms are god-awful slow. Symmetric algorithms are much faster. But they require that we both know a secret (the shared private key).
Rich : so both parties need to exchange public keys and encrypt with private keys to ensure 2 way auth
Craig : Yeah, but let's come back to that.
Rich : ok
Rich : got the issue about speed
Craig : OK. So given that we'd rather use a symmetric key algorithm, the problem becomes one of key exchange. Obviously, we don't want to just send the thing over the wire - security depends on the secrecy of the key. Can you think of how we might pull it off?
Rich : so if I encypt the shared secret with my private key, you knwo it came from me, then we can use the shared secret for symetric
Craig : Almost. Can you think of the problem with that?
Rich : someone intercepts - has my publc key (as its public) and can see the secret and c an then listen on the conversation
Craig : Right!
Rich : so I encrypt with your public key
Craig : Bingo.
Craig : That's basically how SSL works.
Rich : but then how do you knwo it came from me
Craig : Ah - good question.
Craig : So we haven't used hashes yet. Think of a way we can use them?
Rich : and SSL periodically renegiciates the
Rich : renegociates the shared secret?
Craig : I don't actually know how often SSL does that. Let's stick to sort of generic crypto for the moment.
Rich : ok - hmmm hashes ...
Craig : Hint: you need hashes plus something.
Rich : so if I hash my something that oneonly I know ... my private key ... but then you don't have that dso you can't has it as well ... hmmm ...
Rich : has = hash
Craig : You're very close.
Craig : What if I hash the message I'm sending and then encrypt just the hash with my private key?
Rich : ahh - so as long as we both have the same hash alogorithm which we can then you now have auth#
Rich : as I have the message too
Craig : Yes. And also integrity - that is, no one in the middle can change the message, right?
Craig : If they did, what would happen?
Craig : (The Socratic method doesn't bother you, does it?)
Rich : nope - the decypt with your private key would result in something else and the hashes would be different
Craig : Exactly.
Rich : this is neat
Craig : BTW, a private-key encrypted hash is called a signature.
Craig : OK, one more and then you have just about all the cypto basics I can think of.
Rich : ahhh - like in the sig in a strong named assembly header
Craig : Yes, exactly like.
Craig : It's a hash of the assembly manifest (which itself contains a hash of the modules), encrypted with the private key.
Craig : It can be verified with the public key, which is right in the assembly.
Rich : yep - cool
Craig : Which, of course, leads right into the last thing I was going to talk about: how do you know that's the right public key?
Rich : must be a hash of the assembly contents though surely
Rich : anyway back to crypt
Craig : No, actually. It's a hash of the manifest. Which itself contains hashes of the module contents.
Rich : ahhh
Craig : So if you change the module, the module hash differs, which changes the signature.
Rich : yep - thats clear
Craig : Anyway, the question is: when I'm verifying a signature, how do I know what public key to use?
Rich : so how do I know its your public key
Craig : Any thoughts?
Rich : because we also hash the sig wityh the right public key?
Craig : Whose public key?
Rich : hold on - back pedal slightly ...
Rich : so I think this message is from you but I have to verify the sig
Craig : That's right.
Craig : To do that, you need the public key that matches the private key used during signing.
Craig : How do you know which one to use?
Rich : so if you hash the sig with your public key, which I have, then I can hash it too and veryify its the rightr public key for the sig
Craig : Well, let's be a little careful. You don't hash something with a public key. You just hash it. Then you encrypt with a key. So we could say that I sign something with a public key, but you wouldn't hash it with a public key.
Craig : Care to restate?
Rich : ok .... let me try again ...
Craig : I'll give you a hint: if you're clever, you can actually send the public key along with the message.
Rich : so you encyupt the your public key with my pubvlic key and I decrypt it with my private key. which relies on both of us having key pairs
Craig : Yep. That's actually fairly close. The problem then just becomes, how do I know that that's yourpublic key and not just some public key that some evil guy faked me into thinking was yours.
Craig : I'll tell you the answer because I think it's hard to guess it.
Craig : Basically, the problem comes down to the fact that we both have to know something beforehand. In the real world, that thing that we know is Verisign's public key, which gets installed with our browser or operating system.
Craig : What I can do is ask Verisign to sign my public key with their private key, after I prove that it's really my public key to them somehow.
Craig : Anyone can now verify that it's my public key, because we all know Verisign's public key, so they can validate the signature.
Craig : I can send my Verisign-signed public key to anyone in the clear, and they can be confident that it's mine. We call this a certificate.
Rich : although we have to assume that mr nasty hasn't put their veri
Rich : verisign encrypted key in
Rich : so we have to trust verisign to check out everyone whose key they encrypt
Craig : Yes! Totally! I defy you to think of a security system that doesn't rely on trust.
Craig : The reason that we trust Verisign is that they'd go out of business if we didn't.
Craig : But that's basically the only reason.
Rich : so a hacker can destroy your message but not interfere with it
Craig : That's right.
Rich : in other words they could sub IBMs key into your message instead
Rich : but then they could issue a DDoS attack on you too
Craig : They could. Which raises the question: does sending a certificate prove identity?
Rich : only if you can provae that you have received the cert the originator sent
Craig : Right, but you can't prove that.
Craig : So receiving a cert in and of itself proves nothing.
Craig : A cert is just a way to verify that the public key you think is mine is, in fact, mine.
Craig : To prove identity, you must also verify that the sender knows the private key. Say, by sending them a random number and asking them to encrypt it with their private key.
Craig : Making sense?
Rich : unless they encrypt the cert with their private key, but hen how do you know which public key to use to decrypt ...and round we go again
Craig : Exactly.
Craig : Ready for one more?
Rich : OK
Craig : OK. Let's talk about how you prove your identity to someone without using asymmetric (public) key algorithms.
Rich : retinal scan?
Craig : :)
I'm the server. I want to know that you are who you say you are. So what I need to do is set up some sort of a shared secret beforehand.
Craig : Usually, this ia a password.
Rich : ok
Craig : If I want you to prove to me that you know the password, I could just have you send it over the wire. This is fine if you've already set up a secure channel - say SSL.
Craig : However, often this isn't the case. So what do we do?
Rich : ok, otherwuise we both need a hash of the shared sectretr
Craig : Well, that's not actually true.
Craig : Here's what the server does:
Craig : The server sends the client a random number and says, "Hash this with your password and send it back to me."
Craig : The client does so, and then the server performs the same operation. If they match, then the client knows the password.
Craig : BTW, "hash this with your password" means something like "concatenate this with your password and then hash the result".
Rich : ahh - but then the server needs to store the pwd in a clear, or decryptable form
Craig : Yes.
Craig : Which is a problem.
Craig : The algorithm I described is essentially NTLM, BTW.
Rich : cool
Craig : What NT does is that the server - which probably isn't a domain controller - gets a challenge from the DC, and then asks the DC to verify the response.
Rich : is this done only once per session?
Craig : Yes. Which is a problem if you have a sophisticated attacker, because they can hijack your session.
Craig : And one of the many reasons security experts rightfully say that NT security sucks.
Rich : lol
Rich : so kerb uses a differnet aproach
Rich : issues a expirable lease
Rich : ticket
Craig : Kerberos is fairly complicated.
Rich : lets not go there then ;)
Craig : But basically, a ticket is a bunch of information that has been signed by the Kerberos server after the client proves their identity.
Rich : you should write this down in a white paper for develop.com
Craig : I'll let you look up Kerb on the web - you've got all the stuff you need to understand it: hashes, encryption, signatures, certificates.
Craig : These are the basics.
Craig : I was going to ask you if it was okay if I posted this conversation.
Rich : thx that was fantastic - you rock Craig
Craig : Thanks!
Rich : of course you can
Craig : I've been thinking about this stuff a lot lately.
Craig : You should totally read Secrets and Lies.
Craig : Then you can see how fragile all this crap is. :)
Rich : I will - definitely
Rich : thx again - sadly I now need to go tidy the house :(
Craig : :p
Craig : Catch you later!