Re: [Cfrg] I-D for password-authenticated EAP method

["Scott Fluhrer" <[e-mail]>]

I believe I have found a security problem.  See below for details (and one
way you could modify the method defined by the draft to invalidate this
observation).  Oh, and I wouldn't mind someone reviewing the attack to make
sure I hadn't make a fundamental mistake.

> -----Original Message-----
> From: [e-mail] [mailto:[e-mail]] On 
> Behalf Of Dan Harkins
> Sent: Sunday, February 10, 2008 2:22 AM
> To: [e-mail]
> Subject: [Cfrg] I-D for password-authenticated EAP method
> 
> 
>   Hello,
> 
>   There's a new draft in the Internet-Drafts database called 
> draft-harkins-emu-eap-pwd-00.txt. It describes a new EAP 
> method for authentication using only a password. I believe 
> that it provides resistance to active attack, passive attack, 
> and dictionary attack. It also provides forward secrecy and 
> an authenticated key (not just a shared key between 
> authenticated entities).
> 
>   I would greatly appreciate it if anyone on this list could 
> take a look at the exchange-- esp. sections 2.6.2 and 2.6.3, 
> with the notation from section 2.1-- and whether the analysis 
> in section 6 is correct.

It turns out that there is a problem, in that it doesn't meet the security
goal in section 1.3.3.  That is, an attacker who doesn't know the key is
able to make a single exchange, and then test all the passwords within a
dictionary with just the information he learned from that single exchange
(and without solving any hard problems such as discrete logs).

Here's how it works: the attacker will pose as an EAP-peer.  We'll call the
hash of the real password pws (the actual value depends on the peer-ID and
server-ID in addition to the password; since we're doing everything in the
context of a single exchange, this detail does not matter), and G is the
point used in computing PWE as in section 2.6.2:

   PWE = pws * G

First off, the attacker and the EAP-server exchange EAP-pwd-ID/Request and
EAP-pwd-ID/Response messages.

Then, the EAP-server selects s_rand and ss values, and sends the values
Element_S = -(ss PWE) and Scalar_S = s_rand + ss

Then, the attacker selects arbitrary values between 1 and p for k and
Scalar_P, and transmits Element_P = k * G and Scalar_P in his
EAP-pwd-Commit/Response.  It does not matter how he selects k and Scalar_P.
Note that the severer cannot distinguish this response from the valid
protocol.

Then, the EAP-server will transmit the hash of the following value (there
are other elements hashed with it, but those are values known to the
attacker:

 H = s_rand * (Scalar_P * PWE + Element_P)
   = s_rand * (Scalar_P pws + k) * G

Now, the attacker does not know the value of H; however, if he finds a point
that hashes to that same value, he can verify that.

Now, the attacker has everything he needs to perform his attack.  He goes
through his dictionary, and for each password, he computes the corresponding
pws_test = H(peer-ID | server-ID | password_test).

Then, for that password, he computes the corresponding three points:

  ss' * G = (pws_test ^ -1) * -Element_S
  s_rand' * G = (Scalar_S * G) - (ss' * G)
  H' = (Scalar_P pws_test + k) * (s_rand' * G)

Now, if this guess for the password is correct (that is, if pws ==
pws_test), then ss == ss' and s_rand' == s_rand, and so H = H' (the attacker
won't know the actual values of ss and s_rand, but he doesn't really care
about those).  So, if H' hashes to the same value that was transmitted by
the server, he knows (at least with high probability) that password_test is
the correct one.

If you count it out, this attack takes two point multiplications per
password tested (plus one overall to compute Scalar_S * G), plus a few
faster operations.



Now, having given this attack (and assuming I haven't made any silly
mistakes), we can look at how to modify the protocol to invalidate this
attack.  One crucial observation that this attack uses is how PWE is
generated:

   PWE = pws * G

This allows the attacker to know the discrete log of a potential PWE without
solving any hard problems, and this attack relies on that.  Normally, this
is the way you turn integers into elliptic curve points; however, in this
particular case, that also induces a weakness.

The obvious thing to do is generate PWE in a way that doesn't hand its
discrete log to the attacker.  In the MODP case, that's easy, but it's a
little less trivial in an elliptic curve.  One way to do this is to have pws
seed a deterministic random bit generator.  Then, call the random bit
generator repeatedly generating potential X values until it generates an X
value that works as an x-coordinate in the group equation, with two
potential y coordinates.  Then, get the next bit from the random bit
generator to select between the y coordinates, and then you have your point
PWE.  This will generate a random point on the curve (with all points other
than the point at infinity being equiprobable with reasonable assumptions)
without leaking a discrete log.





> 
>   regards,
> 
>   Dan.
> 
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.ietf.org/mailman/listinfo/cfrg
> 

_______________________________________________
Cfrg mailing list
[e-mail]
http://www.ietf.org/mailman/listinfo/cfrg