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

["Hao, Feng" <[e-mail]>]

Hi Mike,



  *   Have you considered what happens in CPace if Alice’s SampleScalar() function returns 7?  I’m following the notation of https://eprint.iacr.org/2021/114.pdf. In this case, the password will be vulnerable to a dictionary attack: the key K will be 7*Y_b, which an attacker can quickly detect by checking whether

Rsw also gave a similar example of having all zeros for the hash. Let me clarify that we are not – and shouldn’t be - concerned with any of such cases since the values are uniformly distributed within their respective range.

What we are discussing here is structural analysis of a PAKE system with the hash-to-curve being included as a building block. What the map-to-curve function permits in the output is a class of special data structures that fall into a small subgroup. Therefore, it’s necessary to analyse the effect of this class of data to the overall PAKE system.  As I explained, as soon as map-to-curve returns a small subgroup point, it will instantly cause the password in CPace/OPAQUE (PAK as well) to be compromised by offline dictionary attacks. There is nothing you can do at the protocol level to save it.


  *   On a more theoretical note, the hash_to_curve function aims to implement an object which has been studied in the literature, and which is used by several cryptosystems and protocols: for some serializable set S, a function S -> G which acts as closely as possible to a random oracle.  In particular, hash_to_curve is designed to be epsilon-indifferentiable from a random oracle with that signature, in the model that the underlying hash is a random oracle.

Published papers on hash-to-curve define the problem in their own (general) context. This is the first time (I think) we discuss it in the specific context of a PAKE use case with concrete PAKE choices.

I think a major misconception here is that many people may think the use of clearing-the-co-factor step has resolved the small sub-group issue. But that is not true. The clear-the-co-factor step merely changes small subgroup points to infinity points. For the simplicity of discussion, we can remove this step without affecting our analysis at all.

On a theoretical note, be reminded that DDH only holds for non-identity elements in a designated prime-order group on an elliptic curve. When you have small subgroup elements mixed, DDH doesn’t hold. It’s a tiny difference in the group definition, but it can have a significant theoretical effect.


  *   Furthermore, while your proposal is arguably a tiny improvement for SPEKE / CPace, and perhaps even for OPAQUE, it’s also a negligible step backwards for PAK and its variants  (if I recall correctly), since their proof uses the uniformity of the hash-to-curve map.  The same likely holds for other systems.  And it complicates the definition and implementation of hash_to_curve.

About “uniformity”, I think we can try to be more precise: uniformity in what group? With the current map-to-curve functions, the uniformity of the output covers the whole curve, including small subgroup elements. It’s exactly the mixing up with such elements that complicates things.


  *   So I would prefer that we stick here with something that’s been studied and which is already built.

Suppose we keep the draft as it is and only add a note in the security consideration to explain this. What can we possibly say?

One might add a warning to say map-to-curve returns uniformly distributed points on the curve, including small subgroup points. The mapping to small subgroup points is theoretically possible, but statistically unlikely. We don’t know how to remove these points in constant time. However, we have applied co-factor-clearing to turn small subgroup points to infinity points. That doesn’t actually change anything though and we still don’t know how to remove the infinity points in constant time. Therefore, we leave it to the upper layer protocol to decide how to deal with the infinity points.

On the other hand, from the perspective of a higher layer protocol (say CPace, OPAQUE and PAK), it’s simply impossible to handle the exception. As soon as map-to-curve hits the small subgroup, the password in a PAKE system will be compromised. Therefore, the above warning is self-defeating and not meaningful.

Moving forward, I think the best solution is to preclude the small subgroup elements from the map-to-curve function by design. If this can’t be done, or people don’t want to spend efforts to change the current draft, one solution might be to say only the functions defined for certain elliptic curves where co-factor = 1 should be used for PAKE. However, that will significantly limit the usefulness of this draft for the PAKE use case.