Re: [Cfrg] Status of DragonFly

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

From: [e-mail] [mailto:[e-mail]] On Behalf Of Igoe, Kevin M.
Sent: Thursday, December 13, 2012 1:43 PM
To: [e-mail]
Cc: Dan Harkins
Subject: [Cfrg] Status of DragonFly

I'd like the reading list's input on DragonFly (hereafter called DF), Dan Harkins' Password Authenticated
Key Exchange design (draft-irtf-cfrg-dragonfly-00).  I'd like to point out that draft-harkins-tls-pwd-03
is a proposal to use DF in  TLS that differs slightly from the CFRG draft.

Here is where I believe we stand:

1.       Confidentiality: The proof that the confidentiality of the key generated by the DF
protocol is reducible to the standard Diffie-Hellmann problem is quite straight
forward, so the resulting shared secret value is at least as secure as with  standard DH/ECDH.
2.       Authentication: Obviously the system can be no more secure than the password
being used. I believe the most viable attack is to guess a password, use this password
to initiate the  DF protocol with the endpoint being attacked, and see if it works.
Monitoring the system logs should easily detect such an attack.
3.       Timing: I'm particularly concerned about the method used to generate the PE (password
dependent base point) in the ECDH case. Inside a while loop, several parameters,
 including the identities of the two endpoints, the shared password, and a counter are
passed to a KDF to produce an n-bit output, where the curve is mod an n-bit prime p.
The resulting n-bit value X is checked to see if 0 <= X < p and X^3+a*X+b is a quadratic
residue mod p (an event of probability ½).  If both these tests are passed, the while
loop is exited and X is used as the x-coordinate of our PE.

The problem I see with (3) is that the number of times through the loop gives an opponent a
check  on any putative value for the password.  E.g.  if their current guess for the password
takes many passes through the while loop to generate the PE, but they observe that the DF response
 time is inconsistent with that, they have eliminated that guess for the password.

When DF is applied to TLS in as described in draft-harkins-tls-pwd-03, two nonces are used as
inputs to the KDF, which has two consequences:
a.       the PE MUST be computed online
b.      each DF exchange gives an independent timing check on the password.
The opponent can passively sit back, monitoring the timing of DF exchanges on various links until
they stumble across one where the timings match up with the timings associated with one of the
passwords they are testing. They've now are able to bypass the authentication provided by DF.

A possible fix is to use the KDF to generate a random X, 1<X<q, where q is the size of the cryptographic
subgroup of the curve, and take PE = X*G, where G is the generator of the cryptographic subgroup.  For
most cryptographic curves,  q  is very, very close to 2^n, so it is VERY unlikely that more than 1 call to the
KDF will be needed.

You sure?  I believe this breaks the security property of the protocol.  That is, if the attacker knows the order of potential points PE, he knows their relative order, and so is able to test multiple passwords by examining the results of a single exchange.  With Dan's approach, no one knows the relative order of any PE.

Another fix would be to require PE generation be done offline, which would eliminate any possibility of
using nonces in the DF protocol.  One could, however, mix the nonces in after the completion to the
DF based Diffie-Hellmann exchange.

The other possible fix is to mandate that N (where N is perhaps 40) different x values are generated and tested; only after all N are tested, we pick the middle one that succeeded (middle one so an engineer would not be tempted to skip the tests after one passed :-); if all N failed, then we do some error handling (say, keep on generating x's until we do find one that pass).  This takes mostly constant time, and if N=40, the error handling will be hardly ever run (one in a trillion key exchanges).




----------------+--------------------------------------------------
Kevin M. Igoe   | "We can't solve problems by using the same kind
[e-mail]<mailto:[e-mail]>  | of thinking we used when we created them."
                |              - Albert Einstein -
----------------+--------------------------------------------------