Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

[Björn Haase <[e-mail]>]

Dear Hao,

 

>In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator.

>The implicit assumption is that the returned value from hash-to-curve must be a non-identity

>point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

>Has this issue been considered? Apologies if I missed any discussion on this before.

for CPace this has been considered in https://eprint.iacr.org/2021/114.pdf in the context of the proof for theorem 3.6 (and  correspondingly theorem 6.1, "Security of CPace with Map2Point") and become part of the (negligible) loss due to  the increased collision probability for the hash H_1.

 

So yes, for CPace this has been analyzed and quantified, and according to my assessment a corresponding approach will also apply for DH-OPRF-based constructions such as OPAQUE given that the map is "probabilistically invertible" according to the definition in https://eprint.iacr.org/2021/114.pdf  and that it is hard to find pre-images for the hash function used for the map-to-field operation (which is e.g. implied by modeling this as random oracle).

 

I don't identify the need of considering this aspect in the hash2curve level, but I agree that this should be covered by the security analysis of protocols that use the maps.

 

Yours,

 

Björn.

Gesendet: Freitag, 09. April 2021 um 15:44 Uhr
Von: "Hao, Feng" <Feng.Hao=[e-mail]>
An: "CFRG" <[e-mail]>
Betreff: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Hi all,

 

I just read through the latest version of the hash-to-curve ID (v10) and have a question.

 

The methods defined in the draft map field elements in F_p to points on elliptic curves. But the points include small subgroup (low-order) points. What if the mapped point on the curve falls into a small subgroup? The clearing-the-co-factor step (section 7) does no help at all here as it only turns the small subgroup point to an identity point.

 

The chance of falling into a small subgroup is extremely small, but for the completeness of the algorithm specification and the analysis, it’s still necessary to explicitly specify what to do in this case.

 

If the mapping function gives a small subgroup point, you cannot re-run the function to generate another point, as that will defeat the constant time principle. But obviously, a small subgroup point (or an identity point after the co-factor clearing) can’t be used safely for any protocol. It seems we have a failure mode which is “non-recoverable”.

 

In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator. The implicit assumption is that the returned value from hash-to-curve must be a non-identity point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

 

Has this issue been considered? Apologies if I missed any discussion on this before.

 

Cheers,

Feng

 

_______________________________________________ CFRG mailing list [e-mail] https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg