Point.Equal can return 1 with any other point in some special case

[adr1anh]

Before #12, the point returned by ScalarMult would be invalid if the receiver was set beforehand to a point different from the identity.

The actual point was set to the following:

fe := fieldElement{
  l0: 2251799813685229,
  l1: 2251799813685247,
  l2: 2251799813685247,
  l3: 2251799813685247,
  l4: 2251799813685247,
}

p := Point{
  x: fe,
  y: fe,
  z: fe,
  y: fe,
}

This point is definitely invalid. The representation returned by Bytes() is a slice of zeros. Unfortunately, for any Point q, p.Equal(q) will always return 1.

If some other issue would present itself in the future where such a point is returned, that would be quite bad. Perhaps some extra checks could be introduced in checkInitialized

Appendix

Here is a test function that should detect this behavior.

func TestPointEqualityWithInvalidPoint(t *testing.T) {
    pointEqualityWithInvalidPoint := func(x Scalar) bool {
        var p, q Point
        var fe fieldElement

        fe.l0 = 2251799813685229
        fe.l1 = 2251799813685247
        fe.l2 = 2251799813685247
        fe.l3 = 2251799813685247
        fe.l4 = 2251799813685247

        p.x = fe
        p.y = fe
        p.z = fe
        p.t = fe

        q.ScalarBaseMult(&x)
        return p.Equal(&q) != 1
    }

    if err := quick.Check(pointEqualityWithInvalidPoint, quickCheckConfig32); err != nil {
        t.Error(err)
    }
}

P.S. A panic occurs when I set pointEqualityWithInvalidPoint := func(q Point) bool. How would I modify this to get a random Point instead of computing it from a random Scalar?

[FiloSottile]

This only happens if the receiver was uninitialized, not if it was a valid point different from the identity.

https://play.golang.org/p/Q-eIy_C16Qr

The library relies on an invariant that points that are used internally are valid. Every entry point in the public API is guarded by checkUninitialized to make sure this holds. Here it broke down because the receiver is not supposed to be used, only overwritten, so it was not checked. In fact, it's expected that you can call ScalarMult with an uninitialized receiver. The first operation that the receiver is passed to is projP1xP1.Add, which is not a public API so doesn't have checkUninitialized guards.

By the time the point gets to Equal it's invalid and mangled to the point that we can't really try to catch that without an on curve check, which we'd have to put in every public function.

The bug was not overwriting the receiver, and I'll add systematic tests to make sure that doesn't happen again or elsewhere. I think everything else is working as intended.

[adr1anh]

Thank you for explaining this to me, it makes a lot of sense!

[FiloSottile]

Thank you for looking into it!

(This is also a very real shortcoming of Go, where unless you can make the zero value valid, you can't make invalid values unrepresentable, as @hdevalence points out from time to time.)