Re: [Cfrg] Removing the magic constants from SPAKE2

Bodo Moeller <bmoeller@acm.org> Thu, 09 January 2014 09:11 UTC

Return-Path: <SRS0=d0zJ=WP=acm.org=bmoeller@srs.kundenserver.de>
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 2F3BC1AE08F for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 01:11:57 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.467
X-Spam-Level:
X-Spam-Status: No, score=-1.467 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HELO_EQ_DE=0.35, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.538, SPF_HELO_PASS=-0.001, 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 jvzlC4UQYp32 for <cfrg@ietfa.amsl.com>; Thu, 9 Jan 2014 01:11:55 -0800 (PST)
Received: from moutng.kundenserver.de (moutng.kundenserver.de [212.227.17.10]) by ietfa.amsl.com (Postfix) with ESMTP id 0AE5B1AE08D for <cfrg@irtf.org>; Thu, 9 Jan 2014 01:11:54 -0800 (PST)
Received: from mail-ob0-f170.google.com (mail-ob0-f170.google.com [209.85.214.170]) by mrelayeu.kundenserver.de (node=mrbap3) with ESMTP (Nemesis) id 0LqkxG-1VVzVF2t7K-00eZcT; Thu, 09 Jan 2014 10:11:45 +0100
Received: by mail-ob0-f170.google.com with SMTP id uy5so1002281obc.15 for <cfrg@irtf.org>; Thu, 09 Jan 2014 01:11:41 -0800 (PST)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=cPigH/JvDt0zP/mxioVF/cpn3SUSjrkgu91YYEF+1R4=; b=OewkW57YQn8H84VijQFKhlY5S0DTFC6Bwf0LchQoL1YcGXXuz/D2pJSLITqXSSMGE0 vn0YbadefcKklcHj+lt1PYVbB8/u5TmMhTz/5ueSigN9hW+RXaYOEZswNgr4lXr7ZQLi mTBgNPRoNRFrDcGFBcM7vNFLhW0iswq/a5u/ilrc/2gxD7IvVwb3JHc4lbXkwqZswZCi gPwGlA1K6Lg4KuWx6r40MUC1gLC1jIkse/zmOsAOoYgAesCRVlNxOy9m4FUxcGO60Cec ojWtWArc/PB2GQeXJyp1BwS6059yqRdZp1z1uPNNudbAZ0OGeARDiL6rmGzMn6k9Nfkj F/Rg==
MIME-Version: 1.0
X-Received: by 10.60.16.230 with SMTP id j6mr1425470oed.47.1389258701709; Thu, 09 Jan 2014 01:11:41 -0800 (PST)
Received: by 10.60.142.129 with HTTP; Thu, 9 Jan 2014 01:11:41 -0800 (PST)
In-Reply-To: <333749FB-4D07-455E-9646-7A8C571E6226@shiftleft.org>
References: <333749FB-4D07-455E-9646-7A8C571E6226@shiftleft.org>
Date: Thu, 9 Jan 2014 10:11:41 +0100
Message-ID: <CADMpkc+QvOoxSSRoASBMv9aEH0YskXC1atv0g3-uHj0t9Y2S2w@mail.gmail.com>
From: Bodo Moeller <bmoeller@acm.org>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: multipart/alternative; boundary=e89a8f503bb26aabd404ef85ffaa
X-Provags-ID: V02:K0:m0Ljy7U0UkokgEih5jsxIIYLjcDCYD/H7jOuexKIhQr 8Nvl15RNigPuGpOvUNdNZi7hz7Cgwnfwc0J0/0/BJrPIx9jOLP 1FGwPllz/iGGR6dD6CKws8VkH0x7qB1SHgTXQqOnMB2/thCrn9 Y3NaOGalC5G+RdWzWED1BeXMn1Jp8D5gKX9fmgimTOstTQmJX8 VKPAtnbaG8wIbqT0qhGyEiVyyuitFZpKCHjAsClqePgyo7rUZR HfgUBan3Wy8pg8tXKGK2k+RB859Aep1ZO6afjaIy8EcHwXm+vN vS5RCB9pPjYpp7Y7/iHm0lsClZ0Jcju1B91Z3nZ8Rf1SHIC7M/ sKx2pcOOL9E94yEgjdNs5Vp8x8fWM1yVeN/KIBpbVpy+vHQ9sl 4C6mSd9I66eqk54V6pF/ygzw22xZj1ulVhfKPrYijHetQU273y /3+p1
Cc: 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 09:14:57 -0000

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

I like this idea.

For purposes of standardization, instead of generating those "magic" SPAKE2
base points randomly using unbiased US dollar coins in some other agency's
back room, I'd expect you'd be using "verifiably pseudorandom" points based
on some seed (which shouldn't be an unacceptable leap of faith if you're
already relying on the Random Oracle Model for your security proofs), but
using Elligator to obtain proper mask values more directly seems like a
good alternative.


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

Note that there's also a SPAKE variant called SOKE, which only masks one of
the DH shares in the first place (
http://www.bmoeller.de/pdf/soke-asiaccs2006.pdf; this was *meant* for TLS,
but due to patent concerns at the time was soon replaced by a thoroughly
gimmicky protocol that you don't really want to know about, and hence the
I-D was never completed).



> * Is the completely symmetric PAKE desirable?
> * Is SRP-style augmentation desirable?  Should it be optional?


By "SRP-style" augmentation I think you mean a verifier-based PAKE in
general, right?  ("Verifier-based" = the password information as held by
the server cannot be used to impersonate the client to other server
instances, and is rather merely a verifier to check that the client holds
such information.  I don't like the term "augmented" for this because it
appear to refer to an implementation detail of certain solutions, notably
the original Bellovin-Merrit Augmented EKE.)

I think having a verifier-based protocol is highly desirable, but that this
can be optional if that's sufficiently justified by efficiency advantages.

Bodo