[Cfrg] Suggestion for open competition on PAKE -> Was Re: Dragonfly has advantages

Feng Hao <feng.hao@newcastle.ac.uk> Sat, 04 January 2014 15:24 UTC

Return-Path: <feng.hao@newcastle.ac.uk>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DE2131ADFF6 for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 07:24:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.501
X-Spam-Level:
X-Spam-Status: No, score=-1.501 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_DNSWL_MED=-2.3, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id urwNWIFtJSzq for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 07:24:08 -0800 (PST)
Received: from cheviot22.ncl.ac.uk (cheviot22.ncl.ac.uk [128.240.234.22]) by ietfa.amsl.com (Postfix) with ESMTP id C9EAB1ADFDF for <cfrg@irtf.org>; Sat, 4 Jan 2014 07:24:07 -0800 (PST)
Received: from exhubvm02.ncl.ac.uk ([128.240.234.9] helo=EXHUBVM02.campus.ncl.ac.uk) by cheviot22.ncl.ac.uk with esmtp (Exim 4.63) (envelope-from <feng.hao@newcastle.ac.uk>) id 1VzT4w-0007O4-Ew; Sat, 04 Jan 2014 15:23:58 +0000
Received: from EXMBDB02.campus.ncl.ac.uk ([fe80::c039:e17:9d60:9f3]) by EXHUBVM02.campus.ncl.ac.uk ([2002:80f0:ea09::80f0:ea09]) with mapi id 14.03.0158.001; Sat, 4 Jan 2014 15:23:57 +0000
From: Feng Hao <feng.hao@newcastle.ac.uk>
To: Paul Lambert <paul@marvell.com>, Trevor Perrin <trevp@trevp.net>, David McGrew <mcgrew@cisco.com>
Thread-Topic: Suggestion for open competition on PAKE -> Was Re: [Cfrg] Dragonfly has advantages
Thread-Index: AQHPCWD7uc8g4tkQ/kavqKMss/3tVg==
Date: Sat, 04 Jan 2014 15:23:56 +0000
Message-ID: <CEEDD67B.22CC7%feng.hao@newcastle.ac.uk>
In-Reply-To: <CEED247E.2B845%paul@marvell.com>
Accept-Language: en-US, en-GB
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.10.0.110310
x-originating-ip: [10.4.160.6]
Content-Type: text/plain; charset="utf-8"
Content-ID: <E62D2D1DBF8DE74A9528B2379FB23DE5@fangorn.ncl.ac.uk>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: [Cfrg] Suggestion for open competition on PAKE -> Was Re: Dragonfly has advantages
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 04 Jan 2014 15:24:12 -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




On 04/01/2014 10:52, "Paul Lambert" <paul@marvell.com> wrote:

>
>
>On 1/3/14, 6:43 PM, "Trevor Perrin" <trevp@trevp.net> 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
>>Cfrg@irtf.org
>>http://www.irtf.org/mailman/listinfo/cfrg
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org
>http://www.irtf.org/mailman/listinfo/cfrg