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?
$\begingroup$
$\endgroup$
1
asked Feb 28, 2013 at 18:13
-
$\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$– CodesInChaosMar 23, 2013 at 18:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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).
Squeamish Ossifrage
47.9k3 gold badges115 silver badges221 bronze badges
answered Mar 2, 2013 at 19:07
-
$\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$ Mar 4, 2013 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$– ponchoMar 6, 2013 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$– HannoOct 1, 2019 at 12:23
-
$\begingroup$ I have fixed the two article links. The Web is impermanent. $\endgroup$ Oct 1, 2019 at 13:47
-
$\begingroup$ See blog.cryptographyengineering.com/should-you-use-srp for another good explanation. $\endgroup$– mti2935May 21, 2020 at 11:53
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$
pow(g, a, n) * pow(g, u*x, N)becomespoint_mult(a, g) * point_mult(ux * g)- no; that would becomepoint_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$– ponchoMay 21, 2020 at 22:29