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

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 13:44:21 +0000

Hi all,

I just read through the latest version of the hash-to-curve ID (v10) and have a question.

The methods defined in the draft map field elements in F_p to points on elliptic curves. But the points include small subgroup (low-order) points. What if the mapped point on the curve falls into a small subgroup? The clearing-the-co-factor step (section 7) does no help at all here as it only turns the small subgroup point to an identity point.

The chance of falling into a small subgroup is extremely small, but for the completeness of the algorithm specification and the analysis, it’s still necessary to explicitly specify what to do in this case.

If the mapping function gives a small subgroup point, you cannot re-run the function to generate another point, as that will defeat the constant time principle. But obviously, a small subgroup point (or an identity point after the co-factor clearing) can’t be used safely for any protocol. It seems we have a failure mode which is “non-recoverable”.

In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator. The implicit assumption is that the returned value from hash-to-curve must be a non-identity point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

Has this issue been considered? Apologies if I missed any discussion on this before.

Cheers,
Feng

---

From: Loup Vaillant-David <[email-masked]>
Date: Fri, 09 Apr 2021 16:45:00 +0200

Hi,

> The methods defined in the draft map field elements in F_p to points
> on elliptic curves. But the points include small subgroup (low-order) 
> points. What if the mapped point on the curve falls into a small
> subgroup? The clearing-the-co-factor step (section 7) does no help at
> all here as it only turns the small subgroup point to an identity
> point.
>  
> The chance of falling into a small subgroup is extremely small, but
> for the completeness of the algorithm specification and the analysis,
> it’s still necessary to explicitly specify what to do in this case.

My opinion as an implementer is two fold:

1. Excluding low-order points is quite the hassle, and it's not
   clear how I could do it in constant time.
2. We never generate those points to begin with.

I don't want to deal with (1), which makes (2) very convenient for me.
So I'll just justify (2), using Curve25519 as an example:

- The order of the prime subgroup is a little over 2^252.
- The cofactor is 8.
- Therefore, Curve25519 has a little over 2^255 points.
- Selecting a point at random will give a low-order point about
  once every 2^252 trials. That means never.

The security of a curve is basically the square root of its prime
order. Here, 2^125 or so. Breaking it with standard brute force methods
is incommensurately easier than stumbling upon a low-order point by
chance.

In security parlance, a probability of 1/2^255 isn't just "extremely
small", it's "flat out impossible". I can therefore justify my laziness
and chose not to check for that event.

---

Note that generating a small-subgroup point *on purpose* will not work
either: Curve25519 has 8 low-order points, and a maximum of 16
representatives for those points (maybe a couple more if we allow
representatives over 2^255 - 19). The inputs are hashed before we map
the hash to the curve. So it's not enough to pick a matching
representative, we need to pick a hash whose image is one of those
representatives.

To do this, we need to conduct a multi-preimage attack on a 2^255-bit
hash, with 16 images. The difficulty of that attack is roughly 2^251.
Again, this is impossible if the hash is secure.

As a consequence, I cannot generate test vectors that account for this
edge case even if I wanted to. Even if I wasn't lazy, accounting for
low-order points means writing code I cannot trigger even if I want to
—dead code. That will only harm security in practice.

> In CPace and OPAQUE, both protocols use the output of hash-to-curve
> as a base generator. The implicit assumption is that the returned
> value from hash-to-curve must be a non-identity point in a subgroup
> of the large prime order.

This assumption is correct as far as I can tell: yes, in *theory*, we
have a couple exceptions. In *practice*, those exceptions will never
occur. The probabilities are low enough to be considered negligible.

> Has this issue been considered? Apologies if I missed any discussion

Likely. I haven't followed past discussions though, so I cannot say.

Loup.

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 9 Apr 2021 11:58:15 -0300

> On Apr 9, 2021, at 11:45 AM, Loup Vaillant-David <[email-masked]> wrote:
> 
> Hi,
> 
> 

Yeah, the usual answer is: if an event happens with negligible probability,
and an adversary can’t cause it to happen more often, and it only breaks
one thing, then it doesn’t affect security.  Any reasonable adversarial
strategy has some chance to break the protocol anyway (e.g. just guess
someone’s private key), and this unlikely event doesn’t significantly
contribute to that chance.  I haven’t checked the details for CPace and
OPAQUE, but for cases I’ve looked at it’s been fine.

Of course, implementations will not be fully compliant with the spec
unless they can properly handle the identity point.  They would have to
do another analysis to see whether this sort of non-compliance is itself
a security issue, but the answer would probably again be: not unless
an adversary can cause it to happen.

Cheers,
— Mike

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 16:18:33 +0000

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:

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

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

Cheers,
— Mike

---

From: Russ Housley <[email-masked]>
Date: Fri, 9 Apr 2021 12:25:15 -0400

Isn't the best solution to talk about this in the Security Considerations?  This gives ample opportunity to describe the likelihood of landing in a small subgroup, and what, if any, actions an implementor wants to take.

Russ

> On Apr 9, 2021, at 12:18 PM, Hao, Feng <Feng.Hao=[email-masked]> wrote:
> 
> Hi Loup and Mike,
>  
> 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.
> 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.
>  
> _______________________________________________
> CFRG mailing list
> [email-masked] <mailto:[email-masked]>
> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>

---

From: Richard Outerbridge <[email-masked]>
Date: Fri, 9 Apr 2021 12:46:15 -0400

This is annoyingly reminiscent of whether one should check for weak, semi-weak, and demi-semi-weak DES keys :)
__outer

> On 2021-04-09 (99), at 12:18:33, Hao, Feng <Feng.Hao=[email-masked]> wrote:
> 
> Hi Loup and Mike,
>

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 9 Apr 2021 13:59:30 -0300

Hello Feng,

> On Apr 9, 2021, at 1:18 PM, Hao, Feng <[email-masked]> wrote:
> 
> Hi Loup and Mike,
>  

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…

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

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 18:00:53 +0000

That’s certainly a convenient solution. However, a proper one would be to preclude small subgroup points by design. The real problem here is to ensure mapping to points in the “correct” group on an elliptic curve, not just any point. The current draft doesn’t solve that real problem (yet). I don’t think this is impossible to solve, but it needs some more efforts.

Cheers,
Feng

From: Russ Housley <[email-masked]>
Date: Friday, 9 April 2021 at 17:25
To: Hao, Feng <[email-masked]>
Cc: IRTF CFRG <[email-masked]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Isn't the best solution to talk about this in the Security Considerations?  This gives ample opportunity to describe the likelihood of landing in a small subgroup, and what, if any, actions an implementor wants to take.

Russ

On Apr 9, 2021, at 12:18 PM, Hao, Feng <Feng.Hao=[email-masked]<mailto:Feng.Hao=[email-masked]>> wrote:

Hi Loup and Mike,

Cheers,
Feng

Cheers,
— Mike
_______________________________________________
CFRG mailing list
[email-masked]<mailto:[email-masked]>
https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 9 Apr 2021 18:17:15 +0000

Opaque doesn’t use a hash-to-curve operation.

CPace does; it also automatically aborts (fails) if the hash-to-curve operation happens to return a low order point (that is, a point that, after multiplying by the cofactor, is the neutral element).

From: CFRG <[email-masked]> On Behalf Of Mike Hamburg
Sent: Friday, April 9, 2021 1:00 PM
To: Hao, Feng <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 9 Apr 2021 18:25:53 +0000

Correction: Opaque does use a hash-to-curve operation (used to translate the password into an elliptic curve point); if it happens to translate a specific password to a low order point, then that specific password is easy to test for; however there are no other implications…

From: CFRG <[email-masked]> On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Friday, April 9, 2021 2:17 PM
To: Mike Hamburg <[email-masked]>; Hao, Feng <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

From: CFRG <[email-masked]<mailto:[email-masked]>> On Behalf Of Mike Hamburg
Sent: Friday, April 9, 2021 1:00 PM
To: Hao, Feng <[email-masked]<mailto:[email-masked]>>
Cc: CFRG <[email-masked]<mailto:[email-masked]>>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

---

From: Rene Struik <[email-masked]>
Date: Fri, 9 Apr 2021 14:49:49 -0400

Hi Feng et al:

I think one should not bank on "rare" exceptions being rare, since 
history of cryptographic constructs is full of corner cases that can be 
exploited to pull the rug. Fortunately, it is not hard to design the 
curve mapping so as to avoid low-order points, by design -- at least 
when the co-factor h is small (in fact, I looked at this two years ago). 
Here, for this "single" map this can be done without a check of inputs 
or outputs and at very minor cost. For the "summation" map, this may 
require a simple (rare) output check.

I do think one should bear in mind that some of the mappings P( ) have a 
rich structure, e.g., with Montgomery curves and if mapping the pair of 
field elements (t1,t2):=(delta*u1^2, delta*u2^2), where delta is a fixed 
non-square element of GF(p), to R:=P(t1)+P(t2), this yields the identity 
element of the curve if delta*u1*u2=1 [1] or if u1+u2=0. Combining this 
with the hash function (u1,u2):=(H(m1),H(m2)), this condition occurs if 

delta*H(m1)*H(m2)=1 (mod p) or H(m1)+H(m2)=0 (mod p). While this is 
unlikely to occur if the hash function H can be modeled as a random 
functions and while m1 and m2 are derived from message m here, it would 
be hard to argue that practical instantiations of hash functions have 
been studied that well with these properties in mind. So, perhaps, one 
should look beyond modeling things abstractly as "ROM", here.

Two specific comments:
a) if delta above is a "free variable", one can trivially compute the 
pre-image t of a low-order point and realize delta*H(m)^2=t by picking 
delta after the fact. With the hash to curve draft, delta is called Z 
and is not required to be fixed, so this attack would indeed be possible.
b) as Mike Hamburg suggested, "hash to field is an essential element of 
hash to curve". It is somewhat odd that draft-irtf-cfrg-cpace-01 picks 
and chooses some elements of the constructions in 
draft-irtf-cfrg-hash-to-curve-10, where it picks another "hash to field" 
function and ignores the "multiplication by the co-factor" in the end. 
If the hash-to-curve draft were that practical, this deviation should 
not have been necessary. It occurs to me that harmonization potential 
should be further explored. {In my mind, the co-factor multiplication 
can be safely omitted, since could be added by an application that needs 
this. The other complexities seem due to squeezing in both extension 
field and prime field constructions in the same draft: are we sure it 
satisfies both use cases for password-based protocols and for pairings?}

Best regards, Rene

[1] this ignores rules to determine whether the output is a point or its 
inverse.

On 2021-04-09 12:59 p.m., Mike Hamburg wrote:
> Hello Feng,
>
>> On Apr 9, 2021, at 1:18 PM, Hao, Feng <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>> Hi Loup and Mike,
>>  1. 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.
>
>> 1.
>>
>>
>>  2. 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:
> **   (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),
> *   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
>
>
>
>
> [email-masked]

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 19:01:29 +0000

Hi Scott,

It’s not a simple case of testing and aborting. Suppose in a system, hash-to-curve returns a low-order point to the higher protocol (say CPace/OPAQUE) that is calling it, you can’t accept this value (insecure base generator) nor can you reject it (timing side channel will reveal the password). The failure mode here is non-recoverable.

Cheers,
Feng

From: Scott Fluhrer (sfluhrer) <[email-masked]>
Date: Friday, 9 April 2021 at 19:26
To: Scott Fluhrer (sfluhrer) <sfluhrer=[email-masked]>, Mike Hamburg <[email-masked]>, Hao, Feng <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: RE: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Correction: Opaque does use a hash-to-curve operation (used to translate the password into an elliptic curve point); if it happens to translate a specific password to a low order point, then that specific password is easy to test for; however there are no other implications…

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 9 Apr 2021 19:23:20 +0000

Is this a nontrivial concern?

Both CPace and Opaque are PAKEs; what that means is that if the attacker has a guess to the password, he can verify (or refute) that guess by performing a single exchange with the honest server.

