[SOLVED] CPSC 418 -ASSIGNMENT 2 Solved

Problem 1 Arithmetic in the AES MixColumns operation (20 marks)Recall that the MixColumns operation in AES performs arithmetic on 4-byte vectors using the polynomial M(y) = y⁴ + 1. In this arithmetic, we have M(y) = 0, so y⁴ = 1.c(y) = (03)y³ + (01)y² + (01)y + (02) ,that appears in MixColumns, where the coefficients of c(y) are bytes written in hexadecimal (i.e. base 16) notation. Arithmetic involving this polynomial requires the computation of products involving the bytes (01), (02) and (03) in the Rijndahl field GF(2⁸). Recall that in this field, arithmetic is done modulo m(x) = x⁸ + x⁴ + x³ + x + 1.t0
t1t2t3Note that this yields the matrix representation of MixColumns presented (without proof) in class.Problem 2 Error propagation in block cipher modes (12 marks)Error propagation is often an important consideration when choosing a mode of operation in practice. In this problem, you will analyze the error propagation properties of an arbitrary block cipher in various such modes; note that these properties are independent of the cipher used.Problem 3 Binary exponentiation (13 marks)Recall the exponentiation algorithm given in class for evaluating aⁿ (mod m) (a E Z, m, n E N):n = b02^k + b12^k_1 + + bk_12 + bk ,with b0 = 1, bi E {0, 11 for 1 < i < k, and k = Llog₂ n].r²_i (mod m) if bi+1 = 0 ,ibj2^i_j for 0 < i < k .Problem 4 A modified man-in-the-middle attack on Diffie-Hellman (10 marks)Suppose Alice and Bob wish to generate a shared cryptographic key using the Diffie-Hellman protocol. As usual, they agree on a large prime p and a primitive root g of p. Suppose also that p = mq + 1 where q is prime and m is very small (so p 1 = mq has a large prime factor, as is generally required). Since g and p are public, it is easy for anyone to deduce m and q; for example by successively trial-dividing p 1 by m = 2,4,6, and running a primality test such as the Fermat test on the quotient q = (p 1)/m until primality of q is established.Suppose an active attacker Mallory¹ intercepts g^a (mod p) from Alice and g^b (mod p) from Bob. She sends (g^a)q (mod p) to Bob and (g^b)q (mod p) to Alice.Problem 5 A simplified password-based key agreement protocol (8 marks)The following is a simplified (and hence problematic) version of the key generation phase of the password-based key agreement protocol that you are being asked to implement in Problem 9 (the programming problem). Here, a client first performs a one-time registration of their authentication credentials with a server. These credentials can then be used to generate authenticated session keys between server and client via communication over an insecure channel.All participants agree on a large public prime² N = 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 v gp (mod N) and provides the server with the pair (I, v) where I is the clients user id.³Protocol:¹This is a standard name for active attackers and is meant to be reminiscent of the word malicious. ²We denote this prime by N, rather than p, because the letter p is reserved for the clients password. ³In practice, this needs to be done in a secure and tamper-proof manner. Also, in the computation of v, the clientwould use a hash of their password p rather than just p. For details, see the protocol description in Problem 9.Server generates a random value b with 0 b N 1, computes B g^b (mod N), and sends B to client.Server retrieves clients authentication data (I, v) and computes _Kserver (Av)^b (mod N).Note that this protocol is similar to Diffie-Hellman, except that the clients password p and authentication credential v are incorporated in the key computation.Note that the exponents a and b are assumed to be unknown for both these problems. Show how an attacker Mallory who can solve any instance of the key recovery problem can solve any instance of the Diffie-Hellman problem. (So informally, breaking the key agreement protocol above is at least as hard as breaking Diffie-Hellman.)Written Problems for MATH 318 onlyProblem 6 Discrete logs with respect to different primitive roots (6 marks)Let p be a prime and g a primitive root of p. Recall that for any a E Z _p, the discrete logarithm of a with respect to g is unique integer x with 0 x p 2 and g^x ~ a (mod p).Recall that the discrete problem is asserted to be computationally intractable. This raises the natural question of whether this problem might be easier to solve for some primitive roots than for others. In this problem you will prove that that the difficulty of the discrete logarithm problem is independent of the choice of primitive root.Specifically, let g, h be primitive roots of p and assume that for any element in Z _p, computing its discrete logarithm with respect to g is easy. Give an algorithm for easily computing its discrete logarithm with respect to h.Let q 3 be a prime such that p = 2q+1 is also prime. Let g be any primitive root of p. Prove that with the exception of gq (mod p), all the odd powers of g (i.e. g, g³ (mod p), g⁵ (mod p), , gp2 (mod p)), are primitive roots of p.(Hint: the following fact about divisibility, which you may use without proof, might come in handy: for any three nonzero integers a, b, c, if a is a divisor of the product bc and gcd(a, b) = 1, then a is a divisor of c.)Problem 8 An algorithm for extracting discrete logarithms (25 marks)Let p be a large prime and g a fixed primitive root of p. Let h Z p be the modular inverse of g, so gh 1 (mod p). Let a Z _p. Define the following lists of elements in Z _p:yi ahⁱ (mod p), 0 i m 1; zj (g^m)j (mod p), 0 j k 1.Here, m is a positive integer (an as yet unspecified parameter) and k is the smallest integer with k (p 1)/m, so k (p 1)/m > k 1.(Hint: Division with remainder of x by m where x is the (unknown) discrete logarithm of a with respect to g.)Assume the worst case scenario where the entire list Z = (z0, z1,.. . , _zk1) needs to be generated before a match with an element in the list Y is found. How many modular multiplications are required to extract the discrete logarithm of a using the procedure above? Your count should be as accurate as possible (i.e. dont count modular multiplications that arent needed). You may assume that k and g^m (mod p) have been precomputed as they are independent of a.(Hint: Your answer should be a function of p thats close to p.)Programming Problem for CPSC 418 onlyProblem 9 Secure password based authentication and key exchange (37 marks)Overview. This problem considers the full, secure version of the password-based key agreement protocol introduced in Problem 5. This protocol, executed by a Client and a Server, allows the Client to demonstrate to the Server knowledge of a password, but neither the password nor any other information that could be used to derive the password need to be transmitted. Additionally, the Server does not store password-equivalent data, so someone who intercepts authentication data or steals them from the Servers database is unable to masquerade as the Client without brute-forcing the Clients password.To execute the protocol, there is an initialization and registration phase between the Client and Server. Doing this securely is in itself a complex problem, and so we instead perform a simplified version as described below.The Server initializes in the following manner:The Server performs registration as follows:^4A true implementation would not have this last feature, but it makes debugging much easier.The Client performs registration as follows:In a similar manner, if a Client connects to the Server and wishes to initiate the protocol, they will
first send a single byte corresponding to p before commencing with the protocol described below.Protocol.To generate and verify a shared authenticated session key, the Server and Client perform the following steps:Server generates a random value b with 0 b N 1, computes B kv + g^b (mod N), and sends s, B, where s is the Clients salt.Server computes Kserver (Av^u)^b (mod N).Steps 1-3 generate the authenticated key shared between the Client and the Server. Steps 4-7 verify that both parties have computed the same shared key. If executed honestly, _Kclient ^and _Kserver are equal and the Server and Client were able to authenticate each other and establish a shared session key.⁵The program template will do this for you, as well as check that the length of the username encodes to less than 255 bytes.⁶In cryptography, a salt is a random piece of data used as an additional input to a one-way function that hashes data, a password or passphrase.basic auth.pywhich performs the above password-based key agreement protocol. The program consists of functions corresponding to establishing a connection and transmitting data through a socket, parameter generation, and the actions performed by the Client and the Server.All messages over the socket should be echoed to standard output by both the sending and receiving party. Each echoed message should clearly indicate its sender and intended receiver. Use a template like the following:⁷Server: N = (integer value of N)Client: Received <(hex representation of incoming data)> Server: Authentication was successful.Client: ERROR, the socket was closed.For this exercise the hash function H will be SHA2-256 as implemented in the cryptography library. Additionally, when randomness is required use either os.urandom or the secrets library. We will allow use of the sympy library, as it is useful for handling prime numbers; however, you are expected to implement the function prim root on your own, and you may not use sympys primitive root() method in your implementation.Specifications. Fill in the empty functions in the template program basic auth.py. Once complete, you should be able to perform both registration and key agreement between two parties, one acting as the Client and the other as Server, by runningpython3 basic auth.py server 127.0.4.18:3180 python3 basic auth.py client 127.0.4.18:3180 python3 basic auth.py quit 127.0.4.18:3180You may also combine these actions with one invocation of basic auth.py, although this makes debugging substantially more difficult. There will be additional command-line options to change the username and password from the defaults.In detail, the functions youll need to fill in fall into roughly three categories:(i) create socket(), which creates a socket connection on the specified IP and port.⁷The printed text is primarily for human eyes, not computer parsing, so there is no need to match these examples precisely.Note: You may not use sympys primitive root method for your implementation.Note that some values may be supplied as an integer or as a bytes object; your functions will need to translate between them as the context requires. All numbers are converted to bytes via network byte order, which is big-endian.⁸ Additional details and documentation of these functions can be found in the template program found on the Piazza resources page.Submission. Submit a completed version of the template program with filenamebasic auth.pyIf youve spread your code across multiple source files, submit all of them.Provide a description of your implementation in a separate README file in text format. Do not include the written portion of the programming problem in the PDF file containing your solutions to the written problems. Your description should include the following:⁸Functions will be supplied with the template to help with conversion.