Is this variant of SRP for peer-to-peer authentication practical?

Question

I'm interested in using a modified form of SRP as a peer-to-peer authentication method. Since neither side is acting as a host, one of the primary design goals for SRP (that the client doesn't need to know anything but an identity and password, so no key management is required) isn't really necessary.

There's a variant of SRP called SRP-Z where the server also has a secret key, and the verifier for that key is public. While this variant is not authorized by the free license from Stanford, I'm not concerned with that here (the patent expires in three years anyway - and I'm not trying to detract from Tom Wu's creation, I think it's absolutely brilliant).

The Secure Remote Password paper and patent describe a generalized Asymmetric Key Exchange formula thus:

$S(R(P(w), P(x)), Q(y, z)) = S(R(P(y), P(z)), Q(w, x))$

for all $w$, $x$, $y$, $z$

and that for SRP:

$P(x) = g^x$
$Q(w, x) = w + ux$
$R(w, x) = wx^u$
$S(w, x) = w^x$

With $w$, $x$ being the user secrets and $y$, $z$ being the server secrets ($w$ and $y$ being the ephemeral values, $x$ the user's password-derived key and $z$ the server's secret key), setting values as SRP does and substituting in (and adding a new value $h$ as the server's public key) you get:

$k = H(N, g)$
$v = g^x$
$h = g^z$
$A = g^w$
$B = g^y$
$AP = A + kh$
$BP = B + kv$
$u = H(AP, BP)$
$S = (Av^u)^{y + uz} = (Bh^u)^{w + ux} = g^{(w + ux)(y + uz)}$

($AP$ and $BP$ are the values sent between client and server, for simplicity I retain $A$ and $B$ as the simple exponential value)

That's the SRP-Z form of the SRP formula, and I haven't really seen anything describing it.

With normal SRP, $z$ = 0 and $h$ = 1, the above reduces to the standard SRP basic key exchange formula:

$S = (Av^u)^y = B^{w + ux} = g^{wy + uxy}$

(since $k$ and $h$ are constant, it is no longer useful to add $kh$ when sending the value of $A$ to the server)

SRP then creates a proof-of-knowledge and specifies that the client sends the proof before the server does (preventing an off-line dictionary attack). The other place where the protocol is not identical on both sides is in the calculation of $u$.

If instead of a single value of $u$, you use two values $t$ and $u$, where

$t = H(AP, BP)$
$u = H(BP, AP)$
$S = (Av^t)^{y + uz} = (Bh^u)^{w + tx} = g^{(w + tx)(y + uz)}$

then the protocol can be handled identically on both sides ($t$ on one side is the same as $u$ on the other).

Proving that both sides have the same value of $S$ is not quite so straightforward, since either side can present the proof first.

Instead of $g^{(w + tx)(y + uz)} = g^{(wy + txy + uzw + tuxz)}$, a different value gives a cleaner way to present the proof:

$U = H(A^y, v^{ty}, A^{uz}) = H(B^w, B^{tx}, h^{uw})$
$V = H(A^y, A^{uz}, v^{ty}) = H(B^w, h^{uw}, B^{tx})$
$S = A^y A^{uz} v^{ty} = B^w B^{tx} h^{uw} = g^{wy + txy + uzw}$

Compare $U$ on one side to $V$ on the other; if they match on both sides, then calculate $S$ and use that to create a key that will be the same on both sides. I believe that the order that the proof is sent is not important.

More concretely, both sides would look like:

For $x$ = private key, $w$ = random session private key, $h$ = other side's verifier

$A = g^w, v = g^x, AP = A + kv$
Other side calculates $B = g^y, h = g^z, BP = B + kh$

Send $AP$ to other side; receive $BP$ from other side

$t = H(AP, BP)$
$u = H(BP, AP)$
$B = BP - kh$
$U = H(B^w, B^{tx}, h^{uw})$
Other side calculates $A = AP - kv, V = H(A^y, A^{uz}, v^{ty})$

Send $U$; receive $V$

Verify $V = H(B^w, h^{uw}, B^{tx})$
Other side verifies $U = H(A^y, v^{ty}, A^{uz})$

If both sides verify then

$K = H(B^w B^{tx} h^{uw})$
Other side calculates $K = H(A^y A^{uz} v^{ty})$

The only disadvantage I see is that this requires one additional modular exponentiation on each side compared to the fully expanded SRP-Z form.

Even though the use I'm thinking of would be using random private keys rather than password-derived keys, which eliminates the need to guard against a dictionary attack against the verifiers, which allows the verifiers on both sides to be public, I've left in those elements of the SRP protocol that help prevent leaking of the verifier.

Does this look practical? Does removing the value $g^{tuxz}$ reduce security over the SRP-Z formula?

Apologies if I've made any mistakes in transcribing the work I've done on this, different variants of the protocol descriptions use different names for the variables (e.g. $a$ and $b$ instead of $w$ and $y$), and I could well have messed up a few.

Answer 1

Taking a stab at answering my own question.

First, this is very similar to STS (Station to Station) protocol and the KEA+ (Key Exchange Algorithm), which I had not seen before.

I've refined the algorithm above and changed a few variable names for clarity (w, y become a, b; v, h become X, Z).

Changes from the earlier version include removing the $kh$ and $kv$ values when sending $A$ and $B$. $v$ and $h$ (now $X$ and $Z$) are assumed to be public so adding them is no longer useful.

Also removed is the $g^{ab}$ factor from the proof and final key calculations. Both $a$ and $b$ exponents are represented in the final values, so combining them again doesn't increase security. This is similar to dropping the $g^{u^2xz}$ factor from the SRP-Z formula previously given.

One advantage to keeping $g^{ab}$ is that you could then set either or both $x$ and $z$ to 0 and it downgrades to either simple SRP (one way authentication, mutual authentication if verifier is kept secret) or DH if both are zero. Advantage of taking it out is simply one of speed.

The primary difference from KEA+ is that KEA is using a hashing function to get the key from the $g^{az}$ and $g^{bx}$ values while here they're multiplied. In fact, the proof values above ($U$ and $V$) are almost the same as the key values in KEA+.

Multiplying $S1$ and $S2$ allows the protocol to be the same on both sides. While simply using $g^{az + bx}$ opens up some attacks (similar to ones described in the SRP and KEA+ papers), adding in the multipliers $u$ and $t$, which are equally dependent on the ephemeral keys on both sides will prevent those attacks.

With the modified algorithm, this only requires two modular exponentiations and one modular multiply, which compares quite favorably with a DH key exchange plus two RSA key signature encryptions/decryptions (or equivalent public key authentication).

By keeping the exponents relatively small (keeping a, b, x, z, t, u all 256 bits) this runs in about 3.6 msec total per side on a 3GHz i7 using OpenSSL (1.1.0) with a 2048-bit modulus. By comparison, using the built-in DH with a 256-bit private key runs in about 1.7 msec, a private-key encrypt also takes about 1.7 msec (public-key decrypt takes about .08 msec with an exponent of 65537).

Modified algorithm: For safe prime $N$, generator $g$, private keys $x$ and $z$.
All exponentiation done mod $N$.
Both sides execute the same algorithm (with values swapped), i.e.
$(x, z, X, Z, A, B, t, u, U, V, S1, S2, K)_2 = (z, x, Z, X, B, A, u, t, V, U, S2, S1, K)_1$

$X = g^x$
$Z = g^z$

$N$, $g$, $X$, $Z$ are known to both sides.

Create random a where $0 < a < (N - 1)$
$A = g^a$

Send $A$, receive $B$ (in either order)

$t = H(A | B)$
$u = H(B | A)$
$S1 = B^{tx}$
$S2 = Z^{ua}$
$U = H(S1, S2)$

Send $U$, receive $V$ (in either order)
Verify $V = H(S2, S1)$

If valid
$S = S1 \times S2 \mod N$
$K = H(S)$