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

[Rene Struik <[e-mail]>]

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 <[e-mail] 
>> <mailto:[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/
>>
>> 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]
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>> -- 
>> email:[e-mail]  | Skype: rstruik
>> cell: [phone] | US: [phone]
>> _______________________________________________
>> CFRG mailing list
>> [e-mail] <mailto:[e-mail]>
>> https://www.irtf.org/mailman/listinfo/cfrg
>

-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]