Subject: [Cfrg] Dragonfly has advantages -> was Re: Requesting removal of CFRG co-chair

From: Paul Lambert <[email-masked]>
Date: Sat, 4 Jan 2014 02:52:52 -0800

On 1/3/14, 6:43 PM, "Trevor Perrin" <[email-masked]> wrote:

Trevor,

>
>But there's a bigger picture:  Regardless of timing attacks, Dragonfly
>is inferior to alternatives already standardized

No. The Dragonfly proposal was submitted by Dan as an IPR free
contribution.
This has considerable value and makes it implementable in consumer
products.

It is also closely related to other work adopted in commercial sytems and
should be pursued as an RFC to ensure it¹s continued vetting.

The discussion has resulted in mitigating risks.  To date I have not seen
any indication that the protocol is Œbroken¹.

I agree that it has more complexity and message exchanges that other
approaches.  These other protocols have NOT been viable to ship in the
products I build.

>or found in the
>literature.
Please write an RFC then.

>
>This opinion was well-expressed on the TLS and CFRG mailing lists when
>Dragonfly was proposed.  This opinion was probably shared by many more
>people than expressed it (like me),

I believe that you have expressed your opinion 12 to 15 times on this
mailing 
list about Dragonfly based on comments and analysis made by other
knowledgeable individuals.

Please let others speak for themselves.

Paul

> and was never adequately
>addressed.  By Dec 2012, I assume most people had tuned-out a
>discussion about an non-useful protocol that was proceeding without
>regard to group opinion.
>
>
>Trevor
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Feng Hao <[email-masked]>
Date: Sat, 4 Jan 2014 15:23:56 +0000

Hi,

As a newcomer to CFRG, I missed the initial discussion about dragonfly.
Seeing the recent threads of emails on the subject helps me understand a
bit more how CFRG works. I would like to say my personal opinions on the
dragonfly protocol - for your reference only.

Declaration: there is a potential conflict of interest for me to comment
as Dragonfly and J-PAKE can be seen as competitors, but I will try to
stick to the technical observation from an independent point of view.

1. Comments of Dragonfly

Dragonfly was first brought to my attention by a colleague when the
Dragonfly-00 draft was presented to IETF. With Dylan Clarke, we found that
the Dragonfly-00 draft was based on an earlier conference paper by Dan
[1]. We understood that the text in the internet draft might change, so we
did the analysis on the peer-reviewed paper in [1]. But the basic protocol
in Dragonfly-00 and [1] are the same. It is observed that no public key
validation is mandated in [1] or Dragonfly-00. The effect of such missing
is not obvious, and it may even appear harmless. But it turns out it can
be fatal - a small subgroup confinement attack can reveal both the
password and the session key (see [2] for details). We communicated the
issue to Dan, who acknowledged it gracefully. The attack has been
addressed in Dragonfly-01 and Dragonfly-02, so it is no longer applicable.

In the above analysis, we only looked at the two-round interactions in the
dragonfly protocol, namely, the commit and confirm exchanges. We didn't
look at the password element derivation as that was not relevant to the
small-subgroup confinement attack. We assumed that derivation was done
securely and efficiently. But looking at the dragonfly-02 and also other
people's comments, I think more efforts would be needed to get that
password element derivation procedure right.

For the case of a prime field (3.2.2): the process is repeated up to k=40
times. In each process, it involves the operation of raising the seed to
the power of (p-1)/q. Note that it's not just one modular exponentiation,
but one "expensive" modular exponentiation. If one uses the 1024-bit p and
160-q setting, the exponent is 1024-160=864 bits. This is equivalent to
roughly 5 times the cost of performing an exponentiation with a 160-bit
exponent.

For the case of the ECC (3.2.1), the cost of "hunting and pecking" is not
as high as in the prime field, since the co-factor is small. In the
algorithmic process, it only checks if the point is on the curve. This is
only sufficient if the co-factor is one, but in the general case, when
co-factor can be other values (say, 2, 4), there should be an additional
check to ensure the point lies in the designated group on the curve. That
can be done with a negligible cost (because co-factor on EC is usually
small). Just a suggestion for Dan.

It seems several people on the list have concerns on the side-channel
attacks on Dragonfly. To be fair to Dragonfly, researchers in the PAKE
field generally don't consider side-channel attacks in the security
analysis of a PAKE protocol. Side-channel attacks are very much
implementation-dependent.

That said, I think the protocol design and its implementation are closely
related. A well-designed protocol should be easy to implement. On the
contrary, if one struggles to implement a protocol correctly, that may
suggest some basic issues rooted in the theoretical design of the
protocol. It is not common in the PAKE literature to see the use of c code
to define part of the protocol as in Dragonfly-02. It can get tricky as
the compiler might sometimes change the behaviour of the code to optimise
the performance in different platforms.

