Subject: Re: [Cfrg] [CFRG] PAKE / Hash2Curve First Internet draft for balanced CPace subcomponent available

From: "Hao, Feng" <[email-masked]>
Date: Tue, 7 Jan 2020 16:17:48 +0000

Dear Bjorn,

  *   There seems to be the need for more clearly specify, what is "identity".  For the CPace draft, I assumed that the receiver or sender "identity", i.e. the content  of the strings A and B in the CPace draft, would be something like a destination IP address and  a destination port on this machine. I.e. information that is required for establishing the link and exchanging the message.

At the protocol level, we normally don’t concern the communicating identities such as IP/MAC addresses (although they might be used as identities in special circumstances) as they are implementation details at a lower level. By “identity”, I mean the normal definition in a key exchange protocol in a general case: a unique string that identifies each party in the communication process. If you require the other party’s “identity” to be known beforehand, you need to state that assumption explicitly. I just wanted to point out that it’s not safe to make that assumption in the general case.

  *   It's also all about patents, IMO, why J-PAKE has been integrated by companies like Mozilla, and SPEKE and SPAKE2 were not considered. (In fact, I  believe that very few people will be talking openly about this type of reasoning.)

I can’t talk about other people’s reasoning (the decision to choose J-PAKE in Mozilla and Thread is entirely the result of the industry’s own “independent” assessment; as designers of J-PAKE we were not involved). But I want to clarify that the motivation of J-PAKE was not to avoid patent, but to actually solve the problem! Patented alternatives such as EKE and SPEKE have various idiosyncrasies that make technical analysis and implementation difficult. Patent is a thorny issue, but not a blocker as ultimately people need a secure and efficient solution (for that paying royalty is a common practice in business).

  *   Actually as mentioned above, I personally don't see any remaining technical or security risks. (This is also what I did take with me from discussions with the BSI people that designed the PAKE protocol for the german identity cards.) Also note, that there *are* already high security applications that use PAKE with mapping, such as the "french" version of PACE. Maybe you could be more specific, where exactly, you identify security issues with hashing to curves.

I suggest we wait until the hash-to-curve draft is complete and fixed first so we are not analysing a moving target. But as a suggestion, I recommend authors of the hash-to-curve draft to provide more explicit design requirements that the proposed function is supposed to satisfy. That would be helpful. Currently the draft mentions “plausibly constant time”, “random oracle encoding” … These are a bit vague. Presumably, with a hash-to-curve function, you want to (somehow) randomly maps an input string from an infinite domain to a point in a finite domain which satisfies specific curve constraints while keeping the operation constant-time. Clearly due to the domain mismatch, such an ideal (random oracle) mapping is theoretically impossible, so the best that can be done is to have one that is computationally secure. For that purpose specific requirements should be defined, e.g., they might include similar requirements as a hash such as pre-image, second pre-image and collision resistance + guaranteed validity of the output (valid point in the designated group) + constant time? With the list of requirements, it will help other researchers to analyse the functions in a more concrete way. The very tricky thing here is that there is a custom-built security primitive for each of the many curves that people want to support, so you need to ensure each must be secure and be analysed properly … Still this gives no forward compatibility – things might break in the future with new curves. A general solution that securely works with any elliptic curve suitable for cryptography at a reasonable cost will be far more attractive. That problem remains open as far I know.

---

From: Björn Haase <[email-masked]>
Date: Tue, 7 Jan 2020 23:18:40 +0100

Dear Feng,

 >I can’t talk about other people’s reasoning...

and also I'm not able to or interrested in reading other people's minds.
I did not mean to be offensive. I aim at being fair to all candidates in
the discussions and specifically also to J-PAKE.

I agree with you that reasoning what other peoples did think is
guesswork. Maybe let's better re-phrase my earlier statement more
accurately as follows:

J-PAKE beside the two additional rounds and the efficiency
disadvantages, in my opinion has four outstanding points:

1.) The simple structure that avoids the risk to overlook errors and
problems in the proof strategy (as pointed out correctly by Scott!)
because with your construction, you don't need assumptions similar or
close to things such as the "known-exponent assumption". You simply
proove that the remote side did now the exponent and use this in the proof.

2.)  with this structure, you don't need programmable RO

3.)  you don't need the complexity of hashing to curves.

4.) and finally:  It's not covered by the patents.

Even if it was quite obviously not your main objective, I believe that
from all of the advantages the feature 4.) might indeed have been the
single one most valuable property of J-PAKE for industry.

Yours,

Björn.

P.S.:

