Dual EC SRP (request for feedback)

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 Diffie-Hellman 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 Diffie-Hellman Key Exchange (DHKE).  SRP resists both passive and active attacks and does not store a password-equivalent 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 Diffie-Hellman 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 SHA-1 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:

1. 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.
2. 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.
3. 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 Diffie-Hellman 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).
4. 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.
5. Both sides compute the value S which will be hashed to create the key in step 8.
1. The client computes S = (B - 3g^x)^a+ux = (3g^x + g^b - 3g^x)^a+ux = (g^b)^a+ux = g^ba+bux
2. The server computes S = (Av^u)^b = (g^a(g^x)^u)^b = (g^a+ux)^b = g^ba+bux
6. The client hashes the values A, B and S to create the verifier M₁ and sends it to the server which verifies M₁ using its own calculation for S.
7. The server calculates M₂ by hashing the values A and M₁ along with its own calculated value for S and sends the result to the client.  The client verifies M₂.
8. 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=gx
2	x=H(s, H( I:P))	<-----s
3	A=ga	A---->	B = 3v + gb
4	u = H(A,B)	<----B	u = H(A,B)
5	S = (B - 3gx)a+ux		S = (Avu)b
6	M1 = H(A,B,S)	M1---->	(verify M1)
7	(verify M2)	<----M2	M2 = H(A, M1, S)
8	K = H(S)		K= H(S)

