Subject: [Cfrg] PAKE Selection Process: Round 2, Documents for Stage 4

From: Björn Haase <[email-masked]>
Date: Mon, 10 Feb 2020 14:50:44 +0000

Dear CFRG,

as requested for the beginning of stage 4 of the second round of the PAKE selection process, I have compiled the additional documentation at the following places.

Paper: 
https://github.com/BjoernMHaase/AuCPace/blob/master/aucpace_security_analysis_20200208.pdf

Internet Drafts:
https://tools.ietf.org/html/draft-haase-aucpace-01
https://tools.ietf.org/html/draft-haase-cpace-01

Reference implementations:
https://github.com/BjoernMHaase/AuCPace

Please find a short version of my replies below:

Question 2):
"(to CPace and AuCPace): Can you propose a modification of CPace and AuCPace (preserving all existing good properties of these PAKEs) with a correspondingly updated security proof (maybe, in some other security models), addressing the issue of requiring the establishment of a session identifier (sid) during each call of the protocol for the cost of one additional message?"

Reply to 2) :
I have re-reviewed this issue and integrated the alternative approach as suggested by Ran Canetti on the CFRG list in the paper and security analysis (see “paper” link above). The specification in the CPace and AuCPace internet drafts now also correspond to this approach. With this method, there is no longer the need for an additional communication round.

Question 3):
 "(to all 4 remaining PAKEs) : Can the nominators/developers of the protocols please re-evaluate possible IPR conflicts between their candidates protocols and own and foreign patents? Specifically, can you discuss the impact of U.S. Patent 7,047,408 (expected expiration 10th of march 2023) on free use of SPAKE2 and the impact of EP1847062B1 (HMQV, expected expiration October 2026) on the free use of the RFC-drafts for OPAQUE?"

Reply to 3):
I have re-visited all patents and did not find any IPR that might generate conflicts with CPace and AuCPace. The topic of the mapping algorithms is resolved in my opinion with the latest changes in the hash_to_curve draft (which avoids the “-1 non-s	quare” topic and the “three-polynomial” issue for SSWU).

In contrast, in the course of this research I came to the conclusion that SPAKE2 is probably affected by US 7,047,408. The exceptional feature is that the duration of this patent seems to have been extended to a period of exceptional 23 years instead of 20 years! I have double-checked and that seems indeed to be legally possibly in the US. I have just filed a corresponding IPR disclosure.

Question 4): 
"(to all 4 remaining PAKEs) What can be said about the property of "quantum annoyance" (an attacker with a quantum computer needs to solve [one or more] DLP per password guess) of the PAKE?"

Reply to 4):

As previously noted also by “Steve Thomas”, for CPace an active adversary needs to solve at least one DLP per password guess this also holds for the conventionally augmented AuCPace variant. 

The additional guarantee of “pre-computation attack resistance” provided by the OPRF construction of strong AuCPace, however will not be preserved. This means that the *strong* AuCPace protocol will fall back the conventionally augmented AuCPace in the post-quantum world, which itself is again quantum annoying.  (This comes as a consequence of the issue with the "static Diffie-Hellmann oracle topic" regarding the OPAQUE OPRF, as brought up recently by Steve Thomas recently on the crypto panel list).

Question 5):  "(to all 4 remaining PAKEs) What can be said about "post-quantum preparedness" of the PAKE?"

Reply to 4):

In the Internet Drafts regarding CPace and AuCPace I have added a short discussion on this topic.

I believe that the fact that CPace and AuCPace don’t actually require a full group structure but only operations in a "group modulo negation" might provide a path for using isogeny-based cryptography as kind of a drop-in replacement for the Diffie-Hellmann substeps. 

While primitives such as SIKE and CSIDH provide functionality similar to a DH secret establishment (where both parties contribute to the key), there is no such equivalent of “point addition” in the isogeny world. In my opinion, for the augmentation layer of AuCPace, the mechanisms on isogenies for Diffie-Hellmann-style secret establishment could already be used as-is. For the application in CPace (with the need of an isogeny-equivalent of a secret password-derived base point), there is ongoing research which is, however, not yet stabilized and mature in my opinion. Here I have added a links regarding possible migration paths regarding CPace in the security considerations section of the internet draft.

Additionally, the modularized security analysis of CPace as a building block of AuCPace allows for replacing the CPace component by any future balanced post-quantum PAKE (in the style that Hugo suggests for OPAQUE).
 For instance, I believe it to be promising to consider constructions based on the LWE problem where the matrices are kept secret and derived from a password and an ephemeral session id, in the style of "New hope" which uses SHAKE for generation of ephemeral LWE matrices. Still again, this topic, just as the isogenies, would require significant future research in my opinion.

I am unfortunately not aware of any current concept regarding a post quantum primitive for the OPRF construction as needed for *strong* AuCPace.

Yours,

Björn Haase

P.S.: A compilation regarding my personal view on the current state of the selection process is found at

https://github.com/BjoernMHaase/fe25519/blob/master/Slides_PAKE_selection_at_CFRG_Brainpool_20200115.pdf 

I tried to be as objective as one could reasonably be expecting from an individual having own nominations running.

Mit freundlichen Grüßen I Best Regards 

Dr. Björn Haase 

Senior Expert Electronics | TGREH Electronics Hardware
Endress+Hauser Conducta GmbH+Co.KG | Dieselstrasse 24 | 70839 Gerlingen | Germany
Phone: +49 7156 209 377 | Fax: +49 7156 209 221
[email-masked] |  www.conducta.endress.com 

Endress+Hauser Conducta GmbH+Co.KG
Amtsgericht Stuttgart HRA 201908
Sitz der Gesellschaft: Gerlingen
Persönlich haftende Gesellschafterin:
Endress+Hauser Conducta Verwaltungsgesellschaft mbH
Sitz der Gesellschaft: Gerlingen
Amtsgericht Stuttgart HRA 201929
Geschäftsführer: Dr. Manfred Jagiella

Gemäss Datenschutzgrundverordnung sind wir verpflichtet, Sie zu informieren, wenn wir personenbezogene Daten von Ihnen erheben.
Dieser Informationspflicht kommen wir mit folgendem Datenschutzhinweis (https://www.endress.com/de/cookies-endress+hauser-website) nach.

Disclaimer: 

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon, this information by persons or entities other than the intended recipient is prohibited. If you receive this in error, please contact the sender and delete the material from any computer. This e-mail does not constitute a contract offer, a contract amendment, or an acceptance of a contract offer unless explicitly and conspicuously designated or stated as such.