[curves] Ed25519 "clamping" and its effect on hierarchical key derivation

[Gregory Maxwell]

On Mon, Mar 6, 2017 at 7:36 PM, Tony Arcieri <bascule at gmail.com> wrote:
> Ed25519 performs the following operations on private scalars immediately
> prior to use:

I assume the bytes of the scalar here is written least significant
first; otherwise I can't make sense of your message.

> scalar[0] &= 248;

This is making the number a multiple of 8, presumably due to the
cofactor. You can simply make your derivation scheme multiply its
scalar by the cofactor for this... Then everything is compatible.
Hurray.

> scalar[31] &= 63;
> scalar[31] |= 64;

This is clamping to ~the order and making the most significant bit 1.
Your application should already be assuring that the scalar is in
range for the group size.

Setting the most significant bit is a (IMO mildly offensive)
performance hack so that the exponentiation ladder does not need to
correctly handle the point at infinity.  To deal with this the point
arithmetic likely needs to have a conditional move to handle
propagating through a point at infinity when the scalar's most
significant bits are a run of zeros. The only real solution to this
one is "don't do that optimization" (or do it and use an extra
addition and a conditional swap).

Good luck with mysterious failures when someone combines your
application which relaxes this restriction with found-on-the-internets
ed25519 code which expects it to be upheld.