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

[Mike Hamburg <[e-mail]>]

Hello Feng,

> On Apr 9, 2021, at 1:18 PM, Hao, Feng <[e-mail]> wrote:
> 
> Hi Loup and Mike,
>  
> Thanks for the comments. As your arguments have something in common, so I will reply together.
>  
> First, let me re-iterate my two main questions:
>  
> Do we agree we need an algorithm specification be “complete”, covering all usual and edge cases? In the current hash-to-curve draft, there is a failure mode that is non-recoverable. I’m concerned about this as I haven’t come across something like this before. My question is not on the probability, but the “completeness” of an algorithm specification.

An algorithm specification should be complete, though many algorithms do have paths that end in failure.  The hash-to-curve specification is, as far as I’m aware, complete.  It does not end in failure if it returns the identity point.  That point is simply the correct output for certain inputs.

I don’t know if the same holds for OPAQUE or CPace: for all I know, they may have specification holes and/or end in failure in that case.

> If a protocol is provably secure under some assumption, do we agree the assumption should be “precise”? There is a clear discrepancy in what’s assumed in the CPace, OPAQUE and maybe other protocols and what’s actually provided by the concrete construction. Either should the assumption in the security proof be modified to fit the real construction, or the construction modified to fit the actual assumption in the proof.

Ideally assumptions should be precise, though in practice they are not: they assume that an adversary cannot feasibly solve a certain mathematical problem with more than negligible probability, where “feasibly” and “more than negligible” are a bit fuzzy.  That said, the mathematical problem being solved should be precise.

Security proofs, which might more accurately be called security arguments, usually take the following form:
*   Given an algorithm A which breaks the scheme’s security goals in some model with probability epsilon,
*   We can create an algorithm B, running in “not much more time or other resources” than A
**   (or some other bound; “not much more time" is not precise but pinning it down exactly is a huge pain for usually not much gain),
*   Which solves an assumed-hard math problem with some probability delta
*   Where delta is bounded from below based on epsilon and perhaps some other factors **   (e.g. the number of times the adversary calls the hash function, or the number of users of the system).

If hitting the point at infinity affects the probability of B’s success — in some cases it will, and in some (e.g. PAK) it won’t — then the proof must account for this in its bound.  However, if the adversary can’t cause this to happen, then the term from this effect will be on the order of q/p, where q is the amount of work that honest parties do, and p is the order of the group.  Such terms are typically much less than the epsilon for a reasonable attack strategy, so they won’t significantly worsen the bounds in the security proof.

> Both of you mention that the probability of falling into a small subgroup in common elliptic curves is negligible, and hence should be ignored. However, we should be aware of the function creep once the map-to-curve functions are deployed at scale. For example, if a user already has an input value in F_p, does he still have to go through the hash_to_field step (which is complex on its own)? A conscious implementer will quite likely skip this step. But that will give more freedom to an attacker to engineer the input such that the output falls into a small subgroup.

Hash_to_field is an essential part of hash_to_curve.  These protocols are often completely insecure if you skip that step and allow the attacker to choose the inputs, small subgroup or no.  Also, if an implementer skips this step, then their implementation won’t work: or rather, it won’t interoperate with anyone else’s.

> The negligible probability in your analysis will no longer hold. For a safe implementation, precluding small-group points should be built into the map-to-curve function itself (in constant time of course). I know that’s hard, but that’s exactly why the hash-to-curve function has remained so tricky to get right in PAKE since early 2000s.
>  
> Cheers,
> Feng

We could always say something like: if the output would be the identity then instead output the generator.  But again, I’m not aware of a case where this meaningfully affects the security, especially because even finding an input that maps to the identity likely constitutes an attack on the hash function.

Furthermore, the goal of hash-to-curve is usually to find a point of unknown discrete log.  If the attacker can guess the discrete log of the hash image, or if honest parties choose a point whose discrete log the adversary somehow knows — which happens with the same probability 1/q as finding the identity point — then in most cases the adversary wins.  So again, changing the identity to some other point often doesn’t change anything.

Overall, while I like to remove rough edges, I’m not sure this is a rougher edge than a check that changes the identity point to some other point.

Cheers,
— Mike