When using Ristretto or Decaf with Ed25519 and Ed448, do scalars still need pruning/trimming/clamping?

Question

Decaf is a point compression method that builds a prime-order group for (twisted) Edwards curves and Montgomery curves with cofactor $h = 4$ based on the Jacobi quartic [H2015]. The promise is to eliminate the cofactor when only operating on points decoded from Decaf. Ristretto then extends this approach to curves with cofactor $h = 8$[HVLA20].

However, I'm still not clear on whether scalars when using ristretto255 with Curve25519/Ed25519 still require clamping. Clamping does three things:

1. It clears the lower three bits of the first byte, i.e. the lower three bits of the scalar to multiply with base point $B$. This is presumably there to clear the cofactor. However, it's unclear to me from [H2015] and [HVLA20] whether scalar multiplication needs the cofactor cleared in the first place or whether points with low-order components onto the prime-order group are “valid” input for Ristretto (and/or Decaf) or whether I should be clearing the cofactor for scalar multiplication. Experimental testing has shown that points with low-order components interoperate properly, but that means little regarding security.
2. It clears the top bit of the last byte, i.e. bit 255 of the scalar. This is presumably there to always be in range of a valid scalar (since $8\ell$ = 0x80000000000000000000000000000000a6f7cef517bce6b2c09318d2e7ae9f68 for Curve25519).
3. It sets bit 6 of the last byte, i.e. sets bit 254 of the scalar (so that the scalar is always at least $2^{254}$). Going by [BJLS2015], this is there to thwart kangaroo attacks. However, [BL2013.Twist] notes that kangaroo attacks can be stopped by rejecting any point $P$ for which $hQ = 0$ holds (but that implementations would be likely to forget it, which may likely the reason for the inclusion in Ed25519/Curve25519), or having cofactor $h = 1$, i.e. having the order be prime.

So as far as I can tell, assuming that Ristretto (and Decaf) create prime-order groups and the base point is on the prime-order group, none of this bit twiddling would be required for any scalar multiplication. However, in spite of this, the Ed448-Goldilocks code using Decaf/Ristretto does the complete clamping procedure with just the comment /* Blarg */: https://sourceforge.net/p/ed448goldilocks/code/ci/master/tree/src/per_curve/eddsa.tmpl.c#l36 (Note that according to HISTORY.txt, it uses Ristretto, despite having decaf in function names)

This may be the case because the same code likely does the batched version of Decaf introduced in [H2015], which re-introduces a cofactor $h=2$, going by the power. However, even with that, I do not see the reason to clamp by the full cofactor $h=4$ or $h=8$.

Thus my question: Do I need to perform the full clamping procedure with Ristretto and/or Decaf for Ed25519 and Ed448, can it be skipped entirely, do only parts of it need to be performed or is an entirely different procedure necessary?

---

Implementation overview

I went and scoured the other implementations of Ristretto as well.

• Go github.com/gtank/ristretto255: scalar/scalar.go reduces modulo Edwards25519 $\ell$. Opaque look-up tables make it difficult to see what is actually going on afterwards.
• Rust curve25519-dalek: The Scalar type reduces scalars modulo Edwards25519 $\ell$ before scalar multiplication, see scalar.rs and constants.rs in various subdirectories. Opaque look-up tables make it difficult to see what is actually going on afterwards.
• C libsodium: core_ristretto255.c generates random scalars the same as for Ed25519 in core_ed25519.c (which clears the top bit, but neither sets the high bit nor clears the low ones), selecting a scalar $S$ candidate (after truncating the top three bits, no doubt to try to get it maybe below Edwards25519 $\ell$) if it is in the range $0 < S < \ell$. crypto_scalarmult_ristretto255_base() and crypto_scalarmult_ristretto255() in scalarmult_ristretto255_ref10.c clear the top bit, but do not set the high bits and do not clear the low bits. This scalar is then immediately used for a scalar multiplication without clamping.
• JavaScript ristretto255-js: Does not do any clamping. getRandomScalar() clips the top bit, but otherwise just checks a scalar candidate $S$ for $0 \le S < \ell$. Neither scalarMult() nor scalarMultBase() set the high bit or clear the low bits before passing it off to tweetnacl-js scalarmult, which does perform the clamping in crypto_scalarmult (and apparently operates in Montgomery space anyway?). It has test vectors to test against curve25519-dalek though.
• WebAssembly/TypeScript wasm-crypto: Makes its intention very clear. The only difference between _signEdKeypairFromSeed() and _signKeypairFromSeed is the former calling scClamp() before doing the scalar multiplication.

Results remain inconclusive, but seem to strongly hint towards not clamping. However, that's just a heuristic based on how people implemented it, rather than what is actually correct, and as such not any kind of canonical answer.

---

References

BJLS2015: Daniel J. Bernstein, Simon Joseffson, Tanja Lange, Peter Schwabe, Bo-Yin Yang. EdDSA for more curves, https://ed25519.cr.yp.to/eddsa-20150704.pdf

BL2013.Twist: Daniel J. Bernstein, Tanja Lange. SafeCurves: choosing safe curves for elliptic-curve cryptography: Twist security, https://safecurves.cr.yp.to/twist.html

H2015: Mike Hamburg. Decaf: Eliminating cofactors through point compression, https://www.shiftleft.org/papers/decaf/decaf.pdf

HVLA2020: Mike Hamburg, Henry de Valence, Isis Lovecruft, Tony Arcieri et al. The Ristretto Group, https://ristretto.group/ristretto.html

Answer 1

The answer is contained in the Decaf paper [H2015], p. 3 already.

Clearing the top bit(s). This appears to be just to get the scalar value $s$ in the range of $0 \le s < \ell$ (with an additional check whether it actually holds true after clearing the top bit(s)). This is just an implementation detail being mixed with actual cryptographic math; see the implementation overview in the question. Clearing the top bits is an option to maximize chances to find a scalar $s < \ell$, but so is choosing something in a larger range and then reducing modulo $\ell$ (which e.g. EdDSA does as part of key generation).

Setting the high bit. The kangaroo attack being more efficient than the rho attack requires $h > 1$ and can be stopped by rejecting any point $Q$ for which $hQ = 0$ [BL2013.Twist]. However, [H2015] notes that points with low-order components ($P+T$, where $T$ is a low-order point) may appear internally, but are considered equal to those without ($P$) and encode to the same value. When encoded, points with a low-order component are “snapped” to the next element of the prime-order subgroup, and not allowing them during decoding. Decoding from such a value with Decaf therefore always rejects points for which $hQ = 0$. Setting the high bit is therefore not necessary. The cofactor issue is handled at the point encoding and decoding layer.[H2014]

Clearing the low bits. This is there to clear the cofactor. The cofactor does not need to be cleared because the low-order components are normalized during encoding [H2015][H2014]. The same reason that lets us avoid setting the high bit therefore also lets us avoid clearing the low bits.

Ristretto does not change this general idea, and is just an extension of Decaf for cofactor $h=8$ [HVLA2020].

In conclusion: The bit twiddling is completely optional for both Decaf and Ristretto if code selects a scalar uniformly from $0 \le s < \ell$. Clearing the top bits is just an option to maximize chances to find a scalar $s < \ell$ when choosing one uniformly at random.

H2014: https://moderncrypto.org/mail-archive/curves/2014/000345.html