Subject: [Cfrg] Status of DragonFly

From: "Igoe, Kevin M." <[email-masked]>
Date: Thu, 13 Dec 2012 18:42:54 +0000

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.

      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.

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

---

From: Rene Struik <[email-masked]>
Date: Thu, 13 Dec 2012 14:11:47 -0500

Hi Kevin:

I do share some of your timing attack concerns. Unless I missed 
something here, your suggested fix does not seem to work, however:

Suppose A and B use ECDH with as generator the point G(p):= pG, where 
p:=kdf(..) {I use small-case p ("password") rather than capital-case X 
below (so as to separate scalars and elliptic curve points)}. Now, 
suppose A and B exchange X:=xG(p) where p is the correct password and 
where Y:= y G(p'), where p' is any guess for p by B (or just takes 
p":=1). Then A (the legitimate party holding password p) computes Ka:= 
(xy) G(p')= (xy p') G and B computes Kb:=(yx) G(p)= (yxp) G. In other 
words, Ka:= p' K, Kb:= p K, where K:= (xy)G. So, Ka:= (p'/p) Kb. Now, 
once A sends B a key confirmation message, B can just cycle through the 
password space, compute a candidate key that A could have computed and 
check the validity of his guess via verification of the key confirmation 
message just received.

As to implementing Dragonfly, one has to be careful in case of active 
attacks: as an example, if one uses multiple-point multiplications, one 
may end up at the point of infinity as intermediate point in the 
computation, thus forcing implementations to use exception handling 
routines for point addition/doubling along the entire computational path 
(Note: if one hits the point at infinity, this exposes the password 
used, thus leaking the entire password in an observable way). If one 
does not use multiple-point multiplications, this attack seems much 
harder but requires two full scalar multiplications (rather than one 
scalar multiplication as, e.g., SPEKE requires).

Best regards, Rene

==
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.

On 12/13/2012 1:42 PM, Igoe, Kevin M. wrote:
> is a proposal to useDF in  TLS that differs slightly from the CFRG draft.
>  1. Confidentiality: The proof that the confidentiality of the key
>     generated by the DF
>  2. Authentication: Obviously the system can be no more secure than
>     the password
>  3. Timing: I'm particularly concerned about the method used to
>     generate the PE (password
>  1. the PE MUST be computed online
>  2. each DF exchange gives an independent timing check on the password.
>
> 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.
> [email-masked] <mailto:[email-masked]>  | of thinking we used when 
> we created them."
>                 |              - Albert Einstein -
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 13 Dec 2012 19:14:12 +0000

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

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.

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.

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).

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Thu, 13 Dec 2012 20:19:27 +0000

Thanks Rene.  I agree with your analysis on my first proposed fix.  Clearly this needs some more thought.
Pre-computing PE offline may well turn out to be the best option.

From: Rene Struik [mailto:[email-masked]]
Sent: Thursday, December 13, 2012 2:12 PM
To: Igoe, Kevin M.
Cc: [email-masked]; Dan Harkins
Subject: Re: [Cfrg] Status of DragonFly

Hi Kevin:

I do share some of your timing attack concerns. Unless I missed something here, your suggested fix does not seem to work, however:

Suppose A and B use ECDH with as generator the point G(p):= pG, where p:=kdf(..) {I use small-case p ("password") rather than capital-case X below (so as to separate scalars and elliptic curve points)}. Now, suppose A and B exchange X:=xG(p) where p is the correct password and where Y:= y G(p'), where p' is any guess for p by B (or just takes p":=1). Then A (the legitimate party holding password p) computes Ka:= (xy) G(p')= (xy p') G and B computes Kb:=(yx) G(p)= (yxp) G. In other words, Ka:= p' K, Kb:= p K, where K:= (xy)G. So, Ka:= (p'/p) Kb. Now, once A sends B a key confirmation message, B can just cycle through the password space, compute a candidate key that A could have computed and check the validity of his guess via verification of the key confirmation message just received.

As to implementing Dragonfly, one has to be careful in case of active attacks: as an example, if one uses multiple-point multiplications, one may end up at the point of infinity as intermediate point in the computation, thus forcing implementations to use exception handling routines for point addition/doubling along the entire computational path (Note: if one hits the point at infinity, this exposes the password used, thus leaking the entire password in an observable way). If one does not use multiple-point multiplications, this attack seems much harder but requires two full scalar multiplications (rather than one scalar multiplication as, e.g., SPEKE requires).

Best regards, Rene

==

Cfrg mailing list

[email-masked]<mailto:[email-masked]>

--

email: [email-masked]<mailto:[email-masked]> | Skype: rstruik

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 17 Dec 2012 21:10:02 +0000

OK folks, we are still on the hook to provide the TLS WG with our analysis of DragonFly
as it currently exists.  Here's what I see:

1)      The confidentiality provided by DragonFly is at least as good as Diffie-Hallmann.

2)      Impersonation is a different matter. The nefarious Eve can run through a list
of likely passwords, attempting to run the DragonFly protocol once for each
guess until she hits one where the DragonFly protocol runs to completion,
meaning Eve has almost certainly found the correct password.  Proper
monitoring of the error logs should detect such an attack.

In the EC case, the situation is a bit muddier.  The use of the nonces in the
generation of PE leads to a timing attack.   Assuming the observer can determine
precisely how many passes have been made through the  while-loop, each observed
instance of the DragonFly protocol between Alice and Bob provides 2 bits of information
about their common password.  If the adversary has a list of 2^M passwords which is
likely to contain the password in use, passively observing about M+8 or so DragonFly
exchanges betwixt Alice and Bob provides enough information to uniquely identify the
password (if it is on the list) with high probability.  This is not without cost to the
attacker, they need to test the putative passwords one at a time until they find one
that generates the observed pattern of number of passes through the while loop. It
all comes down to how well the passwords are chosen, and we all know how
good users are at picking passwords.

Scott Fluhrer proposed an elegant change to DragonFly that fixes this.  In the EC case, replace
 the while-loop with a for-loop, say "for t = 1,,,,40".  On each pass through this for-loop generate
a possible x- coorodinate as in DragonFly,  saving off the first x value which corresponds to a
point on the curve.  The only thing that can go wrong here is doing all 40-iterations without
finding a good x-coordinate.  This is quite unlikely to occur (~ 10^-12), but when it does occur
it gives 40 bits of information about the password.  In some VERY high volume applications it
might be prudent to choose a value larger than 40.

Many thanks to Rene Struik and Scott Fluhrer for their insightful comments.  Would anyone else on the list
like to join in?  We can't learn from our mistakes until we realize we've made them.

From: [email-masked] [mailto:[email-masked]] On Behalf Of Igoe, Kevin M.
Sent: Thursday, December 13, 2012 3:19 PM
To: 'Rene Struik'
Cc: Dan Harkins; [email-masked]
Subject: Re: [Cfrg] Status of DragonFly

Hi Kevin:

Best regards, Rene

==

Cfrg mailing list

--

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 17 Dec 2012 14:54:00 -0800 (PST)

Hi Kevin,

On Mon, December 17, 2012 1:10 pm, Igoe, Kevin M. wrote:
> OK folks, we are still on the hook to provide the TLS WG with our analysis
> of DragonFly as it currently exists.  Here's what I see:
>

  This technique is already used in draft-harkins-tls-pwd-03. There is an
additional security parameter, k, that is used to ensure that k iterations
of the loop are performed. There are no interoperability issues with any
particular value of k and I do not recommend a value. But I do make
this statement in the Security Considerations:

      "The probability that a password will require more than k
       iterations is roughly (q/2p)^k so it is possible to mitigate a side
       channel attack at the expense of a constant cost per connection
       attempt."

where q is the order of the group formed by the generator and p is the
prime. Is that statement correct and is it adequate?

  regards,

  Dan.

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Tue, 18 Dec 2012 14:20:38 +0000

A friend of mine once claimed the central skill in cryptology
is setting the parameters properly.  I believe a 40-long for-loop 
is good enough, but 32-long for-loop is a wee bit too small.  Let
me run through the "back of the envelope" calculation that led
me to choose a 40-long for-loop.  

Consider trying to attack bank logins that use DF.  Eve would start
by setting up a network of "listening posts" to monitor DF bank logins,
looking for for-loop overflows.  Once the network "listening posts" is 
in place, Eve would just sit back and wait until one of the listening posts 
reported back with an overflow event and the associated metadata.  Eve 
would then stand a good chance of recovering this user's password and 
raiding their account. 

Our goal is to set the loop size so that Eve rarely, if ever, observes an 
overflow. 

Cisco forecasts there will be about 2^70 bytes/year of internet traffic in
2016. Let's make some conservative assumptions:

	- Assume Eve is able to monitor 1/1000 = 2^-10 of the traffic 
        => Eve's network of listening posts see 2^60 bytes/year.
	- Assume that 2^-10 of this consists of DF exchanges => 2^50 bytes/year 
        of DF exchange data. 
	- Finally assume each DF exchange takes about 2^10 bytes.  This mean 
        Eve's listening post will see about 2^40 DF exchanges per year. 
 
Hence if a 40 long for-loop is used,  Eve expects to get 1 overflow per year. 
Tough to make a profit at that rate!

> -----Original Message-----
> From: Dan Harkins [mailto:[email-masked]]
> Sent: Monday, December 17, 2012 5:54 PM
> To: Igoe, Kevin M.
> > 1)      The confidentiality provided by DragonFly is at least as good
> as
> > Diffie-Hallmann.
> >
> > 2)      Impersonation is a different matter. The nefarious Eve can
> run
> > through a list
> > of likely passwords, attempting to run the DragonFly protocol once
> for
> > each
> > In the EC case, the situation is a bit muddier.  The use of the
> nonces in
> > the
> > generation of PE leads to a timing attack.   Assuming the observer
> can
> > determine
> > precisely how many passes have been made through the  while-loop,
> each
> > observed
> > instance of the DragonFly protocol between Alice and Bob provides 2
> bits
> > of information
> > about their common password.  If the adversary has a list of 2^M
> passwords
> > which is
> > likely to contain the password in use, passively observing about M+8
> or so
> > DragonFly
> > exchanges betwixt Alice and Bob provides enough information to
> uniquely
> > identify the
> > attacker, they need to test the putative passwords one at a time
> until
> > they find one
> > that generates the observed pattern of number of passes through the
> while
> > loop. It
> > Scott Fluhrer proposed an elegant change to DragonFly that fixes
> this.  In
> > the EC case, replace
> > a possible x- coorodinate as in DragonFly,  saving off the first x
> value
> > which corresponds to a
> > point on the curve.  The only thing that can go wrong here is doing
> all
> > 40-iterations without
> > finding a good x-coordinate.  This is quite unlikely to occur (~ 10^-
> 12),
> > but when it does occur
> > it gives 40 bits of information about the password.  In some VERY
> high
> > volume applications it

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Tue, 18 Dec 2012 15:49:25 +0000

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Dan Harkins
> > OK folks, we are still on the hook to provide the TLS WG with our
> > analysis of DragonFly as it currently exists.  Here's what I see:
> >
> > of likely passwords, attempting to run the DragonFly protocol once for
> > each guess until she hits one where the DragonFly protocol runs to
> > completion, meaning Eve has almost certainly found the correct
> > password.  Proper monitoring of the error logs should detect such an
> > attack.
> >
> > precisely how many passes have been made through the  while-loop, each
> > observed instance of the DragonFly protocol between Alice and Bob
> > provides 2 bits of information about their common password.  If the
> > adversary has a list of 2^M passwords which is likely to contain the
> > password in use, passively observing about M+8 or so DragonFly
> > uniquely identify the password (if it is on the list) with high
> > probability.  This is not without cost to the attacker, they need to
> > test the putative passwords one at a time until they find one that
> > generates the observed pattern of number of passes through the while
> > loop. It all comes down to how well the passwords are chosen, and we
> > all know how good users are at picking passwords.
> >
> > Scott Fluhrer proposed an elegant change to DragonFly that fixes this.
> > In the EC case, replace  the while-loop with a for-loop, say "for t =
> > 1,,,,40".  On each pass through this for-loop generate a possible x-
> > coorodinate as in DragonFly,  saving off the first x value which
> > corresponds to a point on the curve.  The only thing that can go wrong
> > here is doing all 40-iterations without finding a good x-coordinate.
> > This is quite unlikely to occur (~ 10^-12), but when it does occur it
> > gives 40 bits of information about the password.  In some VERY high
> > volume applications it might be prudent to choose a value larger than
> > 40.
> 
>   This technique is already used in draft-harkins-tls-pwd-03.

