6
$\begingroup$

I'm building a solution based on the stellar codebase and using the Ed25519 curve for the signatures. One of the features I've been adding to the system is a support for hierarchical deterministic wallets according to BIP32. For that use case I've removed the clearing of the lowest 3 bits and setting the 254 bit for derived keys still having this features for regularly generated keys.

This allowed me to implement the HD part, but exposed the signature made by a derived key to the timing and the small-subgroup attacks. The derived keys are used as a single/couple time signers and does not participate in any DH communication.

This brings me to the question whether such schema can be considered secure?

$\endgroup$
  • 1
    $\begingroup$ Why do you not clear the lowest 3 bits? I don't see a reason for ever using a non zero value for those. $\endgroup$ – CodesInChaos Jul 21 '16 at 15:36
  • $\begingroup$ Depending on why you are doing this, sometimes a clearing of lower bits can be replaced by a *8 scalarmult $\endgroup$ – aegbert Jul 21 '16 at 18:23
2
$\begingroup$

Small-subgroup attacks are not relevant to Ed25519: You never reveal $[n]P$ for attacker-controlled $P$ where $n$ is your secret scalar. Clearing and setting high bits of the secret scalar to put the highest set bit in a fixed position is not relevant to Ed25519: It is important only for easy implementations of the Montgomery ladder in $x$-restricted scalar multiplication, which Ed25519 does not use.

The only reason to use the same secret scalar clamping as X25519 is to allow the use of the same secret key material and software both for X25519 and Ed25519, e.g. in XEdDSA, and generally for compatibility with existing software.

Of course, you can only clamp the original scalars, not the derived scalar, since standard clamping is not a homomorphism of the scalar ring $\mathbb Z/h\ell\mathbb Z$, where $\ell$ is the large prime order of the standard base point and $h$ is the small cofactor: if your master secret scalar is $s \in \mathbb Z/h\ell\mathbb Z$, and you have random function $H\colon \{0,1\}^T \to \mathbb Z/h\ell\mathbb Z$ mapping tweaks to scalars, there is no way for the holder of the public key $[\operatorname{clamp}(s)]P$ to compute $[\operatorname{clamp}(s\cdot H(t))]P$, while they can compute $[\operatorname{clamp}(s)\cdot\operatorname{clamp}(H(t))]P$.

If you're not restricted to compatibility with existing software, but you still want to make sure low-order base points can't cause trouble, you can use a nonstandard clamping scheme suggested by Ian Goldberg, George Kandianakis, Isis Lovecruft, and Henry de Valence. Let $\alpha$ solve the CRT system \begin{align*} \alpha &\equiv 1 \pmod \ell, \\ \alpha &\equiv 0 \pmod h. \end{align*} Then for any scalar $s$, the action of $\alpha s$ on a point in the order-$\ell$ subgroup generated by the standard base point is the same as the action of $s$ since $\alpha s \equiv s \pmod \ell$, but $\alpha s$ annihilates any $h$-torsion points since $\alpha s \equiv 0 \pmod h$. Since multiplication by $\alpha$ is a homomorphism of $\mathbb Z/h\ell\mathbb Z$ and fixes the action of $\mathbb Z/h\ell\mathbb Z$ on the subgroup generated by the standard base point, it doesn't matter whether you do it to the original scalars, the derived scalars, or both. This technique does not put put the highest set bit in a fixed position, however, so it requires more careful handling in a scalar multiplication ladder.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.