In summary, if the password element derivation in Dragonfly can be done
securely and efficiently, that would be a good contribution in my view.
That would even resolve an issue that SPEKE can't. The way that SPEKE
works is by requiring the use of a safe prime, but then for 1024-bit p,
the exponent will be 1023 bits - one modular exponentiation will be
equivalent to about 6 times of the exponentiation with a 160-bit exponent.

(Some people compare PAKEs by merely counting the number of modular
exponentiations, but they should also look at if the protocol readily
accommodates short exponents. The length of the exponent has a direct
impact on the cost of exponentiation.)

2. Comments on PAKE

I believe PAKE has compelling advantages in some practical scenarios -
especially in the initial bootstrapping of a secure communication when a
PKI doesn't exist. For example, two mobile phone users can simply enter a
short password on the key pad so to establish an end-to-end secure
communication channel that even the network provider cannot eavesdropper.
This is just one example and there are more, e.g., pairing of two devices
for secure sync over an insecure network.

I suggest CFRG to actively investigate further in this area. I believe
there is a genuine demand from the industry for secure PAKE techniques. In
the past, the deployment of PAKE has been greatly hampered by all the
patent issues. But with the available patent-free/loyalty-free PAKE
techniques, the situation may change soon.

3. Suggestion for open competition

It will be very helpful to have an open competition among the contemporary
PAKEs to choose those that are secure, efficient and patent/loyal-free.
That should include both balanced and augmented PAKEs to suit for
different application requirements.

It will be timely and nice if IETF/CFRG can help coordinate such.

Regards,
Feng

[1]  Dan Harkins. Simultaneous authentication of equals: A secure,
password-based key exchange for mesh networks. In Second International
Conference on Sensor Technologies and Applications (SENSORCOMM), pages
839--844, 2008

[2] Dylan Clarke, Feng Hao, "Cryptanalysis of the Dragonfly Key Exchange
Protocol," to be published by IET Information Security, 2014.
http://homepages.cs.ncl.ac.uk/feng.hao/files/Dragonfly_final.pdf

---

From: Feng Hao <[email-masked]>
Date: Sat, 4 Jan 2014 15:28:17 +0000

>approaches.  These other protocols have NOT been viable to ship in the

Have you looked at J-PAKE? It's a balanced PAKE, same as Dragonfly.

http://www.lightbluetouchpaper.org/2008/05/29/j-pake/

In the update of "2013-12-30", you can find a prototype implementation of
J-PAKE using the elliptic curve group setting.

Cheers,
Feng

---

From: David McGrew <[email-masked]>
Date: Sat, 04 Jan 2014 11:42:00 -0500

Hi Feng,

thanks for your suggestion and comments.   A quick response to your 
suggestion:

> It will be timely and nice if IETF/CFRG can help coordinate such.

It would be a good idea for the RG to author an RFC describing the 
requirements of PAKE protocols and surveying the existing protocols.   
The RFC could also record the consensus of the RG, if there is one, and 
describe the diversity of opinion otherwise. This is not quite the same 
as a competition, but it would fit easily into the IRTF process.   I 
would expect that there would be multiple authors, probably including 
multiple PAKE protocol authors.   We should also line up some reviewers 
as well.  What do you think?

As a side note, I personally would also like to see 
guidance/documentation on how PAKEs can best be used, and I agree with 
your comment about bootstrapping authentication.  Replacing a raw 
username/password exchange inside of TLS with a PAKE would be good, and 
using a PAKE for password-based certificate enrollment would be good.   
Replacing certificate based authentication with a PAKE would be not so 
good.

David

---

From: Trevor Perrin <[email-masked]>
Date: Sat, 4 Jan 2014 08:47:39 -0800

> approaches.  These other protocols have NOT been viable to ship in the

Hi Paul,

SPAKE2 has no current patents I'm aware of.  SRP has royalty-free licensing.

Both have been deployed in commercial products.  Why aren't they viable for you?

  http://www.di.ens.fr/~abdalla/papers/AbPo05a-letter.pdf
  http://tools.ietf.org/search/rfc5054

(Of course, there are other promising alternatives - e.g. AugPAKE,
J-PAKE, or an Elligator-based PAKE).

Trevor

---

From: Trevor Perrin <[email-masked]>
Date: Sat, 4 Jan 2014 09:18:44 -0800

Hi Feng,

Minor comments:  I don't agree that Dragonfly could "resolve an issue
that SPEKE can't".

It's true that SPEKE is generally described in terms of safe primes to
avoid the problems Dragonfly is running into.

But any password element derivation that works for Dragonfly would of
course work for SPEKE.

> impact on the cost of exponentiation.)