So, if the user selects a password with 128 bits of minentropy (which is a far better password than what almost any human would use), that gives a 2^-128 failure probability against an attacker that tries just one exchange.  This probability is inherent in the system, and (other than asking users to use even better passwords), there isn't anything we can do about it.

In contrast, what it the probability of a hash-to-curve generating a low-order point?  If it is (say) 2^-252 (I don't know the exact probability; that is the approximate probability of a random Curve25519 point being a low order one), then that is far smaller than the inherent failure probability already in the system.

For PAKE uses of hash-to-curve, that wouldn't appear (IMHO) to be worth worrying about.  Of course, this logic need not apply to other uses of hash-to-curve...

From: Hao, Feng <[email-masked]>
Sent: Friday, April 9, 2021 3:01 PM
To: Scott Fluhrer (sfluhrer) <[email-masked]>; Scott Fluhrer (sfluhrer) <sfluhrer=[email-masked]>; Mike Hamburg <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Hi Scott,

It's not a simple case of testing and aborting. Suppose in a system, hash-to-curve returns a low-order point to the higher protocol (say CPace/OPAQUE) that is calling it, you can't accept this value (insecure base generator) nor can you reject it (timing side channel will reveal the password). The failure mode here is non-recoverable.

Cheers,
Feng

From: Scott Fluhrer (sfluhrer) <[email-masked]<mailto:[email-masked]>>
Date: Friday, 9 April 2021 at 19:26
To: Scott Fluhrer (sfluhrer) <sfluhrer=[email-masked]<mailto:sfluhrer=[email-masked]>>, Mike Hamburg <[email-masked]<mailto:[email-masked]>>, Hao, Feng <[email-masked]<mailto:[email-masked]>>
Cc: CFRG <[email-masked]<mailto:[email-masked]>>
Subject: RE: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Correction: Opaque does use a hash-to-curve operation (used to translate the password into an elliptic curve point); if it happens to translate a specific password to a low order point, then that specific password is easy to test for; however there are no other implications...

From: CFRG <[email-masked]<mailto:[email-masked]>> On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Friday, April 9, 2021 2:17 PM
To: Mike Hamburg <[email-masked]<mailto:[email-masked]>>; Hao, Feng <[email-masked]<mailto:[email-masked]>>
Cc: CFRG <[email-masked]<mailto:[email-masked]>>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Opaque doesn't use a hash-to-curve operation.

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.

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 20:09:01 +0000

Hi Scott,

Apologies if I didn’t make this clear. By the timing side channel, I mean an “offline” attack. The fact of rejecting/aborting (or delaying in responding) reveals that the password (maybe with some auxiliary public data) is hashed to a low-order point. Given that low-order points are rare, offline dictionary attacks to recover the password will be trivial.

I’m not claiming this attack must be practical. So far it’s just theoretic analysis. I’m highlighting here the possibility that what the mapping functions returns may be a small subgroup and that can significantly mess up the security proofs/arguments (and cause real damage in practice if the attacker were able to directly influence the input to the map-to-curve function as Rene pointed out).

Cheers,
Feng

From: Scott Fluhrer (sfluhrer) <[email-masked]>
Date: Friday, 9 April 2021 at 20:23
To: Hao, Feng <[email-masked]>, Scott Fluhrer (sfluhrer) <sfluhrer=[email-masked]>, Mike Hamburg <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: RE: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Is this a nontrivial concern?

So, if the user selects a password with 128 bits of minentropy (which is a far better password than what almost any human would use), that gives a 2^-128 failure probability against an attacker that tries just one exchange.  This probability is inherent in the system, and (other than asking users to use even better passwords), there isn’t anything we can do about it.

In contrast, what it the probability of a hash-to-curve generating a low-order point?  If it is (say) 2^-252 (I don’t know the exact probability; that is the approximate probability of a random Curve25519 point being a low order one), then that is far smaller than the inherent failure probability already in the system.

For PAKE uses of hash-to-curve, that wouldn’t appear (IMHO) to be worth worrying about.  Of course, this logic need not apply to other uses of hash-to-curve…

Hi Scott,

Cheers,
Feng

---

From: [email-masked]
Date: Fri, 9 Apr 2021 16:59:26 -0400

Hello Feng,

Thanks for bringing this up. It's good to discuss this so that we are
all on the same page. Below I'll give one low-level answer, and then
a higher-level one.

"Hao, Feng" <Feng.Hao=[email-masked]> wrote:
> 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)?

The answer to this question is unquestionably yes---hash_to_field
must *always* be used before map_to_group in any construction that
purports to be a conforming hash-to-curve implementation.

The hash functions defined in the draft are very clearly defined
to require all steps. Skipping steps in a cryptographic construction
is generally a recipe for disaster, and this is no exception. The
hash-to-curve document does not make any security claims about
implementations that skip steps, nor (in my opinion) would it
be reasonable for CFRG to require that implementations that are
non-compliant somehow remain secure anyway (after all: what would
this even mean?).

Zooming out, the higher-level question seems to be: should the
hash-to-curve functions defined in the draft somehow be designed
never to return the identity point? The answer is no, they should
not be designed in that way---returning the identity point with
negligible probability is absolutely fine from a security point
of view, as Mike and others have already pointed out.

I will not rehash [ ack! no pun intended :) ] their arguments. Instead,
I'll ask an analogous question: should SHA-3 have been designed such
that the all-zeros string is never produced?

It seems clear that the answer here is no---and yet if we use SHA-3
in a Schnorr signature, we might very well worry that the all-zeros
string would break things rather badly! Indeed, if the verifier's
challenge (generated by hashing the prover's randomness and the
message) equals 0, the signer can "sign" for any public key. Even
worse, if the signer's initial randomness (which, in a deterministic
signature, is also generated by hashing) equals 0, the signature
reveals the signer's secret key!

In both of these cases, it seems pretty clear that the issue is not
in the hash function, but in the application's use of it. If one
is worried about SHA-3 returning zero in a Schnorr signature, perhaps
one adds a special check in the implementation (though I'd say this
is clearly unnecessary). Similarly, if one is worried about the
(negligible!) probability that hash-to-curve returns the identity
point, one would "fix" this in the calling application.

No such fix is necessary, however---again, for the reasons that Mike
and others have pointed out.

Regards,

-=rsw

---

From: Björn Haase <[email-masked]>
Date: Fri, 9 Apr 2021 23:07:49 +0200

Dear Hao,

>In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator.

>The implicit assumption is that the returned value from hash-to-curve must be a non-identity

>point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

>Has this issue been considered? Apologies if I missed any discussion on this before.

for CPace this has been considered in https://eprint.iacr.org/2021/114.pdf in the context of the proof for theorem 3.6 (and  correspondingly theorem 6.1, "Security of CPace with Map2Point") and become part of the (negligible) loss due to  the increased collision probability for the hash H_1.

So yes, for CPace this has been analyzed and quantified, and according to my assessment a corresponding approach will also apply for DH-OPRF-based constructions such as OPAQUE given that the map is "probabilistically invertible" according to the definition in https://eprint.iacr.org/2021/114.pdf  and that it is hard to find pre-images for the hash function used for the map-to-field operation (which is e.g. implied by modeling this as random oracle).

I don't identify the need of considering this aspect in the hash2curve level, but I agree that this should be covered by the security analysis of protocols that use the maps.

Yours,

Björn.

Gesendet: Freitag, 09. April 2021 um 15:44 Uhr

Von: "Hao, Feng" <Feng.Hao=[email-masked]>

An: "CFRG" <[email-masked]>

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

Hi all,

Cheers,

Feng

_______________________________________________ CFRG mailing list [email-masked] https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Hao, Feng" <[email-masked]>
Date: Fri, 9 Apr 2021 22:25:23 +0000

Dear Björn,

> for CPace this has been considered in https://eprint.iacr.org/2021/114.pdf in the context of the proof for theorem 3.6 (and  correspondingly theorem 6.1, "Security of CPace with Map2Point") and bec…

It's good to see this has been considered in your new paper. In your theorem 3.6, I wonder if the proof covers the cyclic groups in general or the specific groups on elliptic curves. As you may know, small subgroup confinement is a common issue for both MODP and EC groups. The practical effect for the former is far more severe than the latter since the size is larger, but the theoretical principle of the small subgroup confinement applies the same for both settings.

  *   I don't identify the need of considering this aspect in the hash2curve level, but I agree that this should be covered by the security analysis of protocols that use the maps.

So far hash2curve and CPace/OPQUE have been developed separately with the former being largely assumed as an idealized function. I think now is a good time to look at the integration of the two in a system context. With the current hash2curve draft, as long as map-to-curve returns a low-order point, the user’s password will be inevitably broken by offline dictionary attacks based on the side-channel information. There is nothing the protocol can do (rejecting the point gives away the exact side-channel information needed for offline dictionary attacks). However, one can argue that the chance of this “really bad event” happening is L/q where L is the size of the small sub-group. It’s too small to be of any concern over common elliptic curves, and we hope that never happens. I think this is a perfectly sensible argument from a practical point of view. From a theoretical point of view, the argument is not appealing or neat. Hence, my question is why the small subgroup points can’t be precluded from the map-to-curve function?

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 9 Apr 2021 21:06:38 -0300

> On Apr 9, 2021, at 7:25 PM, Hao, Feng 

Hello Feng,

Have you considered what happens in CPace if Alice’s SampleScalar() function returns 7?  I’m following the notation of https://eprint.iacr.org/2021/114.pdf <https://eprint.iacr.org/2021/114.pdf>. In this case, the password will be vulnerable to a dictionary attack: the key K will be 7*Y_b, which an attacker can quickly detect by checking whether

ISK == H2(sid || 7*Y_b || oc(Y_a, Y_b))

(If ISK is not available, then some hash or encryption with it surely will be.)

Then the adversary will know that G = Map2Point(H_1(sid || oc(P, P’) || pw)) = Y_a / 7, which enables an offline dictionary attack.

Of course, the same consideration applies to every other scalar Alice could sample: if an adversary looks for that event, which occurs with probability 1/p, then Alice will be hacked: her password will be subject to an offline dictionary attack, and her session key will also be compromised.  At first blush, to me anyway, this looks quite similar to what happens if hash_to_curve outputs the identity.  And there’s an independent chance of that happening once per connection, because the sid should be unique.

In other words, the security risk introduced by the point at infinity is on the same order as the most trivial other attack on the protocol.

Nor is the possibility of failure a meaningful concern in practice.  A 2^-256 probability is ridiculously small: it stacks up against events like "Alice and Bob fail to exchange keys because they both get struck by lightning simultaneously, while also being hit by meteors simultaneously”.

The only meaningful concern here is the much greater risk that someone would somehow screw up the failure detection code in a way that introduces an exploitable flaw.

On a more theoretical note, the hash_to_curve function aims to implement an object which has been studied in the literature, and which is used by several cryptosystems and protocols: for some serializable set S, a function S -> G which acts as closely as possible to a random oracle.  In particular, hash_to_curve is designed to be epsilon-indifferentiable from a random oracle with that signature, in the model that the underlying hash is a random oracle.

This is the standard object that has been studied, and which protocols are built around.  You are proposing that we change it to a negligibly different object.  I’m sympathetic to this, but ultimately it is similar to an argument that we should replace pi with tau := 2*pi in mathematical analysis.  It’s extra work for essentially no gain, it requires redoing work that’s been done and will work fine.  There just isn’t enough time in the day for this kind of thing.

Furthermore, while your proposal is arguably a tiny improvement for SPEKE / CPace, and perhaps even for OPAQUE, it’s also a negligible step backwards for PAK and its variants  (if I recall correctly), since their proof uses the uniformity of the hash-to-curve map.  The same likely holds for other systems.  And it complicates the definition and implementation of hash_to_curve.

So I would prefer that we stick here with something that’s been studied and which is already built.

Regards,
— Mike

---

From: "Hao, Feng" <[email-masked]>
Date: Sat, 10 Apr 2021 09:32:24 +0000

