Problem 5 - A password-based key agreement protocol (7 marks) Consider the following password-based key agreement protocol which allows a server (e.g. UCIT's central computer) and a registered client (e.g. you) to agree on a shared cryptographic key. Here, the client first performs a one-time registration of their password-based authentication credentials with the server. These credentials can then be used to generate authenticated keys between server and client via communication over an insecure channel. All participants agree on a large public prime 2N=2q+1, with q prime, and a public primitive root g of N. Each client has their own password p. To register with the server, a client computes vgp(modN) and provides the server with the pair (I,v) where I is the client's user id..3 Protocol: 1. Client generates a random value a with 0aN1, computes Aga(modN), and sends (I,A) to server, where I is the Client's user id. Server generates a random value b with 0bN1, computes Bgb ( modN ), and sends B to client. 2. Client computes KclientBa+p(modN). Server retrieves client's authentication data (I,v) and computes Kserver(Av)b(modN). Note that this protocol is similar to Diffie-Hellman, except that the client's password p and authentication credential v are incorporated in the key computation. a. [2 marks] Prove that Client and Server have a shared key after executing this protocol, i.e. prove that Kserver=Kclient. b. [3 marks] Suppose an adversary Mallory obtains client Ian's authentication data (I,v) (by intercepting Ian's transmission to the server upon his registration or by hacking into the server's database). Show how Mallory can masquerade as Ian, i.e. execute the protocol with the server and generate a valid key Kclient that the server believes is shared with Ian. Hint: Let Mallory generate a random value a with 0aN1. Since she receives B from the server, she can compute Ba(modN), and she wants to make this value the shared key. In order to achieve that, she needs to find a value A such that the server's key computation produces Ba(modN), i.e. (Av)bBa(modN). So how does she choose A ? c. [2 marks] Consider the following two problems: - Key Recovery Problem: Given any values Aga(modN) and Bgb(modN) and any vZN, find the server key Kserver(Av)b(modN). - Diffee-Hellman Problem: Given any values Aga(modN) and Bgb(modN), find a Diffie-Hellman key Kgab(modN). Note that the exponents a and b are assumed to be unknown for both these problems. Suppose an attacker Mallory can solve the key recovery problem for any inputs A,B,v. Show how she can solve the Diffie-Hellman problem for any inputs A,B. (So informally, breaking the key agreement protocol above is at least as hard as breaking Diffie-Hellman.) Hint: Don't overthink this. This is a really easy question. 2 We denote this prime by N, rather than p, because the letter p is reserved for the client's password. 3 In practice, this needs to be done in a secure and tamper-proof manner. Also, in the computation of v, the client would use a hash of their password p rather than just p. But we disregard these issues here