Key equivalence III: Asymmetric Techniques

| Comments (2) | COMSEC
As I mentioned earlier, all symmetric authentication mechanisms have some level of key/password equivalence. However, this can be removed with asymmetric (aka "public key") techniques.

The simplest such technique is very much like a challenge/response technique except that the response sent by the AP is a public key digital signature. The way that this works is that the VP knows the AP's public key but not the AP's private key. The VP then provides the AP with a random challenge and the VP returns: Sign(Kpub, Challenge.1. This technique is what's used in SSL client authentication and in the SSH RSA and DSA modes (sometimes used with certificates). A related technique is to have the AP have a encryption/decryption key rather than a signature key and have the VP encrypt a message under that key (this is how SSL server authentication often works).

So, if these techniques are so great, why aren't they used all the time? There are a number of reasons:

  1. Public keys are hard to work with. They require the AP to have a public key pair stored on a disk somewhere (impairing portability) and requires some way to carry a fairly heavyweight data object (~100 bytes of binary data) to the server. People put up with this for SSH but they don't like it.
  2. It doesn't provide mutual authentication (and inherently can't because the server only has the public key). Obviously, you can have the server have a public key pair as well, but that makes the key management problem even more annoying.

The first problem is soluble, at least in part if you're willing to trade in some security. The idea here is that you generate your key pair by hashing your password. Then the AP doesn't need to store a public key (again, assuming that you have some other method of authenticating in the other direction). The security tradeoff here is that an attacker can now mount a dictionary attack on your communications with the server unless they're encrypted. He just captures a transcript and then keeps generating trial passwords until he finds one that generates the right private key and hence signature. Of course, this problem already existed with challenge/response-based password mechanisms so the problem hasn't been made any worse.

We can also improve the problem of the key that gets copied to the VP by storing a hash of the key rather than the full key. The AP then needs to provide the public key which can be compared to the hash. This brings the size of the data stored by the VP down to about 128-160 bits. An alternative is to simply give the VP the password on initial registration and let him compute the private/public key pair and then "forget" the password. This obviously needs to be used with some technique to ensure that the private keys are different for multiple VPs even if you use the same password all the time. None of these techniques solve the mutual authentication problem, which needs to be attacked by other means.

This brings us to the topic of zero-knowledge password proofs (also known as password-authenticated key agreement. These protocols use public key techniques to allow two parties who jointly share a password to establish a shared key which is not accessible to any attacker. These protocols can also be constructed so that the VP does not have a password/key equivalent. This differs from the easier-to-understand public key techniques in two important ways. First, they support mutual authentication natively. Second, they don't allow the attacker to mount a dictionary attack on a single connection. For each guess he wants to check he needs to do an online communication with one side. The major remaining attack is that the VP can mount a dictionary attack on his stored value in an attempt to recover the AP's password (though of course the AP/VP terminology is less useful in a mutually authenticated environment). Short of using high-entropy passwords/keys, this attack doesn't seem removable.

1. Actually standard practice is for the AP to provide some randomness of its own, but the attacks where that's relevant aren't that important for understanding the concept.


See for an attempt at a ZKPP protocol that equates the VP stored credential attack to breaking RSA.


The VP then provides the AP with a random challenge and the VP returns: Sign(Kpub, Challenge.

I believe that should read:

The VP then provides the AP with a random challenge and the AP returns: Sign(Kpri, Challenge).

Leave a comment