Hi Mike,

  *   Have you considered what happens in CPace if Alice’s SampleScalar() function returns 7?  I’m following the notation of https://eprint.iacr.org/2021/114.pdf. In this case, the password will be vulnerable to a dictionary attack: the key K will be 7*Y_b, which an attacker can quickly detect by checking whether

Rsw also gave a similar example of having all zeros for the hash. Let me clarify that we are not – and shouldn’t be - concerned with any of such cases since the values are uniformly distributed within their respective range.

What we are discussing here is structural analysis of a PAKE system with the hash-to-curve being included as a building block. What the map-to-curve function permits in the output is a class of special data structures that fall into a small subgroup. Therefore, it’s necessary to analyse the effect of this class of data to the overall PAKE system.  As I explained, as soon as map-to-curve returns a small subgroup point, it will instantly cause the password in CPace/OPAQUE (PAK as well) to be compromised by offline dictionary attacks. There is nothing you can do at the protocol level to save it.

  *   On a more theoretical note, the hash_to_curve function aims to implement an object which has been studied in the literature, and which is used by several cryptosystems and protocols: for some serializable set S, a function S -> G which acts as closely as possible to a random oracle.  In particular, hash_to_curve is designed to be epsilon-indifferentiable from a random oracle with that signature, in the model that the underlying hash is a random oracle.

Published papers on hash-to-curve define the problem in their own (general) context. This is the first time (I think) we discuss it in the specific context of a PAKE use case with concrete PAKE choices.

I think a major misconception here is that many people may think the use of clearing-the-co-factor step has resolved the small sub-group issue. But that is not true. The clear-the-co-factor step merely changes small subgroup points to infinity points. For the simplicity of discussion, we can remove this step without affecting our analysis at all.

On a theoretical note, be reminded that DDH only holds for non-identity elements in a designated prime-order group on an elliptic curve. When you have small subgroup elements mixed, DDH doesn’t hold. It’s a tiny difference in the group definition, but it can have a significant theoretical effect.

  *   Furthermore, while your proposal is arguably a tiny improvement for SPEKE / CPace, and perhaps even for OPAQUE, it’s also a negligible step backwards for PAK and its variants  (if I recall correctly), since their proof uses the uniformity of the hash-to-curve map.  The same likely holds for other systems.  And it complicates the definition and implementation of hash_to_curve.

About “uniformity”, I think we can try to be more precise: uniformity in what group? With the current map-to-curve functions, the uniformity of the output covers the whole curve, including small subgroup elements. It’s exactly the mixing up with such elements that complicates things.

  *   So I would prefer that we stick here with something that’s been studied and which is already built.

Suppose we keep the draft as it is and only add a note in the security consideration to explain this. What can we possibly say?

One might add a warning to say map-to-curve returns uniformly distributed points on the curve, including small subgroup points. The mapping to small subgroup points is theoretically possible, but statistically unlikely. We don’t know how to remove these points in constant time. However, we have applied co-factor-clearing to turn small subgroup points to infinity points. That doesn’t actually change anything though and we still don’t know how to remove the infinity points in constant time. Therefore, we leave it to the upper layer protocol to decide how to deal with the infinity points.

On the other hand, from the perspective of a higher layer protocol (say CPace, OPAQUE and PAK), it’s simply impossible to handle the exception. As soon as map-to-curve hits the small subgroup, the password in a PAKE system will be compromised. Therefore, the above warning is self-defeating and not meaningful.

Moving forward, I think the best solution is to preclude the small subgroup elements from the map-to-curve function by design. If this can’t be done, or people don’t want to spend efforts to change the current draft, one solution might be to say only the functions defined for certain elliptic curves where co-factor = 1 should be used for PAKE. However, that will significantly limit the usefulness of this draft for the PAKE use case.

---

From: Mike Hamburg <[email-masked]>
Date: Sat, 10 Apr 2021 11:52:11 -0300

> On Apr 10, 2021, at 6:32 AM, Hao, Feng <[email-masked]> wrote:
> 
> Hi Mike,
>  

Hi Feng,

hash_to_curve is (epsilon-close to) uniformly distributed within its range, which is the prime-order group of points on the curve, which is also the range specified by these schemes in the literature.

> As I explained, as soon as map-to-curve returns a small subgroup point, it will instantly cause the password in CPace/OPAQUE (PAK as well) to be compromised by offline dictionary attacks. There is nothing you can do at the protocol level to save it.

No, not PAK.  PAK uses the hash output as an additive blinding factor, so it ideally wants the value to be uniform in the group, non uniform among non-identity elements.  Of course, removing the identity won’t harm it, since again, that’s a negligible change.

> On a theoretical note, be reminded that DDH only holds for non-identity elements in a designated prime-order group on an elliptic curve. When you have small subgroup elements mixed, DDH doesn’t hol…

No, it’s pretty much the exact opposite of that.

DDH is usually written as distinguishing (G, aG, bG, abG) from (G, aG, bG, cG) where g is a generator and (a,b,c) are uniformly random mod the group order.  See eg http://theory.stanford.edu/~dabo/papers/DDH.pdf <http://theory.stanford.edu/~dabo/papers/DDH.pdf> (which uses exponential notation but is otherwise the same), though variants (such as c != ab) are sometimes used instead.  Here aG, bG and cG can be the identity.  In this formulation, G cannot be the identity: it’s defined as a generator.  But if it were the identity then the two distributions would be identical — they would each be 4 copies of the identity — so DDH would still hold.

DDH does not hold in a group with a small cofactor h.  The problem is not that you might choose a small-order element by chance, but that the attacker can project to the subgroup by multiplying everything by p.  Clearing the cofactor resolves this issue.  So removing that step does affect the analysis, at least if you’re assuming DDH.

> About “uniformity”, I think we can try to be more precise: uniformity in what group? With the current map-to-curve functions, the uniformity of the output covers the whole curve, including small su…

In many cases things are cleaner if indeed you achieve uniformity in a group, which is why hash_to_curve does this.  You are suggesting uniformity in G \ {0}, which is not a group.

> Suppose we keep the draft as it is and only add a note in the security consideration to explain this. What can we possibly say?

A negligible probability of the adversary getting your key is not a security consideration, as explained above.  The only security consideration is “don’t screw up the error handling”, or maybe a note to say why we aren’t worried about the identity.

> One might add a warning to say map-to-curve returns uniformly distributed points on the curve, including small subgroup points. The mapping to small subgroup points is theoretically possible, but statistically unlikely. We don’t know how to remove these points in constant time.

If you’re using my library, libdecaf, then you can use decaf_point_eq and decaf_point_cond_sel to remove the identity in constant time.  Similar functions are likely available in other libraries.

> Moving forward, I think the best solution is to preclude the small subgroup elements from the map-to-curve function by design. If this can’t be done, or people don’t want to spend efforts to change…

No, hash_to_curve on curves with cofactor = 1 can also return the identity point, because it adds two map_to_curve results together.  That case is arguably harder, because there are very simple complete addition laws for Edwards curves with cofactor 4, but the complete addition laws for Short Weierstrass curves with cofactor 1 are more complex.

Regards,
— Mike

---

From: [email-masked]
Date: Sat, 10 Apr 2021 11:12:54 -0400

Hello Feng,

"Hao, Feng" <Feng.Hao=[email-masked]> wrote:
> Rsw also gave a similar example of having all zeros for the hash.
> Let me clarify that we are not – and shouldn’t be - concerned with
> any of such cases since the values are uniformly distributed within
> their respective range.

Right. And the argument is precisely the same for hash-to-curve!

Let me be perfectly clear: the property that hash_to_curve gives
is that the output is a uniformly* distributed point in the (big)
prime-order subgroup of the target elliptic curve.

At the risk of seeming didactic (in which case, apologies): the
identity element is indeed an element of the target group G.

Put another way: fix a generator g of group G of prime order q. Then,
hash_to_curve returns g^r in G, for r sampled uniformly* at random
in 0 <= r < q. Under the assumption that discrete log is hard in G,
hash_to_curve does not reveal r. Under the preimage and collision
resistance of the underlying hash function, one cannot choose any
particular r or find two inputs that hash to the same r.

I hope this helps clarify the security properties, and why focus
on low-order points at intermediate steps of the computation is not
relevant to the security of hash_to_curve as specified.

* uniformly except for some statistical distance less than 2^-100.

Regards,

-=rsw

---

From: Rene Struik <[email-masked]>
Date: Sat, 10 Apr 2021 11:34:27 -0400

Hi "rsw":

As a general courtesy, may I suggest that all communications use 
people's real names and not some obscure acronym.

The CFRG is supposed to be a research forum, where people do not hide 
their identity. In fact, in my opinion, IETF should have no place for 
communications by "anonymous".

Rene

---

From: Hugo Krawczyk <[email-masked]>
Date: Sat, 10 Apr 2021 13:27:55 -0400

Feng, you say:

> On the other hand, from the perspective of a higher layer protocol (say
CPace, OPAQUE and PAK), it’s simply impossible to handle the exception. As
soon as map-to-curve hits the small subgroup, the password in a PAKE system
will be compromised. Therefore, the above warning is self-defeating and not
meaningful.

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.

(The same alarm should go off if it just happens in a run of any other
protocol.)

(*) Of course, you should first check that you really have a preimage of
the identity under the hash - the most probable event to produce such a
result is an implementation error.

Hugo

PS: When you have an analysis that assumes a uniform distribution and then
decide to deviate from it as a way to "enhance" the design, you may be
introducing subtle weaknesses. An historic example (irrelevant to the cases
we are discussing here but illustrating the principle) is Enigma's
avoidance  of encrypting letters to themselves - something Turing was fast
to exploit
https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties

---

From: Rene Struik <[email-masked]>
Date: Sat, 10 Apr 2021 13:51:45 -0400

Hi Hugo:

It would be of interest what the impact of a "broken" hash function in 
the hash to curve construction on the security of password based schemes 
would be. In the case of mappings that always yield a high-order point, 
the impact may not immediately be obvious, while with mappings that do 
not preclude low-order points this might show more readily, also to 
offline observers. This may be an interesting addition to security proof 
papers that now focus mostly on idealized functionality (such as random 
oracles).

As an aside, as I noted in my email of yesterday [1],  mappings that 
fix 
a particular image point for a specific input are trivial if the 
construction itself has "free variables" one could fix after the fact 
(e.g., pick delta such that delta*H("Hugo123")^2=t0), thereby yielding 
an immediate attack, irrespective of hash function functionality. See 
specific comment a) in [1].

All in all, it seems that guaranteeing that curve mappings would never 
yield low-order points seems prudent, esp. if it comes at roughly the 
same computational cost as ones that do not give those assurances.

Best regards, Rene

Ref: [1] 
https://mailarchive.ietf.org/arch/msg/cfrg/lAhuAaEBIgaxhf3Q81jOFjXQLz0/

On 2021-04-10 1:27 p.m., Hugo Krawczyk wrote:
> Feng, you say:
>
> > On the other hand, from the perspective of a higher layer protocol 
> (say CPace, OPAQUE and PAK), it’s simply impossible to handle the 
> exception. As soon as map-to-curve hits the small subgroup, the 
> password in a PAKE system will be compromised. Therefore, the above 
> warning is self-defeating and not meaningful.
>
> 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.
>
> (*) Of course, you should first check that you really have a preimage 
> of the identity under the hash - the most probable event to produce 
> such a result is an implementation error.
>
> Hugo
>
> PS: When you have an analysis that assumes a uniform distribution and 
> then decide to deviate from it as a way to "enhance" the design, you 
> may be introducing subtle weaknesses. An historic example (irrelevant 
> to the cases we are discussing here but illustrating the principle) is 
> Enigma's avoidance  of encrypting letters to themselves - something 
> Turing was fast to exploit
> <https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties>
>
> On Sat, Apr 10, 2021 at 11:13 AM <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     Hello Feng,
>
>     "Hao, Feng" <Feng.Hao=[email-masked]
>     <mailto:[email-masked]>> wrote:
>     <https://www.irtf.org/mailman/listinfo/cfrg>
>
>