Hmmm, I see it in the ECC section, but not the MODP section.  It would seem appropriate for MODP groups as well, at least in the case where q = (p-1)/2 (e.g. the standard IKE groups).  I believe that either you need to prohibit such groups, or modify the algorithm to handle such groups (possibly making a distinction between those groups, and the 'small subgroup' case; alternatively, just note that k=1 is fine in cases where q<<p).

Also, I suggested 'the middle value' (so that if we scanned through the 40 values, and found that 20 of them were quadratic residues, we'd take number 10).  This was intended to make sure that a well-meaning engineer wouldn't attempt to 'optimize' the search (after all, why keep searching once you've found your result?).  However, it does mean that the value 'k' needs to be agreed to be everybody; everyone can't have their own value; it'd need to be part of the cipher-suite.

I'm not sure whether this idea or your original one (with a stern warning not the 'optimize' the search) is better.

> There is an
> additional security parameter, k, that is used to ensure that k iterations of
> the loop are performed. There are no interoperability issues with any
> particular value of k and I do not recommend a value.

I do believe that you should (at least) offer a solid suggestion; after all, that value will be chosen by people who will read this RFC and nothing else; they may not appreciate all the implications of the below statement.

And, if someone does pick a value that's too low, they're in danger of exposing the secret on behalf of everyone who shares that secret; not just them.

> But I do make this
> statement in the Security Considerations:
> 

Actually, for MODP groups, the probability that k modular-exponentiations is required is about (q/p)^k ; for ECC groups, your listed probability on the number of QR tests is correct, but it can be more easily stated as about (1/2)^k

However, your random 'hunt-and-peck' method for forming the pwd-value also doesn't take constant time, at least for some groups.  For primes p which are just under a power of 2 (standard IKE groups, NIST ECC curves), it's fine; however, other groups (IKE group 24, Brainpool curves), it'll take a variable number of iterations, and hence potentially leaking some information. You might consider the algorithm in B.4.1 from FIPS 186-3 as an alternative; this essentially generates a random number 64 bits larger than what you need, and then modulo-reduce that into the range you want; that gives you an (almost) uniform random number in the range in pretty close to constant time.

Also, if you want to put in a potential optimization in the ECC side, you can note that attempting the compute the square-root is not always the most efficient way to compute whether a number has a square root (aka "is a quadratic residue"); it would be adequate to compute the Legendre symbol (the number is a quadratic residue if the symbol is 1); you would need to take the square root only on the pwd-value we would actually use.  Since computing the Legendre symbol is potentially cheaper than computing the square root (and also does not modify the constant time aspect of the algorithm, at least, no more than computing the square root), you may want to mention that as an acceptable alternative implementation.

If you want a reference on how to compute the Legendre symbol, well, if we're pointing them to FIPS 186-3 anyways, a reference would be the algorithm in C.5 (they call it the Jacobi symbol; it's the same algorithm).