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

[Mike Hamburg <[e-mail]>]

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 <[e-mail]> 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.
> 
> Best regards, Rene
> 
> Ref: [1] https://mailarchive.ietf.org/arch/msg/cfrg/lAhuAaEBIgaxhf3Q81jOFjXQLz0/ <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.
>> 
>> 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 <[e-mail] <mailto:[e-mail]>> wrote:
>> Hello Feng,
>> 
>> "Hao, Feng" <Feng.Hao=[e-mail] <mailto:[e-mail]>> 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
>> 
>> _______________________________________________
>> CFRG mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
>> 
>> 
>> _______________________________________________
>> CFRG mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/cfrg <https://www.irtf.org/mailman/listinfo/cfrg>
> 
> -- 
> email: [e-mail] <mailto:[e-mail]> | Skype: rstruik
> cell: [phone] | US: [phone]
> _______________________________________________
> CFRG mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg