[Cfrg] Removing the magic constants from SPAKE2

Michael Hamburg <mike@shiftleft.org> Wed, 08 January 2014 23:19 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 []) by ietfa.amsl.com (Postfix) with ESMTP id C2E4C1AD8F3 for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 15:19:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 2.156
X-Spam-Level: **
X-Spam-Status: No, score=2.156 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, J_CHICKENPOX_18=0.6, RDNS_DYNAMIC=0.982, SPF_PASS=-0.001] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id C0_ZZ0djAolT for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 15:19:40 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net []) by ietfa.amsl.com (Postfix) with ESMTP id 960CA1A1F5F for <cfrg@irtf.org>; Wed, 8 Jan 2014 15:19:40 -0800 (PST)
Received: from [] (w035.z205158021.lax-ca.dsl.cnc.net []) by aspartame.shiftleft.org (Postfix) with ESMTPSA id C8BAF3AA04 for <cfrg@irtf.org>; Wed, 8 Jan 2014 15:18:13 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1389223093; bh=c7u8KZP0pzjPhkDokNlnSvqSwzxOvNHFA/N2fib9cJM=; h=From:Subject:Date:To:From; b=MM5GAcA8hGUqffwQxzJNoInwiblWHF5CD5r/E8kUHnxtmSGG6uJIhqvYBo7nQ6n/e 4gEV/LxJ2Q/BQFFWTb6s1FSLuRUfLz+7OaxaOR3g+7x7JYtJMRKGgjJfrEYQHjc6pi UUUCdwIKPBkZq4hUJ2WGaGzLetoa4NtxKGAOmUoo=
From: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: quoted-printable
Message-Id: <333749FB-4D07-455E-9646-7A8C571E6226@shiftleft.org>
Date: Wed, 08 Jan 2014 15:19:30 -0800
To: cfrg@irtf.org
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
X-Mailer: Apple Mail (2.1827)
Subject: [Cfrg] Removing the magic constants from SPAKE2
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: Wed, 08 Jan 2014 23:19:42 -0000

Hello CFRG,

There’s been a lot of discussion of PAKE here, and one of the contenders is SPAKE2.  The goal of this post is to suggest that a SPAKE2 variant might be a suitable standardized PAKE now that SPAKE2 itself is out of patent.  I believe that it can be as fast as Dragonfly, but with smaller messages, a security proof, and fewer flames from Trevor Perrin.  As a reminder, at a high level SPAKE2 uses 3 independent generators g,M,N on the curve, and does:

c->s: X = g^x M^h(password)
s->c: Y = g^y N^h(password), serverValidator(K)
c->s: clientValidator(K).

Here the session key K is h(password,X,Y,g^xy).  If there’s extra information that both sides understand from the connection (eg, user name, server domain, etc), it should be thrown into the hash as well, or salted into the password, to prevent rebinding.  This PAKE also supports a Dragonfly-style flow, where the client and server exchange X,Y, and then exchange their validators in a second round.

However, the protocol is considered problematic (and is out of favor with CFRG) in large part because of the magic curve points M,N.  The discrete logs of these points would be a backdoor in SPAKE2, so care must be taken to ensure that M,N are generated at random.

However, there’s another way to do SPAKE2, which doesn’t need magic curve points.  Instead, M^hash(password) and N^hash(password) can be replaced with Elligator(hash(“M to the”, password)) and Elligator(hash(“N to the", password)).  This obviously achieves the same bounds in the ROM.

Furthermore, if a completely symmetric PAKE is desired, there’s nothing really wrong with setting these two blinding factors to the same value.  That is, they can both be M^hash(password) or Elligator(hash(“M to the”, password)).  The disadvantage is in the proof: the proof will now be based on “CDH squaring” instead of regular CDH, i.e. computing g^(x^2) from (g,g^x).  Because of quarter-squares the two problems are equivalent, but it changes the epsilon^2 in SPAKE to an epsilon^4.  This isn’t a huge deal, and if you prefer stronger proof frameworks like Kudla-Patterson’s GapDH trick, then it doesn’t change the bounds at all.

One more important note!  Because Elligator only works on curves with a cofactor, care must be taken not to leak bits from the cofactor.  That is, either g needs to generate the whole group and not just the q-torsion, or else the parties should send (g^x Elligator(…))^4.  This could also be avoided by using a prime-order curve and SWU/BCIMRT instead of Elligator.

Does anyone on CFRG find this approach interesting?  If there’s enough interest, I’m willing to spec it, though I’d like to understand CFRG’s preference on the various options here:
* Which curve(s)?  Ed25519?  Safecurves?  Is NIST curve compatibility a requirement?
* How much metadata should be present (ASN.1 or fixed curves?)
* Is the completely symmetric PAKE desirable?
* Is SRP-style augmentation desirable?  Should it be optional?
* Are the flows being integrated into TLS or something?
* Should false start be in the spec?

— Mike Hamburg