Re: [Cfrg] Removing the magic constants from SPAKE2

Michael Hamburg <mike@shiftleft.org> Thu, 09 January 2014 03:39 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 979491AE0A2 for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 19:39:44 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 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, 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 wx2srztgpk2l for <cfrg@ietfa.amsl.com>; Wed, 8 Jan 2014 19:39:43 -0800 (PST)
Received: from aspartame.shiftleft.org (199-116-74-157-v301.PUBLIC.monkeybrains.net [199.116.74.157]) by ietfa.amsl.com (Postfix) with ESMTP id 6C4551ADFDA for <cfrg@irtf.org>; Wed, 8 Jan 2014 19:39:43 -0800 (PST)
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 7ABC13AA04; Wed, 8 Jan 2014 19:38:15 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1389238695; bh=U+xwhfR3t0UbSPdi7Ga9+OP8ywphGN9q5RgAsOCkOZ4=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=PBGiLlPJ1T8jcBqXqglNbujvTSDbmjgKmQPiRr7sclTeYpufLdUIzRu0ZvjD2AjQf wUfzTkvDJJ2GJyd4sZM4/KwfpxHZ6kKiTD3wBsS4gQGOHn5D3wIvu5dBKmR/Lno219 L1YefHEQAHCn0LLOG2hh7QZkVFqmss7asbeRjdD4=
Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <CACsn0ckYYf7AvFNENAeKjBrCuhR_+xNLfUo6s9A-0Lc4xj6S=w@mail.gmail.com>
Date: Wed, 8 Jan 2014 19:39:31 -0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <48724EEE-2EA6-4AC6-9854-32A7A39B6CCA@shiftleft.org>
References: <333749FB-4D07-455E-9646-7A8C571E6226@shiftleft.org> <CACsn0ckYYf7AvFNENAeKjBrCuhR_+xNLfUo6s9A-0Lc4xj6S=w@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
X-Mailer: Apple Mail (2.1827)
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [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: Thu, 09 Jan 2014 03:39:44 -0000

On Jan 8, 2014, at 6:23 PM, Watson Ladd <watsonbladd@gmail.com> wrote:

> On Wed, Jan 8, 2014 at 3:19 PM, Michael Hamburg <mike@shiftleft.org> wrote:
>> Hello CFRG,
>> 
>> <snip>
> 
>> 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.
> 
> But it unfortunately falls apart in the standard model, because I can
> cook the hash. The obvious choice for original SPAKE2 is the M and N
> with smallest x or y coordinates that are on the curve besides the
> generator. I don't think M&N are the issue here.
> 
> Basically, I think derandomization is better than SHA3 being like a
> random oracle in all the ways that matter as an assumption.

I believe we discussed this at BaySec.  SPAKE2 uses the random oracle model anyway, as does every fast-ish PAKE including J-PAKE (depending on the signature scheme used by J-PAKE, but the default is Schnorr IIRC).

But regardless, I don’t agree with your intuition here.  The derandomized case is probably impossible to break in real life, but once an attacker solves the discrete logs of M and N once, she can hack everyone forever.  It’s a class break.

For the Elligator version, for the attacker to try (p1,p2) with only one login attempt, she has to solve a CDH challenge derived from SHA3(p1) and SHA3(p2), ideally salted with the username and the server domain.  And then she still has to test all other passwords sequentially.  And this only works for one user and domain.  For there to be a practical attack, somehow points of the form Elligator(SHA3(password)) have to have easily computable relations a significant fraction of the time.  With non-pathologically-chosen hash functions (eg, SHA2 or SHA3), this seems extremely unlikely.

In other words, while an attacker could get a few free guesses with a cleverly “cooked" hash function, the hash function has to be truly pathologically related to the elliptic curve for it to actually break things.

So while the Elligator construction uses the ROM more pervasively, I think it’s theoretically more sound than the original SPAKE2.

Cheers,
— Mike