---

From: Watson Ladd <[email-masked]>
Date: Sat, 10 Apr 2021 11:27:10 -0700

On Sat, Apr 10, 2021 at 10:52 AM Rene Struik <[email-masked]> wrote:
>
> Hi Hugo:
>
> It would be of interest what the impact of a "broken" hash function in the hash to curve construction on the security of password based schemes would be. In the case of mappings that always yield a high-order point, the impact may not immediately be obvious, while with mappings that do not preclude low-order points this might show more readily, also to offline observers. This may be an interesting addition to security proof papers that now focus mostly on idealized functionality (such as random oracles).
>
> As an aside, as I noted in my email of yesterday [1],  mappings that fix a particular image point for a specific input are trivial if the construction itself has "free variables" one could fix after the fact (e.g., pick delta such that delta*H("Hugo123")^2=t0), thereby yielding an immediate attack, irrespective of hash function functionality. See specific comment a) in [1].
>
> All in all, it seems that guaranteeing that curve mappings would never yield low-order points seems prudent, esp. if it comes at roughly the same computational cost as ones that do not give those assurances.

Good news: all the mappings we do provide that guarantee with the same
probability that we regard as negligible in cryptography.

Sincerely,
Watson

---

From: Mike Hamburg <[email-masked]>
Date: Sat, 10 Apr 2021 16:09:26 -0300

Hi Rene,

I’m not sure about specific PAKEs, but typically a password would be hashed through a salted KDF construction like Argon2 or PBKDF2, and some protocols include a nonce as well.  For honest users, this means that (unless the hash is truly terrible, i.e. fails to roughly preserve entropy) the identity will never be encountered, even if the hash or map-to-curve is subtly backdoored.

The argument breaks down if an active adversary can find a salt/nonce such that hash(pw, salt) maps to the identity point for many passwords pw.  This is unlikely to happen even if the hash is broken, because the salt is typically short.  But even so, I’m not sure this is unique to the identity element: at least if the client confirms first, then the adversary just needs to find a salt such that dlog(hash(pw1, salt), hash(pw2, salt)) is known — or better yet, such that dlog relations are known for a large set of passwords — in order to break SPEKE or CPace's security.

Again, I’m sympathetic to the idea that returning the identity complicates error handling.  At least for some protocols, we have to forbid sending it to keep the protocol contributive (or for other reasons), so the identity would cause an error, which might be the only possible error in some code paths.  We could instead specify a hash_to_curve that’s uniform over non-identity elements.  This could be achieved by eg computing (1 + (hash1 mod p-1)) * cofactor * map_to_curve(hash2), at least if you can keep low-order elements out of map_to_curve(h2).  If a low-order element is an image, you could use (1 + (hash1 mod p-1)) * cofactor * (map_to_curve(hash2) + Q), where Q is the precomputed lexicographically least point such that no low-order point is an image.

This is slower, but if you’re going to scalarmul again anyway, then you could fold the multiplies together so that the leading term costs basically nothing.  Or, since most protocols don’t actually need uniformity, just do the analysis and drop the leading term.

But I don’t think this is convincing.  The counterargument is: uniform maps to G are already analyzed, already implemented, simpler, and preferable in some cases (again, at least for PAK), and the security implications are pretty much negligible, and are likely to remain negligible even if the hash is broken.  So it’s just not worth re-doing at the map to curve level.  It’s easier to just say: if in your protocol you don’t want the identity to come out of hash_to_curve, then detect it and replace it with the generator.  Or again, drop uniformity and use cofactor * (map_to_curve + Q).

Cheers,
— Mike

> On Apr 10, 2021, at 2:51 PM, Rene Struik <[email-masked]> wrote:
> 
> Hi Hugo:
> 
> Ref: [1] https://mailarchive.ietf.org/arch/msg/cfrg/lAhuAaEBIgaxhf3Q81jOFjXQLz0/ <https://mailarchive.ietf.org/arch/msg/cfrg/lAhuAaEBIgaxhf3Q81jOFjXQLz0/>
> 
>> 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.
>> 
>> (The same alarm should go off if it just happens in a run of any other protocol.)
>> 
>> (*) Of course, you should first check that you really have a preimage of the identity under the hash - the most probable event to produce such a result is an implementation error.
>> 
>> Hugo
>> 
>> PS: When you have an analysis that assumes a uniform distribution and then decide to deviate from it as a way to "enhance" the design, you may be introducing subtle weaknesses. An historic example (irrelevant to the cases we are discussing here but illustrating the principle) is Enigma's avoidance  of encrypting letters to themselves - something Turing was fast to exploit
>> https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties <https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties>
>> 
>> On Sat, Apr 10, 2021 at 11:13 AM <[email-masked] <mailto:[email-masked]>> wrote:
>> Hello Feng,
>> 
>> "Hao, Feng" <Feng.Hao=[email-masked] <mailto:[email-masked]>> wrote:
> email: [email-masked] <mailto:[email-masked]> | Skype: rstruik

---

From: "Hao, Feng" <[email-masked]>
Date: Sat, 10 Apr 2021 19:20:07 +0000

*   hash_to_curve is (epsilon-close to) uniformly distributed within its range, which is the prime-order group of points on the curve, which is also the range specified by these schemes in the literature.
Please kindly note that I explicitly refer to map_to_curve, which can return low-order points. This function is followed by clearing-the-co-factor step, but as explained this step does no help to resolve the real issue.

  *   No, not PAK.  PAK uses the hash output as an additive blinding factor, so it ideally wants the value to be uniform in the group, non uniform among non-identity elements.  Of course, removing the identity won’t harm it, since again, that’s a negligible change.
Please See Figure 1 on p. 11 in [1]. PAK uses the result from H1 as a base generator before being raised to the power of r. The follows the same idea as SPEKE.

  *   No, it’s pretty much the exact opposite of that.

  *   DDH is usually written as distinguishing (G, aG, bG, abG) from (G, aG, bG, cG) where g is a generator and (a,b,c) are uniformly random mod the group order.  See eg http://theory.stanford.edu/~dabo/papers/DDH.pdf (which uses exponential notation but is otherwise the same), though variants (such as c != ab) are sometimes used instead.  Here aG, bG and cG can be the identity.  In this formulation, G cannot be the identity: it’s defined as a generator.  But if it were the identity then the two distributions would be identical — they would each be 4 copies of the identity — so DDH would still hold.
Sorry, that can’t be right. if you want uniform distribution of values in Gq, the items in DDH can’t be identity elements. They should have the prime order q. Please see the explicit definition of Decision Diffie-Hellman (Problem 6.4 in Section 6.7.3) In Stinson’s book [2]. The definition in Stinson’s book makes perfect sense to me, and matches what I observe by experiments (just try toy examples yourself, and see actual distributions of values).

  *   If you’re using my library, libdecaf, then you can use decaf_point_eq and decaf_point_cond_sel to remove the identity in constant time.  Similar functions are likely available in other libraries.
That’s interesting. Why not integrate it into the hash-to-curve draft?

  *   No, hash_to_curve on curves with cofactor = 1 can also return the identity point, because it adds two map_to_curve results together.  That case is arguably harder, because there are very simple complete addition laws for Edwards curves with cofactor 4, but the complete addition laws for Short Weierstrass curves with cofactor 1 are more complex.
Yes, you’re right. I was thinking of the Icart’s method and SWU. But if you add two results, then it’s possible to give an identity. My point is that it’s possible to remove the identity and low-order points by design (easier if you work with co-factor =1 and a bit harder for co-factor > 1).

[1] https://eprint.iacr.org/2000/044.pdf
[2] Doug Stinson, “Cryptography: theory and practice: third edition”, 2006.

---

From: "Hao, Feng" <[email-masked]>
Date: Sat, 10 Apr 2021 19:40:07 +0000

Hi rsw,

That current map-to-curve functions don’t preclude low-order points is a known fact, and acknowledged by the authors in their papers. This is also clear from the hash-to-curve draft.

What people have tried (so far) to address this issue is by using the clearing-the-co-factor trick. But as explained, this trick doesn’t do any help to address the small subgroup issue in the use case of PAKE. Here, we are talking about a theoretical flaw not a practical attack. The practical effect of this flaw varies according to the underlying groups – if it were in MODP, the effect will be very severe, but the effect has been vastly reduced on elliptic curve due to the size of the small subgroup being small. Ideally, these effects should be removed by design. The security of a protocol shouldn’t depend so much on the choices of the underlying groups.

Cheers,
Feng

From: [email-masked] <[email-masked]>
Date: Saturday, 10 April 2021 at 16:13
To: Hao, Feng <[email-masked]>, CFRG <[email-masked]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
Hello Feng,

Regards,

-=rsw

---

From: Rene Struik <[email-masked]>
Date: Sat, 10 Apr 2021 16:05:11 -0400

Hi Mike:

Arguments as to why something is implausible would not even be necessary 
if one could simply rule out specific corner cases by design. This is, 
to my understanding, the point Feng Hao tried to bring across (and a 
reason for me to weigh-in).

Rene
{heading back outside due to unseasonably warm weather of 22 oC right 
now in Toronto}

On 2021-04-10 3:09 p.m., Mike Hamburg wrote:
> Hi Rene,
>
> I’m not sure about specific PAKEs, but typically a password would be 
> hashed through a salted KDF construction like Argon2 or PBKDF2, and 
> some protocols include a nonce as well.  For honest users, this means 
> that (unless the hash is truly terrible, i.e. fails to roughly 
> preserve entropy) the identity will never be encountered, even if the 
> hash or map-to-curve is subtly backdoored.
>
> The argument breaks down if an active adversary can find a salt/nonce 
> such that hash(pw, salt) maps to the identity point for many passwords 
> pw.  This is unlikely to happen even if the hash is broken, because 
> the salt is typically short.  But even so, I’m not sure this is unique 
> to the identity element: at least if the client confirms first, then 
> the adversary just needs to find a salt such that dlog(hash(pw1, 
> salt), hash(pw2, salt)) is known — or better yet, such that dlog 
> relations are known for a large set of passwords — in order to break 
> SPEKE or CPace's security.
>
>
>
> Again, I’m sympathetic to the idea that returning the identity 
> complicates error handling.  At least for some protocols, we have to 
> forbid sending it to keep the protocol contributive (or for other 
> reasons), so the identity would cause an error, which might be the 
> only possible error in some code paths.  We could instead specify a 
> hash_to_curve that’s uniform over non-identity elements.  This could 
> be achieved by eg computing (1 + (hash1 mod p-1)) * cofactor * 
> map_to_curve(hash2), at least if you can keep low-order elements out 
> of map_to_curve(h2).  If a low-order element is an image, you could 
> use (1 + (hash1 mod p-1)) * cofactor * (map_to_curve(hash2) + Q), 
> where Q is the precomputed lexicographically least point such that no 
> low-order point is an image.
>
> This is slower, but if you’re going to scalarmul again anyway, then 
> you could fold the multiplies together so that the leading term costs 
> basically nothing.  Or, since most protocols don’t actually need 
> uniformity, just do the analysis and drop the leading term.
>
> But I don’t think this is convincing.  The counterargument 
is: uniform 
> maps to G are already analyzed, already implemented, simpler, and 
> preferable in some cases (again, at least for PAK), and the security 
> implications are pretty much negligible, and are likely to remain 
> negligible even if the hash is broken.  So it’s just not worth 
> re-doing at the map to curve level.  It’s easier to just say: if in 
> your protocol you don’t want the identity to come out of 
> hash_to_curve, then detect it and replace it with the generator.  Or 
> again, drop uniformity and use cofactor * (map_to_curve + Q).
>
> Cheers,
> — Mike
>
>> On Apr 10, 2021, at 2:51 PM, Rene Struik <[email-masked] 
>> <mailto:[email-masked]>> wrote:
>>
>> Hi Hugo:
>>
>> It would be of interest what the impact of a "broken" hash function 
>> in the hash to curve construction on the security of password based 
>> schemes would be. In the case of mappings that always yield a 
>> high-order point, the impact may not immediately be obvious, while 
>> with mappings that do not preclude low-order points this might show 
>> more readily, also to offline observers. This may be an interesting 
>> addition to security proof papers that now focus mostly on idealized 
>> functionality (such as random oracles).
>>
>> fix a particular image point for a specific input are trivial if the 
>> (e.g., pick delta such that delta*H("Hugo123")^2=t0), thereby 
>> yielding an immediate attack, irrespective of hash function 
>> functionality. See specific comment a) in [1].
>>
>> All in all, it seems that guaranteeing that curve mappings would 
>> never yield low-order points seems prudent, esp. if it comes at 
>> roughly the same computational cost as ones that do not give those 
>> assurances.
>>
>> Best regards, Rene
>>
>> Ref: [1] 
>>> 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.
>>>
>>> (*) Of course, you should first check that you really have a 
>>> preimage of the identity under the hash - the most probable event to 
>>> produce such a result is an implementation error.
>>>
>>> Hugo
>>>
>>> PS: When you have an analysis that assumes a uniform distribution 
>>> and then decide to deviate from it as a way to "enhance" the design, 
>>> you may be introducing subtle weaknesses. An historic example 
>>> (irrelevant to the cases we are discussing here but illustrating the 
>>> principle) is Enigma's avoidance  of encrypting letters to 
>>> themselves - something Turing was fast to exploit
>> email:[email-masked]  | Skype: rstruik

