I'm looking for feedback on a proposal for adapting Secure Remote Passwords (SRP) to Elliptic Curves.
Update: Steve Thomas provided an attack on this proposal. I've been trying to find a way to protect against it without introducing new flaws but I have not been able to do so. I will post about these efforts soon and link to the new post here.
For readers already familiar with elliptic curves and SRP, the very short version is this: I propose a protocol based on SRP and DiffieHellman using a public point Q and a secret point P=xQ where x is the user's password hash. The exchange of public values A and B is modified slightly. The server will generate a value B' = bQ but will also generate a random number r and multiply both P and Q by r. the value rQ is sent to the client along with the value B = B' + rP. The client must calculate the value rP = xrQ and subtract rP from B to get B'. A wrong value of B' resulting from the client's lack of knowledge of x or the server's lack of knowledge of P (in the case of an impostor) will result in a wrong value of S where S=aB'=bA=baQ. After calculating S, the client sends a verifier M1=H(A,B,S) which the server authenticates and responds to with H(A,M1,S).
I look forward to your comments. The (very rough) version follows below.
Abstract
Secure
Remote Passwords (SRP) is a password authentication protocol based on DiffieHellman
Key Exchange (DHKE). SRP resists both
passive and active attacks and does not store a passwordequivalent on the
authenticating server. There has been interest in adapting SRP to work on
elliptic curves, but elliptic curves provide only an additive group whereas SRP
requires a field (with addition and multiplication of field elements).
Secure Remote Passwords
Secure Remote Passwords (SRP) is a password
authentication and key exchange protocol based on DiffieHellman Key Exchange
(DHKE). All computations in SRP are done
in a finite field
_{n}^{*} where
n is a large prime(Wu, 1998). The
verifier stored on the server is the value g^{x}
where g is a generator of
_{n}^{*} and x is the SHA1 hash of the user's
password (Wu, 1998; Wu, 2000). In
addition to the verifier, the server stores a salt value s which is not secret and is used to compute the salted hash of the
user's password. The salt for each user
should be unique.
The steps in the SRP protocol, illustrated in Table 1, are as follows:
 The client signals his intent to log in and transmits his username, I, to the server. The server looks up the user's verifier v=g^{x} mod n and the salt value s.
 The server responds to the client with the salt value s. The client uses the hash function H to hash the salt, username and password into the digest value x.
 The client generates a secret ephemeral value a, computes A=g^{a} and sends A to the server. The server computes B = 3v + g^{b} = 3g^{x} + g^{b}. Notice that this value of B is different than what we would expect in a DiffieHellman Key Exchange. The addition of the value 3v serves two purposes. First, the addition of v integrates the verifier into the protocol so that the server can prove knowledge of v and the client can prove knowledge of x. Second, the multiplication by three introduces an asymmetry that prevents a novel (but not very serious) attack where an active attacker attempting to impersonate the server can make two guesses at the password (Wu, 2002).
 The server sends the value B to the client and both sides hash the public values A and B to compute u. The value u is used to ensure that the following computations are specific to this choice of public values (and therefore the ephemeral keys a and b) in order to prevent attacks where the client knows the verifier and can construct A to cancel out v in the server’s calculation of S.
 Both sides compute the value S which will be hashed to create the key in step 8.
 The client computes S = (B  3g^{x})^{a+ux} = (3g^{x} + g^{b}  3g^{x})^{a+ux} = (g^{b})^{a+ux} = g^{ba+bux}
 The server computes S = (Av^{u})^{b} = (g^{a}(g^{x})^{u})^{b} = (g^{a+ux})^{b} = g^{ba+bux}
 The client hashes the values A, B and S to create the verifier M_{1} and sends it to the server which verifies M_{1} using its own calculation for S.
 The server calculates M_{2} by hashing the values A and M_{1} along with its own calculated value for S and sends the result to the client. The client verifies M_{2}.
 The client and server both hash their previously calculated values of S (which should be equal) to create the session key K.
Step

Client

Traffic

Server

1

I
= username >

Lookup
the salt s
and
verifier v=g^{x}


2

x=H(s, H( I:P))

<s


3

A=g^{a}

