curve25519-dalek
curve25519-dalek copied to clipboard
dalek-cryptography
Batch double-and-compress (on ristretto255) fails on the identity point
RistrettoPoint::double_and_compress_batch() may fail if one of the input points is the Ristretto identity. The function computes, for each input point, the values e, f, g, and h (in a BatchCompressState structure) then inverts the product of all four values. All the inversions are performed in a call to FieldElement::batch_invert(). However, that function does not tolerate zeros as input; there is even an explicit assert!() to verify that all inputs are non-zero.
Values e and f can be zero for some points which all represent the Ristretto identity (namely, when the representative element is, on the twisted Edwards curve, a point of order 1, 2 or 8). In particular, you get that situation by using the point returned by RistrettoPoint::identity(). In that case, the corresponding input to batch_invert() is zero, and the assertion fails, which triggers a panic.
To fix this issue, it suffices to make batch_invert() tolerate zeros, returning zero as an "inverse" of itself (while zero is not formally invertible, returning zero as its own inverse works with the double-and-compress formulas). This can be done by "skipping" zeros (in a constant-time way, of course) in both passes of the batch invert function.
