Incorrect (non canonical) representative output for ScalarBaseMult()

[LoupVaillant]

Hi,

I learned of this bug was found by @tankf33der. Contrary to the original paper, the Elligator 2 representative of of a public key is not always canonical. That is, this library does not make sure the output stay between 0 and (p-1)/2 (that is, 2²⁵⁴-10).

The mapping is such that for each point on the curve we can map, two representative (r1 and r2) map to that point on the curve, and those points are such that r1+r2=(2²⁵⁵-19). Which means one of them is in [0, 2²⁵⁴-11], and the other is in [2²⁵⁴-10, 2²⁵⁵-18]. We are supposed to chose the smaller of the two. If we don't, there is no guarantee the distribution of canonical and non-canonical output will be even. And if it's not, we'll introduce exactly the kind of bias Elligator was meant to eliminate, and basically ruin everything.

The problem can be reproduced with this code:

package main
import "fmt"
import "github.com/agl/ed25519/extra25519"

func main() {
    var pub, rep, prv [32]byte
    extra25519.ScalarBaseMult(&pub, &rep, &prv)
    fmt.Println("prv", prv)
    fmt.Println("pub", pub)
    fmt.Println("rep", rep)
}

We get this output:

prv [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
pub [47 229 125 163 71 205 98 67 21 40 218 172 95 187 41 7 48 255 246 132 175 196 207 194 237 144 153 95 88 203 59 116]
rep [57 78 64 213 212 109 157 152 11 141 41 37 247 235 7 83 93 151 203 254 156 94 163 90 91 71 179 230 39 79 78 120]

What we are most interested in is the most significant byte of rep, whose value, 120, exceeds 63. Which means the representative as a whole exceeds 2²⁵⁴, and is therefore not canonical. The test suite doesn't spot the error because the round trip works: as I've said two representatives map to the same point, r and p-r.

Pull request #12, which by the way is over 5 years old, aims to fix the issue (I haven't tested). I encourage desperate users to try and merge it on their own.

[agl]

Thank you for pointing that out. As you've probably noticed, I'm no longer active in Go crypto (Filippo replaces and improves upon me) and I shouldn't leave ignored repos like this hanging around if I'm not going to be reading PRs etc.

Thus I've replaced this repo with a pointer to the x/crypto version of Ed25519. It doesn't contain everything but hopefully what it does contain actually works!

[LoupVaillant]

That works for me, thank you! (And by the way, your blog post on the subject helped me a lot.)