Re: [Cfrg] PAKE selection process: status after Phase 1 and following steps

steve@tobtu.com Fri, 19 July 2019 20:50 UTC

Return-Path: <steve@tobtu.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D1C7812079C for <cfrg@ietfa.amsl.com>; Fri, 19 Jul 2019 13:50:02 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, SPF_NONE=0.001] autolearn=ham autolearn_force=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 pginONW4DvTh for <cfrg@ietfa.amsl.com>; Fri, 19 Jul 2019 13:50:00 -0700 (PDT)
Received: from mout.perfora.net (mout.perfora.net [74.208.4.194]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 01C4F12008A for <cfrg@irtf.org>; Fri, 19 Jul 2019 13:49:59 -0700 (PDT)
Received: from oxuslxaltgw11.schlund.de ([10.72.76.67]) by mrelay.perfora.net (mreueus004 [74.208.5.2]) with ESMTPSA (Nemesis) id 1Mw8kq-1igfsf1Gtw-00s4iF for <cfrg@irtf.org>; Fri, 19 Jul 2019 22:49:57 +0200
Date: Fri, 19 Jul 2019 15:49:55 -0500 (CDT)
From: steve@tobtu.com
To: CFRG <cfrg@irtf.org>
Message-ID: <5126097.88110.1563569395169@email.ionos.com>
In-Reply-To: <CAMr0u6kxgX+gL7ABxiyDG6KiWdH0qe48R_jL+GHbQNsS0h6yYQ@mail.gmail.com>
References: <CAMr0u6kxgX+gL7ABxiyDG6KiWdH0qe48R_jL+GHbQNsS0h6yYQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Priority: 3
Importance: Medium
X-Mailer: Open-Xchange Mailer v7.8.4-Rev59
X-Originating-Client: open-xchange-appsuite
X-Provags-ID: V03:K1:/nNFDWBEjs2Btc19EiC9iSCnsSomK5e5c/iTqjhVgp9tF9jU3Im KbGL9hztvJjaPcmsutZwiU5O8VJhmHYl0HjaYblD10wpl2ZRCDXG65aa9P7nkj+i++AWsjl InQn7icdWal1NKsmYWNrk1Y/knPChSpoSjp84hDnQC+GgljsVRGUZhJ+cEve4LC/+We5yB0 l3qeUx8vI6O5R4/iBv/og==
X-UI-Out-Filterresults: notjunk:1;V03:K0:PAESyOLlHhk=:2kidmCcnQpCMaEJdqhRu8O 7DP6ZAJQt2t0sC/zkafZnjcFNqQa5dws67tbZpPe2QMFzUaDIj5WhGkWA1l6Q+xdxdaICkmtp rUHGM+0Yrxfxupkz5+hxAk5yxOS9laRIoX9bCx6Z7uLr+bsqeLUuHDwLLX261ufZ/L7kmY6X+ uBLGgMoVS+vQg/en8mJZTgAYzjN+g9EIxkwuOjSmptaMNYnB9TmJ85RfajOBvKlTDxqtGzcMO E4rve+3XffuWdwMgItlF4lC0aiAog5alZJ3Sq/Vn8+y7XITa6xPjnOHLmd3T6QIxDKNGEiFzx jSF7BuBZ+JT5iiVt+/88OJ/eVv+5w6sNKryPUJ6JXJDBKcvtskFeYypgZmqlO59XlxyXAiVzB M+LaTUM2sW3uugOK2KrKEyoxw2r5QX9a4oQZ/1X8MasgxAkrLyZF+Es9yBN3PSl/NmEvx2kT+ Eu6U/2J88SdyPAWqoexHnBE2uurQqY21XYKpCQknOgaSeLnPLkwDCuFUyIDvlopgrdXzfROjF R5SRL7VNDJ2eiU82hrIq2celUPg9JHxRNlcB9ToiW+zZVop81xSClsh3pIrAllB4iGqks1TkC 1VV9rQg7VIr/1DKRuq5HpRDv2Y3+y6aSeHUOTSKy/Gwn+uBGCzEaEfjm+6LZBN/SSAOvn82b6 KqkdPWW+pAmVxDfeut5JdwE1FzIRy8qvY4Ob6H6dQn/VBzYxEqV0pu0dPG8nDHfXfNoXUGfHN XMlucCM5NnZzGUpmw7qMl26BYDYiks849b2V6AUwZxOKGa1SYJvLuOsJStA=
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/DCa5Z1o6h3CTuf0QUd9v7t41wys>
Subject: Re: [Cfrg] PAKE selection process: status after Phase 1 and following steps
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 19 Jul 2019 20:50:03 -0000

** BSPAKE **

   REQ1:  A PAKE scheme MUST clearly state its features regarding
          balanced/augmented versions.

Augmented PAKE


   REQ2:  A PAKE scheme SHOULD come with a security proof and clearly
          state its assumptions and models.

This is based off SPAKE2 which has a security proof in Abdalla, M. and D. Pointcheval, "Simple Password-Based Encrypted Key Exchange Protocols.", Feb 2005.

SPAKE2+ adds one term to the end hash of SPAKE2 (b*v*G). b is the server's ephemeral private key and v is derived from the password. Server stores v*G it is assumed that solving the DLP to get v is hard. It is assumed a proper KDF is used and it is not possible to generate v from the other server data. Client generates v from the password and applies that to b*G. Thus SPAKE2+ is a secure aPAKE.

SPAKE2+EE changes the blinding terms from H(pw, N)*N and H(pw, M)*M to hashToPoint(H(pw, N)) and hashToPoint(H(pw, M)) where hashToPoint is Elligator or Shallue-Woestijne-Ulas (SWU). Most assume hash to point to be a random oracle. The only issue is with uneven distribution from field P to cyclical group size Q. If someone determines this to be a problem which I don't think it is, we can fix it by multiplying the point generated from the hash to point algorithm by another key based off the password: "H(pw, N2)*hashToPoint(H(pw, N))". This only adds two multiplies to the client side and server can do these once (or be given the points during registration) and store the points. Since the client is doing a password KDF this change should not affect runtime by much.

BSPAKE adds blind salt to SPAKE2+EE which should be able to use OPQAUE's security proof of blind salt. There's also security analysis of blind salt in this paper https://eprint.iacr.org/2015/644.pdf. Also note that blind salt only adds precomputation security.


   REQ3:  The authors SHOULD show how to protect their PAKE scheme
          implementation in hostile environments, particularly, how to
          implement their scheme in constant time to prevent timing
          attacks.

Elligator or Shallue-Woestijne-Ulas (SWU) can be done in constant time. The only thing is in the hash to point. There is an if statement while doing the square root, this should use a conditional move to prevent timing attacks. Everything else is standard ECC operations, finite field operations, or hashing. Well besides the password KDF but that's pick one without timing attacks.


   REQ4:  If the PAKE scheme is intended to be used with ECC, the
          authors SHOULD discuss their requirements for a potential
          mapping or define a mapping to be used with the scheme.

Elligator and Shallue-Woestijne-Ulas (SWU) are good choices. Other hash to point algorithms that don't rely on a loop and are constant time should also be fine.


   REQ5:  The authors of a PAKE scheme MAY discuss its design choice
          with regard to performance, i.e., its optimization goals.

Server can store the blinding points "N" and "M" to minimize computations or store a key that is expanded to those and "k3". So either store N, M, k3, and v*G or "k" and v*G. Then with "k" derive keys necessary for N, M, and k3.

Client side the initial blind salt calculation "r*H(pw, serverId, clientId)*G" can be done x=r*H(pw, serverId, clientId) (mod cyclical group size) then do one scalar multiply x*G. Also if using Ed25519 generate r as 1/(8*random()). This way when you unblind by multiplying by 1/r it is a multiple of 8.

For minimizing RTT, the client can start encrypting after 2 messages (client->server, server->client) and the server after 3 messages (client->server, server->client, client->server). Note, which applies to all PAKEs, either party can encrypt a message with a random key and send that key in their "first" encrypted message to decrease latency due to bandwidth.


   REQ6:  The authors of a scheme MAY discuss variations of their scheme
          that allow the use in special application scenarios.  In
          particular, techniques that facilitate long-term (public) key
          agreement are encouraged.

Like all PAKEs you end up hashing a bunch of stuff to get a key. From that key you derive verifiers and session keys. The session keys can be used long-term. I may have misunderstood the question. Also I'm not technically an author unless you call adding blind salt to SPAKE2+EE being an author.


   REQ7:  Authors of a scheme MAY discuss special ideas and solutions on
          privacy protection of its users.

If user is not found, one could use default values for N, M, k3, and v*G (or k and v*G) because there's no way to determine if the same values are used every time. Also the default values should be generated from random as to not make a successful exchange.


   REQ8:  The authors MUST follow the IRTF IPR policy
          <https://irtf.org/ipr>;.

I am unaware of any patents on BSPAKE.


* How does it meet the "SHOULD" requirements of RFC 8125?

See above.


* Does it meet "crypto agility" requirements, not fixing any particular primitives and/or parameters?

Works with any ECC curve that works with Elligator and Shallue-Woestijne-Ulas (SWU). For example it works with all NIST P curve but P-224 because its field is not 3 modulo 4.


* What setting is the PAKE suitable for, which applications does it have? 
 + "Peer communication" (where both ends share the same password) or "client-server" (where the server does not store the password but only a one-way function of the password)? 

Client-server, but technically all client-server PAKEs can be used as peer communication. It's just less efficient.


 + A nomination should specify for which use-cases the protocol is recommended ("PAKE as a more-secure replacement for a PSK on a machine-2-machine interface" or "PAKE for securely accessing a remote HMI interface server (e.g. a web server) without configured WEB-PKI certificates").

"PAKE for securely accessing a remote HMI interface server (e.g. a web server) without configured WEB-PKI certificates."


 + Can two communicating parties initiate the key exchange process at the same time, or must it always be the case that only one party can initiate the process?

Client initiates the process.


 + Is it suitable to be considered as a standalone scheme? 

Yes?


 + Can it be integrated into IKEv2? TLS Handshake? Any other protocols?

Yes. Only requirement is that the protocol let's you add the aPAKE's session key(s) to the protocol's session key(s).


* Is there a publicly available security proof? If yes,

Sort of, see REQ2.


 + Are there known problems with the proof?

Yes, it's not a legit proof.


 + Is the considered security model relevant for all applications that PAKE is intended for (e.g., if a PAKE is to be used in TLS Handshake, it is important that the TLS adversary model is considered for the PAKE)?

No. It's assumed everyone is malicious and have access to a "slow" quantum computer. If the attacker observed a successful PAKE exchange, can solve a DLP in about a minute, and the password is not in the top 10,000 passwords, then it will take over a year to crack the password. Also depending on rate limiting you can probably guess 10,000 passwords in under a year by just acting like a user. Note most other PAKEs get offline classical computer password cracking if you solve just one or two DLPs.


 + Does it allow to be sure in sufficient level of security for common values of password lengths?

Yes? Like all aPAKEs it depends on weather rate limiting is used and if the server's data is taken, then the password KDF. Active attackers can just make online password guesses or stop exchanges. PQ attackers need to observe a successful exchange and solve a DLP per password guess. Most other PAKEs it's solve one or two DLPs and get offline classical computer password cracking. In the case of OPAQUE a PQ attacker doesn't need to observe a successful exchange as all the information is given during a normal wrong password guess.


* Security assessment.
 + Does its security depend on any nontrivial implementation properties? Are they clearly stated in the document?

Hash to point is the only issue. I believe the main issue is with uneven distribution of hash to point. There is a remedy in REQ2 (part 3).


 + Does the PAKE have precomputation security (for augmented PAKEs)?

Yes.


 + If the PAKE relies on the assumption of a trusted setup - more specifically, the discrete logarithm relationship between the two group elements in the system setup MUST be unknown - in anticipation of the worst but not impossible scenario, the authors should clearly state the security implications when the discrete logarithm relationship becomes known, and the subsequent mitigation measures.

No.


* Performance assessment.
 + What's with the “round efficiency” of the PAKE? In a standard two/multi-party secure computation setting, the “round” is defined as a step in which all parties can complete operations at the same time without depending on each other. In practice, a 2-round protocol could be implemented as 2 flows or 3 flows depending on the application context, but that’s more the implementation detail.

Only 4 messages/"flows" are sent to verify both parties (client->server, server->client, client->server, server->client). The client can start encrypting after 2 messages (client->server, server->client) and the server after 3 messages (client->server, server->client, client->server). Server verifies the client after 3 messages and client verifies the server after 4 messages.


 + How many operations of each type (scalar multiplications, inversions in finite fields, hash calculations etc.) are made by each side?

Client: 5 scalar multiplications, 6 finite field inversions, 2 point adds, 2 from data to point, 1 finite field multiply, 2 hash to point, 1 password KDF, 8 hashes (one of which is ~4 blocks)
Server: 4 scalar multiplications, 4 finite field inversions, 2 point adds, 2 from data to point, 0 finite field multiply, 0 hash to point, 0 password KDF, 4 hashes (one of which is ~4 blocks and one is optional)

When the server stores v*G and "k" (vs N, M, k3, and v*G) it adds 2 hash to point, 3 hashes (one is optional) to the server.


* Which recommendations for secure usage can be given?
 + Is it defined how the explicit key confirmation is performed/must be performed externally? Are there clear statements whether this procedure is optional or mandatory?

Either but you save on RTT if it's done during. It is not clear, but to make it clear: it is optional but the client should be the first to verify or send encrypt data (with AEAD so the server can verify). This is to not let a malicious client from gaining data that they can use for an offline PQ attacker.


 + Can any recommendations on using iterated hashing (e.g., with Scrypt) with the PAKE be given?

Argon2 is probably the one to go with. If a good cache hard password KDF comes out, that would probably be ideal. This is because cache hard algorithms are harder for GPUs at shorter runtimes than memory hard algorithms like Argon2 and scrypt. Also memory hard algorithms aren't good for lightweight computers such as wireless routers.

PBKDF2 should be avoided unless required to be use because of NIST or other regulatory requirements. If you do use PBKDF2, be mindful of its footgun. Or use its footgun to make a better password KDF ("Parallel PBKDF2").


 + Can any recommendations to avoid a user enumeration attack be given?

See REQ7.



> On July 5, 2019 at 1:38 AM "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>; wrote:
> 
> 
> Dear CFRG,
> 
> The first phase of the PAKE selection process is over.
> 
> We've obtained the following nominations (by e-mails directly to the chairs
> or to the CFRG mailing list).
> 
>    - SPAKE2 (nominated by Watson Ladd and Benjamin Kaduk), balanced;
>    - OPAQUE (nominated by Hugo Krawczyk), augmented;
>    - J-PAKE (nominated by Feng Hao), balanced;
>    - SPEKE (nominated by Dan Harkins), balanced;
>    - AuCPace (nominated by Björn Haase), augmented;
>    - CPace (nominated by Björn Haase), balanced;
>    - VTBPEKE (nominated by Guilin Wang), augmented;
>    - "SPAKE2+EE with blind salt"/BSPAKE (nominated by Steve (steve@tobtu.com),
>    augmented.
> 
> Please send an e-mail to cfrg-chairs@ietf.org if your nomination was lost
> or, on the contrary, if your personal opinion about good properties of some
> PAKE was misinterpreted as a nomination.
> Also, please let the chairs know if some of the proposed questions to be
> considered is not present in the list further in the current message
> (several groups of questions were merged, since essentially they were about
> the same things - but if some parts have been lost, please let the chairs
> know, so the list will be updated before the end of phase 2 of the
> selection process).
> 
> 
> Dear Watson, Benjamin, Hugo, Feng, Dan, Björn, Guilin and Steve,
> 
> According to the plan of PAKE selection process, now we're on phase 2,
> which will last until the 19th of July.
> To give the reviewers (on the future steps of the process) as much
> information about each PAKE, as possible, the designers of the protocols
> (or the persons who nominated them) should prepare papers (as separate PDFs
> or just in a form of a message to the CFRG mailing list or to the CFRG chairs)
> with:
> a.      expanded answers for all positions of RFC 8125 regarding their
> PAKEs;
> b.      their own opinions on the following questions (they does not need
> to be complete: for example, a designer of a PAKE might not be an expert in
> TLS and might not be able to reply how his PAKE can be incorporated in TLS
> 1.3):
> 
>    - How does it meet the "SHOULD" requirements of RFC 8125?
>    - Does it meet "crypto agility" requirements, not fixing any particular
>    primitives and/or parameters?
>    - What setting is the PAKE suitable for, which applications does it
>    have?
>       - "Peer communication" (where both ends share the same password) or
>       "client-server" (where the server does not store the password but only a
>       one-way function of the password)?
>       - A nomination should specify for which use-cases the protocol is
>       recommended ("PAKE as a more-secure replacement for a PSK on a
>       machine-2-machine interface" or "PAKE for securely accessing a remote HMI
>       interface server (e.g. a web server) without configured WEB-PKI
>       certificates").
>       - Can two communicating parties initiate the key exchange process at
>       the same time, or must it always be the case that only one party can
>       initiate the process?
>       - Is it suitable to be considered as a standalone scheme?
>       - Can it be integrated into IKEv2? TLS Handshake? Any other protocols?
>    - Is there a publicly available security proof? If yes,
>       - Are there known problems with the proof?
>       - Is the considered security model relevant for all applications that
>       PAKE is intended for (e.g., if a PAKE is to be used in TLS
> Handshake, it is
>       important that the TLS adversary model is considered for the PAKE)?
>       - Does it allow to be sure in sufficient level of security for common
>       values of password lengths?
>    - Security assessment.
>    - Does its security depend on any nontrivial implementation properties?
>       Are they clearly stated in the document?
>       - Does the PAKE have precomputation security (for augmented PAKEs)?
>       - If the PAKE relies on the assumption of a trusted setup - more
>       specifically, the discrete logarithm relationship between the two group
>       elements in the system setup MUST be unknown - in anticipation
> of the worst
>       but not impossible scenario, the authors should clearly state
> the security
>       implications when the discrete logarithm relationship becomes known, and
>       the subsequent mitigation measures.
>    - Performance assessment.
>    - What's with the “round efficiency” of the PAKE? In a standard
>       two/multi-party secure computation setting, the “round” is defined as a
>       step in which all parties can complete operations at the same
> time without
>       depending on each other. In practice, a 2-round protocol could be
>       implemented as 2 flows or 3 flows depending on the application
> context, but
>       that’s more the implementation detail.
>       - How many operations of each type (scalar multiplications,
>       inversions in finite fields, hash calculations etc.) are made by
> each side?
>    - Which recommendations for secure usage can be given?
>       - Is it defined how the explicit key confirmation is performed/must
>       be performed externally? Are there clear statements whether this
> procedure
>       is optional or mandatory?
>       - Can any recommendations on using iterated hashing (e.g., with
>       Scrypt) with the PAKE be given?
>       - Can any recommendations to avoid a user enumeration attack be given?
> 
> Best regards,
> Stanislav Smyshlyaev
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg