Key equivalence II: Symmetric Cryptography

| Comments (1) | COMSEC
In our previous episode, we talked about key equivalence in physical locks and password systems. As you'll recall, conventional password systems have the problem that the authenticating party (i.e., the user, hereafter called the AP for generality) needs to provide their password to the verifying party (VP, i.e., the server). This has (at least) two bad properties:
  1. An attacker who can intercept your communication with the verifying party or who temporarily controls the verifying party can capture your authenticator (password) when you use it to log in and use it to impersonate you to that verifying party.
  2. An attacker who can intercept your communication with the verifying party or who temporarily controls the verifying party can capture your authenticator (password) and use it to impersonate you to other verifying parties with which you used the same password (and you know you do)

The way to solve the first problem is to have a protocol that allows the AP to prove that they know the password without actually revealing it to the VP. The standard solution to this is what's called a challenge-response protocol. The VP provides the AP with a randomly chosen challenge (technically the challenge just has to be one the VP hasn't used before, but this is almost always chosen randomly) and the AP computes some one-way function of the password/key as the response. The VP stores a copy of the password/key and can thus independently recompute the response. If they match, then the VP knows the AP is who he says he is (or at least knows the password/key).

But wait, last time I said that it was bad for the VP to have the password:

This has a big problem. If someone breaks into the server and gets a copy of the password list they get a copy of everyone's password and can impersonate users. This is what's called a password equivalent or a key equivalent for reasons that will become clear a little later. This lets them leverage a disclosure exploit (i.e., one that lets them read files on a system) into an intrusion exploit (i.e., one that lets them break in or pose as another user). It also means that the password file has to be stored with very strict permissions.

Previously, we solved this problem by storing the hash of the password, but that worked because the AP gave the VP the password to hash. In a challenge-response system the VP needs to independently compute the response. Now, you can of course compute the response based on the password hash rather than the password, i.e., response = F(challenge, H(password)) but that doesn't solve the problem because the VP's password file contains H(password). So, while you don't actually have the password you have a value which is equivalent to it, hence the term password equivalent. Anyone who compromises the password file can impersonate the AP to the VP. So, we've solved the problem of someone intercepting1 the authentication exchange being able to impersonate the AP but we've actually made the problem of password file theft worse.

We can improve the problem somewhat by making sure that each VP has a different password. Then at least you can't compromise one VP and use it to attack another. Of course, it's not practical to believe that people will actually use a different password for each of the 30 web sites they have logins for, but you can solve this problem by hashing in the name of the VP to the stored password. I.e., the VP stores H(VP-name, password)2 and the response is computed using that value as the input. So, if you get at a VP's password file you can impersonate APs to that VP, but not to any other VP. This is an improvement (call it weak password equivalence), but it's not perfect. However, it's the best we can do with symmetric cryptography. In our next installment, we'll see how to improve the situation still further.

1. Well, mostly. An attacker can still mount a man-in-the-middle attack on a single authentication, and then pose as the AP for the duration of that session, but he can't reuse the captured authenticator later. Moreover, this attack can be fixed by binding the challenge-response to a cryptographically protected channel between client and server. One example of this is TLS pre-shared key mode (RFC 4507). 2. Yeah, I'm sure you'd rather use HMAC, but a hash is close enough to get the idea across and is mostly secure in most settings.


You're committed to finishing this series, 'cause I've linked it here, so my thous...uh... tens of readers are waiting for each installment with bated breath.

Leave a comment