1CS 161– 27 September 2006© 2006 Doug Tygar 1CS 161 – Authentication Protocols27 September 2006CS 161 – 27 September 2006© 2006 Doug Tygar 2Zero knowledge review• Goal: authenticate without leaking any information• What you need to know about Rabin signatures:– Squares mod pq have four square roots (r, -r, s, -s)– If we add together ±r and ±s – And take the greatest common divisor with pq–We get p or q• GCD(pq, ±r + ±s) = p or q2CS 161 – 27 September 2006© 2006 Doug Tygar 3Leaky protocols• Many protocols leak information• For example, consider the following authentication protocol:A → B: Prove you are Bob, sign message MB → A: Sign(M, B)• Now Alice has some information she didn’t have before• She has Sign(M, B)• Perfect for what kind of attack?CS 161 – 27 September 2006© 2006 Doug Tygar 4Zero-knowledge protocol• Idea: interactive proof• At the end of the proof, A is convinced B knows a proof of fact F• But A has no information about that proof3CS 161 – 27 September 2006© 2006 Doug Tygar 5How to prove identity using zero-knowledge• B publishes b2mod pq•B → A: r2mod pq (random r)• A flips coin•A → B: coin flip• If heads–B → A: r mod pq– A verifies (r mod pq)2= r2mod pq• If tails–B → A: rb mod pq– A verifies (rb mod pq)2= (r2)(b2) mod pqCS 161 – 27 September 2006© 2006 Doug Tygar 6Comments1. This is an easy-to-perform protocol2. After each round, convinced with 50% probabilityIf B knows both rb & r (mod pq), he knows rb/r (mod pq)Fake-B will be caught 50% of the time3. A learns nothing – if she does, she could just generate pairs <r, r2>on her own. (Or, <rb, (rb)2>.)4CS 161 – 27 September 2006© 2006 Doug Tygar 7Authentication• Alice and Bob love each other, but they live far apart• We’ve learned how they can encrypt their messages• How can they make sure they are talking to each other?• This is the question of authenticationCS 161 – 27 September 2006© 2006 Doug Tygar 8Types of authentication• End user → End user (Alice & Bob)• End user → Local computer (login)• End user → Remote computer (web site login)•Computer → Computer (DRM)• Local computer → End user (fake ATM check)• Remote computer → End user (phishing check)5CS 161 – 27 September 2006© 2006 Doug Tygar 9More types of authentication• Software authentication: tougher!• Still under active development – (we may talk about it at the end of class)• “Trusted computing”CS 161 – 27 September 2006© 2006 Doug Tygar 10Authentication is complicated• It is surprisingly hard to get authentication right• Most first, second, & third attempts get it wrong• Ph.D. level courses on authentication don’t cover all• This lecture will talk about the basics6CS 161 – 27 September 2006© 2006 Doug Tygar 11Encrypting digital content• Goal: prevent people from copying digital content:– Contemporary high-definition TV sets accept HDMI with HDCP– (high definition copy protection)• Handshake to authenticate recipient – enforces copy protection• Older HD TVs don’t accept HDCP• Rules say: HDCP cannot be converted to analogue.CS 161 – 27 September 2006© 2006 Doug Tygar 12HDCP strippers• SPATZ-TECH (I am not making this up) – Makes DVI (HDMI equivalent) repeater – Called DVI Magic – Strips HDCP7CS 161 – 27 September 2006© 2006 Doug Tygar 13HDCP strippers continued• MPAA could revoke SPATZ-TECH’s key– Then SPATZ-TECH could no longer authenticate• Revocation list is contained in every HD broadcast– every HD DVD.• Equipment suddenly stops workingCS 161 – 27 September 2006© 2006 Doug Tygar 14Public key authentication is trickyA → B : {random message}BB → A : {random message}What’s wrong with this?8CS 161 – 27 September 2006© 2006 Doug Tygar 15Ultimate public key authentication• We learned zero knowledge authentication• But it is patented & slow• What if we want something more streamlined?CS 161 – 27 September 2006© 2006 Doug Tygar 16Original Needham-Schroeder (Keberos)• We need a trusted server S• Alice shares (symmetric) key a with S • Bob shares (symmetric) key b with SA → S: { “I want Bob” }aS → A : { “Use temp key” t; “send to Bob this ticket:”{ “This is Alice using temporary key” t }b}aA → B : { “This is Alice using temporary key” t }bA ↔ B : { “I love you” }t9CS 161 – 27 September 2006© 2006 Doug Tygar 17Problems with original N-S• Needham-Schroeder reigned supreme for many years • But then people noticed a problem• Replay attackBad Guy → B : { “This is Alice using temporary key” t }bBad Guy ↔ B : { “I love you” }tCS 161 – 27 September 2006© 2006 Doug Tygar 18Solution: nonces• One needs to add nonces (such as a timestamp TS):A → S: { “I want Bob”, TS }aS → A : { “Use temp key” t; “send to Bob this ticket:”, TS{ “This is Alice using temporary key” t, TS }b}aA → B : { “This is Alice using temporary key” t, TS }bA ↔ B : { “I love you”, TS }t10CS 161 – 27 September 2006© 2006 Doug Tygar 19Problems with revised N-S• Requires a trusted third party• Requires real-time access to trusted third partyCS 161 – 27 September 2006© 2006 Doug Tygar 20Authentication: still a problem• Most attacks we see today are authentication attacks – (often on passwords)–Phishing– Spyware password stealing– Bogus web sites• We need better
View Full Document
Unlocking...