CS 261 Computer SecurityCrypto Protocols - Design & AnalysisLecture by Prof. David WagnerScribe: Thomas KhoNovember 20, 20071 Certificates vs. Public KeysIn public key crypto, you need to know principals’ public keys to make surethat you’re not talking to an impostor. The goal of a public key infras-tructure (PKI) is to ensure that the name-to-public key binding is secure.For example, one way you might achieve this is if the telephone companypublishes the name-public key associations in the phone book. This impliestrust in the telephone company.Certificates are of the form[DavidW agner, 0xDEF 8...]CAwhere 0xDEF8... is the public key of David Wagner and the message(certificate) is signed by a certificate authority (CA).1.1 Kerberos vs. PKIWe can contrast this to Kerberos: instead of a placing trust in a KDC, weinstead trust a certificate authority.In Kerberos, revocation is sim ple–you delete an account and all acc es swill be revoked once any outstanding keys expire. Key revocation is not sosimple with certificates. In a PKI, revocation can be done by publishing acertificate revocation list of all certificates that have been revoked. Anotherway of revocation in a PKI is an online system like OSCP where one queriesa CA to see if a key has been revoked. Yet another alternative is to haveexpiration dates on certificates.1One advantage of a PKI over Kerberos is that PKI allows multiple co-existing certificate authorities and hierarchical chains of trust. For example,one might have the arrangement:CA/ \UCB Stanford/ \ / \DAWThe above is a certificate chain in which the CA asserts UCB’s identityand UCB asserts user DAW’s identity.An unstrutured form of the above is the Web of Trust approach wherepeers sign each others’ keys to extend trust.PKI allows for a public key to be signed by multiple CAs, and someonewho receives a certificate signed by multiple CAs can check if he trusts anyof the CAs that have signed the certificate.2 Discussion of paperMost of class was spent looking at proposed protocols and noting their flaws,and the discussion follows the protocols examined in the paper. Most of thiscontent can be found in the slides accompanying the lecture.2.1 Notation1. A → B : X means that the protocol des igner intended for the messageX to be sent by A to B, with no assurances to secrecy or reliability of thecommunications channel.2.2 WarmupWe’re given the following protocol:1. A → B : A2. B → A : NB3. A → B : [NB]K−1A4. A → B : {message}KB5. A → B : {message0}KB2The flaw in this protocol is that there is no binding of the message sentin (3) to messages (4) and (5). There’s no authentication in either me ss ages(4) or (5) that they came from A.2.3 Denning-Sacco #1, key exchange1. A → S : A, B2. S → A : certA, certB3. A → B : certA, certB, {[kAB, TA]K−1A}KBThe flaw in this protocol is that B can re-encrypt mess age (3) and sendit to C, and C will think that it was sent to C from A.The moral is to be explicit and to bind names with messages. Signaturesserve to bind together parts of a message’s contents so that one c annotchange any field of the message.2.4 SSL version 1, key exchange with mutual authenticationThere was a flaw in version 1 of the SSL protocol:1. A → B : {kAB}KB2. B → A : {NB}kAB3. A → B : {certA, [NB]K−1A}kABA hint to finding the flaw in this protocol (SSL version 1 was neversubmitted for standards) is that A will sign anything with her public key([NB]K−1Ain message (3)).The obvious flaw given the hint is that Alice becomes a signing oracleand will sign arbitrary messages. This leads to the following attack: animpostor B can connect to C and pretend to be A.1’. B → C : {kBC}KC2’. C → A : {NC}kBC1. A → B : {kAB}KB2. B → A : {NC}kAB3. A → B : {certA, [NC]K−1A}kAB3’. B → C : {certA, [NC]K−1A}kAB3B initiates a connection with C, which authenticates via a signed nonceNC. B turns around and challenges A with this same nonce NCin a differentSSL session (where B is the server) and has A sign NC. B can then extractthe signed NCfrom (3) and use it in his session with C (3’) to gain A’scredentials.2.5 ”How could I have found this?To discover something like this SSL flaw, it might be instructure to gothrough the goals of the protocol in your head. For example, the main goalsmight be for A and B to know they’re talking with each other and not withan impostor, and that the key remains a secret. With a set of listed goals,it’s easier to see if any are violated.The fix to the protocol is to introduce more information. The message[NB]K−1Ashould be replaced with [A, B, NA, NB]K−1A.The moral here is that you shouldn’t let yourself be used as a signingoracle by naming principals and adding randomness to anything you sign.2.6 GSM challenge-responseGSM is the communications protocol used by some c ell networks. A handsetA and a base station B communicate with a long-lived symmetric key KAB:1. B → A : NB2. A → B : A, [NB]K−1AB, {data}kwhere k = f (KAB, NB) is the voice privacy key.One weakness in this protocol is that the base station never authenticatesitself to the handset. While a fake base station could not decode the data,it could mount a denial of service to the handset.2.7 X.509 Standard #1The protocol is for sending a signed, encrypted message from A to B asfollows:1. A → B : A, [TA, B, {message}KB]K−1AThe subtle issue in this protocol is that there is no indication that Aknew the contents of the message. For example, take a system where youprove your identity by sending a password. Alice proves she has acce ss to asystem by sending a password:41. A → B : A, [TA, B, {password}KB]K−1AAn attacker could extract {password}KBand sends:1’. M → B : M, [TM, B, {password}KB]K−1MAnother example where this can introduce iss ues is in se cure auctions,where an eavesdropper can duplicate another bidder’s bid without knowingthe bid amount.The takeaway from this example is the role that authentication can playin systems:1. Authentication as endorsement (i.e. taking responsibility)2. Authentication as a way of claiming credit (i.e. stating authorship)Signatures serve purpose (1) but not (2), and the moral is to sign beforeencrypting.2.8 An aside on timestamping servicesTimestamping services serve to provide unforgeable signatures that bind adocument to a time. One proposal is to use hash chains, which have thefollowing form:M1M2M3M4↓ ↓ ↓ ↓ hashH1H2H3H4↓ ↓ ↓ ↓0 → X1→