|
8/1/98 __________________________________________________________ Vol. 3 No. 8, Part 1 The Magical Mystical Crypto-Primer ____________________________________________________________ By Tim "No Sinister Nickname" Skorick <TIM_SKORICK@non-hp-usa-om7.om.hp.com> Thanks for the suggestions and comments: Carolyn Meinel (naturally!), Bruce Schneier, John Young (for his internet Crypto vigilance), Mark Skorick, Eric Brisnehan, Mom, Dad, kenspiraC, Rahul Bheemidi, venMus, Everett Gidlund, Gomez, Skip Stavis, Jon Tempest and Prabaker Balasubramanium. Last, but not least, an emotional, teary-eyed "thank-you" to Juan Valdez for bringing the world 100% Columbian coffee, the richest coffee in the world. Part One: the Crypto-bottom What I'm going to tell you The bottom How they used to do it How they do it today What's the easiest way to get into all this? Other ways to start using crypto Wrap up stuff Wanna learn more? Tim what's up with you and all this? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I. WHAT I'M GOING TO TELL YOU Okay, some of you out there know generally what cryptography is supposed to do, how it is used, and what its limitations are. A lot of you probably even have a really good grasp of the mathematics involved. This primer won't tell you people anything you don't already know. Basically, I'm writing this for the cipher-newbies out there that have never used cryptography, or "crypto," and have no idea how it works, and like the idea of starting at the bottom. And it isn't going to be a quick thing. There is too much science, history, theory, and other stuff involved for a person to learn all the basics of cryptography quickly. BUT - as with most computer stuff, it is still way simpler than most people make it sound. When you're done reading this you will have a whole metric ton of cool crypto-words you can throw around to impress your buds, and you should be just enough of a knowledgeable cryptodude to be able to find the real cryptography and avoid the "kindergarten cryptography." II. THE BOTTOM (or "What the?") Okay. "What the heck is cryptography?" you ask. Well, dang it I'll tell ya (This is the crypto-bottom, chitlins.) Everybody at some time or another sends someone message that they would rather be kept secret. Whether you are sending an e-mail to a friend, your doctor is faxing your medical records to the insurance company, you are ordering a take-out dinner over your wireless phone (and using your debit card number to pay in advance), or saving the plans for your latest development tool to your business partner's network drive, privacy these days is super important. Cryptography is the art of taking a perfectly good message and scrambling the living snot out of it so as to make it completely 100% unreadable to everyone except for the party who is supposed to be reading it. Now the whole crypto thing is rolled up into the subject of "cryptology." There are a few different disciplines within cryptology. "Cryptography" is the art of creating the schemes used in the whole process. "Cryptanalysis" is the discipline of cracking what the cryptographers come up with. Most really hard core cryptographers were people who spent a LOT of time and effort being cryptanalysts, so they know enough to keep from making all those idiotic mistakes cryptographers usually make. People have actually been doing this for a long time III. HOW THEY USED TO DO IT (or "Beware the Ides of March") A. The Ceasar cipher ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Remember Ceasar? Back when he was conquering the world, he had to send messages back and forth across enemy territory. He sometimes would have to send his troops really important information, and his generals had to come up with a way of screwing the message up to keep the enemy gauls or whoever from reading it if the messenger got captured. This screwing up of the message is called "enciphering" a text. But here's the catch: It would be So here's what they did. They wrote the text of the message: "Hey Brutus, here's my salad dressing recipe, give it to Mark Antony on March 15, and do me a favor, sharpen my knives for me." They then took each letter in the message and replaced it with the letter four spaces down in the alphabet. That made the message look like this: "Lic Fyxyw liviw qc wepeh hviwwmrk vigmti Now when the person the message is for got the message, he would only have to look at each letter, replace it with the letter four letters UP the alphabet. Then he would have the "plaintext" back again and could run out and buy romaine lettuce and croutons. Neat huh? So if the poor slob delivering the letter was captured by a motley horde of gauls, the enemy would have no idea what the message said. Of course Ceasar would have really been writing in Latin, and who can read that stuff anyway? But the crux of the matter is this: They used what is ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ A "substitution cipher" just creates the cipher by substituting each piece of text with a different piece of text. It's old, insecure, and unused today outside of elementary school playgrounds, but nevertheless has one thing in common with all cryptosystems: Like any cipher, it's pretty much B. What exactly is an algorithm? We use these really complex algorithm things today, but there was an algorithm involved even then. You're gonna love this: An "algorithm" is Now, don't go batty on me with the "what problem? Is this math again?" In a way, yeah it is, but in the case of an algorithm, the problem it's solving is that the message is in plain English and has to get encrypted somehow. See? No big deal. The algorithm used to encrypt with a Ceasar cipher took place in the guys' little pointed heads instead of in a computer and went like this: 1. Look at the plaintext letter You just read an algorithm! The guys would start at the top of the message and do this over and over until the enciphering was done. The decryption steps were the same as above but done backwards, counting four letter UP the alphabet. That's an algorithm. Algorithms used in ciphers today are seriously complicated, but are based around the same idea of taking a math action and turning it into an automatic process that goes until it solves a problem, in this case the problem of encrypting and decrypting stuff. Have you heard names like "RSA," "IDEA," "DES," "Blowfish," "CAST," and "El Gamal?" Those are the really popular algorithms (Except for DES. DES is the old unpopular one that's getting a little weary and tired). To make things more confusing, sometimes the algorithms that encrypt and decrypt are different. We'll go into why later, but just remember, the "encryption algorithm" turns plaintext into ciphertext, and the "decryption algorithm" turns ciphertext back into plaintext. Now what C. The key to it all Awright, chitlins, this is the funnest part. The key to the cryptosystem! Keys are super-important. A key is the special information that the algorithm uses in its job of encrypting and then later decrypting messages. If you're thinking about a key as in how you lock your house, you is right on de' money. Your key to your house has to fit your lock perfectly. It has to be able to lock AND unlock your house. Most importantly, it has to be different from most other keys, so your neighbor can't just wander into your locked house with HER key and dig into your chips and guacamole. Like she lives there or something, sheesh! I get really bitter when that happens. Keys are important. The cryptosystem key is what makes the encryption different for everybody that uses it. People have to use the same algorithm to encrypt and decrypt stuff, so there has to be something in the whole chain that is used to make your encryption special. The algorithm HAS to have a special key, not like anyone else's. Back in the old days people would use passphrases like Bible quotes and sayings as keys. Then they would use numbers. The smart ones would use both. What they could use as a key depended a lot on what kind of a system they used. Now when we actually look at today's keys, they look like big blobs of numbers and characters and who knows what else. This is the first few lines of one of my public keys, check it out: -----BEGIN PGP PUBLIC KEY BLOCK----- Version: PGP for Personal Privacy 5.0 mQGiBDU3uhARBAD6JcwWAU68HZUtONoew0sB24wr5v9YCDEPHy4rb/141+l4pOOh Nuts, huh? Important thing: that is just the "text" way of showing 110101 110011 10001110010011 111110100101010101011010 110011 ... and on and on and on. ~~~~~~~~~~~~~~~~~~~~~~~~ Head Exercise ~~~~~~~~~~~~~~~~~~~~~~~~ Pretend for a second that you're the algorithm. You're the process that the program repeats over and over to encrypt the data. This is what you would do: First off, you would be waiting inside the PC wishing the air conditioning worked. Then the user would type a letter that they wanted encrypted. As soon as they clicked on the program to encrypt the message, the program would kick you in the behind and swing you into action. You would take the person's key in one hand, and only take a little piece of the message in the other, and start adding them to each other and mashing them around together till you were finished with that piece of message. Then you would grab the next piece of the message, the same key, and do it over again. You would repeat this until all of the text looked like it was put through a meat grinder. The way you would know your job was done with each piece of text (called "blocks" by cryptopeople) was when you had done however many steps (called "iterations" by cryptopeople) you were supposed to on that block. That would be your signal to move on to the next block. The way you would know you were done with the whole shebang was when you ran out of pieces of text to encrypt, or should I say - when you ran out of "blocks" of "plaintext" to perform "iterations" on. Do me a favor, think about whether or not you would have understood that last sentence before you started reading this ... it sounded cool anyway - Heh heh heh. So to sum up: the algorithm does all the freaky mish-mashing on your So that's the part of the algorithm where the key "fits in." Get it? "Fits in?" Nevermind. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ D. How do you make a key? The way the key is generated is really super important. It's also the easiest part for you because the software you're using will do all that for you. Each crypto program will have different crazy ways of making its keys. Some of them tell you to swirl your mouse around and pound on your keyboard for a while. Why do you do this? The answer is simple: random data. You have to use as much random and unpredictable stuff as you possibly can. The reason for this is that if you use really predictable and non-random information like the date and your name to make a key, some attacker who wanted to read your encrypted email could guess what your key is really easily by playing with that kind of info until he had it right. If people can guess your stuff THAT easy, sheesh what's the point? That ain't real cryptography, it's kindergarten cryptography. You HAVE to have random numbers in a cryptosystem. ~~~~~~~~~~~~~~~~~~~ Head Exercise ~~~~~~~~~~~~~~~ Random numbers are tougher to come up with than you might think. Here's an example of what I'm talking about: Pretend for a second that your crypto program comes up with keys by taking the date, say 1-15-98, and multiplies it by 50 (011598 x 50 = 579900) and then randomly comes up with another number by multiplying two double digit numbers (like 36 x 73 = 2628 and then multiplies them all: 1523977200 is the That's 1011010110101100000101111110000 in binary form. Looks pretty random, huh? But it's not at ALL. A cryptanalyst can come along and take the output of all possible dates multiplied by 50 (there's only 365 numbers it could be), and then go through all those and multiply them by non-prime integers between 1000 and 9801 (there are only so many products of double digit numbers) and he will have your key before you can blink. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This is where we have more help from programmers. They write programs called "Random Number Generators." They're super high-tech programs way deep inside the key-making programs that use really strange stuff (like static) and weird things (like how you type) to come up with freaked-out numbers that NOBODY would have predicted. These Random Number Generators are often just called RNGs and are a real vital part of making a key. Always remember that the program for generating a key is one of the most intense and crucial parts of any cryptosystem. E. More crypto-history Okay, ciphers have evolved over the ages. A lot. There were disc ciphers that could rotate between alphabets, electrical ciphers that looked like typewriters but spat out ciphertext, and others. I have to skip over a lot of these for right now to get to other important stuff, but fear not - I'll cover more classical crypto stuff later on. IV. HOW THEY DO IT TODAY (or "Bigger isn't better") A. Keys are important still, but not the only thing. Today's ultra-modern crypto stuff is still based around making sure that the ciphertext can only be decrypted with that one special key. The keys you see these days are made up of strings of numbers, characters and stuff all broken down into digital form of 1s and 0s. The more numbers in the key, and the more random the info that makes it, the "stronger" the key is. Important thing: Having a big ol' humongous strong key doesn't necessarily Are you going "aroof" and scratching your head yet? Look at it this way. A strong algorithm is like knowing self-defense, and a big key is like having big muscles. Having big muscles doesn't mean you know how to defend yourself. And knowing how to defend yourself doesn't mean you're strong enough to. If you have the ability, then you use your big muscles to get the job of defending yourself done, but neither is any good without the other. *************************************************** Big Manly Key + Weak Wimpy Algorithm = Weak System Note: All apologies to the females in the audience, the word "manly" just had the vibe I was looking for. No offense intended :) *************************************************** Now I have to confuse you again, but all will be made clear. The big key and strong algorithm don't *guarantee* a strong system necessarily. Why? Well, it's always possible that YOU the user can mess everything up and make the whole dang thing insecure by trusting the wrong person with your key, not knowing who has access to your computer, setting crypto stuff up wrong, and just not being careful. Having big muscles and the knowledge to defend yourself won't make you safe if you happen to be drunk when attacked. But back to the whole "big key" thing: it doesn't really have anything to do B. What's "brute forcing?" Making sure your key is nice and big just makes it harder to guess the key if you were going down the list of all possible keys. This is called a "brute force" attack. This means that if you have a six-digit number, you could crack the key by starting guessing it at 000001 then 000002 then 000003 on the way to 999999 till you get the key. A typical ATM pin number four digits long would be harder to "brute force" if it were ten numbers. The number of guesses you would have to go through to get the key increase hugely each time a number is added to a key, and your poor PC is worked overtime in the rush to figure out all the possible combinations. ~~~~~~~~~~~~~~~~~~~~~~~~ Head Exercise ~~~~~~~~~~~~~~~~~~~~~~~~ You can brute force a key of two digits in your head. Get a friend to think of a two-digit number, and not tell you. Easy to guess, right? There are only 99 numbers it could possibly be, so you count down the list till you guess the right one. Now tell your friend to add just one more teensy little digit, so they have a secret number with three digits. Now there are 999 possible numbers it could be. See? 999 may only have one more digit than 99, but it's more than ten times bigger. It gets ten times harder each time you add a digit. You can still try to guess it, but how high do you feel like counting? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ With modern keys of 4096 bits, brute forcing takes dang near forever and there's just more intelligent ways of doing it. This is why the brute force method of cracking a large key is the very last resort of any smart cryptanalyst (those are the guys that crack the crypto stuff, remember?). And if a key can ever be brute forced, that means it's reeeeaaaaalllllly weak. Unfortunately some cryptosystem engineers haven't figured out that a bigger key isn't necessarily a better system. For instance, the PCS phone carrier that I use advertised the safety of talking on their phones by saying that "Our phones are so friggin' secure that in order to break through their communications privacy you'd have to guess four trillion keys in less than a second! Hoo yah! We're all that!" They didn't use those actual words, but it was something like that. Anyway, you know by now that they were talking about a brute force attack. The problem is that they didn't really look at the rest of the actual cryptosystem they used. Then some really awesome hackers looked at the actual system and process they used to encrypt the communication (remember the "algorithm?") and found some mathematical flaws that would allow anyone with a little ingenuity and some common equipment to decrypt the phone call information. Needless to say I made fun of my PCS people forEVER after that. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Cool thing: That was an actual true story. The algorithm is called CMEA, http://www.counterpane.com/cmea.html ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ *************************************************** Other note: The president of Counterpane Systems that published the hack is So remember. A stupid cryptosystem that happens to use a key seven gazillion digits long is still a stupid cryptosystem. You might as well just write the message on a dang postcard in large letters and attach a big neon sign to it that reads "Private but unprotected data! Don't read! Please! You might have to take all my money! Aaaaaa!" C. What is "public key" supposed to mean? Easy. You know how the ciphers we've been talking about have a secret key that both encrypts AND decrypts the message? Public key systems have two different keys that each will do one of those things. ? Okay okay, hold on. First let's have a little "Words You Need To Know" update: A cryptosystem that uses the same key to encrypt and decrypt the Other more ordinary words for these systems are "private key" or "secret key" crypto for symmetrical, and "public key" for asymmetrical. Okay, you got the terms lah dee dah yeehaw let's get on with it. The problem started when people got sick of having to go through the hassle of getting the great and powerful secret key back and forth between the senders and receivers and all that stuff. I mean, how many ways can you get a secret key to someone without an eavesdropper snatching it en route? Not many. So some guy at Bell Labs came up with the genius idea of a system that would generate two numbers based on a certain kind of mathematical problem. When one of the numbers was used to encrypt data, only the other number generated with it would decrypt it. Woa! It was expanded upon by some cryptographers in Britan, and then some guys at Stanford came up with an even better idea (not even knowing about the previous work!). I'll tell you about those people in a sec. So you would generate the two numbers you'd use as keys (called a key pair). Give everybody in the universe one of the keys, and keep the other one on a floppy disc in your ventilation duct or your underwear drawer or somewhere else really private. Anyone who encrypted a message to you with the key that you gave them would be making a ciphertext that nothing in the world could decrypt except the key you have hidden between your undies and your socks. Nowadays there are a few different systems that use this clever little scheme hiding in your underwear. You can imagine how popular it is, no need to sneak around slipping floppies under doors and all that irritating cloak and dagger stuff. You download and install the software, generate the keys, and start emailing people your public key. If somebody encrypts something with your public key, only your private key can decrypt it. When you want to email someone an encrypted message, you get their public key. If you encrypt a message with somebody else's public key, only their private key can decrypt it. Reeeeeeaaaallll simple. Little secret: about fourteen years before these guys invented this system, http://www.cesg.gov.uk/ellisint.htm D. What's a Diffie-Hellman and who's RSA? Check it out, those are just different kinds of systems and keys. Diffie-Hellman keys are generated using a specific method for public key crypto, and RSA keys are generated using a completely different method for public key crypto. The basic public key thing is the same, but the two systems come up with the keys in a different way and go about the crypto thing using different algorithms. Whitfield Diffie, Ralph Merkle and Martin Hellman independently thought up a great way of generating a key pair in 1976 using a really tripped out math problem called the "discrete logarithm" problem. I ain't even going near explaining that, it's gonna hafta wait. Then the next year, some more brainiacs named Ron Rivest, Adi Shamir and Leonard Adleman invented the RSA scheme that essentially does the same job but based on a different mathematical problem called the "Integer Factorization Problem." Again, not touchin' it with a ten-foot pole. I'll go into it later. Much later. So keys created using Diffie, Merkle and Hellman's method are still called "Diffie-Hellmans." In fact, the newer ones are getting more popular because they can be used for digital signatures and everything. RSA still does all this stuff too and also is a big huge company. Funny thing: The early public key discoveries made at Bell Labs and in _______________________________________________________________________ _________________________________________________________ Carolyn Meinel M/B Research -- The Technology Brokers http://techbroker.com/ |