FYI: With our company we have actually tried to get / evaluate the cost
of licences. That did turn out to be extremely painful (already to find
the right contact person, agree on commonly accepted NDA forms, agree on
licensing contract frameworks, trying to setup the reporting process
regarding production and number of uses of the patent, volumes in the
specific countries with valid patent and without, what to do with apps
and service software tools that are typically shipped for free, where
royalty conditions of the patent holder might force you to *sell*
individual licenses or require complex online registering processes for
your own customers, such that you could report how many times the
software is actually installed and used and in which country ....

In the end, our legal department requested us to implement a solution
not covered by patents ...

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 10 Jan 2020 14:45:23 +0000

Dear Bjorn,

> I aim at being fair to all candidates in the discussions and specifically also to J-PAKE.

Thanks for doing this. I believe a fact-based approach is what's needed to drive this process forward. We often see too many opinions which are not substantiated.

> J-PAKE beside the two additional rounds and the efficiency disadvantages, in my opinion has four outstanding points:

Being 2 rounds is a factual limitation for J-PAKE as compared to 1-round PAKE (acknowledged in the original J-PAKE paper). However, in terms of computation efficiency, J-PAKE has no disadvantage if you compare protocols side-by-side fairly.
    
So far, the most established 1-round protocol (without trusted setup) is the (patched) SPEKE, which is specified in ISO/IEC 11770-4 (2017). We can have a fair comparison since neither requires a trusted setup.

 * In the finite field setting, SPEKE requires 2 modular exponentiations (with long exponents) while J-PAKE needs 14 modular exponentiation (with short exponents). Overall, the computational cost of SPEKE is about the same as (or even higher than) J-PAKE. This is explained in the original J-PAKE paper. Unfortunately, several experts in the reviewing process only counted the number of modular exponentiations without considering the critical difference in the bit length on the exponent. The unfortunate use of the long bit length in SPEKE is a known idiosyncrasy in the design, which is rooted in the need to perform an hash-to-field-element operation. Given that CPace is a SPEKE variant, if you specify CPace in the finite field, you should find it will have no computational advantage than J-PAKE for the same reason.
 * In the elliptic curve setting, the SPEKE specification in ISO/IEC 11770-4 is not really established, so its efficiency is yet to be established. For this reason, it cannot be compared with J-PAKE. SPEKE critically depends on a hash-to-curve function (also called Integer-to-Point or I2P in the IEEE P1363.2 and ISO/IEC documents; but it's the same thing). Such a function is provided in ISO/IEC 11770-4, but with the following note

" This function is believed to hold properties of the randomness and onewayness, i.e. converting an integer to a point such that the point is randomly distributed in the selected group and that given current knowledge, recovering the integer from the point is computationally infeasible. This function is also used by IEEE P1363[7]. However, there is no formal security proof of this function published"

The same note might be applicable to the current IETF draft on hash-to-curve. This is why I suggested that we should wait until the IETF draft to be finalized before we can evaluate the security and efficiency of PAKE protocols that critically depend on it.

> Even if it was quite obviously not your main objective, I believe that from all of the advantages the feature 4.) might indeed have been the single one most valuable property of J-PAKE for industry.
    
I agree parents have unfortunately messed up the PAKE field, but if you look at the history of the developments in this field and take a critical view to examine all the proposed solutions, you may find that a more fundamental obstacle in deploying PAKE is actually a technical one.

About 10-20 years ago (IEEE P1363.2 had a public and intensive standardization process on PAKE in 2000-2008), many people believed the PAKE problem had been solved - with an "ideal cipher" that performs a random-oracle like mapping keyed by a low-entry password, you can have a "provably secure" PAKE with formal security proofs. Hence the problem is reduced to a simpler task of instantiating the "ideal cipher". But later it turned out that this was much trickier than what one might have expected. Instead, alternative approaches were proposed based on "trusted setup", and "hash-to-curve" functions. All these proposals were intensively reviewed during the IEEE standardization process, but by the end of 2008 (8 years after when the standardization started and that was the maximum life span normally expected for a standardization project), it became all clear that the PAKE problem had actually remained unsolved, as none of the techniques (including patented ones) was found filling the bill. This was what motivated us to design a practical solution to this engineering problem back in 2008, by taking a fresh and completely different approach. Whether J-PAKE has actually solved this problem of if there will be a better solution remains to be seen but I recall back in the time when I was a PhD student, David Wheeler (Cambridge) used to say to us: 

"In computer science, you can solve any problem by adding an extra layer of indirection, until that extra layer of indirection becomes a new problem."

I'm happy to say, at least, J-PAKE was fully specified and fixed (without any extra layer of indirection) at the time when it was first presented at SPW'08, and since then it hasn't changed despite intensive public scrutiny.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 10 Jan 2020 13:44:12 -0800

Hello Hao,

"Hao, Feng" <[email-masked]> wrote:
>     "However, there is no formal security proof of this function published"
> 
> The same note might be applicable to the current IETF draft on
> hash-to-curve.

The constructions in the draft all have published security analyses.

Apologies if this is not clear from the draft; I will take a note
to go over it and make sure that it is made clearer.

-=rsw

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 10 Jan 2020 21:52:19 +0000

Hi Riad,

That will be great. Following my previous comment, please also add a list of explicit design requirements that the constructions are supposed to satisfy, so we know what exactly have been proved and the security guarantee.

Cheers,
Feng

On 10/01/2020, 21:44, "Riad S. Wahby" <[email-masked]> wrote:

    Hello Hao,

    
    
    -=rsw