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

[Hugo Krawczyk <[e-mail]>]

On Sat, Apr 10, 2021 at 4:37 PM Hao, Feng <[e-mail]> wrote:

> 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!)
>

You can see the details here
https://github.com/cfrg/draft-irtf-cfrg-opaque

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

I don't see any timing attack here. We are talking about a user that
chooses a password that is mapped to the identity (let's call such a
password *magic) *and is asked to choose a new one. Only non-magic
passwords are allowed. All the attacker learned is that the user *initially*
chose  a magic  password that was rejected and then chose a regular
non-magic password. It knows nothing about the user's accepted password.

Of course, this is a purely fictional discussion since the probability to
have a magic password in a dictionary of 2^128 passwords (as rich as an
AES-128 random key) is 2^{-128}  (for curves of size 2^256).

This reminded me of the well known medieval question of "how many angels
can dance on the head of a PIN" but in the present case it seems more
appropriate to ask "how many angels can dance on the head of a password".

Hugo


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