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

["Hao, Feng" <[e-mail]>]

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) <[e-mail]>
Date: Friday, 9 April 2021 at 20:23
To: Hao, Feng <[e-mail]>, Scott Fluhrer (sfluhrer) <sfluhrer=[e-mail]>, Mike Hamburg <[e-mail]>
Cc: CFRG <[e-mail]>
Subject: RE: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
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 <[e-mail]>
Sent: Friday, April 9, 2021 3:01 PM
To: Scott Fluhrer (sfluhrer) <[e-mail]>; Scott Fluhrer (sfluhrer) <sfluhrer=[e-mail]>; Mike Hamburg <[e-mail]>
Cc: CFRG <[e-mail]>
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) <[e-mail]<mailto:[e-mail]>>
Date: Friday, 9 April 2021 at 19:26
To: Scott Fluhrer (sfluhrer) <sfluhrer=[e-mail]<mailto:sfluhrer=[e-mail]>>, Mike Hamburg <[e-mail]<mailto:[e-mail]>>, Hao, Feng <[e-mail]<mailto:[e-mail]>>
Cc: CFRG <[e-mail]<mailto:[e-mail]>>
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 <[e-mail]<mailto:[e-mail]>> On Behalf Of Scott Fluhrer (sfluhrer)
Sent: Friday, April 9, 2021 2:17 PM
To: Mike Hamburg <[e-mail]<mailto:[e-mail]>>; Hao, Feng <[e-mail]<mailto:[e-mail]>>
Cc: CFRG <[e-mail]<mailto:[e-mail]>>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

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 <[e-mail]<mailto:[e-mail]>> On Behalf Of Mike Hamburg
Sent: Friday, April 9, 2021 1:00 PM
To: Hao, Feng <[e-mail]<mailto:[e-mail]>>
Cc: CFRG <[e-mail]<mailto:[e-mail]>>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

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.