---

From: Mike Hamburg <[email-masked]>
Date: Sat, 10 Apr 2021 17:19:03 -0300

Hi Feng,

> On Apr 10, 2021, at 4:20 PM, Hao, Feng <[email-masked]> wrote:
> 
> Please kindly note that I explicitly refer to map_to_curve, which can return low-order points.

Ah, sorry, I thought we were still talking about hash_to_curve.

> Please See Figure 1 on p. 11 in [1]. PAK uses the result from H1 as a base generator before being raised to the power of r. The follows the same idea as SPEKE.

I was insufficiently precise.  I’d forgotten that PAK refers to several PAKE algorithms; I was thinking of some of the elliptic curve versions, such as PAK-EC from "More efficient password-authenticated key exchange" by Philip MacKenzie, CT-RSA 2001.  I re-proposed a variant of this protocol, not knowing that it had been done before, as "SPAKE2: Elligator Edition”.  This design is slightly slower than SPEKE, but it has a simpler security analysis than SPEKE.  It sends something very roughly of the form aG + hash_to_curve(password), so you want hash_to_curve to be uniform.  Security follows by a very simple argument (compared to most other PAKEs) under ROM + strong DH.

> Sorry, that can’t be right. if you want uniform distribution of values in Gq, the items in DDH can’t be identity elements.

The DDH assumption is that those two distributions are hard to distinguish, not that they’re uniform.  And it is indeed hard to distinguish (Id, Id, Id, Id) from (Id, Id, Id, Id).

> They should have the prime order q. Please see the explicit definition of Decision Diffie-Hellman (Problem 6.4 in Section 6.7.3) In Stinson’s book [2].

I don’t have this book.  Is Stinson's definition different from Boneh’s?

Even if you ask for it to be hard to distinguish (G, aG, bG, abG) from (random, random, random, random), this is still hard if G is a uniformly random element of the group, because with overwhelming probability G will not actually be the identity.
> That’s interesting. Why not integrate it into the hash-to-curve draft?

Because, as I have been arguing, it’s not necessary and is only negligibly useful.  I guess it could be a note or security consideration?

> What people have tried (so far) to address this issue is by using the clearing-the-co-factor trick. But as explained, this trick doesn’t do any help to address the small subgroup issue in the use c…

But as I have already explained, clearing the cofactor isn’t to get rid of low-order points.  It would be required even if the hash cannot return low-order points.  The problem also isn’t more severe for Fp* groups, so long as there is a large prime-order subgroup (and if not, the scheme is insecure anyway, because discrete log is easy).

Regards,
— Mike

---

From: Mike Hamburg <[email-masked]>
Date: Sat, 10 Apr 2021 17:20:50 -0300

Hi Rene,

But again, there is an attack if the adversary can find hash outputs of known dlog, even if that dlog isn’t 0.

Have a nice outing,
— Mike

> On Apr 10, 2021, at 5:05 PM, Rene Struik <[email-masked]> wrote:
> 
> Hi Mike:
> 
> Arguments as to why something is implausible would not even be necessary if one could simply rule out specific corner cases by design. This is, to my understanding, the point Feng Hao tried to bring across (and a reason for me to weigh-in).
> 
> Rene
> {heading back outside due to unseasonably warm weather of 22 oC right now in Toronto}
> 
>>> On Apr 10, 2021, at 2:51 PM, Rene Struik <[email-masked] <mailto:[email-masked]>> wrote:
>>> 
>>> Hi Hugo:
>>>

---

From: Mike Hamburg <[email-masked]>
Date: Sat, 10 Apr 2021 17:22:48 -0300

> On Apr 10, 2021, at 5:19 PM, Mike Hamburg <[email-masked]> wrote:
> 

Replying to myself here, because I forgot to mention: as in most other uses of hash/map to curve, PAK-EC is provably secure even for somewhat nonuniform outputs, such as map_to_curve outputs.  It’s just most secure with uniform outputs.

Regards,
— Mike

---

From: "Hao, Feng" <[email-masked]>
Date: Sat, 10 Apr 2021 20:37:15 +0000

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?

---

From: Watson Ladd <[email-masked]>
Date: Sat, 10 Apr 2021 14:20:01 -0700

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

What is the probability that the map to curve output is the identity?

Sincerely,
Watson

-- 
Astra mortemque praestare gradatim

---

From: [email-masked]
Date: Sat, 10 Apr 2021 17:56:40 -0400

Hello Feng,

"Hao, Feng" <[email-masked]> wrote:
> That current map-to-curve functions don’t preclude low-order points
> is a known fact, and acknowledged by the authors in their papers.

The function that is being standardized is hash_to_curve, which has
the properties I listed in my prior email. Conforming implementations
of the hash-to-curve draft do not have the issue you have raised
in this thread, period, because no conforming implementation uses
one of the deterministic maps in a standalone way.

Further discussion of whether the deterministic maps described in the
hash-to-curve draft do or do not return low-order points is not a good
use of time. Yes, they do. We all know that. But that is irrelevant,
because they should never be used on their own.

Regards,

-=rsw

---

From: Loup Vaillant-David <[email-masked]>
Date: Sun, 11 Apr 2021 00:04:07 +0200

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

Only if precluding those points is less risky than just hoping. And by
a very wide margin, it's not. We have to choose between two risks:

1. The map-to-curve generates the identity point. The probability of
   that occurring is less than 2^-250 at each trial. Realistically, the
   probability that it occurs even *once* in the foreseeable future is
   well below 2^-128. Those numbers aren't just very low, they are
   *impossibly* low. I would stake my life and that of my entire family
   for a penny with those odds, and still sleep soundly at night.

2. The preclusion introduces a critical bug. The probability of *that*
   occurring is far from negligible. We can lower it, but we're only
   human. We make mistakes. We write bugs. Heck, I've even recently
   been made aware of a bug in a formally verified system (not telling
   more for obvious reasons).

Ironically, I would perhaps *not* stake lives on the correctness of the
present email, despite what I said above. I'm infinitely more likely to
have made a mistake here than I am to flip 128 coins and having them
all come up heads.

The correct way to minimise risks in this case is to simplify specs and
code as much as we can. Adding a check, especially one that you cannot
test in a black box context, is infinitely riskier than gambling on 2^-
128 probability being close enough to "impossible".

Thus, precluding small subgroup points by design is a bad idea. Don't.

Loup.

---

From: "Riad S. Wahby" <[email-masked]>
Date: Sat, 10 Apr 2021 18:09:08 -0400

Hi Mike,

I'm really sorry for a pedantic email. I just want to head off
potential confusion:

Mike Hamburg <[email-masked]> wrote:
> Replying to myself here, because I forgot to mention: as in most
> other uses of hash/map to curve, PAK-EC is provably secure even
> for somewhat nonuniform outputs, such as map_to_curve outputs.
> It’s just most secure with uniform outputs.

The function you're referring to, which has a non-uniform output
distribution, is called encode_to_curve in the draft. As you say,
PAK-EC remains secure with encode_to_curve.

(I'm being pedantic here because there seems to be some confusion
in this thread over whether it is recommended to directly use one
of the deterministic maps as a hash function---which of course it
is not---and we use the term map_to_curve to mean those maps.)

Cheers,

-=rsw

---

From: "Filippo Valsorda" <[email-masked]>
Date: Sun, 11 Apr 2021 02:46:37 +0200

> communications by "anonymous".

I am not aware of any real name rules in IETF forums.

The field of cryptography has benefited greatly from the contributions of pseudonymous and anonymous people, so I see no reason why the *Crypto Forum Research Group* should exclude them.

---

From: Scott Arciszewski <[email-masked]>
Date: Sat, 10 Apr 2021 20:50:50 -0400

To add to this, there are a lot of people who are harmed by real name
policies.

https://geekfeminism.wikia.org/wiki/Who_is_harmed_by_a_%22Real_Names%22_policy%3F

We should be very cautious with implementing a policy that causes harm to
vulnerable populations.

On Sat, Apr 10, 2021, 8:47 PM Filippo Valsorda <[email-masked]>
wrote:

> 2021-04-10 17:34 GMT+02:00 Rene Struik <[email-masked]>:
>
> Hi "rsw":
>
> The field of cryptography has benefited greatly from the contributions of
> pseudonymous and anonymous people, so I see no reason why the *Crypto
> Forum Research Group* should exclude them.

---

From: Daniel Franke <[email-masked]>
Date: Sat, 10 Apr 2021 20:58:12 -0400

The right to pseudonymity is, in my view, something pretty fundamental to
the ethos of the IETF(/IRTF). I went searching through our BCPs for a
statement to this effect and was rather surprised that I didn't find one,
though there is certainly nothing to the contrary. This strikes me as an
oversight that should be corrected.

rsw, please continue to participate under whatever handle you think best
represents you.

---

From: Watson Ladd <[email-masked]>
Date: Sat, 10 Apr 2021 19:09:09 -0700

> people's real names and not some obscure acronym.

The custom of using login names to refer to people online is ancient
and venerable.

Sincerely,
Watson

---

From: Michael StJohns <[email-masked]>
Date: Sat, 10 Apr 2021 22:25:22 -0400

> The custom of using login names to refer to people online is ancient

The custom of using login names to refer to people online is also 
somewhat elitist.  The "in" people know who is referred to, the "out" 
people do not.

It took me all of about  a minute to find RSW's CV, and I'm glad he's 
amended his replies to include his name.  It gives me a better idea of 
his quals and whether or not I should discount 90% of what he is saying.

Unless there's a real reason to do so (e.g. fear of retribution, etc) , 
as the Rene said, it's courtesy to not make us guess who you are.   
Let's avoid making this yet another culture war please.

Mike

---

From: Henry de Valence <[email-masked]>
Date: Sat, 10 Apr 2021 20:27:48 -0700

> Let's avoid making this yet another culture war please.

Surely the best way to avoid starting a “culture war” — a fairly loaded way
to describe “conflict over shared norms” — would be to avoid trying to
impose new norms on others, as in the original mail:

> In fact, in my opinion, IETF should have no place for communications by
"anonymous".

Cheers,

hdevalence

---

From: Dan Harkins <[email-masked]>
Date: Sat, 10 Apr 2021 21:02:31 -0700

On 4/10/21 5:50 PM, Scott Arciszewski wrote:
> <https://geekfeminism.wikia.org/wiki/Who_is_harmed_by_a_%22Real_Names%22_policy%3F>

   I'm sorry, that is just ridiculous.

     "People whose names subject them to discrimination based on race, 
religion,
      cultural and/or socio-economic bias: for example, anyone named 
