Cryptographic protocols:design and analysisDavid WagnerUniversity of California, Berkeley1NotationA, B, C, S: names of legitimate parties.(Short for: Alice, Bob, client, server.)M: name of a malicious attacker. (Short for: Mallet.)2Notation1. A → B : xThe above means:1. Protocol designer intended the message x to be sent by party A toparty B.2. This message was intended to be sent first in a series of several.3Caveats1. A → B : xDo note:1. B only receives the message x, not who it came from.(Thus, messages should include the sender’s name if the recipientneeds to know it.)2. There is no guarantee that A, the network, or the adversary will behaveas intended.(Thus, messages might be intercepted, modified, re-ordered, etc.)4More Notationk is a key; k−1is its inverse.For symmetric cryptosystems, k = k−1; for public-key cryptosystems, k isthe public key and k−1the corresponding private key.5Notation Without End{x}kmeans x encrypted under k.Warning: This is implicitly assumed to provide both secrecy and integrity, inthe standard notation. For instance, {x, y}ksecurely binds x to y.(Excercise: How do you implement {x}k?)[x]k−1means x signed under k−1.Most authors conventionally use {x}k−1for signatures,but I don’t like the standard notation. (Exercise: Why not?)6Still More NotationTAis a timestamp chosen by A.NAis an unpredictable random nonce (a “challenge”) chosen by A.7Who’s awake?What does the following notation mean?1. A → B : {A, [kAB, A, B]K−1A}KB2. B → A : {message}kAB8WarmupEstablishing a secure channel with a challenge-response protocol:1. A → B : A2. B → A : NB3. A → B : [NB]K−1A4. A → B : {message}KB5. A → B : {message0}KB. . .Can you spot the flaw?9Denning-Sacco #1Key exchange between A, B, with the aid of an online certification server S.1. A → S : A, B2. S → A : certA, certB3. A → B : certA, certB, {[kAB, TA]K−1A}KBCan you spot the flaw?10Breaking Denning-Sacco #1Look closely:3. A → B : certA, certB, {[kAB, TA]K−1A}KBThe key kABisn’t bound to the names of the endpoints A, B.Therefore, B can extract the quantity [kAB, TA]K−1Aand use it to spoof Ain a new connection to C, like this:30. B → C : certA, certC, {[kAB, TA]K−1A}KCAs a result, C mistakenly concludes he is speaking with A.11A LessonMoral: Be explicit. Bind all names, and all other relevant context, toevery message.Exercise: Why do so many protocols fail this way?Credits: Abadi and Needham.12Early SSLKey exchange with mutual authentication:1. A → B : {kAB}KB2. B → A : {NB}kAB3. A → B : {certA, [NB]K−1A}kABCan you spot the flaw?13Breaking early SSLLook closely:1. A → B : {kAB}KB2. B → A : {NB}kAB3. A → B : {certA, [NB]K−1A}kABAlice will sign anything with her private key.14The attack on early SSLB can open a connection to C and pretend to be A, as follows:1’. B → C : {kBC}KC2’. C → A : {NC}kBCWhen C challenges B with nonce NC, Bob sends NB= NCback to Aand uses her as an oracle.1. A → B : {kAB}KB2. B → A : {NC}kAB3. A → B : {certA, [NC]K−1A}kABA will sign anything, so B extracts [NC]K−1Aand he’s in:3’. B → C : {certA, [NC]K−1A}kAB15Fixing early SSLFix: replace [NB]K−1Awith [A, B, NA, NB]K−1A.1. A → B : {kAB}KB2. B → A : {NB}kAB3. A → B : {certA, [A, B, NA, NB]K−1A}kABMoral: Don’t let yourself be used as a signing oracle. Add your ownrandomness—and bind names—before signing.Credits: Abadi and Needham.16GSM challenge-responseA is cellphone handset, B is a base station.1. B → A : NB2. A → B : A, [NB]K−1AB, {data}kwhere k = f (KAB, NB) is the voice privacy key.Can you spot the weakness?17X.509 standard #1Sending a signed, encrypted message to B:1. A → B : A, [TA, B, {message}KB]K−1ACan you spot the flaw?18Breaking X.509 standard #1Look again:1. A → B : A, [TA, B, {message}KB]K−1AThere’s no reason to believe the sender was ever aware of the contents ofthe message.19An Attack on X.509 #1Example: Proving yourself by sending a password.Attacker M intercepts Alice’s encrypted password:1. A → B : A, [TA, B, {password}KB]K−1AThen M extracts {password}KB, and sends10. M → B : M, [TM, B, {password}KB]K−1MNow M is in, without needing to know the password.20Another Attack on X.509 #1Example: Secure auctions.The same attack provides an easy way for M to send in a copy of A’s bidunder his own name, without needing to know what A’s bid was.21LessonsAn important difference between• Authentication as endorsement (i.e., taking responsibility).• Authentication as a way of claiming credit.Encrypting before signing provides a secure way of assigning responsibility,but an insecure way to establishing credit.Moral: sign before encrypting.Credits: Abadi and Needham.22TMNPop quiz. Watch carefully.A, B establish a shared key kBusing the help of a fast server S:1. A → S : {kA}KS2. B → S : {kB}KS3. S → A : kA⊕ kBA recovers kBas kA⊕ (kA⊕ kB).Can you spot the flaw?23Breaking TMNLet’s play spot the oracle!The attack: Given {kB}KS, M, M0can conspire to recover kB:10. M → S : {kB}KS20. M0→ S : {kM0}KS30. S → M : kB⊕ kM0Now M, M0can recover kBfrom {kB}KS.Credits: Simmons.24Goss railway protocolA and B establish an authenticated shared key kAB= rA⊕ rB:1. A → B : A, {rA}KB2. B → A : B, {rB}KADo you see the subtle weakness?25Triangle attacks on GossIf session keys sometimes leak, the system breaks.M can recover rAfrom {rA}KBby opening a session to B and replayingA’s encrypted contribution to the key:1. M → B : C, {rA}KB2. B → M : B, {r0B}KMNow if M can learn kBMsomehow, he can compute rA= kBM⊕ r0B.Basically, if B lets session keys leak, M can use him as as a decryptionoracle to obtain rAfrom {rA}KB.Play the same games with A to recover rBfrom {rB}KA;you then learn kAB.Credits: Burmester.26Implementing protocolsExplicitness is powerful (and cheap).The mathematical notation1. B → A : NB2. A → B : {NB, kA,B}KAmight be implemented in practice as1. B → A : “Msg 1 from B to A of GSM protocol v1.0 is a challenge NB.”2. A → B : {“Msg 2 from A to B of GSM protocol v1.0 is a response tothe challenge NB; and A asserts that the session key kA,Bisfresh and good for communication between A and B on thesession where NBwas seen.”}KA(Can you see why each of the elements above are there?)27Implementing protocolsAny value received as cleartext should be treated as untrustworthy: youmay use it as a hint for performance, but don’t depend on it for security.Minimize