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

Feng Hao <feng.hao@newcastle.ac.uk> Sat, 04 January 2014 19:05 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 15DF41AE089 for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 11:05:45 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.202
X-Spam-Level:
X-Spam-Status: No, score=-4.202 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001, 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 To83nWAd6n4R for <cfrg@ietfa.amsl.com>; Sat, 4 Jan 2014 11:05:43 -0800 (PST)
Received: from cheviot12.ncl.ac.uk (cheviot12.ncl.ac.uk [128.240.234.12]) by ietfa.amsl.com (Postfix) with ESMTP id DBB221AE051 for <cfrg@irtf.org>; Sat, 4 Jan 2014 11:05:42 -0800 (PST)
Received: from exhubvm02.ncl.ac.uk ([128.240.234.9] helo=EXHUBVM02.campus.ncl.ac.uk) by cheviot12.ncl.ac.uk with esmtp (Exim 4.63) (envelope-from <feng.hao@newcastle.ac.uk>) id 1VzWXO-0006y1-BS; Sat, 04 Jan 2014 19:05:34 +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 19:05:14 +0000
From: Feng Hao <feng.hao@newcastle.ac.uk>
To: Trevor Perrin <trevp@trevp.net>
Thread-Topic: Suggestion for open competition on PAKE -> Was Re: [Cfrg] Dragonfly has advantages
Thread-Index: AQHPCWD7uc8g4tkQ/kavqKMss/3tVpp0z0gAgAAdvoA=
Date: Sat, 4 Jan 2014 19:05:13 +0000
Message-ID: <CEEE06CF.22D08%feng.hao@newcastle.ac.uk>
In-Reply-To: <CAGZ8ZG293hO5HqB7khrcNUhw2x981jna+V3ivQNP3X8Btcp8OQ@mail.gmail.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="us-ascii"
Content-ID: <79F8E83AFCAB884AA67929B0579DD53C@fangorn.ncl.ac.uk>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [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 19:05:45 -0000

Hi Trevor,

On 04/01/2014 17:18, "Trevor Perrin" <trevp@trevp.net> wrote:

>On Sat, Jan 4, 2014 at 7:23 AM, Feng Hao <feng.hao@newcastle.ac.uk> wrote:
>>
>> 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.
>
>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.


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. 


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

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.

>
>
>Trevor