[Crypto-panel] Forwarding a message from Bjoern Haase

["Stanislav V. Smyshlyaev" <[e-mail]>]

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