Key Establishment ================= Our setting so far: Alice and Bob share a (symmetric) secret key, can encrypt/MAC messages Alice and Bob know each other's public keys, can encrypt/sign messages usually public-key crypto is used to bootstrap a fresh symmetric key significant problem in using crypto: where do Alice and Bob get these keys? Direct key exchange Alice and Bob physically meet and exchange keys what needs to happen to make this key exchange meaningful? if exchanging symmetric secret keys, need privacy -- no eavesdroppers Alice and Bob must authenticate one another -- no impersonators Alice and Bob must record keys for later use if they only talk to one another, then it's straightforward if they talk to multiple parties, need to have names for keys afterwards, Alice and Bob can encrypt and authenticate messages where does direct key exchange get used? computer manufacturer might embed a key in the computer they sell you computer now shares key with manufacturer, e.g. to verify updates A is manufacturer, B is computer first-time account creation for new employees in a company walk up to the system administrator, agree on a password A is user, B is administrator user interacting with computer; eg. computer creating public/private key A is user, B is computer often not practical for much more than bootstrapping but some physical key exchange is necessary as basis for next steps Indirect key exchange suppose A, B can't meet in person, but met & exchanged keys with common S A --- S --- B if A and B trust S, S can help A and B set up a key between them goal is to achieve same security as if A and B met, assuming S is good turns out, designing a protocol to do this can be tricky Protocol notation keys K_AS is symmetric key shared between A and S K_BS is symmetric key shared between B and S { M }_K: message M encrypted and authenticated by K recall: usually a bad idea to use same key for encryption & auth'n typical: derive K_Enc and K_Mac from K, then use them for ENC & MAC many protocols use a nonce ("number used once") to avoid replay of messages N_A: nonce generated by A can implement as a counter, or a random number Needham Schroeder symmetric protocol assume A and B share keys with S, called K_AS and K_BS goal: A and B know K_AB that has two properties: (i) K_AB is only known to A and B (ii) K_AB is fresh (never been used before) 1. A -> S: A, B, N_A requests the server S to introduce Alice to Bob 2. S -> A: { N_A, K_AB, B, blob }_{K_AS} where blob = { K_AB, A }_{K_BS} new key K_AB that will be shared between A & B, and a blob for B 3. A -> B: blob = { K_AB, A }_{K_BS} B can decrypt and authenticate blob because it knows K_BS 4. B -> A: { N_B }_{K_AB} challenge A (or whoever knows K_AB) to prove they're participating otherwise, this could be an adversary replaying an earlier blob 5. A -> B: { N_B - 1 }_{K_AB} respond to the challenge (why subtract one?) ==> At this point, A and B can use K_AB to communicate securely this protocol is close to what Kerberos does in practice users and servers are principals keys for users are derived from their password using a ~hash function who knows K_AB? all three parties (S, A, and B) S must be trusted to forget K_AB, otherwise we don't get goal (i) why doesn't A prove to S that it knows K_AS? why do we need B's name in step 1? why do we need A's name in the blob in steps 2 and 3? what if we skip the nonces? adversary could replay all messages from an earlier session e.g. request to delete a file, if user A talking to file server B what are names used for in this protocol? handles for principals (e.g. A decides it wants to talk to B) identifiers that can be embedded in messages (describe a principal) addresses for sending msgs (when B is contacted in 3, it responds to A) as we will see later, naming is a crucial part of key setup protocols Needham Schroeder public-key protocol notation may look somewhat different in the public-key setting PK_A is public key for A SK_A is secret key for A {M}_SK is message M signed with secret key SK (need PK to verify) {M}_PK is message M encrypted with public key PK (need SK to decrypt) assume A and B know PK_S, and S knows PK_A and PK_B 1. A -> S: A, B requests an introduction to B 2. S -> A: { PK_B, B }_{SK_S} server responds with B's public key, and signs so that A can verify 3. A -> B: { N_A, A }_{PK_B} A tells B it wants to communicate, and picks a fresh nonce 3a. B -> S: B, A 3b. S -> B: { PK_A, A }_{SK_S} B finds A's public key, if it doesn't know already. A could have also done the same, and included 3b in its request 4. B -> A: { N_A, N_B }_{PK_A} B proves it's alive and participating by decrypting N_A chooses its own nonce N_B to verify A is really participating 5. A -> B: { N_B }_{PK_B} A proves it's participating as well ==> At this point, A and B know N_A and N_B, and noone else does (assuming S was trustworthy). Can use N_A and N_B to compute session key K_AB. N-S public-key protocol attack discovered by Gavin Lowe in 1995 (17 years after protocol first described) found in the process of trying to prove the N-S protocol secure attack: trick A (in some external way) to initiate a session with adversary E, at which point E will replay messages to B, and convince B that B is really talking to A! 3. A -> E: { N_A, A }_{PK_E} 3. E -> B: { N_A, A }_{PK_B} E decrypts the message using SK_E, re-encrypts using PK_B 4. B -> E: { N_A, N_B }_{PK_A} 4. E -> A: { N_A, N_B }_{PK_A} E passes challenge unmodified to A 5. A -> E: { N_B }_{PK_E} 5. E -> B: { N_B }_{PK_B} E decrypts N_B using SK_E, re-encrypts it using PK_B ==> At this point, E knows N_A and N_B, and B believes that N_A and N_B are a shared secret with A! what went wrong? in step 4, E was able to pass the message unmodified, and A decrypted it, allowing E to pass the challenge. at some level, A and B disagreed on what message 4 meant. B thought it was a challenge from B to A, so it encrypted with PK_A. A thought it was a challenge from E to A, so it responded to PK_E. assumptions (i.e. who you are challenging) not expressed in message fix: include the sender of the challenge in message 4 i.e. { N_A, N_B, B }_{PK_A} a general principle for making protocols secure against certain attacks: include any assumptions/context in which message should be interpreted include a hash of all messages seen in the protocol so far (ensures both parties are seeing the same exact messages) Key establishment protocols a large number of protocols have been developed for different settings typical problems facing a key establishment protocol: naming (how do you tell someone "this Alice"?) identification (how does a user prove they are who they say they are?) trust in authorities, intermediaries scalability usability (often related to naming and trust decisions) how do the NS protocols rate in these categories? naming: server has a single name space (arbitrary strings) identification: server keeps shared key or public key for every user trust: one server, fully trusted (can impersonate anyone) scalability: symmetric protocol requires online access to S public-key protocol could function without S, but S might still be a bottleneck for new users usability: flat names easy to use in single org (e.g. MIT Kerberos) one fully-trusted server works well in single org too next time: how do we scale up key exchange?