'Mohammed'"

Guess what the most popular given name in the world is? Yup, that's right.

No one is bullying anyone here. Please keep such political nonsense out
of this technical group.

> We should be very cautious with implementing a policy that causes harm 
> to vulnerable populations.

   Might I suggest those who are confused look at the editor list of the
I-D in question (specifically page 163) which belies any concerns about
"vulnerable populations" and anonymity.

   Dan.

> On Sat, Apr 10, 2021, 8:47 PM Filippo Valsorda <[email-masked] 
> <mailto:[email-masked]>> wrote:
>
>     The field of cryptography has benefited greatly from the
>     contributions of pseudonymous and anonymous people, so I see no
>     reason why the /Crypto Forum Research Group/ should exclude them.

-- 
"The object of life is not to be on the side of the majority, but to
escape finding oneself in the ranks of the insane." -- Marcus Aurelius

---

From: Hugo Krawczyk <[email-masked]>
Date: Sun, 11 Apr 2021 00:20:52 -0400

On Sat, Apr 10, 2021 at 4:37 PM Hao, Feng <[email-masked]> 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
>    - 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
> 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?
>
>
>
>
>

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 11 Apr 2021 04:43:36 +0000

Henry de Valence <[email-masked]> writes:

>in my opinion, IETF should have no place for communications  by "anonymous".

"I have a dream that my four little children will one day live in a nation
where they will not be judged by the color of their skin, or the name they use
on a mailing list, but by the content of their postings" (from a long-lost
draft of the speech).

I don't care if I'm getting email from the Queen of Sheba, as long as she has
something interesting to say about crypto.

Peter.

---

From: "Hao, Feng" <[email-masked]>
Date: Sun, 11 Apr 2021 10:36:58 +0000

*   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

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Sun, 11 Apr 2021 15:45:29 +0300

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=
[email-masked]>:

>
>    - I don't see any timing attack here. We are talking about a user that
>    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.
>
>
>
> 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
>
>

---

From: Björn Haase <[email-masked]>
Date: Sun, 11 Apr 2021 15:38:26 +0200

Dear Hao,

I would kindly request you in case that you actually really happen to question the security guarantees of the currently proposed CPace and OPAQUE designs as specified in the latest draft versions -- which does not actually happen to be the case after reading the last lengthy posts -- to clearly show up the aspects where the existing security analysis needs to be complemented/extended or corrected according to your assessment.

For CPace you find this analysis in https://eprint.iacr.org/2021/114 and this analysis covers all of: treatment of low-order points and identity elements produced by the map. I.e. both aspects that you seem to be concerned of have extensively been considered and the impact on the security bounds has been quantified.

Note that we explicitly spent the significant effort of incorporating all of the artifacts that could be generated by maps, hash2curve and encode2curve primitives in the above paper in tiny individual steps as to be able to facilitate review. IMO, it should be straight forward for you to pinpoint any aspect in the analysis that has not been correctly assessed in your opinion -- if there actually is any. This would also allow you to make more transparent at which point exactly you identify problems, a topic which is not clear to me even after reading your recent posts several times.

I think that structuring the discussion along the lines of the existing security analysis papers might help avoiding emotional discussion and might help to get things further in a more constructive way.

So far after reading all comments explicitly including yours I conclude that there happens to be consensus in that there is actually 1) neither a security problem with the current draft specifications for hash2curve nor 2) for OPAQUE and CPace regarding identity- and low-order points produced by the various maps, encode2curve constructions and hash2curve constructions as presented in the hash2curve draft.

Yours,

Björn.

P.S.: Please feel also free to contact me directly in order to speed-up discussions and resolve simple misunderstandings earlier. IMO this might also help for getting things further in a constructive way and could possibly avoid some unnecessary confusion of the other the readers on the list.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Sun, 11 Apr 2021 14:07:23 +0000

>    something interesting to say about crypto.

True. 

But if I notice that I "don't get" what the author seems to be saying, the amount of time and efforts I'm likely to spend trying to comprehend that post is directly proportional to the respect I already have for this author. So, Queen of Sheba's emails are much likelier to end up in a digital trashcan, than those from somebody "known". 

Just sayin'  ;-)

---

From: Soatok Dreamseeker <[email-masked]>
Date: Sun, 11 Apr 2021 10:09:25 -0400

> But if I notice that I "don't get" what the author seems to be saying, the amount of time and efforts I'm likely to spend trying to comprehend that post is directly proportional to the respect I al…

What if, instead of Sheba, it were Shiba?

#DogeCoin #ToTheMoon :^)

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 11 Apr 2021 11:19:25 -0300

> On Apr 11, 2021, at 7:36 AM, Hao, Feng <Feng.Hao=[email-masked]> wrote:

Hello Feng,

CPace and OPAQUE require prime-order groups.  Prime-order groups do not have small subgroups, other than {Id}.  CPace and OPAQUE make security assumptions on their groups, but those assumptions plausibly hold for DSA-style groups.

If you start with a uniformly random distribution on an abelian group G of order pq (where p,q are coprime) and then multiply by an appropriate factor (typically q) to get down to a subgroup H of order p, then you will have a uniformly random distribution on H.  The probability of hitting the identity in H is then 1/p, which must be negligible or else rho attacks break your scheme.  It doesn’t matter in the slightest whether q is large or small.

Or, to pull the analysis back to the full group G: the probability of landing in the small subgroup doesn’t depend on its absolute size q.  It depends on its size relative to G, which is q/(pq) = 1/p, i.e. it depends only on the size of the large group.

In sum, no, this isn’t a bigger effect for larger groups.  The only thing it really changes is the difficulty of tweaking the map before the homomorphism in order to guarantee that the identity can’t show up.  If the group is prime-order in the first place, your tweak only has to avoid one element.  But of course, if you tweak after the homomorphism, then you are only avoiding one element regardless.

Cheers,
— Mike

---

From: Daniel Franke <[email-masked]>
Date: Sun, 11 Apr 2021 10:38:23 -0400

On Sun, Apr 11, 2021 at 10:07 AM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

>
> But if I notice that I "don't get" what the author seems to be saying, the
> amount of time and efforts I'm likely to spend trying to comprehend that
> post is directly proportional to the respect I already have for this
> author. So, Queen of Sheba's emails are much likelier to end up in a
> digital trashcan, than those from somebody "known".
>

I think we can all agree that:

1. If you *want* people to link your contributions here to things you've
published under your legal name, then it is better to make this easy than
to make it difficult.
2. As a purely descriptive observation: having a pre-existing reputation
tends to influence how your writing is received.

One can acknowledge these things and still passionately reject the
assertion that "IETF should have no place for
communications by 'anonymous'".

---

From: Mike Hamburg <[email-masked]>
Date: Sun, 11 Apr 2021 11:59:07 -0300

> On Apr 11, 2021, at 11:19 AM, Mike Hamburg <[email-masked]> wrote:

Sorry for the spam: “large group” should read “large prime-order subgroup”. — Mike

---

From: Colin Perkins <[email-masked]>
Date: Sun, 11 Apr 2021 16:25:52 +0100

To the best of my knowledge, there is no requirement for participants in the IRTF to use their real names.

Participants do, however, agree to follow the intellectual property disclosure rules, and other requirements, of the Note Well. These require a certain amount of transparency.

There is some tension between these two points, but my understanding is that it is possible to participate in IRTF pseudonymously while complying with the Note Well.

Colin

> On 10 Apr 2021, at 16:34, Rene Struik <[email-masked]> wrote:
> 
> Hi "rsw":
> 
> As a general courtesy, may I suggest that all communications use people's real names and not some obscure acronym.
> 
> The CFRG is supposed to be a research forum, where people do not hide their identity. In fact, in my opinion, IETF should have no place for communications by "anonymous".
> 
> Rene
> 

-- 
Colin Perkins
https://csperkins.org/

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Sun, 11 Apr 2021 15:29:32 +0000

>   . . . my understanding is that it is possible to participate in IRTF pseudonymously while complying with the Note Well.

It sure is - just counterproductive in many cases.

    -- 
    Colin Perkins
    https://csperkins.org/

---

From: "Hao, Feng" <[email-masked]>
Date: Sun, 11 Apr 2021 18:59:09 +0000

Hi Mike,

Thanks for your comment. I think we can have a more meaningful discussion on this if CPace and OPAQUE were concretely defined in the DSA/Schnorr or other MODP groups. Both protocols assume a special hash function of hashing a password to an non-identity element (base generator) in a designated prime-order group in constant time. So far, they depend on the hash-to-curve draft to realize that function, which leaves it undefined for DSA/Schorr or other MODP groups. As we can see from the example of SPEKE and Dragonfly, doing that in an MODP group is also a non-trivial task. I think this is certainly possible to avoid or minimize the effect of small subgroups in MODP, e.g., SPEKE, which does this mapping but at the cost of very expensive exponentiations because of the use of a safe prime and very long exponents. However, I don’t want to speculate how CPace/OPAQUE will want to do this until they are actually defined in an MODP setting.

Cheers,
Feng

From: Mike Hamburg <[email-masked]>
Date: Sunday, 11 April 2021 at 15:59
To: Hao, Feng <[email-masked]>
Cc: CFRG <[email-masked]>, Hugo Krawczyk <[email-masked]>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

---

From: "Hao, Feng" <[email-masked]>
Date: Sun, 11 Apr 2021 20:12:51 +0000

Hi Bjorn,

  *   I think that structuring the discussion along the lines of the existing security analysis papers might help avoiding emotional discussion and might help to get things further in a more constructive way.

  *   So far after reading all comments explicitly including yours I conclude that there happens to be consensus in that there is actually 1) neither a security problem with the current draft specifications for hash2curve nor 2) for OPAQUE and CPace regarding identity- and low-order points produced by the various maps, encode2curve constructions and hash2curve constructions as presented in the hash2curve draft.

Thanks for your email. I actually don’t feel there is emotion in the discussions and there shouldn’t be. All of the arguments are technical, which I greatly appreciate. My goal is to clarify technical facts, not to debate opinions. People may have different opinions about facts; that’s totally fine and should be respected.

I hope the following gives a factual summary of this discussion to close this topic.

  *   I raised that the clear-co-factor step in the hash-to-curve draft doesn’t really address the small subgroup issue (thanks to Rene for confirming this). It only hides the issue under the carpet of “identity”. Therefore, there is a need to explicitly discuss what will happen if map-to-curve falls into a small subgroup.
  *   We discussed and established that when map-to-curve falls into a small subgroup, the user password in CPace/OPAQUE will be subject to offline dictionary attacks because of the timing side channel (the attack will work even if the user rejects/aborts).
  *   We established that with a correct implementation of hash-to-curve, the probability of falling into a small subgroup is L/q where L is the size of the small subgroup and q is the prime order of the subgroup. For the curves considered in the hash-to-curve draft, the probability is negligible, so there is no real concern for practical security.
  *   I asked for clarification on whether the small subgroup points can be removed from map-to-curve by design. The replies from the hash-to-curve authors indicated no: because 1) too much hassle; 2) not worth it for the negligible probability. I think the rationale is clear.
  *   Thus, the way forward as suggested by Russ and Stanislav is not to change the draft, but to add a note in security consideration to discuss the issues raised in the discussion, which may include 1) informing the reader that map-to-curve might return small subgroup points but at a negligible probability in the normal case; 2) making it very clear that the implementation of hash-to-curve must include all steps, in particular, skipping hash_to_field will cause serious security failure due to small subgroup attacks; 3) be careful with function creep, in particular, it must not be possible for the attacker to influence the input at map-to-curve; in that case, small subgroup attacks will again work trivially. I agree with Russ and Stanislav that adding a note is a good way forward.
  *   I learned from Loup and rsw (thanks!) that it is not that easy to remove small subgroup points with the current hash-to-curve design. This is very useful feedback which informs me and others as well an interesting research problem for future work. So far great work has been done on map-to-curve, but very little on removing the small subgroup points (the clearing the co-factor trick doesn’t really solve this issue).

