Random point has known discrete log (under some conditions)

[lleoha]

This one is subtle.

By taking a look at the random point implementation:

    fn random(mut rng: impl RngCore) -> Self {
        Self::GENERATOR * Scalar::random(&mut rng)
    }

This is technically correct (it is uniform). One potential problem I have with this that knowing the state of PRNG the caller would know the discrete log of the point and this is also technically fine, but taking into account the context and how this crate can be used it is easy to make a mistake to use this function to create a point nobody is supposed to know dlog of. Imagine the case where some PRNG is seeded with transcript state (I know, far stretched but still). Another argument would be that many academia papers when just say "sample a random point" they usually meant a point you're not supposed to know dlog of (otherwise they state explicitly to sample scalar s, and do G * s). It is easy to make a mistake if the implementor is not fully aware or blindly follows what the paper says. I am aware that it is easy to work around and use map to curve or hash to curve on randomly generated data.

Not sure what would be the proposed solution but at least document the proper use cases for it would be nice if changing the implementation itself is too much.

[tarcieri]

Are you asking about k256 specifically? It's unclear which fn random that's supposed to be, but that appears to be the only one that matches that code at first glance.

Using hash2curve for k256 should be fine, but for something like primeorder it might be problematic to require hash2curve for the generic implementation. I'd need to investigate more.

[lleoha]

Yes, sorry I only checked k256 and assumed others would do the same, my bad. So let's assume I am talking about k256 specifically.

[randombit]

For random points you can also do hunt-and-peck style approach where you generate a random x coordinate plus a random sign of y, attempt point decompression, if it succeeds return (x,y) otherwise sample again.

This type approach is not good for PAKEs, where the number of loop iterations depends on a low entropy secret. But I'm pretty sure such a PAKE would also be broken with the current implementation, since most PAKEs security arguments depend on the generated point not having a known dlog.

[tarcieri]

Yes, we could do rejection sampling

[daxpedda]

Using hash2curve for k256 should be fine, but for something like primeorder it might be problematic to require hash2curve for the generic implementation. I'd need to investigate more.

We could use MapToCurve directly without hashing. It would still make hash2curve a mandatory dependency for but I don't think that's an issue.

In the meantime I made #1344 to switch to rejection sampling for now.