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

["Stanislav V. Smyshlyaev" <[e-mail]>]

Hi all,

With my chair’s hat off, I completely agree with Russ Housley: adding some
comments about the issue and recommendations for implementors to the
Security Considerations section seems to be a good solution here.

Regards,
Stanislav

Вс, 11 апр. 2021 г. в 13:37, Hao, Feng <Feng.Hao=
[e-mail]>:

>
>    - 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.
>
>
>
> Once the map-to-curve output falls into a small subgroup, it’s a
> non-recoverable failure mode as the password is inevitably disclosed to a
> passive attacker by the side-channel. Now the user has to choose a new
> password. This is the same as CPace (using the hash-to-curve draft). The
> new password is of course fine. But the scenario might re-cur when the user
> tries to change passwords.
>
>
>    - 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).
>
>
>
> As I clarified before, I don’t claim this is a practical attack. So far
> this is mostly a thought experiment, which I hope can help better
> understand the PAKE system when you have the real hash-to-curve function
> included.
>
>
>
> What this though experiment shows is an idiosyncrasy in the system. It
> seems the small subgroup confinement issue hasn’t been considered in CPace
> and OPAQUE. This is understandable given that both protocols have been
> assuming hash-to-curve as an idealized function. Fortunately, for the curve
> settings considered in the hash-to-curve draft, the size of the small
> subgroups is so small that the practical effect is negligible. But the
> effect can be dramatically different when CPace and OPAQUE are implemented
> in a different group where the size of the small subgroup is not small,
> e.g., DSA, Schnoor.
>
>
>
> We know that both CPace and OPAQUE have been rigorously analysed to be
> provably secure in a strong universally composable model. That’s all good,
> but what exactly does this mean? The proof makes assumptions, which
> typically include certain hard math problems. What the above though
> experiment shows that for both protocols, the assumptions also include
> implementation choices, in particular, the size of the small subgroup must
> be small. This constrains the protocols to specific group settings, and not
> generally applicable to other group setting as one might have expected.
>
>
>
> The idiosyncrasy itself is not a problem (depending on how you view it).
> In the history of PAKE development, there are lots of examples that certain
> aspects of a PAKE system are idiosyncratic but can do negligible harm when
> you choose very specific implementation settings.
>
>
>
> As an example, in 1996, Jaspan described an idiosyncrasy in DH-EKE [1].
> The possibility that the password-encrypted item may be decrypted to a
> value > p gives an oracle for a passive attacker to exclude certain
> passwords. Of course, one can argue we can mitigate the effect of this
> issue by carefully choosing the group parameters: namely, choosing a safe
> prime that is as close to the power of 2 as possible. Thus you can mitigate
> the effect of the leakage as low as you want, say below <2^{-128}. The
> theoretical leakage is still there, but the practical effect is negligible.
> This is fine, but it does mean one has to very carefully choose which
> specific group setting to implement the protocol, and the same protocol can
> be trivially insecure in other groups.
>
>
>
> SRP is another example. In 2010, I analyzed SRP-6. I didn’t find practical
> attacks, but found an idiosyncrasy in the system [2]. The mixing up of
> operations in different groups including small sub-groups gives a
> possibility that an online attacker may guess more than one password. This
> is not any practical attack and the effect on the practical security of
> SRP-6 is negligible. However, this idiosyncrasy shows that it’s simply
> impossible to prove the online dictionary attack resistance for SRP-6
> (namely, limiting to one guess per execution). Indeed, no one has proved
> that property for SRP-6.
>
>
>
> There are other examples, but I won’t go on here.
>
>
>
> In summary, with the current hash-to-curve functions defined in the draft,
> the practical effect of a small subgroup confinement is negligible for
> OPAQUE and CPace. I was hoping we could remove this effect (never mind how
> small it might be) so the security claims in CPace/OPAQUE can be cleaner
> and the hash-to-curve draft can be more useful, but if people think that
> can’t be done or is a waste of time, that’s OK! In that case, one might
> need to explicitly state the assumptions (not just math problems, but also
> specific implementation choices) and be very careful in applying the
> provable security claim to different group settings.
>
>
>
> [1] Jaspan, “Dual-workfactor Encrypted Key Exchange: Efficiently
> Preventing Password Chaining and Dictionary Attacks”, 1996.
>
>
>
> [2] Hao, "On Small Subgroup Non-Confinement Attacks," 2010.
> https://www.dcs.warwick.ac.uk/~fenghao/files/Analysis_of_SRP_final.pdf
>
>
>
> Cheers,
>
> Feng
>
>
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>