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

["Hao, Feng" <[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