Question about prune in eddsa

[matthewdgreen]

Hi all,

I was looking at the implementation of EdDSA in BabyJubJub, specifically the generation of private/public keypairs. I notice you are using a "pruneBuffer" function to set the 3 LSB bits to "0" and to set the second-most-significant bit to "1". The use of this function seems to be inspired by processing from RFC 8032.

However, this approach does not seem to make sense for BabyJubJub. I notice three things in this code that confuse me.

1. First, EdDSA (as in RFC 8032) is using the base point of the entire curve with co-factor 8, which generates 8*order points. This is why they set the three LSB bits to 0. I may be confused here, but my understanding is that in this code you are using the base point "Base8", which does not generate all points on the curve -- instead it only generates a subgroup of prime order. So setting the three LSB bits to zero in this code does not immediately make sense to me.
2. You are setting the second-highest MSB bit to "1" in the private key scalar. I realize this is also done in RFC 8032, but I believe this is to protect against a specific old implementation flaw in a Montgomery implementations, and is not relevant or useful to this curve.
3. On top of this, I am concerned that there may be a minor bias introduced. Imagining that we skip the steps mentioned in (1) and (2), you are sampling a scalar s between {0, ..., 2^255 - 1} and then computing s * B, where B generates a group of prime order L. Here L is a prime with log2(L) = 250.59669135500214387862176939450353061902897749239721141062673528. Since s * B can be viewed as equivalent to (s mod L) * B, then the reduction modulo L causes some values (s mod L) to occur with slightly higher probability.

I don't think that any of this is practically exploitable, since these keys are not used for generating signature nonces. Nonetheless it seems like bad practice, if I am understanding the code correctly.

A proposed resolution would be to use a similar approach as you currently use for generating nonces in signature generation. This code generates a much larger bitstring and then computes a modular reduction mod L, with no "pruning" applied. That approach should thoroughly eliminate the bias mentioned above:

        const sBuff = this.pruneBuffer(createBlakeHash("blake512").update(Buffer.from(prv)).digest());
        let r = Scalar.mod(Scalar.fromRprLE(sBuff, 0, 64), this.babyJub.subOrder);
        const R8 = this.babyJub.mulPointEscalar(this.babyJub.Base8, r);