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

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

Hi Hugo,



  *   If I understand correctly, you are saying that in the case of password protocols, the unlikely event of (a correctly designed, correctly implemented) hash-to-curve mapping some value to the identity has irrecoverable consequences that are specific to the PAKE setting.

  *   I wanted to comment that in the case of OPAQUE, you could check during password registration that a user's password maps to the identity and ask to choose a new password (we are used to websites rejecting some passwords). However, when that happens, the website should immediately (*) sound an alarm to be heard across the universe. You would have found a preimage of the identity under a RO-modeled hash function. Either you are observing an event with probability, say, 2^{-256}, or you are observing a hugely more probable event: Someone broke the one-wayness of the hash function. STOP USING IT IMMEDIATELY FOR ANY PURPOSE.

As you know, hash-to-curve has three components: hash_to_field, map_to_curve and clear_co_factor. For the sake of discussion, let’s remove clear_to_factor as it has been a source of confusion, and this removal doesn’t affect our analysis in any way. Also for generality, let’s assume the small subgroup size is L. The value L depends on the group setting. In MODP, L is large, but in EC, it’s usually small, but that’s the implementation detail.

OPAQUE has a registration phase. In your paper, you assume registration is done securely but without details. Therefore, I have to fill in the details below according to my understanding (apologies if I got anything wrong, but in that case, do correct me!)

Unlike CPace and other balanced protocols which may use an out-of-band channel (visual, sound etc) to distribute a low-entropy secret, OPAQUE has to do the registration over a network since it involves exchanging data of long strings (k, Ps, c). However, in a typical PAKE context, there is no pre-existing secure channel. A natural solution would be to do the registration over SSL/TLS (which introduces a PKI which is what PAKE aims to avoid). But a PKI is needed only for a registration phase, so let’s assume registration is done over SSL/TLS.

The scenario we consider is what happens if the output of map_to_curve falls into a small subgroup. The user has to reject it and choose another password, but the timing side channel gives away the exact oracle to a passive attacker to do an offline dictionary attack. Note that the attacker doesn’t need to read the content in SSL/TLS, but just observes the communication time. He can exclude passwords that don’t fall into the small subgroup.

So the registration phase doesn’t help you. Even if it’s done over a secure SSL/TLS channel, it’s sufficient if the attacker can observe the timing delay in the communication.

Therefore, the best one can do is to hope map-to-curve never falls into a small subgroup. But in that case, wouldn’t it better to preclude small subgroup points from map-to-curve by design?