1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "... an identity and password, so no key management is required" - you still need to distribute the shared secret, which could be considerable management if N is large (lots of clients talking to lots of other clients). Its the key distribution problem all over again. $\endgroup$ – jww Apr 27 '15 at 5:31
  • $\begingroup$ The verifier is effectively the salted hash in traditional client/server systems. But rather than using a salted hash, the verifier is an equivalence class in the field based on exponentiation. The verifier exists because of the added pressures of password storage on the server. That is, the verifier makes it hard to recover the password. In the absence of client/server and the password storage problem on the server, it should be acceptable to allow both sides to use the password directly. Apparently, Thomas and Stanford had this insight. $\endgroup$ – jww Apr 27 '15 at 6:02
  • $\begingroup$ If this were my problem (and in the absence of your research into it), I would use the protocol described as 6a in TLS. I would make the "initiator" the "client", and the "recipient" the "server" and have the server calculate and use the verifier. It may cause an extra exponentiation or an extra message on the wire. But that accounts for little in the grand scheme of things in a peer-to-peer app. $\endgroup$ – jww Apr 27 '15 at 6:07
  • $\begingroup$ @jww If you don't have mutual authentication, the verifiers need to be kept secret (otherwise anyone can pretend to be the server). Even with TLS, you'd still need a way to distribute identities and keys. You could have a single server with a list of all verifiers and their identities. The public key of that server could be distributed to each peer. $\endgroup$ – Steve Peltz Apr 27 '15 at 7:08
  • $\begingroup$ Another use case might be that of a device you're going to plug into a control network - you physically connect it to the controller where it identifies itself (by means of the verifier) and learns the verifier of the controller, then remove it and connect it somewhere else over the network. When it connects to the controller, it knows that the controller is the correct one, and the controller knows that the device is legitimate. $\endgroup$ – Steve Peltz Apr 27 '15 at 7:15
1
$\begingroup$

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)$

$\endgroup$
  • $\begingroup$ Steve, this Q/A site isn't really the best place to perform initial analysis of new algorithms as you may have found out. Invariably you end up with open ended answers, or with disagreeing with the opinion formed by the community. This particular answer is 1) not accepted and 2) doesn't really come to a conclusion. Could you try and add both? $\endgroup$ – Maarten Bodewes Aug 2 '15 at 12:04
  • $\begingroup$ agreed original work probably isn't best posted on a Q/A site. most folks complain of the low quality of both Qs and As so when you come across good original work we should be welcoming. a recent example being this post which points out a flaw in a Turning Prize winners seminal work which has been transcribed into serious critical systems stackoverflow.com/questions/29880949/… Any poster making an original contibution should be applauded. So the question really is where can the OP post this approach to get a proper peer review? $\endgroup$ – simbo1905 Sep 3 '15 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.