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

[Mike Hamburg <[e-mail]>]

> On Apr 9, 2021, at 7:25 PM, Hao, Feng 
> So far hash2curve and CPace/OPQUE have been developed separately with the former being largely assumed as an idealized function. I think now is a good time to look at the integration of the two in a system context. With the current hash2curve draft, as long as map-to-curve returns a low-order point, the user’s password will be inevitably broken by offline dictionary attacks based on the side-channel information. There is nothing the protocol can do (rejecting the point gives away the exact side-channel information needed for offline dictionary attacks). However, one can argue that the chance of this “really bad event” happening is L/q where L is the size of the small sub-group. It’s too small to be of any concern over common elliptic curves, and we hope that never happens. I think this is a perfectly sensible argument from a practical point of view. From a theoretical point of view, the argument is not appealing or neat. Hence, my question is why the small subgroup points can’t be precluded from the map-to-curve function? 

Hello Feng,

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

ISK == H2(sid || 7*Y_b || oc(Y_a, Y_b))

(If ISK is not available, then some hash or encryption with it surely will be.)

Then the adversary will know that G = Map2Point(H_1(sid || oc(P, P’) || pw)) = Y_a / 7, which enables an offline dictionary attack.

Of course, the same consideration applies to every other scalar Alice could sample: if an adversary looks for that event, which occurs with probability 1/p, then Alice will be hacked: her password will be subject to an offline dictionary attack, and her session key will also be compromised.  At first blush, to me anyway, this looks quite similar to what happens if hash_to_curve outputs the identity.  And there’s an independent chance of that happening once per connection, because the sid should be unique.

In other words, the security risk introduced by the point at infinity is on the same order as the most trivial other attack on the protocol.

Nor is the possibility of failure a meaningful concern in practice.  A 2^-256 probability is ridiculously small: it stacks up against events like "Alice and Bob fail to exchange keys because they both get struck by lightning simultaneously, while also being hit by meteors simultaneously”.

The only meaningful concern here is the much greater risk that someone would somehow screw up the failure detection code in a way that introduces an exploitable flaw.



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.

This is the standard object that has been studied, and which protocols are built around.  You are proposing that we change it to a negligibly different object.  I’m sympathetic to this, but ultimately it is similar to an argument that we should replace pi with tau := 2*pi in mathematical analysis.  It’s extra work for essentially no gain, it requires redoing work that’s been done and will work fine.  There just isn’t enough time in the day for this kind of thing.

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.

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

Regards,
— Mike