[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
- Re: [Cfrg] Suggestion for open competition on PAK… Paul Hoffman
- [Cfrg] Dragonfly has advantages -> was Re: Reques… Paul Lambert
- [Cfrg] Suggestion for open competition on PAKE ->… Feng Hao
- Re: [Cfrg] Dragonfly has advantages -> was Re: Re… Feng Hao
- Re: [Cfrg] Suggestion for open competition on PAK… David McGrew
- Re: [Cfrg] Dragonfly has advantages -> was Re: Re… Trevor Perrin
- Re: [Cfrg] Suggestion for open competition on PAK… Trevor Perrin
- Re: [Cfrg] Suggestion for open competition on PAK… Feng Hao
- Re: [Cfrg] Suggestion for open competition on PAK… Feng Hao
- Re: [Cfrg] Suggestion for open competition on PAK… David Jacobson
- Re: [Cfrg] Suggestion for open competition on PAK… Watson Ladd
- Re: [Cfrg] Suggestion for open competition on PAK… Samuel Neves
- Re: [Cfrg] Suggestion for open competition on PAK… Dan Harkins
- Re: [Cfrg] Dragonfly has advantages Paul Lambert
- Re: [Cfrg] Dragonfly has advantages Feng Hao
- Re: [Cfrg] Dragonfly has advantages Paul Lambert
- Re: [Cfrg] Dragonfly has advantages Feng Hao