Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

Michael Hamburg <mike@shiftleft.org> Tue, 15 July 2014 18:13 UTC

Return-Path: <mike@shiftleft.org>
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 237701A0AD9 for <cfrg@ietfa.amsl.com>; Tue, 15 Jul 2014 11:13:37 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.557
X-Spam-Level: *
X-Spam-Status: No, score=1.557 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, SPF_PASS=-0.001] autolearn=no
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 Hh-hRVcmxC2L for <cfrg@ietfa.amsl.com>; Tue, 15 Jul 2014 11:13:35 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C59B51A04E7 for <cfrg@irtf.org>; Tue, 15 Jul 2014 11:13:35 -0700 (PDT)
Received: from [10.184.148.249] (w035.z205158021.lax-ca.dsl.cnc.net [205.158.21.35]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 870763AA12; Tue, 15 Jul 2014 11:12:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1405447929; bh=iSkQUmBQqb/kDhqgjhukqByrwrEZUjcdV3Sn+tkbP8w=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=EK7aOUlwJdfj/5YCWCxtPWa40w5u1QJ0tz+TCFcolU8UWZ2sFyGyZsfYIMK9ZYYjC lBb0yA3yg83kxE2jzZP8PdbrG1y6ko/xutE0G4SFbwvkq9YZ/e7IMsuCEY9XXx1Abm JEpfaDi9n0p5RNAA0OwgTNPGVQwKMwG/EGWx3rXs=
Content-Type: multipart/alternative; boundary="Apple-Mail=_538A2CA8-3DA4-4841-9CBB-06C87C820BCA"
Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CAG5KPzwLSVX6-sx7ZNRXB_s+nc7-Hk_jy4uB8Ai8g3OWutvbDg@mail.gmail.com>
Date: Tue, 15 Jul 2014 11:13:24 -0700
Message-Id: <90B9938A-ADD1-4F83-97A7-4F9AD67E9570@shiftleft.org>
References: <CFE9F2DE.26E5A%kenny.paterson@rhul.ac.uk> <CACsn0cnxswoPzS8VFRXTO=MD+L+ezckKmWwhi26-1bJqNw5YCQ@mail.gmail.com> <BA4311FD-368E-413C-BA59-BBE358495C37@shiftleft.org> <CAG5KPzwLSVX6-sx7ZNRXB_s+nc7-Hk_jy4uB8Ai8g3OWutvbDg@mail.gmail.com>
To: Ben Laurie <ben@links.org>
X-Mailer: Apple Mail (2.1878.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/p5uEmi8Du9hcrq69M9V7YeUTKUo
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves
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: Tue, 15 Jul 2014 18:13:37 -0000

On Jul 15, 2014, at 2:16 AM, Ben Laurie <ben@links.org>; wrote:

> On 15 July 2014 02:47, Michael Hamburg <mike@shiftleft.org>; wrote:
>> “Elligator squared” works for everything.  Elligator 2 works (in DJB’s
>> proposed PAKE)
>> for every prime-field curve of even order.
> 
> What is DJB's proposed PAKE?

It’s an EKE variant.  You keep generating ephemeral keys until you find one which encodes with Elligator (pr ~ 1/2), then encrypt the encoding with the password using a wide-block ideal cipher.  The other party does the same.  Since the encoding looks like a random string, the attacker can’t check a guess for the password.

With Elligator this doesn’t work for every protocol, because Elligator only encodes half the points on the curve, so you have to rejection sample.  For contrast, Tibouchi’s “Elligator squared” [1] — though it’s really a rework of earlier papers, eg [2] on which Tibouchi is also an author — works on every elliptic curve.  It takes twice the space (can be compressed slightly though) and more time to encode, but since you don’t have to rejection sample it can be faster overall.  As a result, even if you like EKE, you can do it on any curve — you just need an ideal block cipher with a sufficiently wide block size.

Cheers,
— Mike

[1] http://eprint.iacr.org/2014/043
[2] https://eprint.iacr.org/2009/340