Symmetric-key login protocol

Question

I'm trying to analyze a login protocol based on symmetric key cryptography. I'm just starting out, so this may very likely be a very bad idea, but nonetheless I'd like to hear your thoughts on it.

The protocol assumes the existence (and agreement on) the following:

• A symmetric-key algorithm $E$ / $D$.
• A key derivation function $KDF$.
• A "strong" hash function $H$.

Additionally, the server $S$ has a secret key $k_{S}$.

When a user $U$ wants to register on a server $S$, the following happens:

1. $S$ generates a random bit string $b_{S}$.
2. $S$ encrypts $b_{S}$, yielding $v_{S} = E_{k_{S}} (b_{S})$.
3. $S$ computes $h_{S} = H(b_{S})$.
4. $S$ sends the pair $\langle v_{S}, h_{S} \rangle$ to the user (this is the server's "verification pair").
5. $U$ chooses a password $p$ and uses $KDF$ to get $k_{U} = KDF(p)$, its secret key.
6. $U$ generates a random bit string $b_{U}$.
7. $U$ encrypts $\langle b_{U}, v_{S}, h_{S} \rangle$ yielding $v_{U} = E_{k_{U}} (\langle b_{U}, v_{S}, h_{S} \rangle)$.
8. $U$ computes $h_{U} = H(b_{U})$.
9. $U$ sends the pair $\langle v_{U}, h_{U} \rangle$ to the server.
10. $S$ stores $v_{U}$ and $h_{U}$, associating them to $U$'s username (or whatever means of identification is used).

Now, in order for a user to authenticate to a server, the protocol proceeds as follows:

1. $U$ "requests" a login from $S$.
2. $S$ responds with $v_{U}$.
3. $U$ decrypts $v_{U}$ getting $\langle b_{U}, v_{S}. h_{S} \rangle = D_{k_{U}} (v_{U})$.
4. $U$ verifies the server's identity:
   1. $U$ sends $v_{S}$ to the server.
   2. $S$ decrypts $v_{S}$ getting $b_{S} = D_{k_{S}}(v_{S})$.
   3. $S$ generates a random bit string $b'_{S}$.
   4. $S$ encrypts $b'_{S}$, yielding $v'_{S} = E_{k_{S}} (b'_{S})$.
   5. $S$ computes $h'_{S} = H(b'_{S})$.
   6. $S$ sends $\langle b_{S}, v'_{S}, h'_{S} \rangle$ back.
   7. $U$ verifies $H(b_{S}) = h_{S}$.
5. If the above procedure was successful, $U$ continues, otherwise, $U$ aborts.
6. $U$ generates a random bit string $b'_{U}$.
7. $U$ encrypts $\langle b'_{U}, v'_{S}, h'_{S} \rangle$ yielding $v'_{U} = E_{k_{U}} (\langle b'_{U}, v'_{S}, h'_{S} \rangle)$.
8. $U$ computes $h'_{U} = H(b'_{U})$.
9. $U$ sends the triplet $\langle b_{U}, v'_{U}, h'_{U} \rangle$ to the server.
10. $S$ verifies $H(b_{U}) = h_{U}$.
11. If the above procedure was successful, $S$ continues (logging $U$ in), otherwise, $S$ aborts.
12. $S$ replaces $v_{U}$ with $v'_{U}$ and $h_{U}$ with $h'_{U}$ for the user.

I know this looks involved, but it's actually pretty simple. The proof $U$ gives to $S$ is knowing how to decrypt a ciphertext into a plaintext with a given (known to $S$) hash. In order to avoid having to persist state on the user's side, more information is encrypted inside $v_{U}$ so that the user may verify the server is who he says it is (by the very same means as he, the user, authenticates to him, the server).

One of the properties I find interesting of this protocol in particular is the fact that no keys need be exchanged at all (something like Shamir's 3-way protocol), and that the server stores no password-equivalent information, furthermore, it resembles (somewhat) Lamport's chained hash login (S/KEY).

So my questions are:

1. Does this work?
2. Are there any evident attacks on it?
3. Is this any better / worse (probably worse) than any other authentication protocol?
4. what can be said about the security provided by this protocol?

Furthermore, I'd like to keep it strictly symmetric-cipher + hash based.

Sorry for the lengthy description, I'd welcome an edit by someone more knowledgeable.

Answer 1

I think my definition of 'simple' is different from yours. : )

Are there any evident attacks on it?

It's vulnerable to man-in-the-middle attacks, like:

Step 9: M replaces $\langle b_{U}, v'_{U}, h'_{U} \rangle$ with $\langle b_{U}, v_{M}, h_{M} \rangle$, where they've calculated their own random bit string and used their own key to encrypt it. Now M can log in as U (and U can't).

That means it's probably no more secure than if you left out the server identification in step 4. and all the related $v_S$ and $h_S$. The identification isn't strong, because there's no authentication for any of the other data exchanged.