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

[Rene Struik <[e-mail]>]

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]