A>

B
= 3v + g^{b}

4

u = H(A,B)

<B

u
= H(A,B)

5

S = (B  3g^{x})^{a+ux}

S
= (Av^{u})^{b}


6

M_{1} = H(A,B,S)

M_{1}>

(verify
M_{1})

7

(verify M_{2})

<M_{2}

M_{2}
= H(A, M_{1}, S)

8

K = H(S)

K=
H(S)

Table 1: The SRP6 Protocol (Wu, 2002).
A Critical Component of SRP
One of the most critical steps in SRP, and the one that
makes it difficult to adapt SRP to elliptic curves is the calculation of B in
step 3. The server adds the user's
verifier and the server's public key (g^{b})
to produce the value B; the client then
subtracts out the verifier exponentiating by a+ux. This critical piece
allows the client to prove knowledge of x
without giving away any knowledge of what he thinks x is. Suppose instead that both sides simply
calculated g^{abx}. An attacker posing as the server would be
able to assemble g^{ab} and
mount a dictionary attack to discover x
since he would be able to check his guesses against the client's value for g^{abx} (using S).
The mechanism used by SRP does not allow this to happen.
The Elliptic Curve Discrete Logarithm Problem
The elliptic curve discrete
logarithm problem (ECDLP) is similar to the ordinary discrete logarithm problem
except that it involves point addition on elliptic curves instead of
exponentiation. It is also considered to
be a hard problem. Given a starting point
P and an ending point T, the ECDLP challenges us to find the value x such that
T = xP = P +...+ P (x times) (Paar and Pelzl, 2010, pg. 247).
Dual_EC_DRBG
Dual_EC_DRBG is a random number generator that uses
elliptic curve operations. (See Figure 1). In 2007, Shumow and Ferguson discovered that
it was possible to backdoor Dual EC by selecting the points P and Q such that P
= dQ for some value d. Since it is
relatively easy to reconstruct R*Q (or a handful of possibilities for R*Q) from
T, an attacker who knows the value d can calculate R*P = d*(R*Q) which allows
him to predict the next state value S.
Figure 1
Dual EC SRP
The SRP protocol cannot be directly adopted for elliptic
curves because elliptic curves provide only an additive group whereas SRP
requires a field (with addition and multiplication of field elements). This paper proposes an adaptation of SRP for
elliptic curves using a mechanism inspired by the Dual EC DRBG
backdoor to establish a shared parameter.
Note: this isn't Dual EC DRBG. I just came about the idea while studying elliptic curve cryptography and Dual EC DRBG. The two points stored by the server in my scheme aren't necessarily any different than in a previous scheme proposed by Wang, but my proposal is simpler.
In this protocol, the server stores two points on an elliptic curve, P and Q where P = xQ and where x is the hash of the user’s password (using a strong password hashing function). The point Q is public. The point P is the verifier which must be kept secret. An attacker can use knowledge of P to impersonate the server or to mount a dictionary attack on x (by guessing values x’ and checking whether P = x’Q.
Note: this isn't Dual EC DRBG. I just came about the idea while studying elliptic curve cryptography and Dual EC DRBG. The two points stored by the server in my scheme aren't necessarily any different than in a previous scheme proposed by Wang, but my proposal is simpler.
In this protocol, the server stores two points on an elliptic curve, P and Q where P = xQ and where x is the hash of the user’s password (using a strong password hashing function). The point Q is public. The point P is the verifier which must be kept secret. An attacker can use knowledge of P to impersonate the server or to mount a dictionary attack on x (by guessing values x’ and checking whether P = x’Q.
Step

Client

Traffic

Server

1

I = username

I >

Lookup
the salt s
and
verifier P = xQ .

2

x=H(s, I, P)

<s


3

A=aQ

A>


4

<B,
T_{q}

Generate
random values r and b. Calculate T_{p}
= rP and T_{q} = rQ
B
= T_{p} + bQ
B’
= bQ


5

T_{p} = xT_{q}
S = a(B – T_{p})
= aB’

S
= bA


6

M_{1} = H(A,B,S)

M_{1}>

(verify
M_{1})

7

(verify M_{2})

<M_{2}

M_{2}
= H(A, M_{1}, S)

8

K = H(S)

K=
H(S)

Table 2: Dual EC SRP
The steps for the proposed
Dual EC SRP protocol are as follows:
 The client signals his intent to log in and transmits his username, I, to the server. The server looks up the user’s verifier P=xQ and the salt value s.
 The server responds with the salt value. The client uses the hash function H to hash the salt, username and password into the digest value x.
 The client generates a secret ephemeral value a, computes A = aQ and sends A to the server.
 The server generates random values r and b and computes B’ = bQ, T_{p} = rP and T_{q} = rQ. The server sends T_{q} and B to the client. T_{p} is never transmitted.
 The client uses his password hash to compute T_{p} = xT_{q} then calculates B’ = B – T_{p}. Finally, S = aB’.
 The client calculates and sends M_{1} = H(A, B, S).
 The server calculates and responds with M_{2 }= H(A, M_{1}, S).
 Both sides compute K = H(S).
Notes
and Analysis
The structure of this protocol is
very close to SRP, but the calculation of B and S is different and the value
u=H(A,B) is missing entirely. The value
u is not used because the verifier P is not used directly in the calculation of
S. Rather, P is used to generate T_{p}
which is calculated indirectly by the client as xT_{q}. An attacker with knowledge of the
verifier cannot determine T_{p}
from T_{q} and cannot trick the server into cancelling it out.
The server does not
directly use either T value in the calculation of S. Instead, the client must be able to determine
T_{p} in order to subtract it from B to learn B’. The server always knows B and B’.
Notice that the server does
not directly use either the verifier or T_{p} in order to calculate the
key. If an attacker poses as the server
without knowing P or x, the attacker will be able to generate the “correct”
key: bA = baQ. The client, however, does
use the value T_{p} in order to determine B’ and will arrive at a
different result. The attacker cannot
use the client’s calculation of S to mount a dictionary attack either since the
client’s calculations require both T_{p} and a. Put differently: the client and server must
agree on the value of T_{p} or the client will end up with the wrong
value for B’.
For a passive eavesdropper,
the security of Dual EC SRP reduces to Elliptic Curve DiffieHellman Problem and
the reduction is simpler than in SRP. The
Elliptic Curve DiffieHellman Problem asks us to determine the value S=baQ from
the values A=aQ and B = bQ. The best known
method for doing so is to compute the discrete logarithm of A or B, but it has
not been proven whether the DiffieHellman and discrete logarithm problems are
actually equivalent.
Here, the only complication
is the addition of the value T_{p} to the server’s transmitted value of
B. The client subtracts out T_{p}
from B and computes aB’. Assume that the passive observer is able to
recover x or T_{p }and can
calculate B’. The eavesdropper then has the values A = aQ
and B’ = bQ.
The transmitted values s
and T_{q }do not carry any information about the values a or b. As with SRP, the verifiers M_{1} and
M_{2} must be computed using a secure cryptographic hash function in
order to prevent preimage attacks which might reveal information about the
computed value S.
Questions
What
have I overlooked?
Can
an active attacker gather enough information to mount a dictionary attack on
the user’s password?
Update: There isn't much in the literature about adopting SRP to elliptic curves, but there have been prior proposals. The only one I have a copy of, by Yongge Wang, was proposed in 2001. I believe that my scheme is simpler, easier to analyze and has a more straightforward reduction to the EC DiffieHellman Problem.
References
Hoffstein, J., Pipher, J., & Silverman,
J. (2008). An Introduction to Mathematical Cryptography. New York, NY: Springer.
Paar, C., Pelzl, J.
(2010). Understanding
Cryptography: A Textbook for Students and
Practitioners. New York, NY: Springer.
Wu, T. (1998). The Secure Remote Password Protocol. In
Proceedings of the1998 Internet
Society Network and Distributed System Security Symposium, San Diego, CA . Retrieved
from http://srp.stanford.edu/doc.html
Wu, T. (2000). The SRP Authentication and Key Exchange
System. In Network Working
Wu, T. (2002). SRP6: Improvements and Refinements to the
Secure Remote Password
No comments:
Post a Comment