Overall, this seems a constructive discussion to me. I thank all again for the replies and comments. I know some of my questions may look silly or not to your taste, but thanks for your patience and for bearing with me.

Cheers,
Feng

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Tue, 20 Apr 2021 11:51:49 +0300

Dear Daira,

As there haven't been any further replies from your side, it seems
reasonable to proceed with the draft taking into account Chris Wood's
comments about your considerations.

Regards,
Stanislav

On Thu, 1 Apr 2021 at 08:41, Stanislav V. Smyshlyaev <[email-masked]>
wrote:

> Dear Daira,
>
> The CFRG is close to moving the hash-to-curve draft forward (i.e., to the
> IRSG review phase) - it might happen in a couple of weeks.
> Could you please reply to Chris Wood's comments in the previous message in
> this thread?
>
> If there are no objections to his comments before the middle of April, the
> draft is expected to be moved forward in the current form – probably, after
> some small modifications to address possible concerns in Shepherd's review,
> but without any changes related to the optimization issue mentioned in your
> message.
>
> Regards,
> Stanislav
>
>
>
> On Thu, 18 Mar 2021 at 03:24, Christopher Wood <[email-masked]>
> wrote:
>
>> Hi Daira,
>>
>> Thanks for the feedback, and apologies for the delayed reply! Given the
>> maturity of this document and its state in the RG, I've two very high-level
>> responses:
>>
>> 1. Changing the sign bit breaks backwards compatibility. Absent more
>> support for this change, especially from those familiar with the challenges
>> in the current design, perhaps now is not the time. I note that future
>> ciphersuites could change the sign computation, should that be desired for
>> certain applications.
>> 2. I think the optimized, curve-specific algorithms in the appendix are
>> constant time as described, so it doesn't *seem* necessary to make any
>> substantial editorial changes to lift those to the main text. The mappings
>> in Section 6 are not intended to be translated directly into code. Instead,
>> each mapping points to a corresponding straight-line implementation in
>> Appendix F.
>>
>> I would love to hear from others who may have opinions on either of these
>> points, or on the particular suggestions below.
>>
>> Best,
>> Chris
>>
>> On Mon, Jan 4, 2021, at 5:40 AM, Daira Hopwood wrote:
>> > Hello,
>> >
>> > This is a response to the RG Last Call for
>> draft-irtf-cfrg-hash-to-curve-10.
>> >
>> > The current draft is based in large part on
>> > [WB2019](https://eprint.iacr.org/2019/403).
>> > However, it does not cover most of the optimizations described in that
>> > paper. This is understandable given that the paper is focussed on
>> > hashing to BLS12-381 G1 and G2, and does not explain in much detail how
>> > to apply these optimizations to other curves.
>> >
>> > In fact, *all* of the optimizations applied for BLS12-381 G1 in [WB2019]
>> > can be adapted to general short Weierstrass curves over an arbitrary
>> > prime field:
>> >
>> > * merging an inversion and square root in map_to_curve;
>> > * eliminating all remaining inversions by use of Jacobian coordinates
>> >
>> >    * in map_to_curve;
>> >    * in the addition, for the random oracle variant; and
>> >    * in the isogeny map, for curves with AB = 0.
>> >
>> > These are all compatible with a constant-time implementation; actually,
>> > they result in an algorithm that is naturally constant time. The
>> > unoptimized algorithm, on the other hand, entails a trade-off between
>> > constant-timeness and speed. That could tempt implementors to rely on
>> > arguments about inapplicability of timing attacks in their context,
>> > that may be incorrect, or may fail when code is reused in a different
>> > context.
>> >
>> > (Yes I have read section 10 of the ID. From experience, implementors
>> > are very likely to ignore even strong recommendations if they have a
>> > performance issue to solve and they believe, correctly or incorrectly,
>> > that they can get away with it for their application.)
>> >
>> > Probably all of the above is also true for curves over extension fields,
>> > but I haven't verified that.
>> >
>> > Recent developments in proof systems have made it more important to be
>> > able to efficiently hash to curves over F_p where p = 1 + m * 2^n for
>> > reasonably large n, say n ~= 32 (informally, "highly 2-adic" fields).
>> > This is effectively a requirement for fast polynomial arithmetic using
>> > FFTs. Some proof systems, such as
>> > [PLONK](https://eprint.iacr.org/2019/953) and its variants, depend
>> > fundamentally on the resulting multiplicative subgroup structure.
>> >
>> > My main concern is a lack of advice in the draft on how to apply the
>> > [WB2019] optimizations to such fields, which is not at all obvious.
>> > The paper only discusses the cases needed for BLS12-381 G1 (where
>> > p = 3 (mod 4)), and G2 (a quadratic extension field where
>> > p^2 = 9 (mod 16)).
>> > The [reference
>> > code](
>> https://github.com/cfrg/draft-irtf-cfrg-hash-to-curve/tree/master/poc)
>> > only has some of the optimizations for simplified SWU on fields where
>> > p = 3 (mod 4), p = 5 (mod 8), and p^2 = 9 (mod 16).
>> >
>> > It took me a couple of days to work out the detail of other cases.
>> > Therefore I think it is likely that the draft as it stands would lead
>> > to many sub-optimal implementations. Also, in my opinion optimization
>> > attempts will carry a great risk of introducing errors or
>> > incompatibilities in corner cases (including some that are
>> > exceptionally unlikely to be picked up in tests not focussed
>> > specifically on those cases), with the specification as it stands.
>> >
>> > The description in the current draft also obscures the extent of the
>> > performance advantage for the simplified SWU mapping, potentially
>> > leading practitioners to make sub-optimal choices in protocol design.
>> > By my estimates, an optimized constant-time simplified SWU
>> > implementation can be at least 3 times faster than a constant-time
>> > SW implementation. Some of the same optimization ideas could in
>> > principle be applied to SW, but some cannot.
>> >
>> > ----
>> >
>> > All of the following assumes that F is a prime field. Again, it is
>> > likely to be easily adaptable to extension fields but I haven't
>> > checked it for that case.
>> >
>> > In order to obtain the speed-ups discussed above for arbitrary prime
>> > fields, it's first necessary to change the interface to the square
>> > root algorithm. We need an algorithm, that I'll call divsqrt, with
>> > the following specification.
>> >
>> > Let h be a fixed nonsquare in F.
>> >
>> >    divsqrt(N: F, D: F \ {0}) -> (F, Bool):
>> >        if N/D is square in F, return (sqrt(N/D), true)
>> >        else return (sqrt(h * N/D), false).
>> >
>> > where sqrt returns an arbitrary choice of square root.
>> >
>> > It's possible to implement this specification in constant time
>> > without computing two square roots or any explicit inversion. For
>> > example this can be done using an adaptation of the algorithm in
>> > [Sarkar2020](https://eprint.iacr.org/2020/1407), combined with
>> > [BDL+12](https://cr.yp.to/papers.html#ed25519) section 5, and some
>> > hints in [WB2019] section 4.2.
>> >
>> > A prototype specialized for n = 32 and the
>> > [Pallas/Vesta](
>> https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/)
>> > curves is at https://github.com/zcash/pasta/squareroottab.sage .
>> > I can provide an implementation that is not dependent on n if needed.
>> > Note that this is also more efficient than the commonly used
>> > Tonelli–Shanks, especially its constant-time variant.
>> >
>> > (That code does data-dependent look-ups, but could be modified to also
>> > be resistant to cache-based side channel attacks by using smaller
>> > tables and accessing all elements. [Sarkar2020] also has a variant
>> > that doesn't use tables, and is still significantly faster than the
>> > constant-time Tonelli–Shanks in Appendix I of the ID.)
>> >
>> > The overhead of handling the division in the square root, relative
>> > to a plain sqrt using a similar algorithm, is just over n squarings
>> > and log2(n) multiplications for F_p where p = 1 + m * 2^n. This is a
>> > substantial saving over a constant-time inversion, which would take
>> > around |p| squarings.
>> >
>> > Now given divsqrt, we can apply another optimization in section 4.2
>> > of [WB2019] that avoids needing to test whether gx1 (using the notation
>> > of the Internet Draft) is square. In brief: we first compute the
>> > numerators and denominators for x1 = N/D and gx1 = U/V as in the
>> > paper. If gx1 is not square, then we have sqrt(h * gx1); using a
>> > precomputed square root of Z/h, we can calculate the numerators and
>> > denominators of x2 and y2, without ever needing to calculate gx2.
>> > The detail is explained in comments at
>> > https://github.com/zcash/pasta/hashtocurve.sage .
>> >
>> > Note that the same procedure works for *all* short Weierstrass curves
>> > to which simplified SWU is applicable. Therefore IMHO (and this is
>> > the main point of this email), it may as well be included in the
>> > description of the basic algorithm rather than presented as an
>> > optimization — especially given that it is naturally constant time,
>> > and the currently presented algorithm isn't!
>> >
>> > As far as I can see, there are only three potential arguments for not
>> > making this change:
>> >
>> > * That divsqrt is more complicated than sqrt. This doesn't really
>> >    hold up, because it is just as easy to implement divsqrt naively
>> >    as it would be to implement the current map_to_curve naively.
>> >
>> > * That it's less obvious how this is derived from the original
>> >    algorithm of [BCI+10](https://eprint.iacr.org/2009/340). But the
>> >    current algorithm already diverges from that paper a little. What
>> >    matters IMHO is that the algorithm is correct and its derivation
>> >    is explained so that anyone with a mathematical background can
>> >    check it.
>> >
>> > * That it would make the map_to_curve dependent on Jacobian coordinates,
>> >    which might not be what an implementor wants to use in the rest of
>> >    their code. But it is straightforward to also say how to obtain the
>> >    output in homogeneous or affine coordinates.
>> >
>> > A naive constant-time implementation of a full hash_to_curve using the
>> > simplified SWU algorithm from the draft takes 1001S + 168M + 4I for
>> > the Pallas curve (a 255-bit non-pairing friendly curve with A = 0 and
>> > a degree-3 isogeny from the curve on which hashing is performed).
>> > With optimizations, it takes 577S + 150M and no inversions, if output
>> > is in Jacobian coordinates.
>> >
>> > Aside: the current draft prohibits Z = -1. It is unclear why, since
>> > that is exactly what [WB2019] uses for BLS12-381 G1.
>> >
>> > ----
>> >
>> > Another possible change I would suggest is in the method of choosing
>> > the sign of the y-coordinate. (Unlike the optimizations discussed
>> > above, this would actually change the map_to_curve function, and so
>> > would probably need to be optional.) The current method involves
>> > ensuring that the low bit of u (as named in the ID) is consistent
>> > with the low bit of y.
>> >
>> > This is fine if we're on a conventional processor where taking the
>> > low bit of a field element is cheap. However, it is unnecessarily
>> > inefficient in the setting of an arithmetic circuit. To take the low
>> > bit of a field element in that setting requires a full decomposition
>> > of the value, with cost O(|p|). In an R1CS-based proof system that
>> > requires one constraint per bit of p. In PLONK it requires one range
>> > check (e.g. implemented using
>> > [plookup](https://eprint.iacr.org/2020/315)) for each chunk of k bits
>> > where k is limited by the circuit size.
>> >
>> > Since it is very cheap to check a square root in an arithmetic circuit
>> > using nondeterminism, these bit decompositions become the major cost
>> > bottleneck of hash-to-curve in a circuit.
>> >
>> > The following modification halves this cost for for arithmetic circuits
>> > while not imposing significant overhead in other settings: simply
>> > require that sgn0(u - y) = 0. This is not the same as requiring that
>> > u and y have the same low bit, but it has a similar effect on the
>> > distribution of y.
>> >
>> > Either for this modification or for the existing algorithm, it would
>> > be desirable to have a proof that it suffices to use the low bit of u
>> > (rather than using an extra random bit independent of u), since this
>> > is not entirely obvious.
>> >
>> > ----
>> >
>> > I work for Electric Coin Company, but I'm not speaking for them here.
>> >
>> > None of the optimizations or changes discussed here are to my knowledge
>> > affected by, or likely to be affected by, patents or other IP issues.
>> >
>> > --
>> > Daira Hopwood
>> >

---

From: Daira Hopwood <[email-masked]>
Date: Fri, 23 Apr 2021 16:03:44 +0100

On 22/04/2021 17:44, Riad S. Wahby wrote:
> Hello Daira,
> 
> Thanks for the comments. They're very helpful! A few responses below.
> 
> By the way, in your original email (which I didn't respond to at the
> time---very sorry!), you ask why we preclude Z = -1 for SSWU. The
> reason is that this specific case appears to be covered by a patent.
> (This is true more generally of the Z selection code, which is
> slightly more complicated than would be necessary absent the patent.)
> We don't explain this in the document because IETF doesn't want
> discussion of IPR in the documents, as I understand it.
> 
> Daira Hopwood <[email-masked]> wrote:
>> This is not just an editorial comment. The implementations in the
>> appendix are indeed technically constant-time, but the map_to_curve
>> for SSWU, for example, uses a square root, a quadratic residue test
>> (which is essentially the same cost as a square root), and an inversion.
>> A good implementation should only require one square root and no
>> inversions, when producing an output point in projective, e.g.
>> Jacobian, form.
> 
> I think you're talking about the straight-line code in Appx. F, right?
> 
> You're obviously right that it's possible to do much better when
> working in projective coordinates. So maybe another way to state
> the objection is, there's no point including Appx. F (or maybe even
> what's in the body text) when everyone should just use code roughly
> like what's in Appx. G. Is that right?

As I already pointed out, the code in Appendix G only covers q = 3 (mod 
4), 5 (mod 8), and 9 (mod 16).

So no, I am not saying that people should use the code in Appendix G.
That code is wildly overcomplicated. I am saying that there is actually
no need to specialize map_to_curve for different fields.

I guess I will have to spell out the changes I'm suggesting:

* Add a section describing sqrt_ratio, with the following specification:

   Let h be some fixed nonsquare in Fq. Define sqrt_ratio for
   u ∊ Fq and v ∊ Fq* as:

     sqrt_ratio(u, v) = (true, sqrt(u/v)),    if u/v is square in Fq
                      = (false, sqrt(h*u/v)), otherwise.

   Include some explanatory text saying how to implement this naively,
   and how to implement it efficiently. (It's the same function described
   at https://ristretto.group/formulas/invsqrt.html , generalized to
   an arbitrary field, with v ≠ 0. A constant-time implementation has
   roughly the same cost as a full-width fixed-scalar multiplication.
   Square root algorithms like Tonelli-Shanks and [Sarkar2020] can be
   straightforwardly modified to sqrt(h*u/v) if u/v is not square with
   almost no additional cost, as I'm sure you know.

* Replace the algorithm in section 6.6.2 with the following, which is
   compatible with the existing specification:

   Let a and b be the parameters of the curve E/Fq : y^2 = x^3 + ax + b.
   Precompute θ = Z/h in Fq.

   Define map_to_curve(u) for u ∊ Fq as follows:

     Zuu = Z·u^2
     ta = Zuu^2 + Zuu
     x1n = b·(ta + 1)
     xd = a·CMOV(Z, -ta, ta == 0)
     U = (x1n^2 + a·xd^2)·x1n + b·xd^3
     x2_num = Zuu·x1_num
     (is_gx1_square, y1) = sqrt_ratio(U, xd^3)
     y2 = θ·Zuu·u·y1
     xn = CMOV(x2n, x1n, is_gx1_square)
     y' = CMOV(y2, y1, is_gx1_square)
     y = CMOV(-y, y, u mod 2 == y mod 2)
     return the point on E with affine coordinates (xn/xd, y).

   (Don't take my word that it is compatible; check it! See
   https://github.com/zcash/pasta/blob/master/hashtocurve.sage#L204-L293
   if needed.)

* Delete Appendix G.2 and references to it, and renumber.

* Replace Appendix F.2 with a straight-line implementation of the
   map_to_curve algorithm above (i.e. one that makes temporaries
   explicit).

Notice that:

- This algorithm doesn't explicitly require Jacobian coordinates. It's
   defined only in terms of field arithmetic, apart from the last step
   constructing the output point. I would expect implementors to use
   Jacobian coordinates, but other choices (including affine, at the
   cost of an inversion) are possible. A note about how to construct the
   point in Jacobian coordinates might be useful.

- If an implementor doesn't care about performance then a naive
   implementation of sqrt_ratio using constant-time Tonelli-Shanks is
   possible, with the same performance as the original algorithms.

I will also throw in my two-penneth on the issue of the hash returning
the zero point. Yes, it's an issue for some protocols, and in particular
it was an issue for our DiversifyHash function in Zcash. It is not good
practice to just ignore exceptional cases even when they occur with
negligible probability; for a start, it makes a protocol more difficult
to audit.

We got around this just by replacing the zero point with a different
precomputed point, which is an output of the hash on a input that
otherwise cannot occur:

   https://zips.z.cash/protocol/nu5.pdf#concretediversifyhash

(Note: this is *not* equivalent to just picking some arbitrary point.
It must be a point that we verifiably could not choose to collide with
some other output of the hash.) The replacement can easily be done in
constant time.

> Two concerns here. First, I would strongly prefer to keep the body
> text in terms of affine coordinates, to avoid mixing implementation
> detail with high-level description. Moreover, if we did talk about
> projective coordinates throughout, we'd likely end up talking about
> different projective systems for different curve shapes, which would
> be confusing for many readers.

This is not an issue, as I explained above.

> Second, I'm not totally convinced that everyone who will use this
> document will want to use projective coordinates.

Also not an issue. They pay no complexity or other cost.

> (Perhaps, though, we should mention projective coordinates explicitly
> in forward-refs from Section 6 and Appx. F to Appx. G.)
> 
> Meanwhile, someone who wants a simple, straight-line function that's
> totally generic and doesn't have to be super fast is probably quite
> happy with what's presented in Appx. F. Isn't this a user we want
> to support, too?

We would be supporting them. The algorithm above is no more complicated
than what is currently in Appendix F.2 (and significantly less
complicated, while being no less efficient, than Appendix G).

> I guess we might worry about the middle case---a person who's trying
> to implement something that's fast, but doesn't know they need
> projective coordinates to do that and doesn't notice the very clear
> "look at Appendix G!" signposting.

If they have a 2-adic field, they can't use Appendix G. As I said,
2-adic fields are commonplace in applications using FFTs. They're not
"weird" or "ugly" (why would one even use such terms about a field?)

Besides, there is *no downside* to making the algorithm work efficiently
for 2-adic fields. None at all.

>> Furthermore, the algorithm for q = 9 (mod 16) is 70 steps, when
>> it can actually be written for *any* field in less than 20 steps.
> 
> Unless I'm missing something, this is only true if we take divsqrt()
> as a one-liner, no? In contrast, the 70-step algorithm essentially
> has divsqrt() inlined.

divsqrt (or sqrt_ratio) is a much simpler thing to test and optimize
if it's independent of map_to_curve. This is a real explanatory
improvement, not just "sweeping complexity under the rug".

> (And assuming we go this way, I'd certainly take you up on your
> offer of an implementation of divsqrt that works for general fields,
> if you're still willing to provide it!)

I can do that, but it's just implementing [Sarkar2020] and the hint
in [BDLSY2012] section 5 for the general case.

[WB2019]     https://eprint.iacr.org/2019/403
[Sarkar2020] https://eprint.iacr.org/2020/1407
[BDLSY2012]  https://ed25519.cr.yp.to/ed25519-20110705.pdf

-- 
Daira Hopwood

---

From: "Riad S. Wahby" <[email-masked]>
Date: Fri, 23 Apr 2021 15:30:36 -0400

Hello Daira,

Thanks for clarifying your feedback.

I remain concerned about mixing implementation detail with high-level
description. Here I am referring to using divsqrt in place of natural
field arithmetic operations (sqrt, inversion, etc.) in the body text.
Describing the algorithm independent of the implementation details is
a way of specifying the mathematical properties of the algorithm, and
having this specification explicit in the document has value, from my
perspective.

But as I said in my prior email, it seems like refactoring Appx. G to
use divsqrt and adding a few implementations of that function for the
relevant cases (3 mod 4, 5 mod 8, 9 mod 16, and general, perhaps?) is
a nice way of cleaning things up. And it seems like the same refactor
applied to SvdW and Elligator in Appx. G would help, too.

This isn't something I can do in the near term, but I'm very happy to
spend time on this once I've got some! I'm hopeful that's about three
weeks from now, but I've been called an optimist before.

Thanks again for the feedback and best regards,

-=rsw

---

From: Rene Struik <[email-masked]>
Date: Fri, 23 Apr 2021 16:47:09 -0400

Hi Riad:

Text along the following lines would avoid implementation detail, but 
would illustrate how one could "mix" inversions and square roots:

The inverses of two nonzero elements y1 and y2 of GF(q) can be computed 
by first computing the inverse z of y1*y2 and by subsequently computing 
y2*z=:1/y1 and y1*z=:1/y2.

This method can be used to compute the inverse and a square root, 
respectively, of two nonzero elements x and y of GF(q) (where y is a 
square in GF(q)) by first computing a square root z of 1/(y*x^2) and by 
subsequently computing a square root of y as x*y*z and the inverse of x 
as x*y*z^2.

I think this would be easier to read than any "div" verbiage and avoids 
having to deal with divisions by zero.

(In the case q = 3 (mod 4), if y is a nonzero element of GF(q) and 
z:=y^{(q-3)/4}, then y is a square in GF(q) only if y*z^2=1. One can 
generalize this to q = 5 (mod 8), q = 9 (mod 16), etc., where the 
general procedure is to compute z:=y^{(q-2^s-1)/2^{s+1}} in GF(q) where 

q:=2^s+1 (mod 2^{s+1}) and where y is a square in GF(q) only if 
(y*z^2)=w, where w^{2^{s-1}}=1. For s large, one gets Daira Hopwood's 

case with higher s, but the principle remains the same (and one could 
refer to a paper for computational tricks or simply declare this out of 
scope).)

Rene

---

From: Loup Vaillant-David <[email-masked]>
Date: Sat, 24 Apr 2021 00:20:01 +0200

Hello,

> applied to SvdW and Elligator in Appx. G would help, too.

It would help quite a bit.

When I implemented Elligator 2 last year, I tried to read earlier
versions of this draft, and failed. I ended up using the original
instead.

Problem is, the original paper's simple equations involve *two*
exponentiations, while an optimised explicit formula only needs one.
That's a 2x speed difference. But the complexity section G.3.1 is such
that we're easily tempted to just give up and suffer a slower mapping.

For instance: Libsodium. While usually optimised to the brim, it chose
the simpler, slower formula. (It was first added in 2017, before this
draft even existed, but subsequent updates didn't address this.)

Compare the current section G.3.1 with an explicit formula that uses
invsqrt (Taken from my Python code, first gifted by Andrew Moon):

  ufactor = -non_square * sqrtm1
  vfactor = sqrt(ufactor)

  def fast_map_to_curve(r):
    t1 = r**2
    t1 = t1 * non_square
    u  = t1 + fe(1)
    t2 = u**2
    t3 = A**2
    t3 = t3 * t1
    t3 = t3 - t2
    t3 = t3 * A
    t1 = t2 * u
    t1, is_square = invsqrt(t3 * t1)
    u  = r**2
    u  = u * ufactor
    v  = r * vfactor
    if is_square: u = fe(1)
    if is_square: v = fe(1)
    v  = v * t3
    v  = v * t1
    t1 = t1**2
    u  = u * -A
    u  = u * t3
    u  = u * t2
    u  = u * t1
    if is_square != v.is_negative():
        v = -v
    return (u, v)

Quite a bit shorter, and needs fewer variables.

Personally, I'm looking forward to that refactoring. It has the
potential to make implementers' lives significantly easier.

Loup.