Auth - Homework

Please answer the following questions in no more than a few sentences each. We don't expect formal proofs; rather, just a high-level argument from intuition. Please submit your answers as a PDF to Gradescope.

Block Cipher Modes of Operation

1. If you were a security engineer and would like to adopt block cipher in your system for symmetric-key message encryption, which mode of operation (among ECB/CBC/CTR/OFB modes) would you choose? Why?
2. What do you need to pay attention to during the deployment of your chosen mode of operation?

Authentication

1. During registration, we ask the user to provide a valid PRG response, even though we just sent the user the PRG seed. Is this step necessary? Hint: we don't allow users to register more than once, and our network may not be stable.
2. A time-to-live, or TTL, specifies the expiration date for a certificate. This is useful if we don't want to indefinitely authenticate a user, but rather clear a user for the next day or so. Explain how you would extend our existing protocol to support TTLs. Be sure to ensure that a user can't change the TTL of their certificate without help from a trusted server.

Man-in-the-Middle

In the Auth project, the user and server first perform an authenticated key exchange step. In particular, the user first sends $$(g^a)$$ where $$g^a$$ is the user's public value. Then, the server sends back $$(g^b, g^a, \sigma_s)$$, where $$g^b$$ is the server's public value and $$\sigma_s$$ is a signature computed on $$(g^a, g^b)$$. Consider a slightly modified protocol where instead the server sent back $$(g^b, \sigma'_s)$$ where $$\sigma'_s$$ is a signature on $$(g^b)$$.

1. Explain a potential man-in-the-middle attack that could arise in the modified protocol.
2. Explain why such a man-in-the-middle adversary still cannot learn anything about the encrypted messages sent from the user to the server.
3. Consider a weaker authentication scheme without 2FA. Suppose an adversary was able to successfully learn the shared secret $$g^{ab}$$ during the registration or login phase. Explain why, even though we never send the password over the wire, and even if the user chooses a very strong password, the adversary may be able to authenticate as this user in the future.

Offline Dictionary Attacks

Our password storage scheme is designed to protect against adversaries tha could potentially corrupt the entire storage of the server. Given a (collision-resistant) hash function $$H$$ and a password $$p$$, the following is how we register and login:

Registration: First, the user sends their id $$id$$ and the server sends a random $$\lambda$$-bit salt $$\sigma$$ to the user. Next, the user computes $$c = H(p || \sigma)$$ by hashing the password with the salt appended. The user then sends their user id $$id$$ and $$c$$. Next, the server will choose a random pepper $$\rho \in \{0, 1\}^k$$ for some small $$k$$ and compute $$c' = H(c || \rho)$$. Finally, the server stores a row $$(id, c', \sigma)$$.

Login: First, the user sends their id $$id$$ and the server responds with the stored salt $$\sigma$$ to the user. Next, the user computes and responds with $$c = H(p || \sigma)$$ by hashing the password with the salt appended. The server will then try for all $$\rho \in \{0, 1\}^k$$ computing $$c' = H(c || \rho)$$, and authenticating the user if $$c'$$ matches the stored value for any $$\rho$$.

1. Explain why this verification scheme is correct; that is, a valid password should be cleared for login.
2. Explain an (inefficient) attack in case the server's entire database is compromised.
3. Explain an attack if the server only stored $$c$$ instead of hashing it again with a pepper to obtain and store $$c'$$ in case the server's entire database is compromised.
4. What roles do the salt and pepper play against offline dictionary attacks, respectively?
5. Given salt-and-peper hashing, can a user safely use a simple/weak password?
6. Explain why we might want to use a slow hash function in authentication.
7. Explain why we might want to use a memory-hard hash function in authentication.

Delegated Trust

The way that our authentication scheme works is that since we trust the server, the server can delegate trust to others that it trusts, allowing us to verify the identity of a third-party without consulting directly with the server. We'll explore the ideas behind larger schemes like CA Certification.

1. Propose a protocol that allows users to delegate trust to other users. What does delegation look like? What does verification look like?
2. Let's say a secret signing key of some user $$u$$ has been compromised, and assume we have some way of invalidating certifications (e.g. a public revocation board). Which users should have their certificates invalidated and reissued in the case of such a compromise?