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

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

 Hi Bjorn,


  *   I think that structuring the discussion along the lines of the existing security analysis papers might help avoiding emotional discussion and might help to get things further in a more constructive way.


  *   So far after reading all comments explicitly including yours I conclude that there happens to be consensus in that there is actually 1) neither a security problem with the current draft specifications for hash2curve nor 2) for OPAQUE and CPace regarding identity- and low-order points produced by the various maps, encode2curve constructions and hash2curve constructions as presented in the hash2curve draft.

Thanks for your email. I actually don’t feel there is emotion in the discussions and there shouldn’t be. All of the arguments are technical, which I greatly appreciate. My goal is to clarify technical facts, not to debate opinions. People may have different opinions about facts; that’s totally fine and should be respected.

I hope the following gives a factual summary of this discussion to close this topic.


  *   I raised that the clear-co-factor step in the hash-to-curve draft doesn’t really address the small subgroup issue (thanks to Rene for confirming this). It only hides the issue under the carpet of “identity”. Therefore, there is a need to explicitly discuss what will happen if map-to-curve falls into a small subgroup.
  *   We discussed and established that when map-to-curve falls into a small subgroup, the user password in CPace/OPAQUE will be subject to offline dictionary attacks because of the timing side channel (the attack will work even if the user rejects/aborts).
  *   We established that with a correct implementation of hash-to-curve, the probability of falling into a small subgroup is L/q where L is the size of the small subgroup and q is the prime order of the subgroup. For the curves considered in the hash-to-curve draft, the probability is negligible, so there is no real concern for practical security.
  *   I asked for clarification on whether the small subgroup points can be removed from map-to-curve by design. The replies from the hash-to-curve authors indicated no: because 1) too much hassle; 2) not worth it for the negligible probability. I think the rationale is clear.
  *   Thus, the way forward as suggested by Russ and Stanislav is not to change the draft, but to add a note in security consideration to discuss the issues raised in the discussion, which may include 1) informing the reader that map-to-curve might return small subgroup points but at a negligible probability in the normal case; 2) making it very clear that the implementation of hash-to-curve must include all steps, in particular, skipping hash_to_field will cause serious security failure due to small subgroup attacks; 3) be careful with function creep, in particular, it must not be possible for the attacker to influence the input at map-to-curve; in that case, small subgroup attacks will again work trivially. I agree with Russ and Stanislav that adding a note is a good way forward.
  *   I learned from Loup and rsw (thanks!) that it is not that easy to remove small subgroup points with the current hash-to-curve design. This is very useful feedback which informs me and others as well an interesting research problem for future work. So far great work has been done on map-to-curve, but very little on removing the small subgroup points (the clearing the co-factor trick doesn’t really solve this issue).

Overall, this seems a constructive discussion to me. I thank all again for the replies and comments. I know some of my questions may look silly or not to your taste, but thanks for your patience and for bearing with me.

Cheers,
Feng