Auth - Homework Solutions

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?

Any mode except ECB is fine as long as you explain their advantages.

2. What do you need to pay attention to during the deployment of your chosen mode of operation?

Regarding different modes of operation:

• CBC mode: IV should be randomly sampled every time.
• CTR mode: Not a single input to the block cipher can be reused.
• OFB mode: IV should be different every time.

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.

If the session drops in the middle of the protocol before the user receives the PRG seed, then the server will finish the rest of the authentication protocol even though the user doesn't have sufficient material to log in later. Since users can't register more than once, this user is forever locked out of this platform.

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.

We should add an expiry date to the certificate and include it in the server's signature. When verifying a certificate, we should also ensure that it has not yet expired.

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.

Consider the following execution where Eve controls all communication between the user and the server:

• Eve generates a Diffie-Hellman pair \((e, g^e)\) for use later.
• The user sends \((g^a)\) to Eve.
• Eve sends \((g^e)\) to the server, who then responds with \((g^b, \sigma_s)\). Both Eve and the server compute shared secret \(g^{eb}\).
• Eve finally responds to the user with \((g^b, \sigma_s)\). The user computes shared secret \(g^{ab}\).

The user and server have finished their key exchange, however the server has a shared key with Eve (\(g^{ae}\)) while the user has a shared key with the server (\(g^{ab}\)).

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.

The Diffie-Hellman key exchagne (and the underlying Diffie-Hellman assumptions) guarantees that it is computationally hard for Eve to figure out \(g^{ab}\), so any message sent from the user to the server encrypted using (a derived key from) \(g^{ab}\) remains hidden to Eve.

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.

The only value the user sends over the wire is \(h := H(pw || salt)\), which will be the same every time the user logs in. Thus, our authentication scheme isn't truly a test of knowledge of the password, but rather a test of knowledge of the hash of the salted password. By sending \(h\) in another session, the adversary can authenticate themselves as the user (assuming they pass the 2FA step).

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.

In the login step, the salt is sent to the user allowing them to compute \(H(p || \sigma)\) properly. Afterwards, the server will run through all possible \(\rho\) values, and it is bound to find one that hashes correctly to \(c'\). Since \(k\) is fairly small, this brute-force search is fast.

2. Explain an (inefficient) attack in case the server's entire database is compromised.

For a user with stored \((id, c', \sigma)\) on the server's database, an attacker could try a possible password \(p'\) by computing \(H(H(p' || \sigma)||\rho)\) for all \(\rho \in \{0, 1\}^k\) to match \(c'\).

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.

For a user with stored \((id, c, \sigma)\) on the server's database, an attacker could try a possible password \(p'\) by computing \(H(p' || \sigma)\) to match \(c\). This is essentially password hashing with only salting and no pepper.

Alternatively: adversary can send \(c\) over the wire to authenticate.

4. What roles do the salt and pepper play against offline dictionary attacks, respectively?

Salt: the attacker has to run a seperate dictionary attack for every user.

Pepper: the computation cost for the attacker to try every single \((id, p')\) is \(2^k\) times more expensive.

5. Given salt-and-peper hashing, can a user safely use a simple/weak password?

No. In case the server's database is compromised, even with salt-and-peper hashing, it is still fairly easy to recover a user's password (using the attack in (2)) if the password is too weak (namely, chosen from a small space).

6. Explain why we might want to use a slow hash function in authentication.

Similar to using a pepper to slow down each step of a brute-force solution, an inefficient hash function would make everything slower for a brute force attack.

7. Explain why we might want to use a memory-hard hash function in authentication.

If our adversary is not compute-bound, but rather memory-bound (i.e. they have access to many GPUs), then having a memory-intensive hash function would bottleneck them at their memory, protecting against GPU-based brute force attacks.

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?

Similarly to how the server signs a certificate for a user, we allow users to sign certificates for other users using their signing keys. To verify, we go up the chain until we reach a trusted server; that is, we verify each certificate by verififying its signer until we hit the server. This is essentially a certificate chain in the public key infrastructure (PKI).

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?

Any user with a certificate signed by \(u\), and downstream from there.