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 BobWe have PROVEN that X-class systems can't be simulated.3:

EveI just simulated the X-class.4:

Alice and BobWhoops--------

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."--------

ConclusionTo paraphraseEd 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,

ifthe attacker is constrained by this particular formal attack model, andifthese 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