Another important issue, particularly for EC protocols, is to
distinguish operations with a fixed base (or fixed point) from
operations with a random base / point.

The fixed operations can be optimized to be several times faster
(perhaps ~4x is a rule of thumb I've heard).

Trevor

---

From: Feng Hao <[email-masked]>
Date: Sat, 4 Jan 2014 18:43:20 +0000

Hi David,

>as well.  What do you think?

I think that's an excellent idea. I expect the most difficult part would
be to kick-start the process, so if it can easily fit into the IRTF
process, that will help. In the end, I think some form of competition
between existing PAKEs would be unavoidable, but if we keep the process
open and transparent, the competition should be healthy and beneficial to
everyone. 

>Replacing certificate based authentication with a PAKE would be not so

Password-based AKE and PKI-based AKE (e.g., TLS/SSL) are two different
types of key exchange protocols. The former is not meant to replace the
latter, but the two can complement each other.

For the same reason, a balanced PAKE and an augmented PAKE are two types
of PAKEs. They can co-exist as well, suitable for different applications.

I think providing a suite of different types of "secure and efficient" key
agreement protocols is important, so people will have a choice to decide
which one suits their needs.

---

From: Feng Hao <[email-masked]>
Date: Sat, 4 Jan 2014 19:05:13 +0000

Hi Trevor,

>But any password element derivation that works for Dragonfly would of

Actually, I don't see disagreement here, but maybe I didn't express myself
clearly.

I mean if Dan manages to work out a way to derive the PE "securely and
efficiently" for Dragonfly, the same technique would also work for SPEKE.
Of course, that is a big "IF" at the moment, but I hope Dan will continue
to work on it. 

>(perhaps ~4x is a rule of thumb I've heard).

I guess you mean optimizing by caching the intermediate terms or saving
them in a look-up table? The amount of speed-up is not surprising. It also
applies to the exponential operation in a prime field, where one can
pre-compute all the square terms for a fixed base.

There are all sorts of similar optimizing tricks (generally involving
memory/speed trade-off and off-line pre-computation) that people can play
to make the cost in the protocol look as small as possible. But that often
raises a lot of confusion. For fairness, one should compare protocols
side-by-side under the same levels of optimization.

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 4 Jan 2014 13:28:21 -0800

The IPsecME WG tried something like this, and it ended with bloody stumps all around. This isn't to say that it would fail in the CFRG, but many of the same people are in both groups.

--Paul Hoffman

---

From: David Jacobson <[email-masked]>
Date: Sat, 04 Jan 2014 13:47:22 -0800

On 1/4/14 9:18 AM, Trevor Perrin wrote:
> operations with a random base / point. The fixed operations can be 
> optimized to be several times faster (perhaps ~4x is a rule of thumb 
> I've heard).
This seems strange to me, and I've implemented ECC several times over 
the last decade.   I think you might have meant that implementations 
using special modulii that can be written as  the sum of  +/- 1 at 
selected word boundaries or as 2^n - k for some small k are several 
times faster than implementations written to support arbitrary moduli.

     --David

---

From: Watson Ladd <[email-masked]>
Date: Sat, 4 Jan 2014 17:04:02 -0500

On Sat, Jan 4, 2014 at 4:47 PM, David Jacobson <[email-masked]> wrote:
>> Another important issue, particularly for EC protocols, is to distinguish
>> operations with a fixed base (or fixed point) from operations with a random
>> base / point. The fixed operations can be optimized to be several times
>> faster (perhaps ~4x is a rule of thumb I've heard).
>
> This seems strange to me, and I've implemented ECC several times over the
> last decade.   I think you might have meant that implementations using
> special modulii that can be written as  the sum of  +/- 1 at selected word
> boundaries or as 2^n - k for some small k are several times faster than
> implementations written to support arbitrary moduli.

This isn't that strange: you simply use a larger, precomputed table
for a higher-radix or sliding window method.

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Samuel Neves <[email-masked]>
Date: Sat, 04 Jan 2014 22:05:25 +0000

> times faster than implementations written to support arbitrary moduli.

Fixed base lets you precompute arbitrary multiples of G offline. For
example, if you compute {0..16} G, 2^4 * {0..16} G, 2^(4i) {0..16} G,
..., you only need to perform around log2(exponent)/4 online group
operations. Doing this safely against side-channel attacks requires some
care, of  course.

---

From: "Dan Harkins" <[email-masked]>
Date: Sun, 5 Jan 2014 00:12:23 -0800 (PST)

Hi David,

> Replacing certificate based authentication with a PAKE would be not so

  I agree with everything above.

  PAKEs are useful because they provide a certain amount of security even
in the presence of weak, low-entropy passwords. And passwords are easy
and simple to use for people who are not computer savvy much less crypto
clueful, they are intuitive to use. So PAKEs can provide a kind of misuse
resistance.

  PAKEs are also useful for bootstrapping and for things like certificate
enrollment. In fact, it is securing an RFC 7030 exchange that prompted
me to push so hard for TLS-pwd. The fact is that if someone does not
have a certificate then he probably also lacks a suitable trust anchor
database with which to properly secure a certificate-based TLS exchange
to enroll with a CA (any step that populates the trust anchor database
can be used to just give the user a certificate and be done with it). And
in that case they will do is accept an unverified self-signed certificate
and use HTTP digest authentication right before they say "give me the
CA's certificate that I will trust from now on". I know this because I've
seen people deploy this nonsense.

  In addition, when someone is requesting certification of a public
key it makes sense to authenticate using a PAKE with the same group--
384 bit prime ECC for a certified public key, then 384 bit prime ECC with
the PAKE. The group used in the PAKE can't be fixed to the password.

  So we need ECC support in a balanced PAKE. And we needed it a
few months ago when RFC 7030 got published.

  No one should ever use a PAKE in lieu of a certificate-based
authentication scheme provided that the certificate can be, and is,
properly validated. I certainly was not suggesting dragonfly for that
use.

  regards,

  Dan.

---

From: Paul Lambert <[email-masked]>
Date: Sun, 5 Jan 2014 16:04:36 -0800

> -----Original Message-----
> From: Feng Hao [mailto:[email-masked]]

Hi Feng,

> Have you looked at J-PAKE? It's a balanced PAKE, same as Dragonfly.
No, not in too much detail, yet ... looks of similar complexity.

> http://www.lightbluetouchpaper.org/2008/05/29/j-pake/	
Interesting, thanks for the reference.

I assume this is a related better spec for this forum: http://tools.ietf.org/search/draft-hao-jpake-00

Seems like the identical problem space as Dragonfly, but a later attempt. Less critical review so far ... 

Note - a nearly identical version of Dragonfly	 is baked into mesh networking ... so I still want to see Dragonfly progress to ensure the side-channel implementation details and the like are clarified to fully address the comments. 

Regards,

Paul

> 
> In the update of "2013-12-30", you can find a prototype implementation
> of J-PAKE using the elliptic curve group setting.
> 
> Cheers,
> Feng

---

From: Feng Hao <[email-masked]>
Date: Mon, 6 Jan 2014 13:01:32 +0000

Hi Paul,

>No, not in too much detail, yet ... looks of similar complexity.

Well, if you look into the protocol and the proofs, you may realize that
J-PAKE is designed for "simplicity" rather than "complexity".

It is my belief that keeping things simple (which should include the
protocol specification, security proofs and implementation) should be the
the most important consideration in the design of security protocols. Some
people may not realize it, but the hardest task in designing a security
protocol is actually to "keep it as simple as possible".

>I assume this is a related better spec for this forum:
>http://tools.ietf.org/search/draft-hao-jpake-00

Yes. Also note that the protocol has remained unchanged from its initial
publication in 2008.

>Less critical review so far ...

Not sure if it's a later attempt, but J-PAKE was first published in 2008.
It may not be obvious to some, but the protocol has actually been
extensively analyzed by researchers in the security community and the
industry in the past 5 years. We patiently waited for 5 years to give the
public ample time to scrutinise the protocol and the proofs, and so far no
attacks has been found.

But as always, I welcome most critical reviews from people on this list.
Feel free to post your comments on the lightbluetouchpaper blog, which is
open to everyone to comment.

>
>Note - a nearly identical version of Dragonfly	 is baked into mesh
>networking ... so I still want to see Dragonfly progress to ensure the
>side-channel implementation details and the like are clarified to fully
>address the comments.

Of course. I think a prototype implementation of Dragonfly (in c or Java
etc) would help clarify a lot of things.

---

From: Paul Lambert <[email-masked]>
Date: Mon, 6 Jan 2014 09:27:26 -0800

Hi Feng,

Thank you for the discussion.

>Yes. Also note that the protocol has remained unchanged from its initial

There seems to be an ongoing disconnect between academic analysis, RFC
publications and real-world applications.

Perhaps clarity in the documentation of use cases, analysis, comparisons
and recommendations is something we can work on within this community.

Paul

---

From: Feng Hao <[email-masked]>
Date: Mon, 6 Jan 2014 17:45:44 +0000

Hi Paul,

>and recommendations is something we can work on within this community.

Agreed. What you recommend is also in line with what David suggested
earlier.

I've been liking the openness of the CFRG forum and the diversity of
backgrounds that its participants are from. I feel it is in a unique
position to bridge that disconnect.

Feng

>
>
>
>>
>>>
>>>Seems like the identical problem space as Dragonfly, but a later
>>>attempt.
>>>Less critical review so far ...
>>
>>