Table 1: The SRP-6 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.

  

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, Tq	Generate random values r and b.  Calculate Tp = rP and Tq = rQ B = Tp + bQ B’ = bQ
5	Tp = xTq S = a(B – Tp) = aB’		S = bA
6	M1 = H(A,B,S)	M1---->	(verify M1)
7	(verify M2)	<----M2	M2 = H(A, M1, 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:

1. 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.
2. 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.
3. The client generates a secret ephemeral value a, computes A = aQ and sends A to the server. 
4. 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.
5. The client uses his password hash to compute T_p = xT_q then calculates B’ = B – T_p.  Finally, S = aB’.
6. The client calculates and sends M₁ = H(A, B, S).
7. The server calculates and responds with M₂ = H(A, M₁, S).
8. 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 Diffie-Hellman Problem and the reduction is simpler than in SRP.   The Elliptic Curve Diffie-Hellman 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 Diffie-Hellman 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₁ and M₂ must be computed using a secure cryptographic hash function in order to prevent pre-image 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 Diffie-Hellman 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

Group, Request for Comments: 2945.    Retrieved from http://tools.ietf.org/rfc/rfc2945.txt

Wu, T.  (2002).  SRP-6: Improvements and Refinements to the Secure Remote Password

            Protocol.   Retrieved from http://srp.stanford.edu/srp6.ps

How the Dual EC DRBG Backdoor Works

In December 2013, Reuters reported that the National Security Agency had paid RSA ten million dollars to use a random number generation algorithm that contained a backdoor.  The algorithm, Dual_EC_DRBG, is the default random number generation algorithm in RSA's BSAFE toolkit which is used by other companies to implement cryptography in their products.  These allegations have seriously damaged the reputations of RSA and of the NSA who had established itself as a partner in the security community.

A great number of articles were published about the RSA-NSA deal after Reuters first reported on the matter.  Many of these make misleading or untrue technical assertions and few of them have attempted to provide any explanation as to how this supposed backdoor works.  Some commentators have claimed that this backdoor (if true) made the products that used the BSAFE toolkit more vulnerable to attack.  This is (mostly) not true.  Because the backdoor, whose possibility was first speculated on by Dan Shumow and Niels Ferguson of Microsoft, relies on techniques from public key cryptography, it is only usable by a person that knows the key and that key cannot be discovered by another party, even if that party knows the full details of the algorithm.

This post explains the Dual_EC_DRBG algorithm and how a backdoor could be implemented.  It is meant to be accessible to non-cryptographers. We’ll begin with a really brief review of modular arithmetic and the discrete logarithm problem, discuss basic operations on elliptic curves and introduce the discrete logarithm problem over elliptic curves (ECDLP).  Then, we’ll see how Dual_EC_DRBG can be engineered to contain a backdoor and explain why the backdoor is only usable to someone who knows the key.  If all of this is new to you, I recommend reading an introductory text such as this one.

Note: I originally wrote this as a paper for a graduate class.  In revising this for my blog, I've removed all of the in-text citations and tried to replace them with links.  My original references are listed at the end.  The point of this post is to explain ideas originated by others; the original ideas are not mine.

Understanding Rabin-Miller

I'm posting this to provide some clarification on the Rabin-Miller primality test as requested on Twitter.  My favorite reference on the test is the notes by Diane Hoffoss located here.  If you're not familiar with primality testing and/or Rabin-Miller; read the notes first then come back to this post if you need any clarification.

My purpose here is to restate a few key points from Hoffoss's notes, provide a little more exposition on the examples and to compare her description of the algorithm with the description given in the Handbook of Applied Cryptography.  This is a derivative work and I do not claim to have originated any of the ideas here.  Of course, any mistakes are my own.

This test is discussed in many books including Practical Cryptography, Understanding Cryptography and the Handbook of Applied Cryptography.

Note: For the examples below, I group digits using commas as is the convention in the U.S.  All of the numbers are integers.

I'm not dead. Happy New Year!

I apologize if this blog is starting to look a little abandoned.  It's not (I promise) I just had to go on hiatus for a few months.

I started a new job in September (Director of Technology for a school district) and it has kept me very busy.  Over the new few months, I'm planning a handful of posts on technical topics plus a few about the realities of trying to run an IT department.

Here are the next three posts that I have in mind:

• Understanding Diffie-Hellman and the Discrete Logarithm Problem
• The Elliptic Curve Discrete Logarithm Problem
• Understanding Dual Elliptic Curve Deterministic Random Bit Generator (Dual EC DRBG)

Dual EC DRBG is the random number generator that the NSA supposedly put a backdoor into.  The first two posts that I'm planning are just to provide background information so that readers can understand the third one.  The third post will explain how Dual EC DRBG actually works and why it's susceptible to key escrow/backdoors.

Career prospects: going to grad school

I've recently been involved in several discussions about whether online schools are really helping their students.  In particular, do they prepare people for the job market?  I can't comment on how this works in other fields, although many are probably similar, but here are my thoughts on IT degrees:

The Oversell

I think that many schools oversell the value of their degrees.  A degree is useful and often required, but it's not a guaranteed ticket to your dream job.  Many schools report that X% of their graduates received a raise or promotion after graduating, but these are rarely automatic.  If you're considering going back to school, the burden is on you to figure out what a degree can do for you and how it fits into your career plan.

What is your narrative?

I've run into a few people who either have no work experience or who are in entry level jobs and have completed graduate degrees in IT.  I think education is a good thing and there's nothing inherently wrong with earning a graduate degree, but you have to think about how it fits into your personal narrative.

Attending an online for-profit school

A few years ago, I decided to go back to school to finish a bachelor's degree.  The school I ultimately chose was Capella University, an online for-profit college.  Online universities, and for-profits in particular, have a poor reputation, but I decided to attend anyway.  Here's my take on for-profit universities and why I plan to return to Capella to finish a master's degree.

Availability

I live in a small town.  When I started going back to school, there were no night-time or degree completion programs that I could take advantage of.  I would have loved to go back to school full-time and attend a well-regarded university, but I support a family and can't afford to relocate and quit work in order to go to school.  I needed a degree program that I could complete while working full-time.

Threat scenarios

When analyzing security features, we often look at them in black and white terms: either they can be broken or they can't.  DES is crackable but as far as we know AES is not so we recommend AES.  This is useful when we're making general recommendations because we don't know what threats everyone is going to be concerned about so it's safer to assume that we'll always need to protect against a skilled, well-funded attacker.  In many cases, however, that assumption is not true.

At Passwords 13, Steve Thomas, a.k.a. sc00bzT, gave a presentation about building a cheap hardware security module (HSM) to store and protect passwords.  During the talk, someone mentioned on IRC that what he developed wasn't a true HSM since the hardware was not tamper resistant.  While that is a valid concern, others correctly pointed out that it may not matter depending on your threat scenario.

Since it has no physical protection, Thomas's HSM is vulnerable to hardware tampering.  It should not be used in situations where that is a valid concern.  If you're worried about foreign governments bribing your employees or about a rogue employee (e.g. at a bank) being able to sell those credentials, then you should consider laying out the cash to get a tamper-resistant HSM.  But, if you're mostly worried about outsiders using SQL injection to dump your password hashes, this solution is perfect.  It's cheap and it solves the problem.

Passwords 13 - Next Week

I haven't posted anything lately, but I'm heading to Passwords '13 in Las Vegas next week and hope to come back with some new thoughts and ideas worth posting about.  In the mean time, here's a picture of my dog.

Basics: Avoiding SQL Injection

SQL injection is a pretty big deal.  The attack is easy to carry out, the vulnerabilities are prevalent and the payoff is potentially large.  Many of the password breaches reported over the last year or two are known or thought to have been carried out via SQL injection. 

SQL injection attacks allow attackers to execute arbitrary queries or commands against a database.  Developers introduce the vulnerabilities into their code when they concatenate or substitute user input into the elements of a SQL query.  In the following Python example, the program will accept any input as the "user_id" variable (returned as a part of login_data) and tack it onto the end of a string that is subsequently executed as a sql query:  

login_data = web.input()
query_string = "SELECT * FROM USERS WHERE ID = '%s'" %

login_data.user_id

cursor.execute(query_string)

Lessons from the S.C. breach

In October, the South Carolina Department of Revenue discovered that it had been breached and contacted Mandiant to assist in the investigation and response.  All told, millions of social security numbers and hundreds of thousands of bank/credit card numbers had been stolen.

In November, Mandiant published their findings.  This is exciting.  All we usually get is a news article lacking in technical detail.  This we can actually learn from.

My goal in this blog post is to explore what, in hindsight, the S.C. Department of Revenue could or should have done better. Please read the Mandiant report before you move on.