Actually, my question isn’t so much about the methods themselves as about what sorts of questions can sensibly be posed for discussion with minimal knowledge.
I’m teaching a crypto course for bright young students this summer (CTY’s summer program, for those who know it). They’ve been through shifts, affine ciphers, substitutions, Vigenére, and spent all today on Enigma. Tomorrow and Monday I’m planning on talking about DES, Blowfish, IDEA, and R?ndael, or at least describing them and waving my hands a lot. The thing is, it’s best to break up lectures with some small-group discussion questions or individual exercises. I can’t really ask them to perform a DES encryption, much less try to break it. What would be good questions to ask them to discuss among two or three of their classmates?
I taught a few days of cryptography/cryptanalysis to my AP Physics students after the AP exam this year. I had them do two in-class projects that took a bit of time and that they had fun with. I also started off the second day with a few messages hidden around the room, scavenger-hunt style, and when they found one message, it led to the next. I kept the messages easy to decrypt, but they did have to work at it a bit. The decrypted messages were also somewhat cryptic, like “Up, up and away!,” and there would be a balloon sitting over in the corner for them to find, with a message on a rolled up paper inside.
The two projects were as follows: the first was a substitution cipher of the opening page of A Tale of Two Cities (“It was the best of times, it was the worst of times,” etc.). I told the class that it was a mono-alphabetic substitution cipher, and that they had better work in parallel to decipher it. I gave them a letter-frequency chart, and I did give them clues, like “Both Anglophiles and Francophiles would like this book,” and “If you were a pessimist, you’d probably agree with half of this, and if you were an optimist, you’d agree with half of this.” Anyway, it took the class about half an hour, but they finally figured it out, and they were pretty proud of themselves.
The second project was a partner project, and it involved writing messages to each other using the Golden Cipher (one-time pads). I gave them a handout that described the one-time pad, and then I let them at it. They had to write messages back and forth and decipher them as they went. They enjoyed it.
Have fun (CTY is a great program!), and good luck.
Public key is good, but I’m starting those in detail on Tuesday. Tomorrow and Monday are (mostly) given over to describing the four I mentioned, and I need stuff I can have them do about them.
Well, yes. All good, but I’ve gotten through most of those by now. Next week is mostly public key and the end of the last week is quantum (I’m seeing what they can take). What I really need are questions that people who’ve done private-key things up through Enigma can discuss about those four cryptosystems I mentioned.
I haven’t worked with source code for IDEA, but Blowfish, DES and AES are all based on rounds that are repeated many times. It would be feasible to walk through the calculations of one or two rounds manually just to demonstrate what each round is doing. You wouldn’t want this to be fully pencil-and-paper, but if you precompute some things (like the blowfish S-boxes based on the key), you could get nitty-gritty with a round or two and discuss why those machinations were useful.
Also, reduced-round versions of these algorithms are much easier to break. I don’t have any samples laying around, but it might be feasible to demonstrate a chosen plaintext attack on a reduced round version just to show cryptanalysis techniques.
A couple of more thoughts… It might be interesting to discuss different block encryption modes (ECB, CBC, etc.). You could easily demonstrate the difference between ECB where blocks are independent and other modes where they’re not. While this is higher level than discussing the algorithms themselves, it’s an important point in the security of an overall system.
Also, it might be interesting to survey some failed encryption proposals. For instance, there were a lot of submissions for AES. Some washed out very quickly. Others were proven fairly solid and it came down to a horserace on features. For anyone interested in pursuing cryptography, it’s important to realize how hard it is to do all the details well, and looking at all the ways a good algorithm can fail is instructive. I’m not saying you’d try to reproduce any of the analysis of AES candidates, but discussing what techniques were used to attack them would be interesting.
Personally, I found cryptographic systems far more interesting than algorithms. Stuff like key servers, kerebos, Certification authorities, webs of trust, replay attacks, the different types of attacks algorithms must be resistant to (known plain text, chosen plain text, brute force etc.) hashes vs encryption.
Also, try reading Bruce Schneiders blog, he has some nice, but slightly more specific topics which I found really interesting. Stuff like passwords vs passphrases, elliptic cyphers, how to become a cryptographer etc.
Well… That’s almost more a social engineering topic. But seriously - spend at least ten minutes somewhere on social engineering. Any cryptographic or security system is only as strong as the person who starts blabbing about how it works and what the soft spots are.
Actually, any system that requires people to keep the details secret is doomed to failure anyway. Modern secure systems do not rely on security through obscurity.
Publishing your keys is a little different than “blabbing about how it works and what the soft spots are”. When I said “details”, I thought it would be obvious I was referring to gotpasswords’ comment about “how it works”.
Good crypto systems are rather out and open, actually. Their workings have been left open to be gone through by people with not only a fine-tooth comb, but a weed-whacker, looking for flaws in the logic. What is, and must stay secret, natually, are the keys.
As an example, the RSA algorithm is all but open source, and is so conceptually simple that they’ve put the actual algorithm on T-shirts.
If someone comes up with a crypto algorithm and says “trust me, it works” but doesn’t leave it out for the crypto community to beat up and try to break it, they won’t be taken too seriously.
When I referred to soft spots, I was meaning more like situations where the “copier guy” is asking subtle questions like “Is there ever a time when there’s nobody in the server room?” or “Would you mind if I borrowed a computer to check my email?”
Absolutely. There is, of course, the “perfect” cipher (that I mentioned above): the golden cipher (or one-time pad), which is 100% secure as long as the keys are kept secure. The problems, of course, lie in the fact that there must be a key transfer (which could be non-secure in itself and also may be inconvenient), generating completely random keys, and the problem with generating as much key material as message material, character-for-character. This last point is somewhat mitigated by the availability of digital mass-storage systems, but if you wanted to send video using the golden cipher, you might run into this problem quickly.
It is nice to know, though, that there is a perfectly secure cipher, dependent only on both sides properly utilizing the technology (unless you work for No Such Agency…).
That’s all second week/beginning of third week stuff. I’m using contemporary private-key systems to cap off the private key stuff in the first week.
Interesting information there, but rather beyond the class. Some of these students have a lot of difficulty with running the Euclidean algorithm with pencil and paper.
I mean, I don’t want to get off on a rant here, but how can you understand that
As long as we’re getting into this kind of crypto-geekery, you might want to look into knapsack algorithms. They were supposed to be used to implement public-key encryption in the days before the first successful public-key algorithm (RSA) was invented.
It’s an example of something Schneier mentions explicitly: It’s easy to construct an algorithm so tough you cannot break it. That doesn’t mean the next person will be stymied.
(Even if your name is Ralph Merkle or Martin Hellman.)
Schneier’s book Applied Cryptography gives a smashing overview of the algorithm itself but he doesn’t go into how it was broken. (He does say the demonstration regarding how easy it was to break them used a single Apple II to do the heavy lifting. I own pocket calculators that can out-muscle that computer.) As always, however, his bibliograhpy is enlightening:
[ul]
[li]W. Patterson, Mathematical Cryptology for Computer Scientists and Mathematicians, Totowa, N.J.: Rowman & Littlefield, 1987.[/li][li]C.P. Pfleeger, Security in Computing, Englewood Cliffs, N.J.: Prentice-Hall, 1989.[/li][/ul]You might even be able to find one of those books in a large library system.
What age are these kids, how many hours are you with them a week and how many weeks does the course run?
If you pick up Kevin Mitnick’s art of intrusion, theres a story near the beginning about a group of kids who managed to crack the algorithm for the RNG of a slot poker machine and made off with a bit of loot doing that. It’s an instructive lesson in security via obscurity, lax programming and how much effort some people will go to to crack your codes.
Also, spending some time on random number generation might be fun as well.