6
$\begingroup$

I'm sure it can, because SRP (secure remote protocol) can be implemented everywhere where Diffie-Hellman works, but I need a proof to put this aspect into Wikipedia.


Edit: ok, can it be at least partially moved to elliptic curves?

$\endgroup$
  • $\begingroup$ It's certainly possible to use a protocol that generates a private key from a password hash with ECC. But the proof that the client possesses the key will be different. $\endgroup$ – CodesInChaos Mar 23 '13 at 18:01
16
$\begingroup$

SRP needs more than a group, it requires a field. See the specification: second user sends $B = v + g^b$. This requires two operations, addition and multiplication. You cannot trivially slap that onto a group which provides only one operation, such as elliptic curves.

Variants of SRP which use elliptic curves have been proposed, but do not seem to have reached wide acceptance or even substantial scrutiny yet. See for instance this proposal. Also, this article gives some details (e.g. it claims to break a previous proposal for an EC-based SRP variant).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Argh, just forgot that, but the rest should work fine with ECC. But why can't we just leave the same + operation mod N? $\endgroup$ – Smit Johnth Mar 4 '13 at 1:07
  • 3
    $\begingroup$ @SmitJohnth: because that would void the security guarrantee that SRP makes. Only some bit patterns are possible Elliptic Curve points (even if you use only the x coordinate); if the attacker sees a value $B = v + bG$, he can guess a possible password, generate the corresponding $v'$ value; if $B - v'$ is not a possible Elliptic Curve point, he now knows that the password was not correct. $\endgroup$ – poncho Mar 6 '13 at 15:45
  • $\begingroup$ @Thomas Pornin, do you have an updated link to (or just the name of) the first article you quoted on ECC based analogues of SRP? The current link doesn't appear to work anymore. Thanks! $\endgroup$ – Hanno Becker Oct 1 '19 at 12:23
  • $\begingroup$ I have fixed the two article links. The Web is impermanent. $\endgroup$ – Thomas Pornin Oct 1 '19 at 13:47
  • $\begingroup$ See blog.cryptographyengineering.com/should-you-use-srp for another good explanation. $\endgroup$ – mti2935 May 21 at 11:53
-1
$\begingroup$

The DH operations in the SRP algorithm cannot simply be replaced with 'equivalent' ECDH operations.

In DH, we generate a public key A from a private key a like so:

A=pow(g, a, n)

where pow(g, a, n) is g^a mod N, and g and N are known constants

In ECDH, we generate a public key A from a private key a like so:

A=point_mult(a, g)

where point_mult represents EC point multiplication, a is a scalar, and g is a known generator point on the elliptical curve.

Let's see what happens if we simply try to replace every instance of DH A=pow(g, a, n) in the SRP algorithm with ECDH A=point_mult(a, g).

In the SRP algorithm, the server generates the server session key as follows:

S_s = pow(A * pow(v, u, N), b, N)

where A was previously calculated as A=pow(g, a, n), and v was previously calculated as v=g^x. So the above equation could be written as:

S_s = pow(pow(g, a, n) * pow(g^x, u, N), b, N)

or

S_s = pow(pow(g, a, n) * pow(g, u*x, N), b, N)

Focusing on just pow(g, a, n) * pow(g, u*x, N) from the above equation, if we replace the DH operations in this expression with their 'equivalent' ECDH operations, we would have:

point_mult(a, g) * point_mult(ux * g)

And, therein lies the problem. The above expression is the product of two points on an elliptical curve. But, in elliptical curve math, there is no way to multiply two points. We can add two points, and we can multiply a point by a scalar - but we cannot multiply a point by another point.

| improve this answer | |
$\endgroup$
  • $\begingroup$ pow(g, a, n) * pow(g, u*x, N) becomes point_mult(a, g) * point_mult(ux * g) - no; that would become point_mult(a, g) + point_mult(u*x, g), where '+' is point addition, which is perfectly well defined. The reason SRP doesn't translate immediately to elliptic curves comes earlier, when B needs to compute B = (v + g^b) % N - the + there is 'field addition', which elliptic curves do not have a corresponding operation $\endgroup$ – poncho May 21 at 22:29

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.