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

[Mike Hamburg <[e-mail]>]

> On Apr 10, 2021, at 6:32 AM, Hao, Feng <[e-mail]> wrote:
> 
> 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 <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.

Hi Feng,

hash_to_curve is (epsilon-close to) uniformly distributed within its range, which is the prime-order group of points on the curve, which is also the range specified by these schemes in the literature.

> 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.

No, not PAK.  PAK uses the hash output as an additive blinding factor, so it ideally wants the value to be uniform in the group, non uniform among non-identity elements.  Of course, removing the identity won’t harm it, since again, that’s a negligible change.

> 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.

No, it’s pretty much the exact opposite of that.

DDH is usually written as distinguishing (G, aG, bG, abG) from (G, aG, bG, cG) where g is a generator and (a,b,c) are uniformly random mod the group order.  See eg http://theory.stanford.edu/~dabo/papers/DDH.pdf <http://theory.stanford.edu/~dabo/papers/DDH.pdf> (which uses exponential notation but is otherwise the same), though variants (such as c != ab) are sometimes used instead.  Here aG, bG and cG can be the identity.  In this formulation, G cannot be the identity: it’s defined as a generator.  But if it were the identity then the two distributions would be identical — they would each be 4 copies of the identity — so DDH would still hold.

DDH does not hold in a group with a small cofactor h.  The problem is not that you might choose a small-order element by chance, but that the attacker can project to the subgroup by multiplying everything by p.  Clearing the cofactor resolves this issue.  So removing that step does affect the analysis, at least if you’re assuming DDH.

> 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. 

In many cases things are cleaner if indeed you achieve uniformity in a group, which is why hash_to_curve does this.  You are suggesting uniformity in G \ {0}, which is not a group.

> 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?

A negligible probability of the adversary getting your key is not a security consideration, as explained above.  The only security consideration is “don’t screw up the error handling”, or maybe a note to say why we aren’t worried about the identity.

> 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.

If you’re using my library, libdecaf, then you can use decaf_point_eq and decaf_point_cond_sel to remove the identity in constant time.  Similar functions are likely available in other libraries.

> 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.

No, hash_to_curve on curves with cofactor = 1 can also return the identity point, because it adds two map_to_curve results together.  That case is arguably harder, because there are very simple complete addition laws for Edwards curves with cofactor 4, but the complete addition laws for Short Weierstrass curves with cofactor 1 are more complex.

Regards,
— Mike