Computer Science: A Hands Off Approach
which did some theory. One thing I did was the following storyline:
- Shift Cipher
- Affine Cipher
- Gen perm cipher (any perm of a,b,c,...,z
- PROOF that perm is unbreakable: Eve has to go through all 26! possibilities
- PROOF that perm IS breakable: Freq analysis. Moral of the story: Any proof that a system is unbreakable makes some assumptions that Eve might not agree to. Hence proving security is tricky.
- Matrix Ciphers. PROOF that if you use a big enough matrix its unbreakable. Sort-of true for ciphertext only (though I doubt really proven). PROOF that requires going through all possibile nxn matrices that have det rel prime to 26 to crack it using plaintext only. PROOF that this is NOT true (I leave that to my reader).
- Vig Cipher. Proof that its unbreakble, Proof that you can break it
(NOTE-- I never teach the cows paradox - all cows are the same color- when
doing induction since half the class will think induction can prove anything and the other half will think that all cows are the same color.)
I then encapsulated all of this with what I call A SHORT HISTORY OF CRYPTO:
For i=1 to infinity
Alice and Bob: We have a cipher that nobody can crack
Alice and Bob: We have PROVEN that it can't be cracked
Eve: I just cracked it
Alice and Bob: Whoops.
(I later did Diffie-Hellman in the class which I will talk about in a later blog.)
I think this is a terrible misrepresentation of crypto to give to students. (Maybe you did it differently in class.) It is true that schemes can be proven secure in one model and broken in a stronger model, and an honest discussion with real-world examples could have been great. But the examples you gave were fatuous:
ReplyDelete- You didn't prove that PERM is unbreakable -- I guess all you proved is that it has lots of keys. If anything, this shows the importance of coming up with a meaningful definition. (To illustrate that large keyspace does not imply security, you could have also given the example of the null encryption scheme that uses 1000-bit random keys but outputs the plaintext in the clear.)
- I'm not sure in what sense you can prove that matrix ciphers are unbreakable.
- The nice thing about the one-time pad/Vernam cipher (which is not the same as the Vigenere cipher, by the way) is that it *is* provable, with respect to a strong notion of secrecy and without making *any* assumptions about the behavior of the adversary. Yes, it is under the assumption that the parties only use the key once; yes, it can be broken completely if the key is used twice. But in scenarios where one-time use can be ensured, the one-time pad might be a perfectly reasonable choice.
(Gee, its odd having he discussion over a blog when your office is about
Delete30 feet from mine.)
1) PERM--- I pointed out that there are 26! possiblities so IF the model
says ALICE MUST GO THROUGH ALL OF THEM then its hard.
However, Alice can do other things.
2) Matrix Cipher- if you have a (say) 200x200 matrix and its cipher-test
ONLY then the freq analsysi washes out so it SEEMS as though you need to go through all possible matrices. NO I didn't say this was proven. But
I wonder- can one prove that? Not sure what the assumptions should be.
3) I didn't mention 1-time pad i my post (though I did in class) so I
don't know what you are getting to. My point in class was that since
VIG with a long key obscures Freq analysis one might think it is
uncrackable- in fact people DID think this. But then I showed how you
could crack it.
4) My POINT of all this I would think you WOULD approve of--- that to prove things UNCRACKABLE you need to do it in a model, and Eve need
not work in your model. Hence you need to be careful.
5) My examples are fatous? Here they are in summary:
PERM- large key space so if you had to look through it too hard, but
there are other ways
MATRIX- if ciphertext only seems hard (though not known) but people
usually have other attacks
VIG- once thought uncrackable beause it washes out freq dist, but
is actually crackable. (This is Vigenere.)
objections?
OK, but in your blog post you kept on saying "PROOF." My point was exactly that these schemes do NOT have proofs. So at best these arguments highlight the importance of proofs in some well-defined model.
DeleteGood point. I should have written ` ``gave an argument''
Deleteor even ``gave an informal argument'' instead of ``proof''
Or perhaps I should have written proof in quotes.
(This IS bill, but I am using my CAAR-REU account righ tnow
so that what my name is. Just like you ARE Jon Katz but choose
to go by Anonymous this time.)
This was a fine post (as it seems to me). History shows us too that parallel computational considerations apply to dynamical simulation:
ReplyDelete--------
For i=1 to Infinity
1: Consensus "X" is a class of dynamical systems that nobody can simulate.
2: Alice and Bob We have PROVEN that X-class systems can't be simulated.
3: Eve I just simulated the X-class.
4: Alice and Bob Whoops
--------
Scott Aaronson's slides to his lecture "The cryptographic hardness of decoding Hawking radiation" explains the origin of "whoops" concisely:
--------
Worst Case (slide 6) "We can argue that a natural formalization of Alice's decoding task is 'generically' hard. We can't rule out that a future theory would make her task easy, for deep reasons not captured by our formalization."
--------
Conclusion To paraphrase Ed Wilson's celebrated aphorism: "Much of the history of complexity theory consists of failed claims of generic computational difficulty."
We all have reason to rejoice that (historically speaking) difficulty-claims have so often failed. Because if past claimed "unbreakable" cryptographic protocols *had* turned out to be unbreakable, and past claimed "unsimulable" quantum dynamical systems *had* turned out to be unsimulable, then the present job market for young computer science professionals would be far less vibrant than it is!
Regarding the "i=1 to infinity" history of crypto, that may have been accurate as ancient history, i.e., before 1980. Today the conversation goes:
ReplyDeleteAlice and Bob: We have a cipher that we have PROVEN nobody can break, if the attacker is constrained by this particular formal attack model, and if these unproved-but-not-yet-falsified complexity assumptions hold.
Eve: I just cracked it.
Alice and Bob: Interesting! Did you falsify (one of) our complexity assumption(s)?
Eve: Yes!
A&B: Wow, that's a tremendous and unexpected algorithmic breakthrough, congratulations. We'll have to design a new scheme based on some other complexity assumption.
OR, MUCH MORE LIKELY:
Eve: No, I circumvented your attack model by doing something realistic that your model doesn't allow.
Alice and Bob: That's clever! We'll strengthen our model to allow the attacker that kind of extra power -- and ideally much much more, since we don't want to have this kind of conversation with you again! Now we have a new scheme that we have PROVEN nobody can break ... etc. etc.
Addendum: the third and most unfortunate possibility is:
DeleteEve: No, I found a bug in your proof.
A&B: Whoops.
It sounds like it would have been a great summer course to attend! It's definitely important to show both math and practical relevance and how unnoticed assumptions can change everything. Hope both you and the kids enjoyed it and that you do it again.
ReplyDelete